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;
}SDE-1
Constraints
1 ≤ n ≤ 15
Example 1
Input:
n = 2Output:
2Explanation: The first Divisible Permutation is [1,2]: permutation[1] = 1 is divisible by i = 1 permutation[2] = 2 is divisible by i = 2 The second Divisible Permutation is [2,1]: permutation[1] = 2 is divisible by i = 1 i = 2 is divisible by permutation[2] = 1
There are N houses along the street. Carbon filters are already installed in some of them. We would like to install filters in the remaining houses (those that do not possess them yet). Two types of filter, named 'a' and 'b', are being used. The filters work best if no three adjacent houses have the same type of filter. The houses are represented as a string of characters 'a', 'b' and '?' ('a' and 'b' denote a house with a filter of a given type installed; '?' represents a house with no filter yet). Your task is to make a plan of the filter types to be installed in the houses that do not yet have them.
Write a function solution that, given a string S of length N, returns a string that is the result of replacing each '?' in string S with 'a' or 'b' character and does not contain three identical consecutive letters (in other words, neither 'aaa' nor 'bbb' may occur in the processed string).
Write an efficient algorithm for the following assumptions:
string S is made only of the following characters: 'a', 'b' and '-'.
N is an integer within the range [1,200,000].
There should be some more assumptions, but source did not cover them..
Write a function:
def solution(S)
that, given a string S consisting of N lowercase English letters, returns the length of the longest substring in which every letter occurs an even number of times. A substring is defined as a contiguous segment of a string. If no such substring exists, return 0.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range
[1..100,000]; - string
Sconsists only of lowercase letters ('a'-'z').
Example 1
Input:
S = "bdaaadadb"Output:
6Explanation: Substrings in which every letter occurs an even number of times are "aa", "adad", "daaadad" and "aaadad". The length of the longest of them is 6.
Example 2
Input:
S = "abacb"Output:
0Explanation: There is no non-empty substring in which every letter occurs an even number of times.
Example 3
Input:
S = "zthtzh"Output:
6Explanation: Every letter in the whole string occurs an even number of times.
解锁全部 3 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理