LeetCode Weekly 259
检测正方形
class DetectSquares {
// 点和对应数量的哈希表
Map<String, Integer> map;
public DetectSquares() {
map = new HashMap<>();
}
public void add(int[] point) {
String key = point[0] + "-" + point[1];
map.put(key, map.getOrDefault(key, 0) + 1);
}
public int count(int[] point) {
int ans = 0;
for (Map.Entry<String, Integer> entry : map.entrySet()) {
String[] strs = entry.getKey().split("-");
int x = Integer.parseInt(strs[0]);
int y = Integer.parseInt(strs[1]);
// 统计以point和(x,y)为对角线的正方形数量
if (x != point[0] && y != point[1] &&
Math.abs(x - point[0]) == Math.abs(y - point[1])) {
int xParCnt = map.getOrDefault(x + "-" + point[1], 0);
int yParCnt = map.getOrDefault(point[0] + "-" + y, 0);
ans += entry.getValue() * xParCnt * yParCnt;
}
}
return ans;
}
}
重复 K 次的最长子序列
⚡ BFS枚举 + 双指针
class Solution {
public String longestSubsequenceRepeatedK(String s, int k) {
String res = "";
// 队列q保存满足条件子串
Queue<String> q = new LinkedList<>();
q.add("");
// BFS 最后一个满足条件的便为答案
while (!q.isEmpty()) {
String sub = q.poll();
for (int i = 0; i < 26; ++ i) {
String next = sub + (char)('a' + i);
if (isSubsequence(s, next, k)) { // 满足条件
res = next;
q.add(next);
}
}
}
return res;
}
// 判断sub * k 是否是 s 的子串
private boolean isSubsequence(String s, String sub, int k) {
int j = 0, repeat = 0;
int n = s.length();
for (int i = 0; i < n; ++ i) {
if (s.charAt(i) == sub.charAt(j)) {
++ j;
if (j == sub.length()) {
++ repeat;
j = 0;
if (repeat == k) return true;
}
}
}
return false;
}
}
第61场双周赛
出租车的最大盈利(经典dp题)
⚡ dp
class Solution {
public long maxTaxiEarnings(int n, int[][] rides) {
Arrays.sort(rides, (x, y) -> {
return x[1] - y[1];
});
// f[i] 表示到i地点的最大盈利
long[] f = new long[n + 1];
int idx = 0;
for (int i = 1; i <= n; ++ i) {
f[i] = f[i - 1];
while (idx < rides.length && i == rides[idx][1]) {
f[i] = Math.max(f[i], f[rides[idx][0]] + rides[idx][1] - rides[idx][0] + rides[idx][2]);
++ idx;
}
}
return f[n];
}
}
使数组连续的最少操作数
⚡ 去重 + 排序 + 滑动窗口
class Solution {
public int minOperations(int[] a) {
// 排序
Arrays.sort(a);
// 去重
int n = unique(a);
// 滑动窗口
int cur = 0, r = 1;
for (int l = 0; l < n; ++ l) {
while (r < n && a[r] - a[l] <= a.length - 1) {
++ r;
}
cur = Math.max(cur, r - l);
}
return a.length - cur;
}
/**
* 在原数组上去重
* @param nums 原数组
* @return 去重后的长度
*/
private int unique(int[] nums) {
int n = nums.length;
int i = 0, j = 1;
while (j < n) {
if (nums[j - 1] != nums[j]) {
nums[++ i] = nums[j];
}
++ j;
}
return i + 1;
}
}
类似题型 - 规划兼职工作
LeetCode Weekly 258
可互换矩形的组数
⚡ GCD + 组合数
class Solution {
public long interchangeableRectangles(int[][] rectangles) {
HashMap<String, Long> map = new HashMap<>();
for (int[] rect : rectangles) {
int gcd = gcd(rect[0], rect[1]);
String key = null;
key = rect[0] / gcd + "/" +rect[1] / gcd;
map.put(key, map.getOrDefault(key, 0L) + 1);
}
long ans = 0;
for (Map.Entry<String, Long> entry : map.entrySet()) {
Long val = entry.getValue();
ans += val * (val - 1) / 2; // 组合数Cn2
}
return ans;
}
private int gcd (int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
LeetCode Weekly 255
最小化目标值与所选元素的差⭐
⚡ 背包型动态规划
第 59 场双周赛
最大方阵和✔️
⚡ 贪心
class Solution {
public long maxMatrixSum(int[][] matrix) {
int n = matrix.length, m = matrix[0].length;
int minAbsNum = Integer.MAX_VALUE;
int count = 0;
long ans = 0;
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < n; ++ j) {
int num = Math.abs(matrix[i][j]);
ans += num;
minAbsNum = Math.min(minAbsNum, num);
if (matrix[i][j] <= 0) {
count ++;
}
}
}
return count % 2 == 0 ? ans : ans - 2 * minAbsNum;
}
}
到达目的地的方案数⭐
⚡ 最短路 + 有向无环图上的动态规划
LeetCode Weekly 248
最长公共子路径
⚡ 滚动哈希 & 二分
class Solution {
int[][] paths;
int N = 100010;
long[] h = new long[N];
long[] p = new long[N]; // p[i]存储base的i次方
int base = 133331;
// 合并的总哈希表
// key序列哈希值 value出现的行数
Map<Long, Integer> cnt = new HashMap<>();
// key序列哈希值 value是最后出现的行号
// 用于判断每行内部有没有重复的哈希表
Map<Long, Integer> S = new HashMap<>();
private long get(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
// 判断是否有长度为mid的公共子路径
private boolean check (int mid) {
cnt.clear();
S.clear();
p[0] = 1;
int k = 0;
for (int[] path : paths) {
// 计算path哈希值数组
int n = path.length;
for (int i = 1; i <= n; ++ i) {
p[i] = p[i - 1] * base;
h[i] = h[i - 1] * base + path[i - 1];
}
for (int i = mid; i <= n; ++ i) {
long t = get(i - mid + 1, i);
// 如果总哈希表cnt中没有出现过，或者S中对应的行号不是当前行
// 则说明是第一次出现，增加cnt中对应的统计次数和更新最后的行号
if (!cnt.containsKey(t) || S.get(t) != k) {
cnt.put(t, cnt.getOrDefault(t, 0) + 1);
S.put(t, k);
}
}
++ k;
}
// 遍历哈希表统计长度为mid的序列出现的最大行数
int res = 0;
for (Map.Entry<Long, Integer> entry : cnt.entrySet()) {
res = Math.max(res, entry.getValue());
}
return res == paths.length;
}
public int longestCommonSubpath(int n, int[][] paths) {
this.paths = paths;
int l = 0, r = N;
for (int[] path : paths) {
r = Math.min(r, path.length);
}
// 二分查找最大的公共子路径
while (l < r) {
int mid = (l + r + 1) /2;
if (check(mid)) l = mid;
else r = mid - 1;
}
return r;
}
}
对应模板题：字符串哈希
第55场双周赛
删除一个元素使数组严格递增
class Solution {
public boolean canBeIncreasing(int[] nums) {
boolean flag = true;
int n = nums.length;
for (int i = 0; i < n - 1; ++ i) {
if (nums[i] >= nums[i + 1]) {
if (flag) {
if (i - 1 < 0 || nums[i - 1] < nums[i + 1]) flag = false;
else if (i + 2 >= n || nums[i] < nums[i + 2]) flag = false;
else return false;
} else {
return false;
}
}
}
return true;
}
}
删除一个字符串中所有出现的给定子字符串
class Solution {
public String removeOccurrences(String s, String part) {
StringBuilder sb = new StringBuilder(s);
int len = part.length();
for (int i = 0; i < sb.length() - len + 1; ++ i) {
if (sb.substring(i, i + len).equals(part)) {
sb.delete(i, i + len);
i = Math.max(-1, i - len);
}
}
return sb.toString();
}
}
最大子序列交替和⭐
⚡ 动态规划
class Solution {
public long maxAlternatingSum(int[] nums) {
int n = nums.length;
long[][] f = new long[n + 1][2];
f[0][0] = 0;
for (int i = 1; i <= n; ++ i) {
f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] - nums[i - 1]);
f[i][1] = Math.max(f[i - 1][1], Math.max(0, f[i - 1][0]) + nums[i - 1]);
}
return Math.max(f[n][1], f[n][0]);
}
}
LeetCode Weekly 246
查询差绝对值的最小值⭐
⚡ 前缀和⭐
class Solution {
public int[] minDifference(int[] nums, int[][] queries) {
int M = 100;
int n = nums.length, m = queries.length;
int[][] s = new int[n + 1][M + 1];
// 处理前缀和
// s[i][j] 表示 nums数组中[0, i - 1]元素中是否有数字 j
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= M; ++ j) {
int t = 0;
if (nums[i - 1] == j) t = 1;
s[i][j] = s[i - 1][j] + t;
}
}
int[] res = new int[m];
int idx = 0;
// 枚举所有询问
for (int[] q : queries) {
int l = q[0] + 1, r = q[1] + 1; // 前缀和数组下标从1开始
int t = M, last = -1;
for (int j = 1; j <= M; ++ j) {
if (s[r][j] > s[l - 1][j]) {
if (last != -1) t = Math.min(t, j - last);
last = j;
}
}
if (t == M) t = -1;
res[idx ++] = t;
}
return res;
}
}
LeetCode Weekly 245
可移除字符的最大数目
⚡ 二分
class Solution {
public int maximumRemovals(String s, String p, int[] removable) {
int n = removable.length;
int l = -1, r = n - 1;
while (l < r) {
int mid = (r + l + 1) / 2;
char[] c = s.toCharArray();
for (int i = 0; i <= mid; ++ i) c[removable[i]] = '0';
if (judge(c, p)) l = mid;
else r = mid - 1;
}
return l + 1;
}
public boolean judge (char[] c, String p) {
int n = c.length, m = p.length();
int i, j;
for (i = 0, j = 0; i < n && j < m;++ i) {
if (c[i] == '0') continue;
if (c[i] == p.charAt(j)) ++ j;
}
if (j == m) return true;
else return false;
}
}
第 54 场双周赛
最大的幻方
⚡ 前缀和
class Solution {
public int largestMagicSquare(int[][] grid) {
int n = grid.length, m = grid[0].length;
// 横向前缀和
int[][] sx = new int[n][m + 1];
for (int i = 0; i < n; ++ i) {
for (int j = 1; j <= m; ++ j)
sx[i][j] = sx[i][j - 1] + grid[i][j - 1];
}
// 纵向前缀和
int[][] sy = new int[m][n + 1];
for (int i = 0; i < m; ++ i) {
for (int j = 1; j <= n; ++ j)
sy[i][j] = sy[i][j - 1] + grid[j - 1][i];
}
// 从大到小遍历所有的边长
for (int edge = Math.min(n, m); edge >= 2; -- edge) {
for (int i = 0; i + edge <= n; ++ i) {
for (int j = 0; j + edge <= m; ++ j) {
int stdSum = sx[i][j + edge] - sx[i][j];
boolean flag = true;
// 行和列
for (int k = 0; k < edge; ++ k) {
int sum1 = sx[i + k][j + edge] - sx[i + k][j];
int sum2 = sy[j + k][i + edge] - sy[j + k][i];
if (sum1 != stdSum || sum2 != stdSum){
flag = false;
break;
}
}
if (!flag) continue;
// 对角线
int d1 = 0, d2 = 0;
for (int k = 0; k < edge; ++ k) {
d1 += grid[i + k][j + k];
d2 += grid[i + edge - 1 - k][j + k];
}
if (d1 == stdSum && d2 == stdSum) {
return edge;
}
}
}
}
return 1;
}
}
LeetCode Weekly 244
使二进制字符串字符交替的最少反转次数⭐⭐
⚡ 滑动窗口
class Solution {
public int minFlips(String s) {
String tar = "01";
int len = s.length();
int cnt = 0;
for (int i = 0; i < len; ++ i) {
if (s.charAt(i) != tar.charAt(i % 2)) ++ cnt;
}
// len - cnt 便是 tar = "10" 时操作2的计数值
int ans = Math.min(cnt, len - cnt);
s += s; // 双倍字符串 即可使用滑动窗口丝滑拼接
for (int i = 0; i < len; ++ i) {
if (s.charAt(i) != tar.charAt(i % 2)) -- cnt;
if (s.charAt(i + len) != tar.charAt((i + len) % 2)) ++ cnt;
ans = Math.min(ans, Math.min(cnt, len - cnt));
}
return ans;
}
}
装包裹的最小浪费空间⭐⭐
⚡ 二分
class Solution {
static int mod = (int)(1e9 + 7);
public int minWastedSpace(int[] packages, int[][] boxes) {
// 用供应商去枚举箱子 用小数组去二分大数组
int n = packages.length;
Arrays.sort(packages);
long sum = 0;
for (int p : packages) sum += p;
long ans = Long.MAX_VALUE;
for (int[] box : boxes) {
Arrays.sort(box);
int m = box.length;
if (packages[n - 1] > box[m - 1]) continue;
long space = -sum;
int last = -1;
for (int b : box) {
int l = last, r = n - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (packages[mid] <= b) l = mid;
else r = mid - 1;
}
if (l == last) continue;
space += (long)b * (r - last); // 这里右边都是int计算结果会越界需要long转型
last = l;
}
ans = Math.min(ans, space);
}
return ans == Long.MAX_VALUE ? -1 : (int)(ans % mod);
}
}
LeetCode Weekly 243
使用服务器处理任务
⚡ 双堆
class Solution {
public int[] assignTasks(int[] servers, int[] tasks) {
int n = tasks.length, m = servers.length;
PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> {
if (x[0] != y[0]) return x[0] - y[0]; // 权重
return x[2] - y[2]; // 下标
});
for (int i = 0; i < m; ++ i) {
pq.offer(new int[]{servers[i], 0, i});
}
PriorityQueue<int[]> pqBusy = new PriorityQueue<>((x, y) -> {
if (x[1] != y[1]) return x[1] - y[1]; // 变成空闲的时间
return x[0] - y[0]; // 权重
});
int[] ans = new int[n];
for (int i = 0; i < n; ++ i) {
while (!pqBusy.isEmpty() && pqBusy.peek()[1] <= i)
pq.offer(pqBusy.poll());
int[] server;
if (pq.isEmpty()) {
server = pqBusy.poll();
server[1] += tasks[i];
} else {
server = pq.poll();
server[1] = i + tasks[i];
}
ans[i] = server[2];
pqBusy.offer(server);
}
return ans;
}
}
准时抵达会议现场的最小跳过休息次数⭐⭐
⚡ 动态规划 & 浮点数精度问题处理
class Solution {
static final double EPS = 1e-8, INT = 1e8;
public int minSkips(int[] dist, int speed, int hoursBefore) {
int n = dist.length;
// f[i][j] 经过了[0, i - 1] 共 i 段路用了 j 次操作的最小时间
double[][] f = new double[n + 1][n + 1];
for (int i = 1; i <= n; ++ i) {
double t = (double) dist[i - 1] / speed;
for (int j = 0; j <= i; ++ j) {
f[i][j] = INT;
if (j <= i - 1) f[i][j] = Math.min(f[i][j], Math.ceil(f[i - 1][j] + t - EPS));
if (j > 0) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + t);
}
}
for (int i = 0; i <= n; ++ i) {
if (f[n][i] < hoursBefore + EPS) return i;
}
return -1;
}
}
🍹y总 - 笔记🍹
第 53 场双周赛
矩阵中最大的三个菱形和⭐
⚡ 斜向前缀和
class Solution {
static int N = 110;
public int[] getBiggestThree(int[][] grid) {
int n = grid.length, m = grid[0].length;
int[][] s1 = new int[N][N];
int[][] s2 = new int[N][N];
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
s1[i][j] = s1[i - 1][j - 1] + grid[i - 1][j - 1];
s2[i][j] = s2[i - 1][j + 1] + grid[i - 1][j - 1];
}
}
TreeSet<Integer> set = new TreeSet<>();
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
set.add(grid[i - 1][j - 1]);
// 枚举所有半径
for (int k = 1; i - k >= 1 && i + k <= n && j - k >= 1 && j + k <= m; ++ k) {
int a = s2[i][j - k] - s2[i - k][j];
int b = s1[i][j + k] - s1[i - k][j];
int c = s2[i + k][j] - s2[i][j + k];
int d = s1[i + k][j] - s1[i][j - k];
// 去掉少算的和多算的点
set.add(a + b + c + d - grid[i + k - 1][j - 1] + grid[i - k - 1][j - 1]);
}
while (set.size() > 3) set.pollFirst();
}
}
int len = set.size();
int[] ans = new int[len];
for (int i = 0; i < len; ++ i) ans[i] = set.pollLast();
return ans;
}
}
两个数组最小的异或值之和⭐⭐
⚡ 状态压缩dp
class Solution {
static int INT = (int)1e9;
public int minimumXORSum(int[] nums1, int[] nums2) {
int n = nums1.length;
// 当前用过的数的状态是 i, 最小的异或值之和
int[] f = new int[1 << n];
f[0] = 0;
for (int i = 1; i < 1 << n; ++ i) {
f[i] = INT;
// 统计1的个数
int cnt = 0;
for (int j = 0; j < n; ++ j) {
if (((i >> j) & 1) == 1) ++ cnt;
}
for (int j = 0; j < n; ++ j) {
if (((i >> j) & 1) == 1) {
f[i] = Math.min(f[i], f[i - (1 << j)] + (nums2[j] ^ nums1[cnt - 1]));
}
}
}
return f[(1 << n) - 1];
}
}
🍹y总 - 笔记🍹
类似题型：AcWing算法基础课 - 最短Hamilton路径
LeetCode Weekly 242
时到达的列车最小时速
class Solution {
public int minSpeedOnTime(int[] dist, double hour) {
int l = 1, r = (int)2e7;
while (l < r) {
int mid = l + (r - l) / 2;
double need = isArrive(dist, mid);
if (need > hour) l = mid + 1;
else if (need <= hour) r = mid;
}
if (isArrive(dist, l) <= hour) return l;
return -1;
}
private double isArrive (int[] dist, int speed) {
int n = dist.length;
double need = 0;
for (int i = 0; i < n - 1; ++ i) {
need += (dist[i] + speed - 1) / speed;
}
need += ((double)dist[n - 1] / (double)speed);
return need;
}
}
跳跃游戏VII⭐
⚡ 动态规划
class Solution {
public boolean canReach(String s, int minJump, int maxJump) {
int n = s.length();
int[] dp = new int[n + 1];
int[] pre = new int[n + 1];
dp[1] = pre[1] = 1;
for (int i = 2; i <= n; ++ i) {
if (s.charAt(i - 1) == '0' && i - minJump >= 1) {
int l = Math.max(1, i - maxJump), r = i - minJump;
if (pre[r] - pre[l - 1] > 0) dp[i] = 1;
}
pre[i] = pre[i - 1] + dp[i];
}
return dp[n] == 1;
}
}
石子游戏VIII⭐⭐
⚡ 动态规划 - 经典题型
class Solution {
public int stoneGameVIII(int[] stones) {
int n = stones.length;
int[] pre = new int[n];
// 求前缀和
pre[0] = stones[0];
for (int i = 1; i < n; ++ i) pre[i] = pre[i - 1] + stones[i];
// dp[i] 表示 Alice [i, n) 内选择下标所能得到的 Alice 与 Bob 分数的最大差值。
int[] dp = new int[n];
dp[n - 1] = pre[n - 1]; // 边界条件
for (int i = n - 2; i > 0; -- i) {
dp[i] = Math.max(dp[i + 1], pre[i] - dp[i + 1]); // 状态转移方程
}
return dp[1];
}
}
LeetCode Weekly 241
找出所有子集的异或总和再求和
⚡ 爆搜
class Solution {
int ans;
public int subsetXORSum(int[] nums) {
ans = 0;
dfs(nums, 0, 0);
return ans;
}
private void dfs (int[] nums, int idx, int xor) {
if (idx >= nums.length) return;
ans += xor ^ nums[idx];
dfs (nums, idx + 1, xor ^ nums[idx]);
dfs (nums, idx + 1, xor);
}
}
⚡ 位枚举
class Solution {
public int subsetXORSum(int[] nums) {
int n = nums.length;
int ans = 0;
for (int i = 0; i < 1 << n; ++ i) {
int xor = 0;
for (int j = 0; j < n; ++ j) {
if ((i >> j & 1) == 1) xor ^= nums[j];
}
ans += xor;
}
return ans;
}
}
构成交替字符串需要的最小交换次数
class Solution {
public int minSwaps(String s) {
char[] c = s.toCharArray();
int n = c.length;
int a = 0, b = 0;
for (int i = 0; i < n; ++ i) {
if (c[i] == '0') ++ a;
else ++ b;
}
if(Math.abs(a - b) > 1) return -1;
int count = 0;
if (a == b + 1 || a == b) {
for (int i = 0; i < n; i += 2) {
if (c[i] != '0') ++ count;
}
}
if (b == a + 1 || a == b) {
int tmpCount = 0;
for (int i = 0; i < n; i += 2) {
if (c[i] != '1') ++ tmpCount;
}
if (a == b) count = Math.min(count, tmpCount);
else count = tmpCount;
}
return count;
}
}
找出和为指定值的下标对
class FindSumPairs {
int[] nums1, nums2;
HashMap<Integer, Integer> map;
public FindSumPairs(int[] nums1, int[] nums2) {
this.nums1 = nums1;
this.nums2 = nums2;
map = new HashMap<>();
for (int num : nums2) {
map.put (num, map.getOrDefault(num, 0) + 1);
}
}
public void add(int index, int val) {
map.put(nums2[index], map.get(nums2[index]) - 1);
nums2[index] += val;
map.put(nums2[index], map.getOrDefault(nums2[index], 0) + 1);
}
public int count(int tot) {
int ans = 0;
for (int num : nums1) {
ans += map.getOrDefault((tot - num), 0) ;
}
return ans;
}
}
恰有K根木棍可以看到的排列数目⭐⭐
⚡ 动规 经典问题-第一类斯特林数
class Solution {
public int rearrangeSticks(int n, int k) {
int mod = (int)(1e9 + 7);
// f[i][j] 表示将i个数划分成j个不同原排列的方案数
int[][] f = new int[n + 1][k + 1];
f[0][0] = 1;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= k; ++ j) {
f[i][j] = (int)(f[i - 1][j - 1] + (long)(i - 1) * f[i - 1][j] % mod) % mod;
}
}
return f[n][k];
}
}
第52场双周赛
将句子排序
class Solution {
public String sortSentence(String s) {
String[] strs = s.split(" ");
Arrays.sort(strs, (a, b) -> a.charAt(a.length() - 1) - b.charAt(b.length() - 1));
StringBuilder ans = new StringBuilder();
for (String str : strs) {
ans.append(str.substring(0, str.length() - 1) + " ");
}
ans.deleteCharAt(ans.length() - 1);
return ans.toString();
}
}
增长的内存泄露
class Solution {
public int[] memLeak(int memory1, int memory2) {
int crashTime = 1;
while(true) {
if (memory1 >= memory2) {
if (crashTime > memory1) return new int[]{crashTime, memory1, memory2};
memory1 -= crashTime;
} else {
if (crashTime > memory2) return new int[]{crashTime, memory1, memory2};
memory2 -= crashTime;
}
++ crashTime;
}
}
}
旋转盒子
class Solution {
public char[][] rotateTheBox(char[][] box) {
int m = box.length, n = box[0].length;
for (char[] c : box) {
int i = n - 1, j = n - 1;
while (i >= 0) {
if (c[i] == '#') {
c[i] = '.';
c[j] = '#';
-- j;
} else if (c[i] == '*') {
j = i - 1;
}
--i;
}
}
char[][] ans = new char[n][m];
for (int i = 0; i < n; ++ i){
for (int j = 0; j < m; ++j) {
ans[i][j] = box[m - 1 - j][i];
}
}
return ans;
}
}
向下取整数对和⭐
class Solution {
public int sumOfFlooredPairs(int[] nums) {
int mod = (int)(1e9 + 7);
int N = 100010;
int[] count = new int[N];
for (int i = 0; i < nums.length; ++ i) {
count[nums[i]] ++;
}
for (int i = N - 2; i >= 1; -- i) {
count[i] += count[i + 1];
}
int ans = 0;
for (int i = 0; i < nums.length; ++ i) {
for (int j = 1; j*nums[i] < N; ++ j) {
ans = (ans + count[j * nums[i]]) % mod;
}
}
return ans;
}
}
LeetCode Weekly 240
人口最多的年份
class Solution {
public int maximumPopulation(int[][] logs) {
int ansYear = 0, max = 0;
Arrays.sort(logs, (x, y) -> x[0] - y[0]);
for (int year = 1950; year <= 2050; ++year) {
int num = 0;
for (int i = 0; i < logs.length; ++i) {
if (year >= logs[i][0] && year < logs[i][1]) ++num;
else if (year < logs[i][0]) break;
}
if (num > max) {
max = num;
ansYear = year;
}
}
return ansYear;
}
}
下标对中的最大距离
⚡ 二分
class Solution {
public int maxDistance(int[] nums1, int[] nums2) {
int len1 = nums1.length, len2 = nums2.length;
int ans = 0;
for (int i = 0; i < len1; i ++) {
int low = 0, high = len2 - 1;
while (low < high) {
int mid = (low + high + 1) / 2;
if (nums2[mid] >= nums1[i]) {
low = mid;
} else {
high = mid - 1;
}
}
if (nums2[low] >= nums1[i] && low >= i)
ans = Math.max(ans, low - i);
}
return ans;
}
}
⚡ 双指针⭐
class Solution {
public int maxDistance(int[] nums1, int[] nums2) {
int ans = 0;
for (int i = nums1.length - 1, j = nums2.length - 1; j >= 0; j --) {
while (i > 0 && nums1[i - 1] <= nums2[j]) i --;
if (nums1[i] <= nums2[j]) ans = Math.max(ans, j - i);
}
return ans;
}
}
子数组最小乘积的最大值
⚡ 单调栈 & 前缀和⭐
class Solution {
public int maxSumMinProduct(int[] nums) {
int n = nums.length;
Deque<Integer> stack = new LinkedList<>();
int[] left = new int[n];
int[] right = new int[n];
// 设置哨兵去除边界情况的判断
Arrays.fill(left, -1);
Arrays.fill(right, n);
// 单调栈求 i 位置左右两边小于 nums[i] 的最小数
for (int i = n - 1; i >= 0; -- i) {
while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
left[stack.pop()] = i;
}
stack.push(i);
}
stack.clear();
for (int i = 0; i < n; ++ i) {
while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
right[stack.pop()] = i;
}
stack.push(i);
}
// 求前缀和 这里设置long防止爆int
long[] pre = new long[n + 1];
for (int i = 1; i <= n; ++ i) {
pre[i] = pre[i -1] + nums[i - 1];
}
// 求乘积的最大值
long ans = 0;
for (int i = 0; i < n; ++ i) {
ans = Math.max(ans, (pre[right[i]] - pre[left[i] + 1]) * nums[i]);
}
return (int) (ans % 1000000007);
}
}
有向图中最大颜色值⭐
⚡ 拓扑排序 & 动态规划
class Solution {
public int largestPathValue(String colors, int[][] edges) {
int n = colors.length();
// 邻接表
List<List<Integer>> g = new ArrayList<>(n);
for (int i = 0; i < n; ++i) {
g.add(new ArrayList<>());
}
// 统计节点入度
int[] indeg = new int[n];
for (int[] edge : edges) {
++ indeg[edge[1]];
g.get(edge[0]).add(edge[1]);
}
// 记录拓扑排序中遇到节点个数
int found = 0;
int[][] f = new int[n][26];
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; ++ i) {
if (indeg[i] == 0) q.offer(i);
}
while (!q.isEmpty()) {
++ found;
int u = q.poll();
// 将节点对应颜色加1
++ f[u][colors.charAt(u) - 'a'];
// 枚举 u 后所有结点 v
for (int v : g.get(u)) {
-- indeg[v];
// 将 f(v,c) 更新为其与 f(u,c) 的较大值
for (int c = 0; c < 26; ++c) {
f[v][c] = Math.max(f[v][c], f[u][c]);
}
if (indeg[v] == 0) q.offer(v);
}
}
if (found != n) return -1;
int ans = 0;
for (int i = 0; i < n; ++ i) {
ans = Math.max(ans, Arrays.stream(f[i]).max().getAsInt());
}
return ans;
}
}
LeetCode Weekly 239
到目标元素的最小距离
class Solution {
public int getMinDistance(int[] nums, int target, int start) {
int n = nums.length;
int abs = Integer.MAX_VALUE;
for (int i = 0; i < n; ++i) {
if (nums[i] == target && Math.abs(i - start) < abs) {
abs = Math.abs(i - start);
}
}
return abs;
}
}
将字符串拆分为递减的连续值⭐
⚡ 暴力枚举法
class Solution {
//由于题中数据范围为 1 <= s.length <= 20
//暴力枚举法
public boolean splitString(String s) {
int n = s.length();
//暴力枚举所有分法
for (int i = 1; i < 1 << n - 1; ++i) {
boolean flag = true;
long last = -1, x = s.charAt(0) - '0';
for (int j = 0; j < n - 1; ++j) {
if ((i >> j & 1) == 1) { //是边界
if (last != -1 && x != last - 1) {
flag = false;
break;
}
last = x;
x = s.charAt(j + 1) - '0';
} else { //不是边界，累计计算此区间数的大小
x = x * 10 + s.charAt(j + 1) - '0';
}
}
if (x != last - 1) flag = false;
else return true;
}
return false;
}
}
邻位交换的最小次数⭐⭐
⚡ 下个排列 & 逆序和
class Solution {
public int getMinSwaps(String num, int k) {
char[] nums = num.toCharArray();
int n = nums.length;
// char[] numsk = nums; //浅复制：仅复制对象的引用
char[] numsk = new char[n];
for (int i = 0; i < n; ++i) {
numsk[i] = nums[i];
}
while (k-- > 0) nextPermutation(numsk);
int[] c = new int[n]; // 存nums里元素在numsk里的下标是多少
int[] cnt = new int[10]; // 存每个数出现的次数
Arrays.fill(cnt, 0);
for (int i = 0; i < n; ++i) {
int x = nums[i] - '0';
cnt[x]++;
int y = cnt[x];
for (int j = 0; j < n; ++j) {
if (numsk[j] - '0' == x && --y == 0) { //表示找到了此x
c[i] = j;
break;
}
}
}
//求c的逆序对
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (c[i] > c[j]) ++ans;
}
}
return ans;
}
// 下一个排列
public void nextPermutation(char[] nums) {
int n = nums.length;
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
--i;
}
if (i >= 0) {
int j = n - 1;
while (j > i && nums[j] <= nums[i]) {
--j;
}
char tmp = nums[j];
nums[j] = nums[i];
nums[i] = tmp;
}
for (int left = i + 1, right = n - 1; left < right; ++left,--right) {
char tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
}
}
}
class Solution {
public int getMinSwaps(String num, int k) {
int n = num.length();
char[] nums = num.toCharArray();
char[] numsk = new char[n];
for (int i = 0; i < n; ++i) {
numsk[i] = nums[i];
}
while (--k >= 0) nextPermutation(numsk);
int ans = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] != numsk[i]) {
for (int j = i + 1; j < n; ++j) {
if (nums[j] == numsk[i]) {
for (int t = j - 1; t >= i; --t) {
++ans;
char tmp = nums[t];
nums[t] = nums[t + 1];
nums[t + 1] = tmp;
}
break;
}
}
}
}
return ans;
}
public void nextPermutation(char[] nums) {
int n = nums.length;
int i = n - 2;
// 从尾部开始找连续递增序列的边界的下个位置 i
while (i >= 0 && nums[i] >= nums[i + 1]) -- i;
// 在递增序列中找到第一个大于 nums[i] 的值
if (i >= 0) {
int j = n - 1;
while (j > i && nums[j] <= nums[i]) -- j;
char tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
// 反转递增序列
for (int left = i + 1, right = n - 1; left < right; ++left, --right) {
char tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
}
}
}
包含每个查询的最小区间🌟
⚡ 并查集
class Solution {
HashSet<Integer> set = new HashSet<>(); //用来去掉数据离散化操作中重复的数
int[] nums = new int[1000000];
int[] union; //并查集
int[] w; //每个点的颜色
int count = 0; //不同的数的个数
public int[] minInterval(int[][] intervals, int[] queries) {
//数据离散化
for (int i = 0; i < intervals.length; i++) {
int a = intervals[i][0];
int b = intervals[i][1];
if (!set.contains(a)){
set.add(a);
nums[count++] = a;
}
if (!set.contains(b)){
set.add(b);
nums[count++] = b;
}
}
for (int i = 0; i < queries.length; i++) {
if (!set.contains(queries[i])){
set.add(queries[i]);
nums[count++] = queries[i];
}
}
Arrays.sort(nums, 0, count);
// 最后一个元素"删掉"后会指向下个元素，因此最后一个元素的下一个元素也会被用到，故初始化需多加一个元素
union = new int[count + 1];
w = new int[count + 1];
Arrays.fill(w, -1);
for (int i = 0; i <= count; i++) union[i] = i;
// 按区间大小排序
Arrays.sort(intervals, (o1, o2) -> (o1[1] - o1[0]) - (o2[1] - o2[0]));
for (int i = 0; i < intervals.length; i++) {
int l = get(intervals[i][0]);
int r = get(intervals[i][1]);
int len = intervals[i][1] - intervals[i][0] + 1;
while (find(l) <= r) { //l右边第一个没有被染色的点没有超过r的话
l = find(l); // 找到l右边第一个没有被染色的点
w[l] = len; // 将其染色为 len
union[l] = l + 1; // 指向下一个点
}
}
// 枚举所有的询问 找到答案数组
int[] res = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int ma = get(queries[i]);
res[i] = w[ma];
}
return res;
}
//并查集find函数
public int find(int x){
if (union[x] != x) union[x] = find(union[x]);
return union[x];
}
//二分查找
private int get(int tar) {
int l = 0;
int r = count - 1;
while (l <= r){
int mid = (l + r) >> 1;
if (nums[mid] == tar){
return mid;
}else if (nums[mid] < tar){
l = mid + 1;
}else {
r = mid - 1;
}
}
return 0;
}
}
第51场双周赛 (AK）
将所有数字用字符替换
class Solution {
public String replaceDigits(String s) {
int len = s.length();
char[] chars = s.toCharArray();
for (int i = 1; i < len; i += 2) {
chars[i] = shift(chars[i - 1], chars[i]);
}
return String.valueOf(chars);
}
private static char shift (char c, int n) {
if (c + n - '0' > 'z') return 'z';
return (char) (c + n - '0');
}
}
座位预约管理系统
//去元素时间复杂度O(n)
class SeatManager {
boolean[] seats;
int empty;
public SeatManager(int n) {
seats = new boolean[n];
empty = n;
}
public int reserve() {
for (int i = 0; i < seats.length; ++i) {
if (!seats[i]){
seats[i] = true;
return i + 1;
}
}
return -1;
}
public void unreserve(int seatNumber) {
seats[seatNumber - 1] = false;
}
}
/**
* Your SeatManager object will be instantiated and called as such:
* SeatManager obj = new SeatManager(n);
* int param_1 = obj.reserve();
* obj.unreserve(seatNumber);
*/
⚡ 优先队列
class SeatManager {
//以O(1)取出队列中权值最小的元素,再以O(logn)维护队列
PriorityQueue<Integer> seats = new PriorityQueue<>();
public SeatManager(int n) {
for (int i = 1; i <= n; ++i) {
seats.add(i);
}
}
public int reserve() {
return seats.poll();
}
public void unreserve(int seatNumber) {
seats.add(seatNumber);
}
}
减小和重新排列数组后的最大元素
class Solution {
public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
Arrays.sort(arr);
arr[0] = 1;
for (int i = 1; i < arr.length; ++i) {
if (arr[i] != arr[i - 1]) {
arr[i] = arr[i - 1] + 1;
}
}
return arr[arr.length - 1];
}
}
class Solution {
public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
Arrays.sort(arr);
int last = 0;
for (int i = 0; i < arr.length; ++i) {
last = Math.min(last + 1, arr[i]);
}
return last;
}
}
最近的房间
class Solution {
public int[] closestRoom(int[][] rooms, int[][] queries) {
//先排序
Arrays.sort(rooms, (o1, o2) -> o2[1] - o1[1]);
int n = queries.length;
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
int absId = Integer.MAX_VALUE;
int minId = -1;
for (int j = 0; j < rooms.length; ++j) {
if (rooms[j][1] < queries[i][1]) {
break;
}
int tmp = Math.abs(rooms[j][0] - queries[i][0]);
if (absId == tmp) {
if (minId > rooms[j][0]) minId = rooms[j][0];
} else if (absId > tmp){
absId = tmp;
minId = rooms[j][0];
}
}
ans[i] = minId;
}
return ans;
}
}
⚡ 离线算法 & TreeSet
class Solution {
public int[] closestRoom(int[][] rooms, int[][] queries) {
int[][] q = new int[queries.length][3];
for(int i = 0; i < q.length; ++i){
q[i][0] = queries[i][0];
q[i][1] = queries[i][1];
q[i][2] = i; // 记录在queries中的原位置
}
// 排序
Arrays.sort(q, (x, y) -> y[1] - x[1]);
Arrays.sort(rooms, (x, y) -> y[1] - x[1]);
TreeSet<Integer> set = new TreeSet<>();
int idx = 0;
int[] ans = new int[q.length];
Arrays.fill(ans, -1);
for (int i = 0; i < q.length; ++i) {
while (idx < rooms.length && rooms[idx][1] >= q[i][1]) {
set.add(rooms[idx][0]);
idx += 1;
}
Integer a = set.floor(q[i][0]); // 返回此set中小于或等于给定元素的最大元素
Integer b = set.ceiling(q[i][0]); // 返回此set中大于或等于给定元素的最小元素
if (a == null && b == null){
ans[q[i][2]] = -1;
} else if (b == null || a == null){
ans[q[i][2]] = (a == null) ? b : a;
} else {
ans[q[i][2]] = ((q[i][0]-a) <= (b-q[i][0])) ? a : b;
}
}
return ans;
}
}
LeetCode Weekly 238
K进制表示下的各位数字总和
class Solution {
public int sumBase(int n, int k) {
int ans = 0;
while(n != 0){
ans += n % k;
n /= k;
}
return ans;
}
}
最高频元素的频数⭐
⚡ 二分
能使用二分的依据：j往左走需要的次数严格单调递增。
class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int[] sums = new int[n + 1];
for (int i = 1; i <= n; ++i) {
sums[i] = sums[i - 1] + nums[i - 1];
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
int l = 1, r = i;
while (l < r) {
int mid = l + r >> 1;
if ((i - mid + 1) * nums[i - 1] - (sums[i] - sums[mid - 1]) <= k) {
r = mid;
} else {
l = mid + 1;
}
}
ans = Math.max(ans, i - r + 1);
}
return ans;
}
}
⚡ 双指针
能使用双指针的依据: i往后走，i对应的j一定单调往后走。
class Solution {
public int maxFrequency(int[] nums, int k) {
int n = nums.length;
Arrays.sort(nums);
int[] sums = new int[n + 1];
for (int i = 1; i <= n; ++i) {
sums[i] = sums[i - 1] + nums[i - 1];
}
int ans = 0;
for (int i = 1, j = 1; i <= n; ++i) {
while ((i - j + 1) * nums[i - 1] - (sums[i] - sums[j - 1]) > k) {
++j;
}
ans = Math.max(ans, i - j + 1);
}
return ans;
}
}
所有元音按顺序排布的最长子字符串⭐
⚡ 动态规划 + 哈希表
class Solution {
public int longestBeautifulSubstring(String word) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int n = word.length();
int[] dp = new int[n];
dp[0] = 1;
int ans = 0;
map.put(word.charAt(0), 1);
for (int i = 1; i < n; ++i) {
char tmp = word.charAt(i);
if (tmp >= word.charAt(i - 1)) {
dp[i] = dp[i - 1] + 1;
map.put(tmp, 1);
if (map.getOrDefault('a', 0) == 1 && map.getOrDefault('e', 0) == 1 && map.getOrDefault('i', 0) == 1 && map.getOrDefault('o',0) == 1 && map.getOrDefault('u',0) == 1){
ans = Math.max(ans, dp[i]);
}
}
else {
dp[i] = 1;
map.clear();
map.put(tmp, 1);
}
}
return ans;
}
}
注：执行时间较高
⚡ 双指针
class Solution {
public int longestBeautifulSubstring(String word) {
int n = word.length();
int ans = 0;
String p = "aeiou";
for (int i = 0; i < n; ++i) {
if (word.charAt(i) != 'a') continue;
int j = i, k = 0;
while (j < n) {
if (word.charAt(j) == p.charAt(k)) ++j;
else {
if (k == 4) break;
if (word.charAt(j) == p.charAt(k + 1)) {
++j; ++k;
} else break;
}
if (k == 4) ans = Math.max(ans, j - i);
}
i = j - 1;
}
return ans;
}
}
最高建筑高度🌟
class Solution {
public:
int maxBuilding(int n, vector<vector<int>>& restrictions) {
auto&& r = restrictions;
r.push_back({1,0}); //增加约束
sort(r.begin(), r.end()); //排序
if (r.back()[0] != n) {
r.push_back({n, n - 1}); //增加约束
}
int m = r.size();
//从左向右传递约束
for (int i = 1; i < m; ++i) {
r[i][1] = min(r[i][1], r[i - 1][1] + r[i][0] - r[i - 1][0]);
}
//从右向左传递约束
for (int i = m - 2; i >= 0; --i) {
r[i][1] = min(r[i][1], r[i + 1][1] + (r[i + 1][0] - r[i][0]));
}
int ans = 0;
for (int i = 1; i < m; ++i) {
//计算 r[i - 1][0] 和 r[i][0] 之间建筑的最大高度
int best = (r[i - 1][1] + r[i][1] + r[i][0] - r[i - 1][0]) / 2;
ans = max(ans, best);
}
return ans;
}
};
LeetCode Weekly 237
判断句子是否为全字母句
class Solution {
public boolean checkIfPangram(String sentence) {
int ans = 0;
for (int i = 0; i < sentence.length(); ++i) {
ans |= (1 << (sentence.charAt(i) - 'a'));
}
return ans == (1 << 26) - 1;
}
}
雪糕的最大数量
class Solution {
public int maxIceCream(int[] costs, int coins) {
int cnt = 0;
Arrays.sort(costs);
for (int cost : costs) {
if (coins >= cost) {
coins -= cost;
++cnt;
}
else break;
}
return cnt;
}
}
单线程CPU🌟
⚡ 排序 & 优先队列(小根堆)
class Solution {
class Task {
int id;
int enqueueTime;
int processingTime;
public Task (int id, int enqueueTime, int processingTime) {
this.id = id;
this.enqueueTime = enqueueTime;
this.processingTime = processingTime;
}
}
public int[] getOrder(int[][] tasks) {
int len = tasks.length;
List<Task> taskList = new ArrayList<Task>();
for (int i = 0; i < len; ++i) {
taskList.add(new Task(i, tasks[i][0], tasks[i][1]));
}
//按入队时间排序
Collections.sort(taskList, (t1, t2) -> t1.enqueueTime - t2.enqueueTime);
//优先队列
PriorityQueue<Task> minHeap = new PriorityQueue<Task>((t1, t2) -> {
//短作业优先
if (t1.processingTime != t2.processingTime) return t1.processingTime - t2.processingTime;
//运行时间相等时按照id排序
else return t1.id - t2.id;
});
long now = 0; //时间戳
int[] ret = new int[len];
int i = 0; //taskList坐标
int j = 0; //ret坐标
while (i < len) {
//将所有开始时间小于等于当前时间戳的task放入优先队列中
while (i < len && taskList.get(i).enqueueTime <= now) {
minHeap.offer(taskList.get(i++));
}
//当堆中没有任务时，前移时间戳
if (minHeap.isEmpty()) {
now = (long) taskList.get(i).enqueueTime;
//加入task进队列
while (i < len && taskList.get(i).enqueueTime <= now) {
minHeap.offer(taskList.get(i++));
}
}
//取出任务执行
Task t = minHeap.poll();
ret[j++] = t.id;
now += (long) t.processingTime;
}
//此时所有taskList所有任务均已执行或加入队列中
//清空队列剩余任务
while (!minHeap.isEmpty()) {
ret[j++] = minHeap.poll().id;
}
return ret;
}
}
所有数对按位与结果的异或和⭐
⚡ 逐位确定结果
class Solution {
public int getXORSum(int[] arr1, int[] arr2) {
int ans = 0;
//依次确定答案二进制表示中的每一位
for (int k = 30; k >= 0; --k) {
int cnt1 = 0;
for (int num : arr1) {
if ((num & (1 << k)) != 0) {
++cnt1;
}
}
int cnt2 = 0;
for (int num : arr2) {
if ((num & (1 << k)) != 0) {
++cnt2;
}
}
//当cnt1和cnt2均为奇数时，结果中k位为1
//一个数与 0 进行异或运算，它的值不改变
if ((cnt1 % 2 == 1) && (cnt2 % 2 == 1)) {
ans |= (1 << k);
}
}
return ans;
}
}
⚡ 利用与异或运算法则
class Solution {
public int getXORSum(int[] arr1, int[] arr2) {
int p1 = 0, p2 = 0;
for (int i : arr1) {
p1 ^= i;
}
for (int j : arr2) {
p2 ^= j;
}
return p1 & p2;
}
}
Comments | NOTHING