Given n vertices, count the number of distinct graphs that can be formed. The graph may be disjoint (edges are optional, no need to connect all vertices). Two graphs are different if any pair of vertices differs in connection. Return the answer modulo 10⁹ + 7.
Example: for n = 4, return 64.
解法
可能的边数为 C(n, 2) = n*(n-1)/2，每条独立选择有/无，共 2^(n*(n-1)/2) 张图。模 10⁹ + 7 快速幂即可。复杂度 O(log(n²))。
def drawing_edges(n):
return pow(2, n * (n - 1) // 2, 10**9 + 7)class Solution {
static long drawingEdges(int n) {
long MOD = 1_000_000_007L, base = 2, exp = (long) n * (n - 1) / 2, res = 1;
while (exp > 0) {
if ((exp & 1) == 1) res = res * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return res;
}
}long long drawingEdges(int n) {
const long long MOD = 1'000'000'007LL;
long long base = 2, exp = (long long) n * (n - 1) / 2, res = 1;
while (exp > 0) {
if (exp & 1) res = res * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return res;
}02Triplets
Given an array d[n] of distinct integers and an integer threshold t, count the index triplets (a, b, c) satisfying both:
d[a] + d[b] < d[c]d[a] + d[b] + d[c] < t
Example
d = [1, 2, 3, 4, 5], t = 8
Triplets (sorted): (1,2,4) sum=7<8 and 1+2<4 ok; (1,2,3) 1+2<3? no; (1,3,4) 4<4? no.
Answer: 1解法
先排序。对每个 c，两个条件简化为 a + b < min(d[c], t - d[c])。在 [0, c-1] 上用双指针 l, r 数对数。复杂度 O(n²)。
def count_triplets(d, t):
a = sorted(d)
n = len(a)
cnt = 0
for c in range(2, n):
limit = min(a[c], t - a[c])
l, r = 0, c - 1
while l < r:
if a[l] + a[r] < limit:
cnt += r - l
l += 1
else:
r -= 1
return cntimport java.util.*;
class Solution {
static long countTriplets(int[] d, int t) {
int[] a = d.clone();
Arrays.sort(a);
int n = a.length;
long cnt = 0;
for (int c = 2; c < n; c++) {
int limit = Math.min(a[c], t - a[c]);
int l = 0, r = c - 1;
while (l < r) {
if (a[l] + a[r] < limit) { cnt += r - l; l++; }
else r--;
}
}
return cnt;
}
}#include <vector>
#include <algorithm>
using namespace std;
long long countTriplets(vector<int>& d, int t) {
vector<int> a = d;
sort(a.begin(), a.end());
int n = a.size();
long long cnt = 0;
for (int c = 2; c < n; c++) {
int limit = min(a[c], t - a[c]);
int l = 0, r = c - 1;
while (l < r) {
if (a[l] + a[r] < limit) { cnt += r - l; l++; }
else r--;
}
}
return cnt;
}There are n students with skill levels in skills[n]. The team must be uniform: when its members' skills are sorted in increasing order, the difference between any two consecutive skill levels is either 0 or 1. Find the maximum team size.
Example: skills = [10, 12, 13, 9, 14] → 3 (valid teams: {9, 10}, {12, 13, 14}).
解法
合法分组只包含值 v 和 v+1。用哈希表统计频次，取 max_v (cnt[v] + cnt[v+1])。复杂度 O(n)。
from collections import Counter
def max_team_size(skills):
c = Counter(skills)
return max(c[v] + c.get(v + 1, 0) for v in c)import java.util.*;
class Solution {
static int maxTeamSize(int[] skills) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int s : skills) cnt.merge(s, 1, Integer::sum);
int best = 0;
for (int v : cnt.keySet())
best = Math.max(best, cnt.get(v) + cnt.getOrDefault(v + 1, 0));
return best;
}
}#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
int maxTeamSize(vector<int>& skills) {
unordered_map<int, int> cnt;
for (int s : skills) cnt[s]++;
int best = 0;
for (auto& [v, c] : cnt) {
int next = cnt.count(v + 1) ? cnt[v + 1] : 0;
best = max(best, c + next);
}
return best;
}