序
1500 - 1600
学会从题干假设结论，然后尝试验证结论（写一个）或者数学证明
这道题主要是怎么分解质因数，属于数学题。
用一个外置的while 循环来判断是否结束，然后从 cur 开始分解，分解从2作为因数开始分解，然后更新 min
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int smallestValue(int n) {
int nChange = 0;
int cur = n;
int count = n;
int min = Integer.MAX_VALUE;
while (nChange != count) {
nChange = count;
cur = count;
count = 0;
while (cur > 1) {
for (int i = 2; i <= cur; i++) {
if (cur % i == 0) {
cur /= i;
count += i;
break;
}
}
}
min = Math.min(min, count);
}
return min;
}
}
|
前后缀分解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public int numSplits(String s) {
char[] sChar = s.toCharArray();
int n = sChar.length;
int[] leftCount = new int[n - 1];
int[] rightCount = new int[n - 1];
Set<Character> left = new HashSet<>();
Set<Character> right = new HashSet<>();
int idxLeft = 0;
int idxRight = n - 2;
for (int i = 0; i < n - 1; i++) {
left.add(sChar[i]);
leftCount[idxLeft] = left.size();
idxLeft++;
}
for (int i = n - 1; i >= 1; i--) {
right.add(sChar[i]);
rightCount[idxRight] = right.size();
idxRight--;
}
int count = 0;
for (int i = 0; i < n - 1; i++) {
if (leftCount[i] == rightCount[i]) count++;
}
return count;
}
}
|
利用题中性质：left 中的每个元素都小于或等于 right 中的每个元素。 <-> 等价于找 left 最大 <= right 最小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public int partitionDisjoint(int[] nums) {
int n = nums.length;
int[] leftMax = new int[n - 1];
int[] rightMin = new int[n - 1];
int max = Integer.MIN_VALUE;
for (int i = 0; i < n - 1; i++) {
if (nums[i] > max) {
max = nums[i];
}
leftMax[i] = max;
}
int min = Integer.MAX_VALUE;
for (int i = n - 1; i >= 1; i--) {
if (nums[i] < min) {
min = nums[i];
}
rightMin[i - 1] = min;
}
for (int i = 0; i < n; i++) {
if (leftMax[i] <= rightMin[i]) {
return i + 1;
}
}
return -1;
}
}
|
dp做法：（超时）这里忽略了memo的声明需要三重循环，即使是ptthon的@cache也会超时，记忆化在这里并不适用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| class Solution {
int[] values;
int[] labels;
int n;
int numWanted;
int useLimit;
Map<Integer, Integer> selectedNumsCount = new HashMap<>();
public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
this.values = values;
this.labels = labels;
this.n = values.length;
this.numWanted = numWanted;
this.useLimit = useLimit;
return dp(0, 0);
}
private int dp(int idx, int sum) {
if (idx >= n) {
return sum;
}
int resNot = dp(idx + 1, sum);
int value = values[idx];
int label = labels[idx];
if (numWanted == 0) return resNot;
if (selectedNumsCount.getOrDefault(label, -1) == useLimit) return resNot;
if (selectedNumsCount.containsKey(label)){
selectedNumsCount.put(label, selectedNumsCount.get(label) + 1);
} else {
selectedNumsCount.put(label, 1);
}
numWanted--;
sum = sum + value;
int resSelected = dp(idx + 1, sum);
sum = sum - value;
numWanted++;
if (selectedNumsCount.get(label) > 1) {
selectedNumsCount.put(label, selectedNumsCount.get(label) - 1);
} else {
selectedNumsCount.remove(label);
}
return Math.max(resNot, resSelected);
}
}
|
正确做法：排序 + 计数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
int n = values.length;
int[][] pairs = new int[n][2];
for (int i = 0; i < n; ++i) {
pairs[i] = new int[]{values[i], labels[i]};
}
Arrays.sort(pairs, (a, b) -> b[0] - a[0]);
Map<Integer, Integer> cnt = new HashMap<>();
int ans = 0;
for (int i = 0; i < n; i++) {
if (numWanted <= 0) {
break;
}
int v = pairs[i][0], l = pairs[i][1];
if (cnt.getOrDefault(l, 0) < useLimit) {
cnt.merge(l, 1, Integer::sum);
numWanted--;
ans += v;
}
}
return ans;
}
}
|
双指针直接模拟：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int minimumLength(String s) {
int n = s.length();
int left = 0, right = n - 1;
char[] cArr = s.toCharArray();
int min = n;
while (left < right) {
if (cArr[left] == cArr[right]) {
char curDup = cArr[left];
while (left <= right && cArr[left] == curDup) {
left++;
}
while (right >= 0 && left <= right && cArr[right] == curDup) {
right--;
}
min = Math.min(min, right - left + 1);
} else {
break;
}
}
return min;
}
}
|
滑动窗口:
当出现重复次数 > 1时，缩短窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int longestSemiRepetitiveSubstring(String s) {
char[] cArr = s.toCharArray();
int n = s.length();
int sameCount = 0;
int left = 0;
int max = 1;
for (int right = 1; right < n; right++) {
if (cArr[right] == cArr[right - 1]) {
sameCount++;
if (sameCount > 1) {
left += 1;
while (left < right && cArr[left] != cArr[left - 1]) {
left++;
}
sameCount--;
}
}
max = Math.max(max, right - left + 1);
}
return max;
}
}
|
由于数据规模比较小，可以直接爆搜：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
int n;
int[] nums;
long max = -10;
LinkedList<Integer> ls = new LinkedList<>();
public long maxStrength(int[] nums) {
n = nums.length;
this.nums = nums;
dfs(0);
return max;
}
private void dfs(int idx) {
if (idx == n) {
if (ls.size() == 0) return;
long curMax = ls.get(0);
for (int i = 1; i < ls.size(); i++) {
curMax *= ls.get(i);
}
max = Math.max(max, curMax);
return;
}
dfs(idx + 1);
ls.add(nums[idx]);
dfs(idx + 1);
ls.removeLast();
return;
}
}
|
O(n): 每一次都取当前的最大和最小，最小的可能是负数，负数和负数相乘能得到一个正数
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public long maxStrength(int[] nums) {
long max = nums[0];
long min = nums[0];
for (int i = 1; i < nums.length; i++) {
long temp = max;
max = Math.max(max, Math.max(nums[i], Math.max(min * nums[i], max * nums[i])));
min = Math.min(min, Math.min(nums[i], Math.min(min * nums[i], temp * nums[i])));
}
return max;
}
}
|
这是一道数学题：
排序之后分组
第一组一个数，第二组两个数，第三组三个数…
那么一定满足要求：
- 第
i 个分组中的学生总成绩 小于 第 (i + 1) 个分组中的学生总成绩，对所有组均成立（除了最后一组）。
- 第
i 个分组中的学生总数 小于 第 (i + 1) 个分组中的学生总数，对所有组均成立（除了最后一组）
这是因为
假设 排序后分组：
a | b, c | d, e, f | …
a < b < c < d < e < f
则有
b + c <= d + e
因此两个条件都可以满足
是用数学公式：
1 + 2 + 3 + … + x <= n
(1 + x) * x / 2 <= n
x + x^2 - 2n <= 0
解一元二次方程
x^2 + x - 2n <= 0
(-b + sqrt(b^2 - 4ac)) / 2
向下取整 因此 x 为：
(-1 + (int) Math.sqrt((double) (1 + 8 * grades.length))) / 2
1
2
3
4
5
6
| class Solution {
public int maximumGroups(int[] grades) {
return (-1 + (int) Math.sqrt((double) (1 + 8 * grades.length))) / 2;
}
}
|
预处理行列，将每一个数代表的位置存储在哈希表中，在遍历arr的过程中快速找到对应行列从而使用行列计算数组「rowCnt」「Colnt」更新来快速找到重叠的元素，第一次碰到的元素一定是下标最小的， 注意m和n rowCnt[x] >= n || colCnt[y] >= m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int firstCompleteIndex(int[] arr, int[][] mat) {
Map<Integer, int[]> hm = new HashMap<>();
int m = mat.length;
int n = mat[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
hm.put(mat[i][j], new int[]{i, j});
}
}
int[] rowCnt = new int[m];
int[] colCnt = new int[n];
for (int i = 0; i < arr.length; i++) {
int[] xy = hm.get(arr[i]);
int x = xy[0], y = xy[1];
rowCnt[x]++;
colCnt[y]++;
if (rowCnt[x] >= n || colCnt[y] >= m) {
return i;
}
}
return -1;
}
}
|
核心在于：
- 如何快速查找子串
- 以及长度为k可以形成的二进制字符串
- 出现在哈希表中的个数 == (1 << k) aka 2^k
滑动窗口优化：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public boolean hasAllCodes(String s, int k) {
if (s.length() < (1 << k) + k - 1) {
return false;
}
Set<Integer> appeared = new HashSet<>();
int num = Integer.parseInt(s.substring(0, k), 2);
appeared.add(num);
for (int i = 1; i + k <= s.length(); i++) {
num = (num - ((s.charAt(i - 1) - '0') << (k - 1))) * 2 + s.charAt(i + k - 1) - '0';
appeared.add(num);
}
return appeared.size() == (1 << k);
}
}
|
暴力做法为 枚举左右端点，扫描区间，拿出来最大值最小值，计算，O(n^3) TLE 所以需要预处理：
区间DP：
使用 dp[l][r][1]表示区间 [l, r] 的最大值，dp[l][r][0]表示区间[l,r]的最小值
初始化，dp[i][i][0] = dp[i][i][1] = nums[i];
那么 dp[l][r][1] 为 dp[l][r-1][1] 和 当前 nums[r] 比较得到较大值
那么 dp[l][r][0] 为 dp[l][r-1][0] 和 当前 nums[r] 比较得到较小值
计算汇总答案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public long subArrayRanges(int[] nums) {
int n = nums.length;
int[][][] dp = new int[n][n][2];
for (int i = 0; i < n; i++) {
dp[i][i][0] = dp[i][i][1] = nums[i];
}
int l = 0;
while (l < n) {
int len = 1;
while (l + len < n) {
int r = l + len;
dp[l][r][0] = Math.min(dp[l][r - 1][0], nums[r]);
dp[l][r][1] = Math.max(dp[l][r - 1][1], nums[r]);
len++;
}
l++;
}
long ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
ans += dp[i][j][1] - dp[i][j][0];
}
}
return ans;
}
}
|
空间优化：
单调栈：
位运算题目，涉及到详细的数学证明：
参考
作者：我爱志方小姐
链接：https://leetcode.cn/problems/find-xor-beauty-of-array/
1
2
3
4
5
6
7
8
9
10
11
| (a | a) & a (b | a) & a (c | a) & a
(a | a) & b (b | a) & b (c | a) & b
(a | a) & c (b | a) & c (c | a) & c
(a | b) & a (b | b) & a (c | b) & a
(a | b) & b (b | b) & b (c | b) & b
(a | b) & c (b | b) & c (c | b) & c
(a | c) & a (b | c) & a (c | c) & a
(a | c) & b (b | c) & b (c | c) & b
(a | c) & c (b | c) & c (c | c) & c
|
根据 按位或 的 对称性，即 x | y = y | x，我们不难发现上面的分块矩阵是一个 对称矩阵，也就是说所有元素的 异或 等于对角线元素的 异或，我们保留 对角线元素(块)，得到如下 3 x 3 矩阵：
1
2
3
| (a | a) & a (b | b) & a (c | c) & a
(a | a) & b (b | b) & b (c | c) & b
(a | a) & c (b | b) & c (c | c) & c
|
由于 a | a = a, a & a = a，我们将上面的矩阵再化简一下，有：
1
2
3
| a b & a c & a
a & b b c & b
a & c b & c c
|
再根据 按位与 运算的 对称性，即 x & y = y & x，我们不难发现，这又是一个 对称矩阵，所有元素的 异或 等于对角线元素的 异或，即：
a ^ b ^ c
因此，我们有如下结论：
1
| nums 的 xor 美丽值即为 nums 所有元素的异或值。
|
1
2
3
4
5
6
| class Solution {
public int xorBeauty(int[] nums) {
int res = Arrays.stream(nums).reduce(0, (sub, cur) -> sub ^ cur);
return res;
}
}
|
方法1：两个哈希表
一个哈希表记录每一个元素的总数，一个哈希表记录当前遍历过程中出现的元素次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int minimumIndex(List<Integer> nums) {
Map<Integer, Integer> hmAll = new HashMap<>();
for (int num : nums) {
hmAll.put(num, hmAll.getOrDefault(num, 0) + 1);
}
Map<Integer, Integer> hmCur = new HashMap<>();
for (int i = 0; i < nums.size(); i++) {
int num = nums.get(i);
hmCur.put(num, hmCur.getOrDefault(num, 0) + 1);
if (hmCur.get(num) * 2 > i + 1 && (hmAll.get(num) - hmCur.get(num)) * 2 > nums.size() - i - 1) {
return i;
}
}
return -1;
}
}
|
方法2：数学推理 + 摩尔投票
证明：分割出的两个数组的支配元素就是原数组的支配元素。
分割出的两个数组的支配元素就是原数组的支配元素。
设这两个数组的支配元素为 y（题目要求支配元素相同），那么对于第一个数组有
freq_1(y) * 2 > i+1
对于第二个数组有
freq_2(y) * 2 > n - i - 1
由于这两个数组合并之后就是原数组，所以
freq(y) * 2 = freq_1(y) * 2 + freq_2(y) * 2 > (i+1) + (n-i-1) = n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public int minimumIndex(List<Integer> nums) {
int mode = mooreVote(nums);
int modeTot = 0;
for (int num : nums) {
if (num == mode) modeTot++;
}
int n = nums.size();
int modeCnt = 0;
for (int i = 0; i < n; i++) {
int num = nums.get(i);
if (num == mode) modeCnt++;
if (modeCnt * 2 > i + 1 && (modeTot - modeCnt) * 2 > n - 1 - i) {
return i;
}
}
return -1;
}
private int mooreVote(List<Integer> nums) {
int x = nums.get(0), cnt = 1;
for (int i = 1; i < nums.size(); i++) {
if (x != nums.get(i)) {
cnt -= 1;
} else {
cnt++;
}
if (cnt == 0) {
x = nums.get(i);
cnt = 1;
}
}
int countX = 0;
for (int num : nums) {
if (num == x) {
countX++;
}
if (countX > nums.size() / 2) return x;
}
return -1;
}
}
|
1600 - 1900
自我认为一道非常好的题，可以使用DFS，并查集来解题：
一开始尝试使用了DFS枚举然后去除，暴力超时
后采用并查集，通过计算乘法原理 O(N^2)
进行数学优化，直接相乘除二即可，O(N + M)
并查集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| class Solution {
LinkedList<LinkedList<Integer>> go = new LinkedList<>();
class UF {
int count;
int[] parent;
int[] size;
UF(int n) {
this.count = n;
this.parent = new int[n];
this.size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
this.size[i] = 1;
}
}
void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
count--;
}
int find(int cur) {
if (parent[cur] != cur) {
parent[cur] = find(parent[cur]);
}
return parent[cur];
}
}
public long countPairs(int n, int[][] edges) {
UF uf = new UF(n);
for (int i = 0; i < n; i++) {
go.addLast(new LinkedList<>());
}
for (int i = 0; i < edges.length; i++) {
int from = edges[i][0], to = edges[i][1];
uf.union(from, to);
}
List<Integer> list = new ArrayList<>();
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) {
int p = uf.find(i);
if (!set.contains(p)) list.add(uf.size[p]);
set.add(p);
}
long res = 0;
for (int ele : list) {
res += (long) ele * (n - ele);
}
return res / 2;
}
}
|
1900 - 2100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
long[][] memo;
int[] nums;
int k;
public long minIncrementOperations(int[] nums, int k) {
int n = nums.length;
long[][] dp = new long[n + 1][3];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
long select = dp[i][0] + Math.max(k - nums[i], 0);
long notSelect = Long.MAX_VALUE;
if (j < 2) {
notSelect = dp[i][j + 1];
}
dp[i + 1][j] = Math.min(select, notSelect);
}
}
return dp[n][0];
}
private long dp(int idx, int left) {
if (idx < 0) {
return 0;
}
if (memo[idx][left] != -1) return memo[idx][left];
long res = dp(idx - 1, 0) + Math.max(k - nums[idx], 0);
if (left < 2) {
res = Math.min(res, dp(idx - 1, left + 1));
}
memo[idx][left] = res;
return res;
}
}
|
