You are presented with a two-dimensional grid of size N x M. Each cell is either black ('B') or white ('W'). A row or column is symmetric if it reads the same forwards and backwards. In one move, you can flip a single cell's color. Determine the minimum number of moves required to make every row and every column symmetric.
Examples:
grid = ["BBWWB", "WWWBW", "BWWWB"]→3grid = ["BWB", "WBB", "WBW"]→4
解法
每个格 (i, j) 属于至多 4 个对称等价位 (i, j)、(n-1-i, j)、(i, m-1-j)、(n-1-i, m-1-j)。对每个等价类把少数色翻转。用 seen[][] 避免重复计算。复杂度 O(N · M)。
def minMovesToSymmetric(grid):
n, m = len(grid), len(grid[0])
seen = [[False] * m for _ in range(n)]
moves = 0
for i in range(n):
for j in range(m):
if seen[i][j]:
continue
cls = {(i, j), (n - 1 - i, j), (i, m - 1 - j), (n - 1 - i, m - 1 - j)}
b = w = 0
for (r, c) in cls:
seen[r][c] = True
if grid[r][c] == 'B':
b += 1
else:
w += 1
moves += min(b, w)
return movesimport java.util.*;
class Solution {
static int minMovesToSymmetric(String[] grid) {
int n = grid.length, m = grid[0].length();
boolean[][] seen = new boolean[n][m];
int moves = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (seen[i][j]) continue;
int[][] cls = {{i, j}, {n - 1 - i, j}, {i, m - 1 - j}, {n - 1 - i, m - 1 - j}};
Set<Long> uniq = new HashSet<>();
int b = 0, w = 0;
for (int[] c : cls) {
long key = (long) c[0] * m + c[1];
if (uniq.add(key)) {
seen[c[0]][c[1]] = true;
if (grid[c[0]].charAt(c[1]) == 'B') b++; else w++;
}
}
moves += Math.min(b, w);
}
return moves;
}
}#include <bits/stdc++.h>
using namespace std;
int minMovesToSymmetric(vector<string>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<bool>> seen(n, vector<bool>(m, false));
int moves = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (seen[i][j]) continue;
vector<pair<int,int>> cls = {{i, j}, {n - 1 - i, j}, {i, m - 1 - j}, {n - 1 - i, m - 1 - j}};
set<pair<int,int>> uniq;
int b = 0, w = 0;
for (auto& c : cls) {
if (uniq.insert(c).second) {
seen[c.first][c.second] = true;
if (grid[c.first][c.second] == 'B') b++; else w++;
}
}
moves += min(b, w);
}
return moves;
}You are given a rooted tree. A node is balanced if all of its subtrees (one per direct child) have the same size. The size of a subtree is the number of nodes it contains. A leaf has zero children, so trivially balanced.
Return the number of balanced nodes in the tree.
解法
后序 DFS 返回子树大小；节点平衡当且仅当所有孩子的子树大小相等。叶子算平衡。复杂度 O(N)。
def countBalanced(tree):
ans = [0]
def dfs(u):
sizes = [dfs(c) for c in tree[u]]
if len(set(sizes)) <= 1:
ans[0] += 1
return 1 + sum(sizes)
dfs(0)
return ans[0]import java.util.*;
class Solution {
int ans = 0;
int dfs(int u, List<List<Integer>> tree) {
int size = 1, first = -1;
boolean balanced = true;
for (int c : tree.get(u)) {
int s = dfs(c, tree);
size += s;
if (first == -1) first = s;
else if (s != first) balanced = false;
}
if (balanced) ans++;
return size;
}
int countBalanced(List<List<Integer>> tree) {
ans = 0;
dfs(0, tree);
return ans;
}
}#include <vector>
using namespace std;
class Solution {
int ans = 0;
vector<vector<int>>* tree;
int dfs(int u) {
int size = 1, first = -1;
bool balanced = true;
for (int c : (*tree)[u]) {
int s = dfs(c);
size += s;
if (first == -1) first = s;
else if (s != first) balanced = false;
}
if (balanced) ans++;
return size;
}
public:
int countBalanced(vector<vector<int>>& t) {
tree = &t;
ans = 0;
dfs(0);
return ans;
}
};You are given an array S of N strings and an integer K. Choose at most K letters from the alphabet that will let you build as many strings from S as possible. Any chosen letter can be used multiple times when building strings.
Return the maximum number of strings from S that can be built.
Examples:
S = ["adf","jjbh","jcg","eijj","adf"], K = 3→2S = ["abcd","efgh"], K = 3→0S = ["bc","edf","fde","dge","abcd"], K = 4→4
Constraints
strings use only the first ten lowercase letters a–j, so the alphabet fits in a 10-bit mask.
解法
每个字符串压成 10 位掩码。枚举所有 popcount = K 的字母选择掩码 cm(至多 C(10, K) ≤ 1024)。对每个 cm 统计 m & ~cm == 0 的字符串数。复杂度 O(C(10, K) · N)。
from itertools import combinations
def maxStringsBuildable(S, K):
str_masks = []
for s in S:
m = 0
for c in s:
m |= 1 << (ord(c) - ord('a'))
str_masks.append(m)
best = 0
for chosen in combinations(range(10), K):
cm = 0
for c in chosen:
cm |= 1 << c
cnt = sum(1 for m in str_masks if (m & ~cm) == 0)
best = max(best, cnt)
return bestclass Solution {
static int maxStringsBuildable(String[] S, int K) {
int n = S.length;
int[] masks = new int[n];
for (int i = 0; i < n; i++)
for (char c : S[i].toCharArray()) masks[i] |= 1 << (c - 'a');
int best = 0;
for (int cm = 0; cm < (1 << 10); cm++) {
if (Integer.bitCount(cm) != K) continue;
int cnt = 0;
for (int m : masks) if ((m & ~cm) == 0) cnt++;
best = Math.max(best, cnt);
}
return best;
}
}#include <vector>
#include <string>
using namespace std;
int maxStringsBuildable(vector<string>& S, int K) {
int n = S.size();
vector<int> masks(n, 0);
for (int i = 0; i < n; i++)
for (char c : S[i]) masks[i] |= 1 << (c - 'a');
int best = 0;
for (int cm = 0; cm < (1 << 10); cm++) {
if (__builtin_popcount(cm) != K) continue;
int cnt = 0;
for (int m : masks) if ((m & ~cm) == 0) cnt++;
best = max(best, cnt);
}
return best;
}