You are given an array of integers numbers. Your task is to count the number of distinct pairs of indices (i, j) (where i < j) such that numbers[i] can be obtained from numbers[j] by swapping exactly two digits in their decimal representation. Both numbers must have the same number of digits to be considered.
Example: numbers = [1, 23, 156, 1650, 651, 165, 32] returns 3 (pairs: (23, 32), (156, 651), (156, 165)).
Constraints
1 ≤ numbers.length ≤ 10⁴, 1 ≤ numbers[i] ≤ 10⁹.
解法
按 (位数, 排序后字符多重集) 分桶；同桶里两两比较字符串，若恰好两位不同则计数。不同桶之间不可能通过单次交换得到，所以可以剪枝。复杂度 O(n·L + Σ m²·L)，L 为数字位数。
def solution(numbers):
buckets = {}
for v in numbers:
s = str(v); key = (len(s), ''.join(sorted(s)))
buckets.setdefault(key, []).append(s)
ans = 0
for arr in buckets.values():
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if sum(1 for a, b in zip(arr[i], arr[j]) if a != b) == 2:
ans += 1
return ansclass Solution {
public int solution(int[] numbers) {
Map<String, List<String>> buckets = new HashMap<>();
for (int v : numbers) {
String s = String.valueOf(v);
char[] arr = s.toCharArray();
Arrays.sort(arr);
String key = s.length() + ":" + new String(arr);
buckets.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
int ans = 0;
for (List<String> arr : buckets.values()) {
int m = arr.size();
for (int i = 0; i < m; i++) for (int j = i + 1; j < m; j++) {
int diff = 0;
String a = arr.get(i), b = arr.get(j);
for (int p = 0; p < a.length(); p++) if (a.charAt(p) != b.charAt(p)) diff++;
if (diff == 2) ans++;
}
}
return ans;
}
}int solution(vector<int>& numbers) {
map<pair<int, string>, vector<string>> buckets;
for (int v : numbers) {
string s = to_string(v), sorted_s = s;
sort(sorted_s.begin(), sorted_s.end());
buckets[{(int)s.size(), sorted_s}].push_back(s);
}
int ans = 0;
for (auto& [_, arr] : buckets) {
int m = arr.size();
for (int i = 0; i < m; ++i) for (int j = i + 1; j < m; ++j) {
int diff = 0;
for (int p = 0; p < (int)arr[i].size(); ++p)
if (arr[i][p] != arr[j][p]) ++diff;
if (diff == 2) ++ans;
}
}
return ans;
}You're given a square matrix matrix of size n × n. Define a bouncing diagonal starting from the left column as the sequence of elements obtained by starting at some cell (i, 0), moving diagonally up-right until hitting the top row, then bouncing diagonally down-right, and so on (alternating direction whenever you hit top or bottom).
Define the weight of a leftmost-column element as the sum of all elements in its bouncing diagonal. Return the leftmost column reordered so that weights are in ascending order. In case of a tie, sort by value in ascending order.
Example: for matrix = [[1,2,3],[4,5,6],[7,8,9]], row 0's diagonal is 1+5+9=15 (down-right), row 1's bounces 4+8+6=18, row 2's bounces 7+5+3=15. Weights (15,15,18) after tie-break by value give new first column [1, 7, 4].
解法
枚举每个起始行模拟反弹路径，逐格累加得到权重；把首列元素按 (权重, 值) 排序后写回首列。模拟一条路径走 n 步，共 n 行，复杂度 O(n²)。
def solution(matrix):
n = len(matrix)
weights = []
for start in range(n):
r, c, dr, s = start, 0, -1, 0
while c < n:
s += matrix[r][c]
if r == 0: dr = 1
elif r == n - 1: dr = -1
r += dr; c += 1
if r < 0 or r >= n: r = max(0, min(n - 1, r))
weights.append((s, start))
weights.sort()
col = [matrix[orig][0] for _, orig in weights]
for i in range(n): matrix[i][0] = col[i]
return matrixclass Solution {
public int[][] solution(int[][] matrix) {
int n = matrix.length;
long[][] weights = new long[n][2];
for (int start = 0; start < n; start++) {
int r = start, c = 0, dr = -1;
long s = 0;
while (c < n) {
s += matrix[r][c];
if (r == 0) dr = 1;
else if (r == n - 1) dr = -1;
r += dr; c++;
if (r < 0 || r >= n) r = Math.max(0, Math.min(n - 1, r));
}
weights[start][0] = s; weights[start][1] = start;
}
Arrays.sort(weights, (a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));
int[] col = new int[n];
for (int i = 0; i < n; i++) col[i] = matrix[(int) weights[i][1]][0];
for (int i = 0; i < n; i++) matrix[i][0] = col[i];
return matrix;
}
}vector<vector<int>> solution(vector<vector<int>> matrix) {
int n = matrix.size();
vector<pair<long long, int>> weights;
for (int start = 0; start < n; ++start) {
int r = start, c = 0, dr = -1;
long long s = 0;
while (c < n) {
s += matrix[r][c];
if (r == 0) dr = 1;
else if (r == n - 1) dr = -1;
r += dr; c += 1;
if (r < 0 || r >= n) r = max(0, min(n - 1, r));
}
weights.push_back({s, start});
}
sort(weights.begin(), weights.end());
vector<int> col(n);
for (int i = 0; i < n; ++i) col[i] = matrix[weights[i].second][0];
for (int i = 0; i < n; ++i) matrix[i][0] = col[i];
return matrix;
}You are given a string binaryString consisting of '0's and '1's, and an array of strings requests containing requests of two types:
requests[i] = "count:<index>"— find the number of'0's inbinaryStringbefore and including the specified 0-basedindex.requests[i] = "flip"— flip all elements ofbinaryString(every'0'becomes'1'and every'1'becomes'0').
Return an array answers, where answers[i] contains the answer for the respective count request.
Example: binaryString="1111010", requests=["count:4","count:6","flip","count:4","flip","count:2"] → [1, 2, 4, 0].
解法
预计算原串 '0' 的前缀和 z[]；flip 不真翻，只切换布尔 flipped。每次 count(idx) 时若被翻转，输出 (idx+1) - z[idx](原串 '1' 的数量即翻转后的 '0')，否则直接返回 z[idx]。每查询 O(1)。
def solution(s, requests):
n = len(s); pz = [0] * (n + 1)
for i, c in enumerate(s): pz[i + 1] = pz[i] + (c == '0')
flipped = False; out = []
for r in requests:
if r == "flip": flipped = not flipped
else:
idx = int(r.split(":")[1]); z = pz[idx + 1]
out.append((idx + 1) - z if flipped else z)
return outclass Solution {
public List<Integer> solution(String s, String[] requests) {
int n = s.length();
int[] pz = new int[n + 1];
for (int i = 0; i < n; i++) pz[i + 1] = pz[i] + (s.charAt(i) == '0' ? 1 : 0);
boolean flipped = false;
List<Integer> out = new ArrayList<>();
for (String r : requests) {
if (r.equals("flip")) flipped = !flipped;
else {
int idx = Integer.parseInt(r.substring(6));
int z = pz[idx + 1];
out.add(flipped ? (idx + 1) - z : z);
}
}
return out;
}
}vector<int> solution(string s, vector<string>& requests) {
int n = s.size();
vector<int> pz(n + 1, 0);
for (int i = 0; i < n; ++i) pz[i + 1] = pz[i] + (s[i] == '0' ? 1 : 0);
bool flipped = false;
vector<int> out;
for (auto& r : requests) {
if (r == "flip") flipped = !flipped;
else {
int idx = stoi(r.substr(6));
int z = pz[idx + 1];
out.push_back(flipped ? (idx + 1) - z : z);
}
}
return out;
}