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 cntclass 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]
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理