A binary string is a string consisting only of 0s and 1s. A substring is a contiguous group of characters within a string.
Given a binary string, find the number of substrings that contain an equal number of 0s and 1s and all the 0s and 1s are grouped together. Note that duplicate substrings are also counted in the answer. For example, "0011" has two overlapping substrings that meet the criteria: "0011" and "01".
Example: s = "00110011" → 6.
解法
将连续相同字符合成游程；相邻两段贡献 min(prev, cur) 个合法子串。复杂度 O(n)。
def getSubstringCount(s: str) -> int:
groups = []
cnt = 1
for i in range(1, len(s)):
if s[i] == s[i - 1]: cnt += 1
else: groups.append(cnt); cnt = 1
groups.append(cnt)
return sum(min(groups[i], groups[i + 1]) for i in range(len(groups) - 1))class Solution {
static long getSubstringCount(String s) {
long ans = 0, prev = 0, cur = 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == s.charAt(i - 1)) cur++;
else { ans += Math.min(prev, cur); prev = cur; cur = 1; }
}
return ans + Math.min(prev, cur);
}
}#include <string>
#include <algorithm>
using namespace std;
long long getSubstringCount(string s) {
long long ans = 0, prev = 0, cur = 1;
for (int i = 1; i < (int)s.size(); i++) {
if (s[i] == s[i - 1]) cur++;
else { ans += min(prev, cur); prev = cur; cur = 1; }
}
return ans + min(prev, cur);
}A popular social media platform provides a feature to connect people online. Connections are represented as an undirected graph where a user can see the profiles of those they are connected to (directly or transitively).
Given connection_nodes users, connection_edges edges in arrays connection_from[] and connection_to[], and a queries[] array, return for each query queries[i] the number of users whose profiles are visible to user queries[i] (i.e., the size of the connected component containing that user).
connection_nodes = 7
edges: (1,2), (2,3), (3,4), (5,6)
queries = [1, 3, 5, 7]
→ [4, 4, 2, 1]解法
带大小的并查集。先把所有边加入 DSU，每次查询返回 size[find(q)]。复杂度 O((E + Q) · α(N))。
def getVisibleProfilesCount(n, c_from, c_to, queries):
parent = list(range(n + 1))
size = [1] * (n + 1)
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]
for u, v in zip(c_from, c_to):
union(u, v)
return [size[find(q)] for q in queries]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[] getVisibleProfilesCount(int n, int[] from_, int[] to_, int[] queries) {
parent = new int[n + 1]; size = new int[n + 1];
for (int i = 0; i <= n; i++) { parent[i] = i; size[i] = 1; }
for (int i = 0; i < from_.length; i++) union_(from_[i], to_[i]);
int[] out = new int[queries.length];
for (int i = 0; i < queries.length; i++) out[i] = size[find(queries[i])];
return out;
}
}#include <vector>
#include <numeric>
using namespace std;
class DSU {
public:
vector<int> parent, size;
DSU(int n) : parent(n + 1), size(n + 1, 1) { iota(parent.begin(), parent.end(), 0); }
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 (size[a] < size[b]) swap(a, b);
parent[b] = a; size[a] += size[b];
}
};
vector<int> getVisibleProfilesCount(int n, vector<int>& from_, vector<int>& to_, vector<int>& queries) {
DSU d(n);
for (int i = 0; i < (int)from_.size(); i++) d.unite(from_[i], to_[i]);
vector<int> out;
for (int q : queries) out.push_back(d.size[d.find(q)]);
return out;
}Determine the number of valid words in a given string s. A valid word contains:
- At least 3 characters.
- Only alphanumeric characters (i.e., the numbers 0–9, letters A–Z in either case).
- At least one vowel (
a, e, i, o, u). - At least one consonant.
解法
按空白切分；每个 token 检查长度 ≥ 3、全是字母数字、至少一个元音和一个辅音。复杂度 O(|s|)。
def countValidWords(s: str) -> int:
VOWELS = set('aeiouAEIOU')
cnt = 0
for w in s.split():
if len(w) < 3 or not w.isalnum():
continue
has_v = any(c in VOWELS for c in w)
has_c = any(c.isalpha() and c not in VOWELS for c in w)
if has_v and has_c:
cnt += 1
return cntimport java.util.*;
class Solution {
static int countValidWords(String s) {
Set<Character> V = Set.of('a','e','i','o','u','A','E','I','O','U');
int cnt = 0;
for (String w : s.split("\\s+")) {
if (w.length() < 3) continue;
boolean alnum = true, hv = false, hc = false;
for (char c : w.toCharArray()) {
if (!Character.isLetterOrDigit(c)) { alnum = false; break; }
if (Character.isLetter(c)) {
if (V.contains(c)) hv = true; else hc = true;
}
}
if (alnum && hv && hc) cnt++;
}
return cnt;
}
}#include <string>
#include <sstream>
#include <cctype>
#include <unordered_set>
using namespace std;
int countValidWords(string s) {
unordered_set<char> V{'a','e','i','o','u','A','E','I','O','U'};
stringstream ss(s);
string w;
int cnt = 0;
while (ss >> w) {
if ((int)w.size() < 3) continue;
bool alnum = true, hv = false, hc = false;
for (char c : w) {
if (!isalnum((unsigned char)c)) { alnum = false; break; }
if (isalpha((unsigned char)c)) {
if (V.count(c)) hv = true; else hc = true;
}
}
if (alnum && hv && hc) cnt++;
}
return cnt;
}