登录
OAmaster

Given an integer array arr of length n, count the number of ways to split it into two non-empty contiguous subarrays (a left and a right part) such that the sum of the left part is greater than the sum of the right part.

Examples:

  • arr = [-3, -2, 1, -6, -30] -> 4

解法

设总和为 S，pref 为前缀和。在 i 处分割合法当且仅当 pref > S - pref，即 2·pref > S。一次遍历。复杂度 O(n)。

def count_splits(arr):
    S = sum(arr)
    pref = 0
    cnt = 0
    for i in range(len(arr) - 1):
        pref += arr[i]
        if 2 * pref > S:
            cnt += 1
    return cnt
class Solution {
    static int countSplits(int[] arr) {
        long S = 0;
        for (int x : arr) S += x;
        long pref = 0;
        int cnt = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            pref += arr[i];
            if (2 * pref > S) cnt++;
        }
        return cnt;
    }
}
#include <vector>
using namespace std;

int countSplits(vector<int>& arr) {
 long long S = 0;
 for (int x : arr) S += x;
 long long pref = 0;
 int cnt = 0;
 for (int i = 0; i < (int) arr.size() - 1; i++) {
 pref += arr[i];
 if (2 * pref > S) cnt++;
 }
 return cnt;
}

A cyber security firm has discovered a new type of encryption. A valid key is a number that has exactly 3 divisors. For example, 4 is valid because its divisors are {1, 2, 4}. 6 is not (divisors {1, 2, 3, 6}).

Given an array keys of length n, find the number of valid keys in [1, keys[i]] (inclusive) for each i.

Example

keys = [10, 15] -> [2, 2] (valid keys <=10: 4, 9; same up to 15)
keys = [100] -> [4] (4, 9, 25, 49)

Constraints

1 <= n <= 10⁵, 1 <= keys[i] <= 2.5 * 10¹³.

解法

一个数恰好 3 个因子当且仅当它是某素数的平方，所以答案 = ≤ floor(sqrt(K)) 的素数个数。线性筛到 sqrt(max)，每次查询二分。复杂度 O(M log log M + n log M)。

import bisect

def valid_keys(keys):
    MAX = int(2.5e13 ** 0.5) + 2
    sieve = [True] * (MAX + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(MAX ** 0.5) + 1):
        if sieve[i]:
            for j in range(i * i, MAX + 1, i):
                sieve[j] = False
    primes = [i for i in range(2, MAX + 1) if sieve[i]]
    return [bisect.bisect_right(primes, int(K ** 0.5)) for K in keys]
import java.util.*;

class Solution {
    static int[] validKeys(long[] keys) {
        int MAX = 5_000_001;
        boolean[] sieve = new boolean[MAX + 1];
        Arrays.fill(sieve, true);
        sieve[0] = sieve[1] = false;
        for (int i = 2; (long) i * i <= MAX; i++)
            if (sieve[i])
                for (int j = i * i; j <= MAX; j += i) sieve[j] = false;
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= MAX; i++) if (sieve[i]) primes.add(i);
        int[] out = new int[keys.length];
        for (int i = 0; i < keys.length; i++) {
            int limit = (int) Math.sqrt((double) keys[i]);
            while ((long) (limit + 1) * (limit + 1) <= keys[i]) limit++;
            int lo = 0, hi = primes.size();
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (primes.get(mid) <= limit) lo = mid + 1; else hi = mid;
            }
            out[i] = lo;
        }
        return out;
    }
}
#include <bits/stdc++.h>
using namespace std;

vector<int> validKeys(vector<long long>& keys) {
 const int MAX = 5'000'001;
 vector<bool> sieve(MAX + 1, true);
 sieve[0] = sieve[1] = false;
 for (int i = 2; (long long) i * i <= MAX; i++)
 if (sieve[i])
 for (int j = i * i; j <= MAX; j += i) sieve[j] = false;
 vector<int> primes;
 for (int i = 2; i <= MAX; i++) if (sieve[i]) primes.push_back(i);
 vector<int> out;
 for (long long K : keys) {
 long long limit = (long long) sqrtl((long double) K);
 while ((limit + 1) * (limit + 1) <= K) limit++;
 out.push_back(upper_bound(primes.begin(), primes.end(), (int) limit) - primes.begin());
 }
 return out;
}

Given an array serverProp representing the properties of n servers, determine the size of the cluster to which each server belongs. Two servers at indexes i and j are considered connected if gcd(serverProp[i], serverProp[j]) > 1. Connected servers form clusters. Return an array where the i-th value is the size of the cluster containing server i.

Examples:

  • serverProp = [3, 3, 3] -> [3, 3, 3]
  • serverProp = [2, 3, 6, 1, 5] -> [3, 3, 3, 1, 1]

解法

按质因子并查集：对每台服务器分解质因数；每个质因子把当前下标与首次见到该质因子的下标合并。簇大小即连通块大小。复杂度 O(n · sqrt(V))。

def server_clusters(serverProp):
    n = len(serverProp)
    parent = list(range(n))
    size = [1] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]

    prime_first = {}
    for i, v in enumerate(serverProp):
        x = v
        p = 2
        while p * p <= x:
            if x % p == 0:
                if p in prime_first:
                    union(i, prime_first[p])
                else:
                    prime_first[p] = i
                while x % p == 0:
                    x //= p
            p += 1
        if x > 1:
            if x in prime_first:
                union(i, prime_first[x])
            else:
                prime_first[x] = i
    return [size[find(i)] for i in range(n)]
import java.util.*;

class Solution {
    int[] parent, size;

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    void union_(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (size[a] < size[b]) { int t = a; a = b; b = t; }
        parent[b] = a;
        size[a] += size[b];
    }

    int[] serverClusters(int[] serverProp) {
        int n = serverProp.length;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
        Map<Integer, Integer> primeFirst = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = serverProp[i];
            for (int p = 2; (long) p * p <= x; p++) {
                if (x % p == 0) {
                    if (primeFirst.containsKey(p)) union_(i, primeFirst.get(p));
                    else primeFirst.put(p, i);
                    while (x % p == 0) x /= p;
                }
            }
            if (x > 1) {
                if (primeFirst.containsKey(x)) union_(i, primeFirst.get(x));
                else primeFirst.put(x, i);
            }
        }
        int[] out = new int[n];
        for (int i = 0; i < n; i++) out[i] = size[find(i)];
        return out;
    }
}
#include <bits/stdc++.h>
using namespace std;

class Solution {
    vector<int> parent, sz;

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
    }

public:
    vector<int> serverClusters(vector<int>& serverProp) {
        int n = serverProp.size();
        parent.resize(n); sz.assign(n, 1);
        iota(parent.begin(), parent.end(), 0);
        unordered_map<int, int> primeFirst;
        for (int i = 0; i < n; i++) {
            int x = serverProp[i];
            for (int p = 2; (long long) p * p <= x; p++) {
                if (x % p == 0) {
                    auto it = primeFirst.find(p);
                    if (it != primeFirst.end()) unite(i, it->second);
                    else primeFirst[p] = i;
                    while (x % p == 0) x /= p;
                }
            }
            if (x > 1) {
                auto it = primeFirst.find(x);
                if (it != primeFirst.end()) unite(i, it->second);
                else primeFirst[x] = i;
            }
        }
        vector<int> out(n);
        for (int i = 0; i < n; i++) out[i] = sz[find(i)];
        return out;
    }
};

Square Point

Square Point OA 真题，三语题解(Python / Java / C++)。

Walleye Capital

Walleye Capital OA 真题，三语题解(Python / Java / C++)。