# LeetCode 3
2021.4
- 80. Remove Duplicates from Sorted Array II（删除有序数组中的重复项 II）
- 153. 寻找旋转排序数组中的最小值
- 33. 搜索旋转排序数组
- 81. Search in Rotated Sorted Array II（搜索旋转排序数组 II）
- 154. 寻找旋转排序数组中的最小值 II
- 287. 寻找重复数
- 1143. 最长公共子序列
- 239. Sliding Window Maximum（滑动窗口最大值）
- 128. 最长连续序列
- 76. Minimum Window Substring（最小覆盖子串）
- 263. Ugly Number（丑数）
- 238. Product of Array Except Self（除自身以外数组的乘积）
- 454. 四数相加 II（4Sum II）
- 227. Basic Calculator II（基本计算器 II）
- 264. 丑数 II
- 23. Merge k Sorted Lists（合并K个升序链表）
- 138. 复制带随机指针的链表
- 752. 打开转盘锁
- 127. Word Ladder（单词接龙）
- 130. Surrounded Regions（被围绕的区域）
- 179. Largest Number（最大数）
- 783. Minimum Distance Between BST Nodes（二叉搜索树节点最小距离）
- 530. Minimum Absolute Difference in BST（二叉搜索树的最小绝对差）
- 236. Lowest Common Ancestor of a Binary Tree（二叉树的最近公共祖先）
- 315. Count of Smaller Numbers After Self（计算右侧小于当前元素的个数）
- 剑指 Offer 51. 数组中的逆序对
- 213. 打家劫舍 II
- 152. 乘积最大子数组
- 309. 最佳买卖股票时机含冷冻期
- 1827. 最少操作使数组递增（第 50 场双周赛）
- 1828. 统计一个圆中点的数目（第 50 场双周赛）
- 1832. 判断句子是否为全字母句（第 237 场周赛）
- 1833. 雪糕的最大数量（第 237 场周赛）
- 220. Contains Duplicate III（存在重复元素 III）
- 139. 单词拆分
- 51. N-Queens（N 皇后）
- 52. N-Queens II（N皇后 II）
- 27. Remove Element（移除元素）
- 698. Partition to K Equal Sum Subsets（划分为k个相等的子集）
- 111. Minimum Depth of Binary Tree（二叉树的最小深度）
- 773. Sliding Puzzle（滑动谜题）
- 77. Combinations（组合）
- 226. Invert Binary Tree（翻转二叉树）
- 114. Flatten Binary Tree to Linked List（二叉树展开为链表）
- 724. Find Pivot Index（寻找数组的中心下标）
- 523. Continuous Subarray Sum（连续的子数组和）
- 剑指 Offer 42. 连续子数组的最大和
- 560. Subarray Sum Equals K（和为K的子数组）
- 930. 和相同的二元子数组
- 1248. Count Number of Nice Subarrays（统计「优美子数组」）
- 974. Subarray Sums Divisible by K（和可被 K 整除的子数组）
- 654. Maximum Binary Tree（最大二叉树）
- 106. Construct Binary Tree from Inorder and Postorder Traversal（从中序与后序遍历序列构造二叉树）
- 652. Find Duplicate Subtrees（寻找重复的子树）
- 897. Increasing Order Search Tree（递增顺序搜索树）
- 5740. 所有元音按顺序排布的最长子字符串（第 238 场周赛）
- 1838. 最高频元素的频数（第 238 场周赛）
- 1837. K 进制表示下的各位数字总和（第 238 场周赛）
- 538. Convert BST to Greater Tree（把二叉搜索树转换为累加树）
- 897. 递增顺序搜索树
- 1011. 在 D 天内送达包裹的能力
- 1373. 二叉搜索子树的最大键值和
- 96. 不同的二叉搜索树
- 95. 不同的二叉搜索树 II
- 938. 二叉搜索树的范围和
- 209. 长度最小的子数组
- 222. 完全二叉树的节点个数
- 35. 搜索插入位置
- 704. 二分查找
- 718. 最长重复子数组
- 633. 平方数之和
- 378. 有序矩阵中第 K 小的元素
- 403. 青蛙过河
- 137. 只出现一次的数字 II
- 690. 员工的重要性
- 剑指 Offer 13. 机器人的运动范围
- 554. 砖墙
- 1847. 最近的房间（第 51 场双周赛）
- 1846. 减小和重新排列数组后的最大元素（第 51 场双周赛）
- 1845. 座位预约管理系统（第 51 场双周赛）
- 1844. 将所有数字用字符替换（第 51 场双周赛）
- 1849. 将字符串拆分为递减的连续值（第 239 场周赛）
- 1848. 到目标元素的最小距离（第 239 场周赛）
- 416. 分割等和子集
- 516. 最长回文子序列
- 377. 组合总和 Ⅳ
- 208. 实现 Trie (前缀树)
- 363. 矩形区域不超过 K 的最大数值和
- 368. 最大整除子集
- 91. 解码方法
- 781. 森林中的兔子
- 面试题 17.21. 直方图的水量
- 1006. 笨阶乘
- ## 87. 扰乱字符串
# 80. Remove Duplicates from Sorted Array II（删除有序数组中的重复项 II）
- 双指针
- 快慢指针
- 有序数组
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
// 数组小于等于2 直接返回 一定满足题意的重复要求
if (n <= 2) return n;
// 上一步排除了前2的问题，因此快慢指针从2开始
int slow = 2, fast = 2;
while (fast < n) {
// slow 代表清除重复元素后的数组长度；fast 代表正在比较的数据
// 起初，slow、fast在同一位置，只需要与slow-2比较是否相等，不相等则fast位置元素个数一定<=2；
// 相等则右移fast继续比较，直到找到第一个与slow-2不相等的数，将其与slow交换。
if (nums[slow-2] != nums[fast]) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}
# 153. 寻找旋转排序数组中的最小值
// 如何分析二分法中条件的设计
// 循环退出条件：
// 如果只剩最后两个数（二分到最后都会变成2个数，在多个数时，也可以将其看成两个数），mid一定等于left；
// 若nums[left/mid]>nums[right]，left右移+1，即left与right相遇了，跳出循环；
// 若nums[left/mid]<nums[right]，right被赋值为mid，即left与right同样会相遇，跳出循环。
class Solution {
public int findMin(int[] nums) {
int n = nums.length;
int l = 0, r = n-1;
// l<r不是l<=r的原因：因为下面赋值是r=mid，所以相等时必须跳出循环
while (l < r) {
// 纯粹/2的方式，奇数个数就取中间，偶数个数就取中间靠左的数
int mid = l + ((r - l) >> 1);
// 由于/2的方式，mid只会>right或者<right，不会=right，因为mid靠近left
if (nums[mid] > nums[r]) {
l = mid+1;
} else {
r = mid;
}
}
return nums[r];
}
}
# 33. 搜索旋转排序数组
由于数组原本是升序的，截断之后，可以发现仍然是两部分保持升序。若将数组二分，其中一部分一定保持有序，则可以判断有序部分元素是否存在，若不存在则缩小二分范围，到无序区间继续二分寻找即可。
- 二分法，部分有序。
class Solution {
public int search(int[] nums, int t) {
int n = nums.length;
int start = 0, end = n-1;
int l = 0, r = n-1;
if (l == r && nums[l] == t) {
return l;
}
while (l < r) {
int mid = l + ((r - l) >> 1);
if (t > nums[end]) {
if (nums[mid] > nums[end]) {
if (t < nums[mid]) {
r = mid;
} else if (t > nums[mid]){
l = mid+1;
} else {
return mid;
}
} else {
r = mid;
}
} else if (t < nums[end]) {
if (nums[mid] > nums[end]) {
l = mid+1;
} else {
if (t < nums[mid]) {
r = mid;
} else if (t > nums[mid]){
l = mid+1;
} else {
return mid;
}
}
} else {
return end;
}
}
return -1;
}
}
分类讨论target与mid的大小，如果target与mid不在一个递增的线上，会出现什么。思路不容易清晰，现场ac率较低，具体代码如下：
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int l = 0, r = n-1;
while (l <= r) {
int mid = l+((r-l)>>1);
if (target == nums[mid]) {
return mid;
} else if (target > nums[mid]) {
if (nums[mid] <= nums[r] && target > nums[r]) {
r = mid-1;
} else {
l = mid+1;
}
} else {
if (nums[mid] >= nums[l] && target < nums[l]) {
l = mid+1;
} else {
r = mid-1;
}
}
}
return -1;
}
}
递归：二分之后，总有一边是有序的，一边是无序的。判断target是否在有序部分中，若不在则继续递归无序部分，若在则递归有序部分。
class Solution {
public int search(int[] nums, int target) {
return binary(nums, target, 0, nums.length-1);
}
public int binary(int[] nums, int target, int l, int r) {
if (l > r) return -1;
int mid = l + ((r-l)>>1);
if (target == nums[mid]) return mid;
if (nums[l] <= nums[mid]) {
if (target < nums[mid] && target >= nums[l]) {
return binary(nums, target, l, mid-1);
} else {
return binary(nums, target, mid+1, r);
}
} else {
if (target > nums[mid] && target <= nums[r]) {
return binary(nums, target, mid+1, r);
} else {
return binary(nums, target, l, mid-1);
}
}
}
}
代码继续精简，但失去了可读性：
class Solution {
public int search(int[] nums, int target) {
return binary(nums, target, 0, nums.length-1);
}
public int binary(int[] nums, int target, int l, int r) {
if (l > r) return -1;
int mid = l + ((r-l)>>1);
if (target == nums[mid]) return mid;
if ((nums[l] <= nums[mid] && target < nums[mid] && target >= nums[l])
|| (nums[l] > nums[mid] && !(target > nums[mid] && target <= nums[r]))) {
return binary(nums, target, l, mid-1);
} else {
return binary(nums, target, mid+1, r);
}
}
}
# 81. Search in Rotated Sorted Array II（搜索旋转排序数组 II）
class Solution {
public boolean search(int[] nums, int t) {
int n = nums.length;
int start = 0, end = n-1;
int l = 0, r = n-1;
if (l == r && nums[l] == t) {
return true;
}
while (l < r) {
int mid = l + ((r - l) >> 1);
// System.out.println("mid: "+mid+"; value:"+nums[mid]);
if (nums[mid] == t) return true;
if (nums[l] == nums[r] && nums[l] == nums[mid]) {
l++;
continue;
}
if (t > nums[end]) {
if (nums[mid] > nums[end]) {
if (t < nums[mid]) {
r = mid;
} else if (t > nums[mid]){
l = mid+1;
} else {
return true;
}
} else {
r = mid;
}
} else if (t < nums[end]) {
if (nums[mid] > nums[end]) {
l = mid+1;
} else {
if (t < nums[mid]) {
r = mid;
} else if (t > nums[mid]){
l = mid+1;
} else {
return true;
}
}
} else {
return true;
}
}
return false;
}
}
# 154. 寻找旋转排序数组中的最小值 II
class Solution {
public int findMin(int[] nums) {
int n = nums.length;
int l = 0, r = n-1;
while (l < r) {
int mid = l + ((r - l) >> 1);
if (nums[l] == nums[mid] && nums[r] == nums[mid]) {
l++;
continue;
}
if (nums[mid] > nums[r]) {
l = mid+1;
} else {
r = mid;
}
}
return nums[r];
}
}
# 287. 寻找重复数
// 二分法
class Solution {
public int findDuplicate(int[] nums) {
int n = nums.length;
int l = 1, r = n-1;
while (l < r) {
int cnt = 0;
int mid = (r + l) >> 1;
for (int i = 0; i < n; i++) {
if (nums[i] <= mid) {
cnt++;
}
}
if (cnt > mid) {
r = mid;
} else {
l = mid+1;
}
}
return r;
}
}
# 1143. 最长公共子序列
经典动态规划题
按照以下图示写出dp方程并画出dp table：
使用二维dp数组解（在空间上从图中可以看出只当前遍历行，只依赖上一行，因此空间可以优化成两个一位数组）：
class Solution {
public int longestCommonSubsequence(String t1, String t2) {
int s1 = t1.length(), s2 = t2.length();
int[][] dp = new int[s1+1][s2+1];
for (int i = 1; i <= s1; i++) {
char c1 = t1.charAt(i-1);
for (int j = 1; j <= s2; j++) {
char c2 = t2.charAt(j-1);
if (c1 == c2) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[s1][s2];
}
}
逻辑无调整，代码结构小优化：
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n1 = text1.length(), n2 = text2.length();
int[][] dp = new int[n1+1][n2+1];
for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; j++) {
if (text1.charAt(i) == text2.charAt(j)) {
dp[i+1][j+1] = dp[i][j] + 1;
} else {
dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
}
}
}
return dp[n1][n2];
}
}
# 239. Sliding Window Maximum（滑动窗口最大值）
// 使用优先级队列（最大堆）
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {
public int compare(int[] o1, int[] o2) {
return o1[0]!=o2[0] ? o2[0]-o1[0] : o2[1]-o1[1];
}
});
for (int i = 0; i < k; i++) {
q.offer(new int[]{nums[i], i});
}
int[] res = new int[nums.length - k + 1];
res[0] = q.peek()[0];
int l = 1, r = k;
while (r < nums.length) {
q.add(new int[]{nums[r], r});
while (q.peek()[1] < l) {
q.poll();
}
res[l] = q.peek()[0];
l++;
r++;
}
return res;
}
}
单调队列：
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length-k+1];
LinkedList<Integer> q = new LinkedList<>();
int size = k;
for (int i = 0; i < nums.length; i++) {
while (q.peekLast()!=null && q.peekLast()<nums[i]) {
q.pollLast();
}
q.offerLast(nums[i]);
if (size <= 0 && q.peekFirst() == nums[i-k]) {
q.pollFirst();
} else if (size > 0) {
size--;
}
if (i >= k-1) {
res[i-k+1] = q.peek();
}
}
return res;
}
}
# 128. 最长连续序列
// [100,4,1,3,2] = 1,2,3,4
// {100=1,4=4,1=4,3=2,2=4}
// 由于是查找数字连续序列，并且只能On时间，也就是1~2次遍历。
// 从数据最少的场景开始分析：
// 每放入一个数时，可以使用字典知道前面放入的元素中是否存在它相邻的元素，比如：字段中已经有{1,3}，现在放入2，通过cur-1,cur+1到字典中查是否存在相邻元素。
// 并且加入一个数时，有插入到连续数的左、右、中三种场景（要更新字典中保存的长度值）：
// 左：{2,3}<1; 更新自己和连续数的右边界；右：{2,3}<4; 更新自己和连续数的左边界；中：{2,4}<3; 更新左右连续数的左右边界。
// 长度是通过边界相减获得的；当前插入数字的连续长度值=字典中左边数相邻连续数长度+字典中右边数相邻连续数长度+1
// 再更新当前数插入后的连续数的边界值的映射长度。
class Solution {
public int longestConsecutive(int[] nums) {
int n = nums.length;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int res = 0;
for (int num : nums) {
if (!map.containsKey(num)) {
int left = map.get(num - 1) == null ? 0 : map.get(num - 1);
int right = map.get(num + 1) == null ? 0 : map.get(num + 1);
int cur = 1 + left + right;
if (cur > res) {
res = cur;
}
map.put(num, cur);
map.put(num - left, cur);
map.put(num + right, cur);
}
}
return res;
}
}
哈希表，先将数组加入到哈希表中，再表里检查集合中是否存在i+1的数，如果i+1存在，继续检查i+2...i+n，同时统计最大值。但此时复杂度是n^2，通过观察可以发现，如果i-1存在，就不用统计i了，因为i-1会统计，可以直接跳过，所以复杂度降为On。
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int n : nums) {
set.add(n);
}
int max = 0;
for (int i : nums) {
if (set.contains(i-1)) {
continue;
}
int n = i+1;
int len = 1;
while (set.contains(n)) {
len++;
n++;
}
max = Math.max(max, len);
}
return max;
}
}
# 76. Minimum Window Substring（最小覆盖子串）
// 滑动窗口
// s = "ADOBECODEBANC", t = "ABC" result: "BANC"
class Solution {
public String minWindow(String s, String t) {
// use arrays; t put in array, acsii length;
// acsii 是0-128大小，包含数字、大小写字母、普通字符
int[] need = new int[128];
for (char c : t.toCharArray()) {
need[c]++;
}
int l = 0, r = 0;
int cnt = t.length();
int min = Integer.MAX_VALUE;
int start = 0;
while (r < s.length()) {
// 通过cnt计算是否包含所有t字符；不包含直接执行最后一步右移right指针
char c = s.charAt(r);
if (cnt > 0 && need[c] > 0) {
cnt--;
}
// 无论s中是否包含t字符，right指针右移过程，都在映射中做减一操作，回头left指针右移时，统一做加一操作，不用区分。
// 非t字符的计数，就可能是负数
need[c]--;
if (cnt <= 0) {
// 清空左边 不包含t的字符（left右移）
while (need[s.charAt(l)] < 0) {
need[s.charAt(l)]++;
l++;
}
// 记录最小的长度
if (r-l+1 < min) {
min = r-l+1;
// 记录最小长度和起始位置，用于获取对应字符串
start = l;
}
// left指针接着右移一位（相当于移出一个t中字符）
need[s.charAt(l)]++;
l++;
cnt++;
}
// 继续右移right指针
r++;
}
return min == Integer.MAX_VALUE ? "" : s.substring(start, start+min);
}
}
# 263. Ugly Number（丑数）
class Solution {
public boolean isUgly(int n) {
if (n <= 0) {
return false;
}
while (n % 5 == 0) {
n = n / 5;
}
while (n % 3 == 0) {
n = n / 3;
}
while (n % 2 == 0) {
n = n / 2;
}
return n == 1;
}
}
代码结构优化：
class Solution {
public boolean isUgly(int n) {
if (n <= 0) {
return false;
}
int[] ugly = new int[]{5,3,2};
for (int u : ugly) {
while (n % u == 0) {
n /= u;
}
}
return n == 1;
}
}
# 238. Product of Array Except Self（除自身以外数组的乘积）
// 不符合题意的使用除法实现，注意判断除数为0的场景/by zero
class Solution {
public int[] productExceptSelf(int[] nums) {
int mul = 1;
int zero = 0;
for (int n : nums) {
if (n == 0) {
zero++;
continue;
}
mul *= n;
}
int[] res = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
if (zero == 1) {
if (nums[i] != 0) {
res[i] = 0;
} else {
res[i] = mul;
}
continue;
} else if (zero > 1) {
res[i] = 0;
continue;
}else {
res[i] = mul/nums[i];
}
}
return res;
}
}
解法一：
// 生成左右乘积
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] left = new int[n];
int[] right = new int[n];
// 两遍循环生成left、right记录当前数的左右两边数的乘积
left[0] = 1;
for (int i = 1; i < n; i++) {
left[i] = left[i-1] * nums[i-1];
}
right[n-1] = 1;
for (int i = n-2; i >= 0; i--) {
right[i] = right[i+1] * nums[i+1];
}
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = left[i] * right[i];
}
return res;
}
}
# 454. 四数相加 II（4Sum II）
class Solution {
public int fourSumCount(int[] a, int[] b, int[] c, int[] d) {
Map<Integer, Integer> map = new HashMap<>();
// 将a,b和c,d分为两组，有a+b = -(c+d);
// 先遍历a+b存入字典，val为值存在的次数
for (int i = 0; i < a.length; i++) {
int ta = a[i];
for (int j = 0; j < b.length; j++) {
Integer tmp = map.get(ta + b[j]);
if (tmp != null) {
tmp++;
} else {
tmp = 1;
}
map.put(ta+b[j], tmp);
}
}
int cnt = 0;
// 遍历c,d如果等于-(a+b)则计数
for (int i = 0; i < c.length; i++) {
int tc = c[i];
for (int j = 0; j < d.length; j++) {
Integer tmp = map.get(-(tc + d[j]));
if (tmp != null) {
cnt += tmp;
}
}
}
return cnt;
}
}
# 227. Basic Calculator II（基本计算器 II）
class Solution {
// * 42 / 47
// + 43 - 45
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
char pre = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 校验空格
while (i+1<s.length() && c == ' ') {
i++;
c = s.charAt(i);
continue;
}
// 取完整数字
String num = "";
while (c > 47 && c < 58) {
num = num + c;
// System.out.println("num:"+num);
if (i+1<s.length()) {
i++;
c = s.charAt(i);
} else {
break;
}
}
if (num != "") {
// 是否存在pre符号
if (pre != 0) {
if (pre == 42) {
int tmp = Integer.valueOf(num) * stack.pop();
// System.out.println("num:"+num+"tmp:"+tmp);
stack.push(tmp);
} else if (pre == 47) {
// System.out.println("peek:"+stack.peek());
int tmp = stack.pop() / Integer.valueOf(num);
// System.out.println("num:"+num+"tmp:"+tmp);
stack.push(tmp);
} else if (pre == 45) {
// 是否是减号
// System.out.println("peek:"+stack.peek());
stack.push(Integer.valueOf(num) * -1);
}
pre = 0;
} else {
stack.push(Integer.valueOf(num));
}
}
// 是否是乘除
while (i+1<s.length() && c == ' ') {
i++;
c = s.charAt(i);
continue;
}
if (c == 42 || c == 47 || c == 45) {
pre = c;
}
}
int res = 0;
if (!stack.empty()) {
res = stack.pop();
}
while (!stack.empty()) {
// System.out.println("res:"+res);
res += stack.pop();
}
return res;
}
}
# 264. 丑数 II
// 优先级队列（最小堆）
// 丑数除了1，其余都是2x,3x,5x，放入最小堆中，每次取出最小结果，再将结果存入到最小堆中（去重存入）
// 遍历第n次即，第n个丑数
// 注意int溢出
class Solution {
public int nthUglyNumber(int n) {
PriorityQueue<Long> q = new PriorityQueue<>();
Set<Long> set = new HashSet<>();
q.offer(1L);
long res = 0L;
int[] factory = new int[]{2,3,5};
for (int i = 0; i < n; i++) {
res = q.poll();
for (int f : factory) {
long t = res*f;
if (!set.contains(t)) {
q.offer(t);
set.add(t);
}
}
}
return (int)res;
}
}
// 动态规划
// p2,p3,p5
// dp[i] = min(dp[p2]*2, dp[p3]*3, dp[p5]*5)
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n+1];
int p2 = 1, p3 = 1, p5 = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
// System.out.println("p2:"+dp[p2]+"p3:"+dp[p3]+"p5:"+dp[p5]);
int t2 = dp[p2]*2, t3 = dp[p3]*3, t5 = dp[p5]*5;
dp[i] = Math.min(Math.min(t2, t3), t5);
if (dp[i] == t2) {
p2++;
}
if (dp[i] == t3) {
p3++;
}
if (dp[i] == t5) {
p5++;
}
}
return dp[n];
}
}
重刷
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int two = 0, three = 0, five = 0;
for (int i = 1; i < n; i++) {
int a = dp[two]*2;
int b = dp[three]*3;
int c = dp[five]*5;
int min = Math.min(a, Math.min(b, c));
if (min == a) two++;
if (min == b) three++;
if (min == c) five++;
dp[i] = min;
}
return dp[n-1];
}
}
# 23. Merge k Sorted Lists（合并K个升序链表）
// 最小堆
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});
int n = lists.length;
if (n < 1) {
return null;
}
for (ListNode node : lists) {
if (node == null) continue;
q.offer(node);
}
ListNode head = new ListNode(0);
ListNode curr = head;
while (!q.isEmpty()) {
ListNode tmp = q.poll();
curr.next = tmp;
curr = curr.next;
if (tmp.next != null) {
q.offer(tmp.next);
}
}
return head.next;
}
}
# 138. 复制带随机指针的链表
// 做映射
class Solution {
public Node copyRandomList(Node head) {
Map<Node, Node> map = new HashMap<>();
Node sentry = new Node(0);
Node curr = sentry;
while (head != null) {
// 从字典中取出对应的拷贝node，如果不存在，new一个；
// 存在是由于random指针指向了一个字典中不存在的节点，需要new一个。
Node copier = map.get(head);
if (copier == null) {
copier = new Node(head.val);
map.put(head, copier);
}
// curr指针的next指向拷贝node，将拷贝node连接起来。
curr.next = copier;
curr = curr.next;
// 处理random指针
Node rd = head.random;
if (rd != null) {
Node nrd = map.get(rd);
if (nrd == null) {
nrd = new Node(rd.val);
map.put(rd, nrd);
}
copier.random = nrd;
}
head = head.next;
}
return sentry.next;
}
}
重刷，写得更简洁了
class Solution {
public Node copyRandomList(Node head) {
Map<Node, Node> map = new HashMap<>();
Node sentinel = new Node(0);
Node nh = sentinel;
while (head != null) {
nh.next = map.getOrDefault(head, new Node(head.val));
map.put(head, nh.next);
if (head.random != null) {
Node nr = map.getOrDefault(head.random, new Node(head.random.val));
nh.next.random = nr;
map.put(head.random, nr);
}
nh = nh.next;
head = head.next;
}
return sentinel.next;
}
}
# 752. 打开转盘锁
// 单向bfs
// 从0000开始，终点为target，障碍物为deadends，求最短距离。
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> deadend = new HashSet<>();
for (String s : deadends) {
deadend.add(s);
}
return bfs(deadend, target);
}
private int bfs(Set<String> deadend, String target) {
Queue<String> q = new LinkedList<>();
Set<String> visited = new HashSet<>();
visited.addAll(deadend);
q.offer("0000");
visited.add("0000");
int step = 0;
while (!q.isEmpty()) {
int n = q.size();
for (int i = 0; i < n; i++) {
String cur = q.poll();
// System.out.println("cur:"+cur);
if (deadend.contains(cur)) {
continue;
}
if (target.equals(cur)) {
return step;
}
// +1 -1
for (int j = 0; j < 4; j++) {
String plusOne = plus(cur, j);
if (!visited.contains(plusOne)) {
q.offer(plusOne);
visited.add(plusOne);
}
String minusOne = minus(cur, j);
if (!visited.contains(minusOne)) {
q.offer(minusOne);
visited.add(minusOne);
}
}
}
step++;
}
return -1;
}
private String plus(String s, int i) {
char[] ch = s.toCharArray();
if (ch[i] == '9')
ch[i] = '0';
else
ch[i] += 1;
return new String(ch);
}
private String minus(String s, int i) {
char[] ch = s.toCharArray();
if (ch[i] == '0')
ch[i] = '9';
else
ch[i] -= 1;
return new String(ch);
}
}
// 双向bfs
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> deadend = new HashSet<>();
for (String s : deadends) {
deadend.add(s);
}
return bfs(deadend, target);
}
private int bfs(Set<String> deadend, String target) {
Set<String> q1 = new HashSet<>();
Set<String> q2 = new HashSet<>();
Set<String> visited = new HashSet<>();
visited.addAll(deadend);
q1.add("0000");
q2.add(target);
int step = 0;
while (!q1.isEmpty() && !q2.isEmpty()) {
if (q1.size() > q2.size()) {
// 交换 q1 和 q2
Set<String> temp = q1;
q1 = q2;
q2 = temp;
}
Set<String> temp = new HashSet<>();
for (String cur : q1) {
if (deadend.contains(cur)) {
continue;
}
if (q2.contains(cur)) {
return step;
}
visited.add(cur);
// +1 -1
for (int j = 0; j < 4; j++) {
String plusOne = plus(cur, j);
if (!visited.contains(plusOne)) {
temp.add(plusOne);
}
String minusOne = minus(cur, j);
if (!visited.contains(minusOne)) {
temp.add(minusOne);
}
}
}
step++;
q1 = q2;
q2 = temp;
}
return -1;
}
private String plus(String s, int i) {
char[] ch = s.toCharArray();
if (ch[i] == '9')
ch[i] = '0';
else
ch[i] += 1;
return new String(ch);
}
private String minus(String s, int i) {
char[] ch = s.toCharArray();
if (ch[i] == '0')
ch[i] = '9';
else
ch[i] -= 1;
return new String(ch);
}
}
两个多月后再次做，朴素做法，但是代码并不是最优的，同时也没有想到双向bfs的方法：
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> dd = new HashSet<>();
for (String d : deadends) {
dd.add(d);
}
String start = "0000";
if (dd.contains(start)) return -1;
return bfs(start, target, dd);
}
private int bfs(String start, String target, Set<String> dd) {
Queue<String> q = new LinkedList<>();
Set<String> visited = new HashSet<>();
q.offer(start);
visited.add(start);
int cnt = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String cur = q.poll();
if (cur.equals(target)) return cnt;
for (int j = 0; j < 4; j++) {
String s1 = process(cur, j, true);
if (!visited.contains(s1) && !dd.contains(s1)) {
q.offer(s1);
visited.add(s1);
}
String s2 = process(cur, j, false);
if (!visited.contains(s2) && !dd.contains(s2)) {
q.offer(s2);
visited.add(s2);
}
}
}
cnt++;
}
return -1;
}
private String process(String s, int index, boolean add) {
char c = s.charAt(index);
char[] cs = s.toCharArray();
if (add) {
if (cs[index] == 57) {
cs[index] = '0';
} else {
cs[index]++;
}
} else {
if (cs[index] == 48) {
cs[index] = '9';
} else {
cs[index]--;
}
}
return new String(cs);
}
}
# 127. Word Ladder（单词接龙）
// bfs
// 找下一个词，从一个词可以得到n（n为词长度）个缺失位词
// 判断在Set中是否存在此缺失位的词，找到存在的放入队列中
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
// endWord不在list中直接返回0
Set<String> words = new HashSet<>();
for (String w : wordList) {
words.add(w);
}
if (!words.contains(endWord)) {
return 0;
}
return bfs(words, beginWord, endWord);
}
public int bfs(Set<String> words, String start, String target) {
Queue<String> q = new LinkedList<>();
Set<String> visited = new HashSet<>();
q.offer(start);
visited.add(start);
int step = 1;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
String cur = q.poll();
// System.out.println("cur:"+cur);
if (target.equals(cur)) {
return step;
}
// 循环单词的每个字符
for (int j = 0; j < cur.length(); j++) {
// 遍历26个字母
for (int k = 97; k <= 122; k++) {
String newWord = cur.substring(0, j) + String.valueOf((char)k) + cur.substring(j+1);
if (words.contains(newWord) && !visited.contains(newWord)) {
// System.out.println("contains:"+newWord);
q.offer(newWord);
visited.add(newWord);
}
}
}
}
step++;
}
return 0;
}
}
# 130. Surrounded Regions（被围绕的区域）
// bfs
class Solution {
public void solve(char[][] board) {
bfs(board);
}
private int[][] directions = new int[][]{{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
public void bfs(char[][] board) {
Queue<int[]> q = new LinkedList<>();
int rows = board.length;
int cols = board[0].length;
// 放入边界节点
// 加入列的边界'0'节点
for (int i = 0; i < rows; i++) {
if (board[i][0] == 'O') {
q.offer(new int[]{i, 0});
}
if (board[i][cols-1] == 'O') {
q.offer(new int[]{i, cols-1});
}
}
// 加入行的边界'0'节点
for (int i = 0; i < cols; i++) {
if (board[0][i] == 'O') {
q.offer(new int[]{0, i});
}
if (board[rows-1][i] == 'O') {
q.offer(new int[]{rows-1, i});
}
}
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
int[] cur = q.poll();
int y = cur[0];
int x = cur[1];
board[y][x] = '#';
for (int[] d : directions) {
int newY = y + d[0];
int newX = x + d[1];
if (inArea(newX, newY, rows, cols) && board[newY][newX] == 'O') {
q.offer(new int[]{newY, newX});
}
}
}
}
// 恢复
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == '#') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
private boolean inArea(int x, int y, int rows, int cols) {
return x >= 0 && x < cols && y >= 0 && y < rows;
}
}
# 179. Largest Number（最大数）
class Solution {
public String largestNumber(int[] nums) {
List<String> list = new ArrayList<>();
for (int n : nums) {
list.add(String.valueOf(n));
}
Collections.sort(list, new MyCompare());
StringBuilder sb = new StringBuilder();
for (String s : list) {
sb.append(s);
}
// 处理前置0，保留一位
int len = sb.length();
int k = 0;
while (k < len-1 && sb.charAt(k) == '0') k++;
return sb.substring(k);
}
class MyCompare implements Comparator<String> {
public int compare(String s1, String s2) {
String r1 = s1+s2;
String r2 = s2+s1;
return r2.compareTo(r1);
}
}
}
# 783. Minimum Distance Between BST Nodes（二叉搜索树节点最小距离）
// 中序遍历，校验前后两个节点的差值，记录最小值
class Solution {
int min = Integer.MAX_VALUE;
int pre = Integer.MAX_VALUE;
public int minDiffInBST(TreeNode root) {
recursive(root);
return min;
}
private void recursive(TreeNode n) {
if (n == null) return;
recursive(n.left);
min = Math.min(min, Math.abs(pre - n.val));
pre = n.val;
recursive(n.right);
}
}
# 530. Minimum Absolute Difference in BST（二叉搜索树的最小绝对差）
class Solution {
int min = Integer.MAX_VALUE;
int pre = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
recursive(root);
return min;
}
private void recursive(TreeNode n) {
if (n == null) return;
recursive(n.left);
min = Math.min(min, Math.abs(pre - n.val));
pre = n.val;
recursive(n.right);
}
}
# 236. Lowest Common Ancestor of a Binary Tree（二叉树的最近公共祖先）
// f(l) = true 表示其子节点存在等于p或者q的
// f(left) && f(right)
// (cur==p || cur==q) && (f(left) || f(right))
class Solution {
TreeNode father = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
f(root, p, q);
return father;
}
private boolean f(TreeNode n, TreeNode p, TreeNode q) {
if (father != null) return false;
if (n == null) return false;
boolean l = f(n.left, p, q);
boolean r = f(n.right, p, q);
if ((l && r) || ((n.val == p.val || n.val == q.val) && (l || r))) {
father = n;
}
if (father == null && (n.val == p.val || n.val == q.val)) {
// System.out.println("p:"+p.val+"q:"+q.val+"n:"+n.val);
return true;
}
if (father == null && (l || r)) {
// System.out.println("l:"+l+"r:"+r);
return true;
}
return false;
}
}
# 315. Count of Smaller Numbers After Self（计算右侧小于当前元素的个数）
// 时间：O(n^2)，会超时
class Solution {
public List<Integer> countSmaller(int[] nums) {
int n = nums.length;
Integer[] res = new Integer[n];
int[] sort = new int[n];
// Arrays.fill(sort, Integer.MAX_VALUE);
// 倒序循环
// 从数组的最后开始选一个数，插入排序到sort数组中
// 每次排序的下标即为结果，存入到res中
sort[0] = nums[n-1];
res[n-1] = 0;
for (int i = n-2; i >= 0; i--) {
int val = nums[i];
int j = n-2-i;
// System.out.println("j:"+j+";val:"+val);
// System.out.println("sort:"+Arrays.toString(sort));
// System.out.println("res:"+Arrays.toString(res));
for (; j >= 0; j--) {
// 此处需要大于等于，因为相同的数，不计入结果中，所以要将相同数放入到最小的位置
if (sort[j] >= val) {
sort[j+1] = sort[j];
} else {
break;
}
}
sort[j+1] = val;
res[i] = j+1;
}
return Arrays.asList(res);
}
}
- 归并排序计算逆序对
class Solution {
private int[] cnt;
private int[] indexes;
public List<Integer> countSmaller(int[] nums) {
int n = nums.length;
cnt = new int[n];
indexes = new int[n];
for (int i = 0; i < n; i++) {
indexes[i] = i;
}
int[] temp = new int[n];
sort(nums, 0, n-1, temp);
List<Integer> res = new ArrayList<>(n);
for (int i = 0; i < cnt.length; i++) {
res.add(i, cnt[i]);
}
return res;
}
private void sort(int[] nums, int left, int right, int[] temp) {
if (left < right) {
int mid = left + (right - left) / 2;
sort(nums, left, mid, temp);// 左边归并排序，使得左子序列有序
sort(nums, mid+1, right, temp);// 右边归并排序，使得右子序列有序
merge(nums, left, mid, right, temp);// 将两个有序子数组合并操作
}
}
private void merge(int[] nums, int left, int mid, int right, int[] temp) {
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = left;//临时数组指针
// mid是左序列的最大边界，right是右序列的最大边界
while (i <= mid && j <= right) {
if (nums[indexes[i]] <= nums[indexes[j]]) {
temp[t++] = indexes[j++];
} else {
cnt[indexes[i]] += right - j + 1;
temp[t++] = indexes[i++];
// left > right时，right将被赋值到结果集中，同时代表left和left之后的所有元素都大于right
// 因此，right的位置也移动了
}
}
// 将左边剩余元素填充进temp中
while (i <= mid) {
temp[t++] = indexes[i++];
}
// 将右序列剩余元素填充进temp中
while (j <= right) {
temp[t++] = indexes[j++];
}
t = left;
// 将temp中的元素全部拷贝到原数组中
while (t <= right) {
indexes[t] = temp[t];
t++;
}
}
}
# 剑指 Offer 51. 数组中的逆序对
class Solution {
private int cnt = 0;
public int reversePairs(int[] nums) {
int n = nums.length;
int[] temp = new int[n];
sort(nums, 0, n-1, temp);
// System.out.println("nums:"+Arrays.toString(nums));
return cnt;
}
private void sort(int[] nums, int left, int right, int[] temp) {
if (left < right) {
int mid = left + (right - left) / 2;
sort(nums, left, mid, temp);// 左边归并排序，使得左子序列有序
sort(nums, mid+1, right, temp);// 右边归并排序，使得右子序列有序
merge(nums, left, mid, right, temp);// 将两个有序子数组合并操作
}
}
private void merge(int[] nums, int left, int mid, int right, int[] temp) {
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
// mid是左序列的最大边界，right是右序列的最大边界
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[t++] = nums[i++];
} else {
cnt += mid-i+1;
temp[t++] = nums[j++];
}
}
// 将左边剩余元素填充进temp中
while (i <= mid) {
temp[t++] = nums[i++];
}
// 将右序列剩余元素填充进temp中
while (j <= right) {
temp[t++] = nums[j++];
}
t = 0;
// 将temp中的元素全部拷贝到原数组中
while (left <= right) {
nums[left++] = temp[t++];
}
}
}
同上面一样使用归并排序解题，但写法不一样
class Solution {
int cnt = 0;
public int reversePairs(int[] nums) {
if (nums.length == 0) return 0;
int[] sorted = mergeSort(nums);
return cnt;
}
private int[] mergeSort(int[] nums) {
int n = nums.length;
if (n == 1) {
return nums;
}
int mid = n / 2;
int[] left = Arrays.copyOfRange(nums, 0, mid);
int[] right = Arrays.copyOfRange(nums, mid, n);
left = mergeSort(left);
right = mergeSort(right);
int[] merged = merge(left, right);
return merged;
}
private int[] merge(int[] left, int[] right) {
if (left == null) left = new int[0];
if (right == null) right = new int[0];
int[] ans = new int[left.length+right.length];
int a = 0, b = 0, i = 0;
while (a < left.length && b < right.length) {
if (left[a] <= right[b]) {
ans[i] = left[a];
a++;
} else {
// 关键步骤
cnt += (left.length-a);
ans[i] = right[b];
b++;
}
i++;
}
if (a < left.length) {
for (int k = a; k < left.length; k++) {
ans[i++] = left[k];
}
} else {
for (int k = b; k < right.length; k++) {
ans[i++] = right[k];
}
}
return ans;
}
}
# 213. 打家劫舍 II
在198题（打家劫舍）中，与此题唯一不同的是，此题的前后房屋是相连的，因此在选第一个节点时，就无法选最后一个节点。如果只有三个节点，只能选一个节点。
思路：既然选第一个就无法选最后一个，选最后一个就无法选第一个，就出现两种场景：
- 从前开始递推，再用原有递推方程，推到倒数第二个（去掉倒数第一个）
- 从后开始递推，推到倒数第二个（去掉第一个） 两个结果比较最大值，即答案。
迭代：
class Solution {
public int rob(int[] nums) {
// 边界场景
int n = nums.length;
if (n < 1) {
return 0;
} else if (n < 2) {
return nums[0];
} else if (n < 3) {
return Math.max(nums[0], nums[1]);
} else if (n < 4) {
return Math.max(Math.max(nums[0], nums[1]), nums[2]);
}
// 初始化
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
// 迭代
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
}
int front = dp[n-2];
// 倒序迭代
dp[n-1] = nums[n-1];
dp[n-2] = Math.max(nums[n-1], nums[n-2]);
for (int i = n-3; i >= 0; i--) {
dp[i] = Math.max(dp[i+1], dp[i+2]+nums[i]);
}
int back = dp[1];
return Math.max(front, back);
}
}
重刷的时候，代码简洁了不少
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
int a0 = 0, b0 = 0;
int a1 = 0, b1 = 0;
for (int i = 0; i < n; i++) {
if (i < n-1) {
int c = Math.max(b0, a0+nums[i]);
a0 = b0;
b0 = c;
}
if (i > 0) {
int c = Math.max(b1, a1+nums[i]);
a1 = b1;
b1 = c;
}
}
return Math.max(b0, b1);
}
}
# 152. 乘积最大子数组
// 如果存在偶数个负号，则最大乘积就是所有数的和；如果是奇数个负号，最大乘积就是排除掉一个负号数后的最大乘积。结论仍然无法支撑递推。
// 换种思路，按照常规递推整数数组方式，，dp[i]代表以i为子数组终点的最大乘积，此时存在两种场景：
// 1.若i为正数，要保证乘积最大，则i-1必须也为最大。
// 2.若i为负数，要保证最大乘积，则i-1必须最小。
// 因此需要定义两个缓存值：i-1乘积的最大值和最小值
// 动归方程：定义两个状态数组max，min；第一个nums[i]为正数，第二个为负数
// max[i] = MAX{max[i-1]*nums[i], min[i-1]*nums[i], nums[i]}
// min[i] = MIN{min[i-1]*nums[i], max[i-1]*nums[i], nums[i]}
// 实时刷新最大的max
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
int res = 0;
int[] max = new int[n];
int[] min = new int[n];
max[0] = nums[0];
min[0] = nums[0];
res = nums[0];
for (int i = 1; i < n; i++) {
if (nums[i] > 0) {
max[i] = Math.max(max[i-1]*nums[i], nums[i]);
min[i] = Math.min(min[i-1]*nums[i], nums[i]);
} else if (nums[i] < 0) {
max[i] = Math.max(min[i-1]*nums[i], nums[i]);
min[i] = Math.min(max[i-1]*nums[i], nums[i]);
} else {
min[i] = nums[i];
max[i] = nums[i];
}
res = Math.max(res, max[i]);
}
return res;
}
}
动态规划，空间优化
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
int pmax = nums[0], pmin = nums[0], res = nums[0];
for (int i = 1; i < n; i++) {
int cmax = nums[i]*pmax;
int cmin = nums[i]*pmin;
pmax = Math.max(nums[i], Math.max(cmax, cmin));
pmin = Math.min(nums[i], Math.min(cmax, cmin));
res = Math.max(res, Math.max(pmax, pmin));
}
return res;
}
}
# 309. 最佳买卖股票时机含冷冻期
// 动态规划
// 买入可以记作负收益-p[i]，卖出可以记作正收益+p[i]
class Solution {
public int maxProfit(int[] p) {
int n = p.length;
int[][] dp = new int[n][3];
// init
// dp[i][0] = Max(dp[i-1][0], dp[i-1][2]-p[i]) 代表当前持有股票，因此有可能由两个状态演化来：
// 1.前一天已经持有 2.前一天不持有（此天必须不能是卖出的），i当天买入
dp[0][0] = -p[0];
// dp[i][1] = dp[i-1][0]+p[i] 代表当前不持有股票，当前卖出。因此前一天一定持有。
dp[0][1] = 0;
// dp[i][2] = Max(dp[i][1], dp[i][2]) 代表当前不持有股票，当天无卖出。当前可能为冷冻期。因此可能由两个状态演化来：
// 1.前一天卖出 2.前一天不支持有并且不处于冷冻期
dp[0][2] = 0;
for (int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2]-p[i]);
dp[i][1] = dp[i-1][0] + p[i];
dp[i][2] = Math.max(dp[i-1][1], dp[i-1][2]);
}
return Math.max(dp[n-1][1], dp[n-1][2]);
}
}
动态规划，空间优化
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int p1 = -prices[0], p2 = 0, p3 = 0;
for (int i = 1; i < n; i++) {
int c1 = Math.max(p1, p3-prices[i]);
int c2 = Math.max(p1+prices[i-1], p1+prices[i]);
int c3 = Math.max(p2, p3);
p1 = c1;
p2 = c2;
p3 = c3;
}
return Math.max(p1, Math.max(p2, p3));
}
}
重刷，状态分析不出来，对于动规，或者说对于如何穷尽状态掌握不好
class Solution {
public int maxProfit(int[] prices) {
// p1持有 p2冷冻 p3非冷冻
int p1 = -prices[0], p2 = 0, p3 = 0;
for (int i = 1; i < prices.length; i++) {
int c1 = Math.max(p1, p3-prices[i]);
int c2 = p1+prices[i];
int c3 = Math.max(p3, p2);
p1 = c1;
p2 = c2;
p3 = c3;
}
return Math.max(p2, p3);
}
}
# 1827. 最少操作使数组递增（第 50 场双周赛）
第一题
class Solution {
public int minOperations(int[] nums) {
int n = nums.length;
int cnt = 0;
for (int i = 1; i < n; i++) {
while (nums[i] <= nums[i-1]) {
nums[i]++;
cnt++;
}
}
return cnt;
}
}
# 1828. 统计一个圆中点的数目（第 50 场双周赛）
第二题
class Solution {
public int[] countPoints(int[][] p, int[][] q) {
int[] res = new int[q.length];
for (int i = 0; i < q.length; i++) {
int cnt = 0;
for (int j = 0; j < p.length; j++) {
int x = p[j][0];
int y = p[j][1];
if (Math.sqrt(Math.pow(x-q[i][0], 2) + Math.pow(y-q[i][1], 2)) <= q[i][2]) {
cnt++;
}
}
res[i] = cnt;
}
return res;
}
}
# 1832. 判断句子是否为全字母句（第 237 场周赛）
第一题
class Solution {
public boolean checkIfPangram(String s) {
int[] cnt = new int[26];
for (int i=0; i < s.length(); i++){
cnt[s.charAt(i) - 'a']++;
}
for (int i = 0; i < 26; i++){
if (cnt[i] == 0) {
return false;
}
}
return true;
}
}
# 1833. 雪糕的最大数量（第 237 场周赛）
第二题
class Solution {
public int maxIceCream(int[] c, int n) {
Arrays.sort(c);
int cost = 0;
int cnt = 0;
for (int i = 0; i < c.length; i++) {
cost += c[i];
if (cost <= n) {
cnt++;
} else {
// 存在整型溢出问题，要提前break
break;
}
}
return cnt;
}
}
暴力回溯解，超时
class Solution {
int res = 0;
public int maxIceCream(int[] c, int n) {
// 不需要排序，无论如何都会遍历所有结果
// Arrays.sort(c);
int cost = 0;
int cnt = 0;
recur(cost, c, n, 0, 0);
return res;
}
private void recur(int cost, int[] c, int n, int i, int cnt) {
if (cost > n || i >= c.length) {
if (cost > n) {
cnt--;
}
res = Math.max(res, cnt);
return;
}
recur(cost+c[i], c, n, i+1, cnt+1);
recur(cost, c, n, i+1, cnt);
}
}
排序+贪心，go解法：
import "sort"
func maxIceCream(costs []int, cs int) int {
sort.Ints(costs)
res := 0
for _, c := range costs {
cs -= c
if cs < 0 {
return res
} else {
res++
}
}
return res
}
计数+贪心，go解法：
import "fmt"
func maxIceCream(costs []int, coins int) int {
var m [100001]int
for _, v := range costs {
m[v]++
}
// fmt.Println(m)
cnt := 0
for i, num := range m {
if i == 0 || num == 0 {
continue
}
if coins >= i {
c := min(num, coins/i)
cnt += c
coins -= c*i
} else {
return cnt;
}
// fmt.Println(strconv.Itoa(coins)+","+strconv.Itoa(cnt)+","+strconv.Itoa(i))
}
return cnt
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 220. Contains Duplicate III（存在重复元素 III）
利用滑动窗口和有序集合，存在数字相加或相减，需要避免整型溢出。
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
int n = nums.length;
TreeSet<Long> set = new TreeSet<>();
for (int i = 0; i < n; i++) {
Long ceil = set.ceiling((long)nums[i]-(long)t);
if (ceil != null && ceil <= (long)nums[i]+(long)t) {
return true;
}
set.add((long) nums[i]);
if (i >= k) {
set.remove((long) nums[i-k]);
}
}
return false;
}
}
还有更优的桶分组解法
// todo
# 139. 单词拆分
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n+1];
Map<String, Boolean> map = new HashMap<>();
// init
for (String w : wordDict) {
map.put(w, true);
}
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = i-1; j >= 0; j--) {
dp[i] = dp[j] && map.getOrDefault(s.substring(j, i), false);
if (dp[i]) break;
}
}
return dp[n];
}
}
动态规划：
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>(wordDict);
int n = s.length();
boolean[] dp = new boolean[n];
for (int i = 0; i < n; i++) {
if (set.contains(s.substring(0, i+1))) {
dp[i] = true;
continue;
}
for (int j = i-1; j >= 0; j--) {
if (dp[j] && set.contains(s.substring(j+1, i+1))) {
dp[i] = true;
break;
}
}
}
return dp[n-1];
}
}
重刷
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>(wordDict);
int n = s.length();
boolean[] dp = new boolean[n+1];
dp[0] = true;
for (int j = 1; j <= n; j++) {
for (int i = j; i >= 1; i--) {
if (dp[i-1] && set.contains(s.substring(i-1, j))) {
dp[j] = true;
break;
}
}
}
return dp[n];
}
}
# 51. N-Queens（N 皇后）
回溯剪枝：
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
recursive(n, 0, new ArrayList<>(), -2);
return res;
}
private void recursive(int n, int depth, List<String> board, int curri) {
// 递归深度（列）超过n
if (depth >= n) {
res.add(new ArrayList(board));
return;
}
// 横行遍历
for (int i = 0; i < n; i++) {
// 跳过无法使用的格子
if (!isValid(n, board, depth, i)) {
continue;
}
// 选择i为Q的位置，生成一行的字符串
String row = "";
for (int j = 0; j < n; j++) {
if (j == i) {
row = row + "Q";
} else {
row = row + ".";
}
}
board.add(row);
recursive(n, depth+1, board, i);
// 回退
board.remove(board.size()-1);
}
}
private boolean isValid(int rn, List<String> board, int row, int col) {
// cn col长度，rn row长度
int cn = board.size();
// 检查列是否有皇后互相冲突
for (int i = 0; i < cn; i++) {
if (board.get(i).charAt(col) == 'Q')
return false;
}
// 检查右上方是否有皇后互相冲突
for (int i = row - 1, j = col + 1;
i >= 0 && j < rn; i--, j++) {
if (board.get(i).charAt(j) == 'Q')
return false;
}
// 检查左上方是否有皇后互相冲突
for (int i = row - 1, j = col - 1;
i >= 0 && j >= 0; i--, j--) {
if (board.get(i).charAt(j) == 'Q')
return false;
}
return true;
}
}
# 52. N-Queens II（N皇后 II）
回溯（将N皇后题中保存结果改为计数即可）：
class Solution {
int cnt = 0;
public int totalNQueens(int n) {
recursive(n, 0, new ArrayList<>(), -2);
return cnt;
}
private void recursive(int n, int depth, List<String> board, int curri) {
// 递归深度（列）超过n
if (depth >= n) {
cnt++;
return;
}
// 横行遍历
for (int i = 0; i < n; i++) {
// 跳过无法使用的格子
if (!isValid(n, board, depth, i)) {
continue;
}
// 选择i为Q的位置，生成一行的字符串
String row = "";
for (int j = 0; j < n; j++) {
if (j == i) {
row = row + "Q";
} else {
row = row + ".";
}
}
board.add(row);
recursive(n, depth+1, board, i);
// 回退
board.remove(board.size()-1);
}
}
private boolean isValid(int rn, List<String> board, int row, int col) {
// cn col长度，rn row长度
int cn = board.size();
// 检查列是否有皇后互相冲突
for (int i = 0; i < cn; i++) {
if (board.get(i).charAt(col) == 'Q')
return false;
}
// 检查右上方是否有皇后互相冲突
for (int i = row - 1, j = col + 1;
i >= 0 && j < rn; i--, j++) {
if (board.get(i).charAt(j) == 'Q')
return false;
}
// 检查左上方是否有皇后互相冲突
for (int i = row - 1, j = col - 1;
i >= 0 && j >= 0; i--, j--) {
if (board.get(i).charAt(j) == 'Q')
return false;
}
return true;
}
}
# 27. Remove Element（移除元素）
双指针，将重复的元素交换到不重复位置即可：
class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
int l = 0, r = 0;
while (r < n) {
// l++: l==r; vr!=val;
if (nums[r] != val) {
swap(nums, l, r);
l++;
}
r++;
}
return l;
}
private void swap(int[] n, int a, int b) {
int tmp = n[a];
n[a] = n[b];
n[b] = tmp;
}
}
# 698. Partition to K Equal Sum Subsets（划分为k个相等的子集）
回溯解法，会超时：
class Solution {
boolean res = false;
public boolean canPartitionKSubsets(int[] nums, int k) {
int[] bucket = new int[k];
int[] uu = new int[nums.length];
int sum = 0;
for (int i = 0; i < nums.length; i++) {
uu[i] = nums[nums.length-i-1];
sum += nums[nums.length-i-1];
}
if (sum % k != 0) return false;
int target = sum / k;
return backtrack(uu, bucket, 0, target);
}
private boolean backtrack(int[] nums, int[] bucket, int index, int target) {
// 结束了
if (index >= nums.length) {
// check
for (int n : bucket) {
if (n != target) {
return false;
}
}
return true;
}
// 遍历桶，每次将以数字装入桶中
for (int i = 0; i < bucket.length; i++) {
if (bucket[i] + nums[index] > target) {
continue;
}
bucket[i] += nums[index];
if (backtrack(nums, bucket, index+1, target)) {
return true;
}
// 回退
bucket[i] -= nums[index];
}
return false;
}
}
# 111. Minimum Depth of Binary Tree（二叉树的最小深度）
// 直接套bfs框架
class Solution {
public int minDepth(TreeNode root) {
return bfs(root);
}
public int bfs(TreeNode n) {
if (n == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(n);
int step = 1;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
if (cur.left == null && cur.right == null) {
return step;
}
if (cur.left != null)
q.offer(cur.left);
if (cur.right != null)
q.offer(cur.right);
}
step++;
}
return -1;
}
}
# 773. Sliding Puzzle（滑动谜题）
class Solution {
// 定义二维对应一维下标的映射
int[][] mapping = new int[][]{
new int[]{1, 3},
new int[]{0, 2, 4},
new int[]{1, 5},
new int[]{0, 4},
new int[]{1, 3, 5},
new int[]{2, 4}
};
public int slidingPuzzle(int[][] input) {
// 将board转为一维数组
int[] board = new int[input.length*input[0].length];
String bb = "";
for (int i = 0; i < input.length; i++) {
for (int j = 0; j < input[0].length; j++) {
board[(i*3)+j] = input[i][j];
bb = bb + input[i][j];
}
}
// 定义target
String target = "123450";
return bfs(bb, target);
}
public int bfs(String board, String target) {
Queue<String> q = new LinkedList<>();
Set<String> visited = new HashSet<>();
q.offer(board);
visited.add(board);
int step = 0;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
String cur = q.poll();
// 判断board是否到终点
if (cur.equals(target)) {
return step;
}
// 找到0的位置，从mapping中获取移动的方向，根据下标交换元素
for (int j = 0; j < mapping.length; j++) {
if (cur.charAt(j) == '0') {
for (int m = 0; m < mapping[j].length; m++) {
String tmp = swap(cur, mapping[j][m], j);
if (!visited.contains(tmp)) {
q.offer(tmp);
visited.add(tmp);
}
}
}
}
}
step++;
}
return -1;
}
private String swap(String s, int a, int b) {
StringBuilder res = new StringBuilder(s);
char tmp = res.charAt(a);
return res.replace(a, a+1, String.valueOf(res.charAt(b))).replace(b, b+1, String.valueOf(tmp)).toString();
}
}
时隔两个月后再次做，这次开始写复杂了，没有定义位置映射，但逻辑一致，后来补上了位置映射：
class Solution {
// 定义二维对应一维下标的映射
int[][] mapping = new int[][]{
new int[]{1, 3},
new int[]{0, 2, 4},
new int[]{1, 5},
new int[]{0, 4},
new int[]{1, 3, 5},
new int[]{2, 4}
};
public int slidingPuzzle(int[][] board) {
String origin = "";
int index = -1;
for (int[] b : board) {
for (int n : b) {
origin = origin + n;
if (n == 0) {
index = origin.length()-1;
}
}
}
return bfs(origin, "123450", index);
}
private int bfs(String origin, String target, int index) {
Queue<Node> q = new LinkedList<>();
Set<String> visited = new HashSet<>();
int mod = 3;
int l = 0, r = 5;
int lm = 2, rm = 3;
visited.add(origin);
q.offer(new Node(origin, index));
int cnt = 0;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
String s = cur.s;
int k = cur.index;
// System.out.println("s:"+s+"; k:"+k);
// end
if (s.equals(target)) {
return cnt;
}
// move
for (int j : mapping[k]) {
String tmp = swap(s, k, j);
if (!visited.contains(tmp)) {
q.offer(new Node(tmp, j));
visited.add(tmp);
}
}
}
cnt++;
}
return -1;
}
private String swap(String s, int i, int j) {
char[] cs = s.toCharArray();
char tmp = cs[i];
cs[i] = cs[j];
cs[j] = tmp;
return new String(cs);
}
class Node {
String s;
int index;
public Node(String s, int index) {
this.s = s;
this.index = index;
}
}
}
# 77. Combinations（组合）
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
Set<Integer> visited = new HashSet<>();
backtrack(n, k, new ArrayList<>(), visited, 1);
return res;
}
private void backtrack(int n, int k, List<Integer> record, Set<Integer> visited, int start) {
if (record.size() >= k) {
res.add(new ArrayList(record));
return;
}
for (int i = start; i <= n; i++) {
if (visited.contains(i)) {
continue;
}
record.add(i);
visited.add(i);
backtrack(n, k, record, visited, i+1);
record.remove(record.size()-1);
visited.remove(i);
}
}
}
# 226. Invert Binary Tree（翻转二叉树）
直接递归遍历二叉树：
class Solution {
public TreeNode invertTree(TreeNode root) {
recursive(root);
return root;
}
private void recursive(TreeNode n) {
if (n == null) {
return;
}
recursive(n.left);
recursive(n.right);
// reverse
TreeNode tmp = n.left;
n.left = n.right;
n.right = tmp;
}
}
# 114. Flatten Binary Tree to Linked List（二叉树展开为链表）
递归，利用stack存储right，左右置换。但空间复杂度不符合要求，此解为O(n)。
class Solution {
public void flatten(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
recursive(stack, root);
}
private void recursive(Stack<TreeNode> stack, TreeNode node) {
if (node == null) {
return;
}
if (node.right != null) {
stack.push(node.right);
node.right = null;
}
if (node.left != null) {
node.right = node.left;
node.left = null;
}
if (node.right == null) {
if (!stack.isEmpty()) {
node.right = stack.pop();
}
}
recursive(stack, node.right);
}
}
# 724. Find Pivot Index（寻找数组的中心下标）
class Solution {
public int pivotIndex(int[] nums) {
int n = nums.length;
int[] pre = new int[n+1];
// init
for (int i = 0; i < n; i++) {
pre[i+1] = pre[i] + nums[i];
}
for (int i = 1; i < pre.length; i++) {
if (pre[n]-pre[i] == pre[i-1]) {
return i-1;
}
}
return -1;
}
}
# 523. Continuous Subarray Sum（连续的子数组和）
public class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int n = nums.length;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int sum = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
if (k != 0) {
sum = sum % k;
}
if (map.containsKey(sum)) {
if (i - map.get(sum) > 1) {
return true;
}
} else {
map.put(sum, i);
}
}
return false;
}
}
前缀和+哈希表：
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int n = nums.length;
int[] pre = new int[n+1];
for (int i = 1; i <= n; i++) {
pre[i] = pre[i-1] + nums[i-1];
}
Set<Integer> set = new HashSet<>();
for (int i = 2; i <= n; i++) {
set.add(pre[i-2]%k);
if (set.contains(pre[i]%k)) {
return true;
}
}
return false;
}
}
# 剑指 Offer 42. 连续子数组的最大和
同53题。
// 动归方程：dp[i]表示以nums[i]结尾的数，最大的子数组合。
// if dp[i-1] > 0, dp[i] = dp[i-1]+nums[i]
// if dp[i-1] <= 0, dp[i] = nums[i]
// 由于只依赖前一个最大子数组的合，所以可以进一步压缩空间，只用pre变量保存即可。
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
// init
int pre = nums[0];
int max = nums[0];
for (int i = 1; i < n; i++) {
int tmp;
if (pre > 0) {
tmp = pre + nums[i];
} else {
tmp = nums[i];
}
max = Math.max(max, tmp);
pre = tmp;
}
return max;
}
}
重刷时，代码写得更简洁了
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0, n = nums.length, max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
if (pre >= 0) {
pre += nums[i];
} else {
pre = nums[i];
}
max = Math.max(max, pre);
}
return max;
}
}
# 560. Subarray Sum Equals K（和为K的子数组）
class Solution {
public int subarraySum(int[] nums, int k) {
// presum[0] = 0;
int[] presum = new int[nums.length+1];
for (int i = 1; i < presum.length; i++) {
presum[i] = presum[i-1] + nums[i-1];
}
// System.out.println("presum:"+ Arrays.toString(presum));
int cnt = 0;
HashMap<Integer, Integer> map = new HashMap<>();
// 如果presum[i] - k==0，自然cnt要+1
map.put(0, 1);
for (int i = 1; i < presum.length; i++) {
// System.out.println("presum[i] - k: "+(presum[i] - k));
if (map.containsKey(presum[i] - k)) {
cnt += map.get(presum[i] - k);
}
map.put(presum[i], map.getOrDefault(presum[i], 0) + 1);
}
return cnt;
}
}
优化后（presum不需要使用数组存储）：
class Solution {
public int subarraySum(int[] nums, int k) {
int presum = 0;
int cnt = 0;
HashMap<Integer, Integer> map = new HashMap<>();
// 如果presum-k==0，自然cnt要+1
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
presum += nums[i];
if (map.containsKey(presum - k)) {
cnt += map.get(presum - k);
}
map.put(presum, map.getOrDefault(presum, 0) + 1);
}
return cnt;
}
}
go解法：
func subarraySum(nums []int, k int) int {
n := len(nums)
pre := make([]int, n)
pre[0] = nums[0]
for i := 1; i < n; i++ {
pre[i] = pre[i-1] + nums[i]
}
var m = make(map[int]int)
m[0] = 1
cnt := 0
for i := 0; i < n; i++ {
cnt += m[pre[i]-k]
m[pre[i]]++
}
return cnt
}
# 930. 和相同的二元子数组
class Solution {
public int numSubarraysWithSum(int[] A, int S) {
int[] presum = new int[A.length+1];
for (int i = 1; i < presum.length; i++) {
presum[i] = presum[i-1] + A[i-1];
}
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int cnt = 0;
for (int i = 1; i < presum.length; i++) {
if (map.containsKey(presum[i]-S)) {
cnt += map.get(presum[i]-S);
}
map.put(presum[i], map.getOrDefault(presum[i], 0)+1);
}
return cnt;
}
}
时隔三个月的前缀和写法：
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
int presum = 0;
int cnt = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
presum += nums[i];
cnt += map.getOrDefault(presum-goal, 0);
map.put(presum, map.getOrDefault(presum, 0)+1);
}
return cnt;
}
}
双指针/滑动窗口：
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
int l1 = 0, l2 = 0, r = 0;
int n = nums.length;
int cnt = 0;
int s1 = 0, s2 = 0;
while (r < n) {
s1 += nums[r];
s2 += nums[r];
while (l1 <= r && s1 > goal) {
s1 -= nums[l1];
l1++;
}
while (l2 <= r && s2 >= goal) {
s2 -= nums[l2];
l2++;
}
r++;
cnt += l2 - l1;
}
return cnt;
}
}
# 1248. Count Number of Nice Subarrays（统计「优美子数组」）
前缀和：
class Solution {
public int numberOfSubarrays(int[] nums, int k) {
// pre[i]记录前面有多少个奇数
int[] pre = new int[nums.length+1];
for (int i = 1; i < pre.length; i++) {
if (nums[i-1] % 2 != 0) {
// 奇数
pre[i] = pre[i-1] + 1;
} else {
pre[i] = pre[i-1];
}
}
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int cnt = 0;
for (int i = 1; i < pre.length; i++) {
if (map.containsKey(pre[i]-k)) {
cnt += map.get(pre[i]-k);
}
map.put(pre[i], map.getOrDefault(pre[i], 0)+1);
}
return cnt;
}
}
相同逻辑的go实现：
func numberOfSubarrays(nums []int, k int) (res int) {
n := len(nums)
pre := make([]int, n+1)
for i := 1; i <= n; i++ {
odd := 0
if nums[i-1] % 2 != 0 {
odd = 1
}
pre[i] = pre[i-1] + odd
}
m := map[int]int{0:1}
for _, val := range pre[1:] {
res += m[val-k]
m[val] = m[val] + 1
}
return
}
# 974. Subarray Sums Divisible by K（和可被 K 整除的子数组）
class Solution {
public int subarraysDivByK(int[] A, int k) {
int[] presum = new int[A.length+1];
for (int i = 1; i < presum.length; i++) {
presum[i] = presum[i-1] + A[i-1];
}
int cnt = 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int i = 1; i < presum.length; i++) {
// 取余数，presum[i]%k会存在负数场景，因此通过+k再取余k，得到正数
int remainder = (presum[i] % k + k) % k;
if (map.containsKey(remainder)) {
cnt += map.get(remainder);
}
map.put(remainder, map.getOrDefault(remainder, 0)+1);
}
return cnt;
}
}
# 654. Maximum Binary Tree（最大二叉树）
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return recursive(nums, 0, nums.length-1);
}
private TreeNode recursive(int[] nums, int left, int right) {
if (left > right || left < 0 || right > nums.length-1) {
return null;
}
// find index of max value
int index = -1;
int max = Integer.MIN_VALUE;
for (int i = left; i <= right; i++) {
if (nums[i] > max) {
max = nums[i];
index = i;
}
}
TreeNode root = new TreeNode(nums[index]);
root.left = recursive(nums, left, index-1);
root.right = recursive(nums, index+1, right);
return root;
}
}
# 106. Construct Binary Tree from Inorder and Postorder Traversal（从中序与后序遍历序列构造二叉树）
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return recursive(postorder, 0, postorder.length-1, inorder, 0, inorder.length-1);
}
private TreeNode recursive(int[] post, int pl, int pr, int[] in, int il, int ir) {
if (pl > pr || il > ir || pl < 0 || pr >= post.length || il < 0 || ir >= in.length) {
return null;
}
int root = post[pr];
TreeNode node = new TreeNode(root);
// 在中序遍历数组中找到root节点
int index = -1;
for (int i = il; i <= ir; i++) {
if (in[i] == root) {
index = i;
break;
}
}
int lsize = index - il;
node.left = recursive(post, pl, pl+lsize-1, in, il, index-1);
node.right = recursive(post, pl+lsize, pr-1, in, index+1, ir);
return node;
}
}
# 652. Find Duplicate Subtrees（寻找重复的子树）
// 后序遍历，获取子树的序列化字串，存入到map中，用来判断是否之前已存在重复
class Solution {
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
HashMap<String, Integer> map = new HashMap<>();
List<TreeNode> res = new ArrayList<>();
recursive(root, res, map);
return res;
}
private String recursive(TreeNode node, List<TreeNode> res, HashMap<String, Integer> map) {
if (node == null) {
return "#";
}
String left = recursive(node.left, res, map);
String right = recursive(node.right, res, map);
String serialize = left +","+ right +","+ node.val;
if (map.getOrDefault(serialize, 0) == 1) {
res.add(node);
map.put(serialize, map.get(serialize)+1);
} else {
map.put(serialize, map.getOrDefault(serialize, 0)+1);
}
return serialize;
}
}
# 897. Increasing Order Search Tree（递增顺序搜索树）
中序遍历，将结果记录在linkedList中：
class Solution {
public TreeNode increasingBST(TreeNode root) {
LinkedList<TreeNode> q = new LinkedList<>();
recursive(root, q);
// 清空最后节点的左右分支，防止TreeNode成环。
q.peekLast().left = null;
q.peekLast().right = null;
return q.poll();
}
private TreeNode recursive(TreeNode node, LinkedList<TreeNode> q) {
if (node == null) return null;
recursive(node.left, q);
if (!q.isEmpty()) {
TreeNode cur = q.peekLast();
cur.right = node;
cur.left = null;
}
q.addLast(node);
recursive(node.right, q);
return node;
}
}
# 5740. 所有元音按顺序排布的最长子字符串（第 238 场周赛）
第三题：
class Solution {
public int longestBeautifulSubstring(String word) {
// 记录种类数，种类不到5个，则不记录为·美丽字串长度·
int type = 0;
// 当前字符大于上一个字符，type++
// 当前字符等于上一个字符，right++
// 当前字符小于上一个字符，right++，type清零
// 当type为0时，必须是a开头，
int left = 0, right = 0;
char pre = 'A';
int max = 0;
while (right < word.length()) {
char w = word.charAt(right);
// System.out.println("w:"+w+"; type:"+type);
if (type == 0) {
if (w != 'a') {
left++;
} else {
type++;
}
right++;
} else {
if (w > pre) {
type++;
right++;
} else if (w < pre) {
// System.out.println("max:"+max+"; right :"+(right-1)+"; left:"+left);
if (type == 5) {
max = Math.max(max, (right-1)-left+1);
}
type = 0;
left = right;
// System.out.println("nums[left]:"+word.charAt(left));
} else {
right++;
}
}
pre = w;
}
if (type == 5) {
// System.out.println("max:"+max+"; right :"+(right-1)+"; left:"+left);
max = Math.max(max, (right-1)-left+1);
}
return max;
}
}
# 1838. 最高频元素的频数（第 238 场周赛）
第二题：
class Solution {
public int maxFrequency(int[] nums, int k) {
// 排序
Arrays.sort(nums);
// 先求出前缀和
int[] presum = new int[nums.length+1];
for (int i = 1; i < presum.length; i++) {
presum[i] = nums[i-1] + presum[i-1];
}
// 滑动窗口
// 1.窗口内容和 > 窗口最大值*数量，left++
// 2.小于，right++；left==right，right++
// while condition：right < nums.length
int max = 1;
int left = 1, right = 1;
while (right < presum.length) {
if (left == right) {
right++;
continue;
}
int sum = presum[right]-presum[left-1];
int cnt = right-left+1;
if (nums[right-1]*cnt - sum > k) {
left++;
} else {
right++;
max = Math.max(max, cnt);
}
}
return max;
}
}
排序+滑动窗口：
class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int l = 0;
int max = 1;
long sum = 0;
for (int r = 1; r < n; r++) {
sum += (nums[r]-nums[r-1]) * (r-l);
while (sum > k) {
sum -= (nums[r]-nums[l]);
l++;
}
max = Math.max(max, r-l+1);
}
return max;
}
}
# 1837. K 进制表示下的各位数字总和（第 238 场周赛）
第一题：
class Solution {
public int sumBase(int n, int k) {
int res = 0;
while (n >= k) {
int r = n % k;
n = n / k;
res += r;
}
res += n;
return res;
}
}
# 538. Convert BST to Greater Tree（把二叉搜索树转换为累加树）
同一题：1038. 把二叉搜索树转换为累加树
// 修改二叉树遍历顺序，从右子树-》根节点-》左子树，累加计数，并返回给上层继续累加即可。
class Solution {
public TreeNode convertBST(TreeNode root) {
recursive(root, 0);
return root;
}
private int recursive(TreeNode node, int pre) {
if (node == null) return pre;
// right
pre = recursive(node.right, pre);
// mid
node.val += pre;
pre = node.val;
// left
pre = recursive(node.left, pre);
return pre;
}
}
# 897. 递增顺序搜索树
使用queue实现：
class Solution {
public TreeNode increasingBST(TreeNode root) {
LinkedList<TreeNode> q = new LinkedList<>();
recursive(root, q);
q.peekLast().left = null;
q.peekLast().right = null;
return q.poll();
}
private TreeNode recursive(TreeNode node, LinkedList<TreeNode> q) {
if (node == null) return null;
recursive(node.left, q);
if (!q.isEmpty()) {
TreeNode cur = q.peekLast();
cur.right = node;
cur.left = null;
}
q.addLast(node);
recursive(node.right, q);
return node;
}
}
不借助数据结构，原地实现（最优解）：
class Solution {
TreeNode p;
public TreeNode increasingBST(TreeNode root) {
TreeNode dummy = new TreeNode(-1);
p = dummy;
recursive(root);
return dummy.right;
}
// 中序遍历，递归到第一个节点时，一定是在中间执行中序逻辑。
private void recursive(TreeNode node) {
if (node == null) return;
recursive(node.left);
p.right = node;
node.left = null;
p = p.right;
recursive(node.right);
}
}
# 1011. 在 D 天内送达包裹的能力
class Solution {
public int shipWithinDays(int[] ws, int d) {
int max = 0, sum = 0;
for (int w : ws) {
max = Math.max(max, w);
sum += w;
}
int l = max, r = sum;
while (l < r) {
int mid = l + r >> 1;
if (check(ws, mid, d)) {
r = mid;
} else {
l = mid + 1;
}
}
return r;
}
// 贪心 ws 重量数组 t 运载能力 d 天数
boolean check(int[] ws, int t, int d) {
// wi 重量数组下标
int wi = 0;
for (int i = 0; i < d; i++) {
for (int sum = t; wi < ws.length && sum - ws[wi] >= 0; ) {
sum -= ws[wi++];
}
}
// d 天走完，是否走完ws重量数组
return wi == ws.length;
}
// 宫水三叶题解
boolean check1(int[] ws, int t, int d) {
int n = ws.length;
int cnt = 1;
for (int i = 1, sum = ws[0]; i < n; sum = 0, cnt++) {
while (i < n && sum + ws[i] <= t) {
sum += ws[i];
i++;
}
}
return cnt - 1 <= d;
}
}
# 1373. 二叉搜索子树的最大键值和
class Solution {
private int max = 0;
// 看子树是否为bst;
// 后序遍历记录子树节点最大和以及节点
public int maxSumBST(TreeNode root) {
func(root);
return max;
}
// 返回结果 res[0] 是否为bst子树 res[1] 子树最大值 res[2] 子树最小值 res[3] 子树所有节点和
private int[] func(TreeNode node) {
if (node == null) return new int[]{1, Integer.MIN_VALUE, Integer.MAX_VALUE, 0};
int[] l = func(node.left);
int[] r = func(node.right);
// 如果左右子树皆为bst，根据左右节点大小，判断当前是否为bst
// 当前节点为bst子树，计算总和，与max比较再更新。
// 叶子节点为bst子树，返回true
int[] res = new int[4];
if (node.left == null && node.right == null) {
max = Math.max(max, node.val);
return new int[]{1, node.val, node.val, node.val};
} else if (l[0] == 1 && r[0] == 1 && l[1] < node.val && node.val < r[2]) {
int tmax = l[3]+r[3]+node.val;
max = Math.max(max, tmax);
return new int[]{1, Math.max(r[1], node.val), Math.min(l[2], node.val), tmax};
}
return new int[]{0, 0, 0, 0};
}
}
# 96. 不同的二叉搜索树
class Solution {
int[][] memo;
public int numTrees(int n) {
memo = new int[n+1][n+1];
return count(1, n);
}
private int count(int low, int high) {
if (low > high) return 1;
// 查备忘录
if (memo[low][high] != 0) {
return memo[low][high];
}
int res = 0;
for (int i = low; i <= high; i++) {
int left = count(low, i-1);
int right = count(i+1, high);
res += left * right;
}
// 将结果存入备忘录
memo[low][high] = res;
return res;
}
}
动态规划
class Solution {
public int numTrees(int n) {
int[] dp = new int[n+1];
dp[1] = 1;
dp[0] = 1;
for (int i = 2; i <= n; i++) {
for (int k = 1; k <= i; k++) {
dp[i] += (dp[k-1]*dp[i-k]);
}
}
return dp[n];
}
}
# 95. 不同的二叉搜索树 II
class Solution {
public List<TreeNode> generateTrees(int n) {
if (n == 0) return new LinkedList<>();
return gen(1, n);
}
private List<TreeNode> gen(int low, int high) {
List<TreeNode> res = new LinkedList<>();
if (low > high) {
res.add(null);
return res;
}
for (int mid = low; mid <= high; mid++) {
List<TreeNode> left = gen(low, mid-1);
List<TreeNode> right = gen(mid+1, high);
for (TreeNode l : left) {
for (TreeNode r : right) {
TreeNode root = new TreeNode(mid);
root.left = l;
root.right = r;
res.add(root);
}
}
}
return res;
}
}
# 938. 二叉搜索树的范围和
class Solution {
int sum = -1;
boolean end = false;
public int rangeSumBST(TreeNode root, int low, int high) {
f(root, low, high);
return sum;
}
private void f(TreeNode node, int low, int high) {
if (end || node == null) return;
f(node.left, low, high);
if (sum == -1 && node.val == low) {
sum = node.val;
} else if (sum != -1 && !end) {
sum += node.val;
if (node.val == high) {
end = true;
}
}
f(node.right, low, high);
}
}
# 209. 长度最小的子数组
朴素的nlogn做法，先求前缀和，再以每个数为left或right做二分：
class Solution {
int N = Integer.MAX_VALUE;
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int[] pre = new int[n+1];
for (int i = 1; i <= n; i++) {
pre[i] = pre[i-1] + nums[i-1];
}
int min = N;
for (int i = 1; i <= n; i++) {
min = Math.min(min, binary(pre, i, target));
}
return min == N ? 0 : min;
}
public int binary(int[] pre, int end, int t) {
int l = 0, r = end;
while (l < r) {
int mid = l + ((r-l+1)>>1);
if (pre[end]-pre[mid] >= t) {
l = mid;
} else {
r = mid-1;
}
}
return pre[end]-pre[r] >= t ? end-r : N;
}
}
最优解，滑动窗口：
// 滑动窗口主要关注：
// 1.什么时候移动left：当满足sum>=target时
// 2.什么时候移动right：
// 3.什么时候计算最小长度
class Solution {
int N = Integer.MAX_VALUE;
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int sum = 0, l = 0, r = 0;
int min = N;
while (r < n) {
sum += nums[r++];
while (sum >= target) {
min = Math.min(min, r-l);
sum -= nums[l++];
}
}
return min == N ? 0 : min;
}
}
# 222. 完全二叉树的节点个数
class Solution {
public int countNodes(TreeNode root) {
int hl = 0, hr = 0;
TreeNode l = root, r = root;
while (l != null) {
l = l.left;
hl++;
}
while (r != null) {
r = r.right;
hr++;
}
if (hl == hr) {
return (int)Math.pow(2, hl) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
# 35. 搜索插入位置
// 题意：找到第一个大于等于target的位置
// 搜索左侧边界
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0, r = nums.length;
while (l < r) {
int mid = l + ((r - l) >> 1);
if (nums[mid] == target) {
r = mid;
} else if (nums[mid] > target) {
r = mid;
} else if (nums[mid] < target) {
l = mid+1;
}
}
// 不能返回r，nums中所有数都小于target时，一直走l=mid+1逻辑，r是不变的。
return l;
}
}
func searchInsert(nums []int, target int) int {
n := len(nums)
l, r := 0, n
for l < r {
mid := l + ((r-l)>>1)
if target == nums[mid] {
return mid
} else if target < nums[mid] {
r = mid
} else {
l = mid+1
}
}
return r
}
# 704. 二分查找
class Solution {
public int search(int[] nums, int target) {
// while条件是小于，right可以等于nums.length
int l = 0, r = nums.length;
while (l < r) {
int mid = l + ((r-l) >> 1);
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
r = mid;
} else if (nums[mid] < target) {
l = mid+1;
}
}
return -1;
}
}
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length-1;
while (left < right) {
int mid = left + ((right-left)>>1);
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
// 如果right==target，mid会一直右移，直到等于right，但while是小于，mid计算落点是靠左的，所以会漏掉right，需要最后进行判断。
return nums[right] == target ? right : -1;
}
}
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length-1;
// while条件是小于等于时，right和left的移位不能直接等于mid，否则会出现死循环。
// 并且right起点可以从nums.length-1开始，最终也不会遗漏每一个可能的下标。
while (left <= right) {
int mid = left + ((right-left)>>1);
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid -1;
} else {
left = mid + 1;
}
}
return -1;
}
}
# 718. 最长重复子数组
动态规划：
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int[][] dp = new int[n+1][m+1];
int res = 0;
for (int i = n-1; i >= 0; i--) {
for (int j = m-1; j >= 0; j--) {
dp[i][j] = nums1[i] == nums2[j] ? dp[i+1][j+1] + 1 : 0;
res = Math.max(res, dp[i][j]);
}
}
return res;
}
}
# 633. 平方数之和
brute force:（超时）
class Solution {
public boolean judgeSquareSum(int c) {
if (c == 0) return true;
// 1-c
for (int i = 1; i*i <= c; i++) {
int a = i*i;
int b = c - a;
if (Math.sqrt((double)b) % 1 == 0) {
return true;
}
}
return false;
}
}
二分法：
class Solution {
public boolean judgeSquareSum(int c) {
int a = 0, b = (int) Math.sqrt(c);
while (a <= b) {
int sum = a*a + b*b;
if (sum == c) {
return true;
} else if (sum > c) {
b--;
} else if (sum < c) {
a++;
}
}
return false;
}
}
# 378. 有序矩阵中第 K 小的元素
brute force:
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int[] res = new int[matrix.length*matrix[0].length];
int i = 0;
for (int[] rows : matrix) {
for (int n : rows) {
res[i++] = n;
}
}
Arrays.sort(res);
return res[k-1];
}
}
归并算法： 时间竟然比暴力法还慢，可能是数据量的问题？
class Solution {
public int kthSmallest(int[][] ma, int k) {
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});
// 把每排第一个放入queue，放入对象为三元素数组，包含信息：value、row坐标、colum坐标，以便从queue中取出时求下一个。
for (int i = 0; i < ma.length; i++) {
pq.offer(new int[]{ma[i][0], i, 0});
}
// 初始化时放入了第一个，后序只要放入k-1个，queue中即有k个元素了。
for (int i = 0; i < k-1; i++) {
int[] po = pq.poll();
if (po[2]+1 < ma[0].length) {
pq.offer(new int[]{ma[po[1]][po[2]+1], po[1], po[2]+1});
}
}
return pq.poll()[0];
}
}
# 403. 青蛙过河
动态规划：未优化版本
class Solution {
public boolean canCross(int[] stones) {
int n = stones.length;
boolean[][] dp = new boolean[n][n];
// init
dp[0][0] = true;
for (int i = 1; i < n; i++) {
for (int j = i-1; j >= 0; j--) {
int k = stones[i] - stones[j];
// why?
if (k > j+1) {
break;
}
dp[i][k] = dp[j][k] || dp[j][k-1] || dp[j][k+1];
}
}
for (boolean b : dp[n-1]) {
if (b) return true;
}
return false;
}
}
# 137. 只出现一次的数字 II
class Solution {
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int n : nums) {
Integer t = map.get(n);
if (t == null) t = 0;
map.put(n, t+1);
}
int res = -1;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue()!=3) {
res = entry.getKey();
break;
}
}
return res;
}
}
# 690. 员工的重要性
// bfs
class Solution {
public int getImportance(List<Employee> employees, int id) {
// list找到对应的id，存入queue中，之后循环即可，题目没有环出现的可能
int res = 0;
Queue<Integer> q = new LinkedList<>();
q.offer(id);
while (!q.isEmpty()) {
int up = q.poll();
for (Employee emp : employees) {
if (emp.id == up) {
res += emp.importance;
for (int sub : emp.subordinates) {
q.offer(sub);
}
break;
}
}
}
return res;
}
}
使用hash做提前优化： 代码可以继续优化，map可以直接用Employee做value，由于是存储的引用，并不会多占用过多内存，时间上更优（复杂度上没区别）。
class Solution {
public int getImportance(List<Employee> emps, int id) {
Map<Integer, Employee> map = new HashMap<>();
int res = 0;
Queue<Integer> q = new LinkedList<>();
q.offer(id);
for (Employee emp : emps) {
map.put(emp.id, emp);
}
while (!q.isEmpty()) {
int up = q.poll();
Employee emp = map.get(up);
res += emp.importance;
for (int sub : emp.subordinates) {
q.offer(sub);
}
}
return res;
}
}
使用dfs效率更佳：
class Solution {
public int getImportance(List<Employee> emps, int id) {
Map<Integer, Employee> map = new HashMap<>();
for (Employee emp : emps) {
map.put(emp.id, emp);
}
return dfs(map, id);
}
private int dfs(Map<Integer, Employee> map, int id) {
Employee emp = map.get(id);
int res = emp.importance;
for (int sub : emp.subordinates) {
res += dfs(map, sub);
}
return res;
}
}
# 剑指 Offer 13. 机器人的运动范围
dfs，向右边和下边搜索，利用二维数组去重
class Solution {
int cnt = 0;
int y;
int x;
boolean[][] valid;
public int movingCount(int m, int n, int k) {
y = m;
x = n;
valid = new boolean[m][n];
dfs(0, 0, k);
return cnt;
}
private void dfs(int m, int n, int k) {
// check 边界\去重、必须小于等于k
if (m < 0 || n < 0 || m >= y || n >= x) {
return;
}
if (invalid(m, n, k)) {
return;
}
if (valid[m][n]) {
return;
}
cnt++;
valid[m][n] = true;
// 右、下
dfs(m, n+1, k);
dfs(m+1, n, k);
}
private boolean invalid(int m, int n, int k) {
int sum = 0;
while (m != 0) {
sum += m % 10;
m = m / 10;
}
while (n != 0) {
sum += n % 10;
n = n / 10;
}
return sum > k;
}
}
# 554. 砖墙
前缀和：
class Solution {
public int leastBricks(List<List<Integer>> wall) {
// <sum, cnt>
HashMap<Integer, Integer> map = new HashMap<>();
int max = 0;
for (List<Integer> w : wall) {
int sum = 0;
// 不要加入最后一个元素计算前缀和，因为边界通路不计算在内
for (int i = 0; i < w.size()-1; i++) {
sum += w.get(i);
int cnt = map.getOrDefault(sum, 0)+1;
map.put(sum, cnt);
// System.out.println("sum:"+sum+"; cnt:"+cnt);
max = Math.max(max, cnt);
}
}
return wall.size() - max;
}
}
# 1847. 最近的房间（第 51 场双周赛）
周赛第四题 treeMap解，但时间复杂度接近暴力，无法通过：
class Solution {
public int[] closestRoom(int[][] rooms, int[][] q) {
TreeMap<Integer, List<int[]>> map = new TreeMap<Integer, List<int[]>>(
new Comparator<Integer>() {
public int compare(Integer obj1, Integer obj2) {
return obj1.compareTo(obj2);
}
}
);
for (int[] r : rooms) {
List<int[]> list = map.get(r[1]);
if (list == null) {
list = new ArrayList<>();
}
list.add(r);
map.put(r[1], list);
}
int[] res = new int[q.length];
for (int i = 0; i < q.length; i++) {
Map<Integer, List<int[]>> smap = map.tailMap(q[i][1]);
int min = Integer.MAX_VALUE;
int index = Integer.MAX_VALUE;
for (Map.Entry<Integer, List<int[]>> entry : smap.entrySet()) {
Integer k = entry.getKey();
List<int[]> vs = entry.getValue();
for (int[] v : vs) {
if (Math.abs(q[i][0]-v[0]) < min) {
index = v[0];
min = Math.abs(q[i][0]-v[0]);
} else if (Math.abs(q[i][0]-v[0]) == min) {
index = Math.min(index, v[0]);
min = Math.abs(q[i][0]-v[0]);
}
}
}
res[i] = index == Integer.MAX_VALUE ? -1 : index;
}
return res;
}
}
其他大佬的解答：
class Solution {
public int[] closestRoom(int[][] rooms, int[][] queries) {
Integer[] index = new Integer[queries.length];
for (int i = 0; i < index.length; i++) {
index[i] = i;
}
// rooms 按照size从大到小排序
Arrays.sort(rooms, (a, b) -> b[1] - a[1]);
// 按照queries size从大到小排序
Arrays.sort(index, (a, b) -> queries[b][1] - queries[a][1]);
TreeSet<Integer> set = new TreeSet<>();
int[] result = new int[queries.length];
for (int i = 0, j = 0; i < index.length; i++) {
// 所有size大于query的roomId放入treeSet中
while (j < rooms.length && rooms[j][1] >= queries[index[i]][1]) {
set.add(rooms[j++][0]);
}
// 找到queries[i] 对应的最近的小值和大值
Integer floor = set.floor(queries[index[i]][0]), ceiling = set.ceiling(queries[index[i]][0]);
// 没有则-1
if (floor == null && ceiling == null) {
result[index[i]] = -1;
} else {
// 绝对值判断大小
if (queries[index[i]][0] - (floor == null ? -999999999 : floor)
<= (ceiling == null ? 999999999 : ceiling) - queries[index[i]][0]) {
result[index[i]] = floor;
} else {
result[index[i]] = ceiling;
}
}
}
return result;
}
}
# 1846. 减小和重新排列数组后的最大元素（第 51 场双周赛）
周赛第三题
class Solution {
public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
Arrays.sort(arr);
if (arr[0] != 1) {
arr[0] = 1;
}
int max = 0;
for (int i = 1; i < arr.length; i++) {
int temp = Math.abs(arr[i]-arr[i-1]);
if (temp > 1) {
arr[i] = arr[i] - temp + 1;
}
}
return arr[arr.length-1];
}
}
每日一题时再做，写法清晰很多了：
class Solution {
public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
Arrays.sort(arr);
int val = 1;
for (int i = 1; i < arr.length; i++) {
if (arr[i] > val) {
val++;
}
}
return val;
}
}
# 1845. 座位预约管理系统（第 51 场双周赛）
周赛第二题
class SeatManager {
PriorityQueue<Integer> pq;
public SeatManager(int n) {
pq = new PriorityQueue<>(new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
return a-b;
}
});
for (int i = 1; i <= n; i++) {
pq.offer(i);
}
}
public int reserve() {
return pq.poll();
}
public void unreserve(int s) {
pq.offer(s);
}
}
# 1844. 将所有数字用字符替换（第 51 场双周赛）
周赛第一题
class Solution {
public String replaceDigits(String s) {
char[] cs = s.toCharArray();
// System.out.println(Arrays.toString(cs));
for (int i = 0; i < cs.length-1; i+=2) {
cs[i+1] = shift(cs[i], cs[i+1]);
}
// System.out.println(Arrays.toString(cs));
return new String(cs);
}
private char shift(char x, char i) {
// System.out.println(x);
// System.out.println((int)i);
return (char)(x+(i-48));
}
}
# 1849. 将字符串拆分为递减的连续值（第 239 场周赛）
第二题
import java.math.BigInteger;
class Solution {
private String s;
public boolean splitString(String ss) {
s = ss;
for (int i = 0; i < s.length()-1; i++) {
String pre = s.substring(0, i+1);
int start = i+1;
// 存在子问题，使用递归
if (func(pre, start)) {
return true;
}
}
return false;
}
private boolean func(String pre, int start) {
if (start >= s.length()) {
return true;
}
BigInteger p = new BigInteger(pre);
for (int i = start+1; i <= s.length(); i++) {
// System.out.println(p+"; "+s.substring(start, i));
if (p.subtract(BigInteger.ONE).equals(new BigInteger(s.substring(start, i))) && func(s.substring(start, i), i)) {
return true;
}
}
return false;
}
}
# 1848. 到目标元素的最小距离（第 239 场周赛）
第一题
class Solution {
public int getMinDistance(int[] nums, int target, int start) {
int l = start, r = start;
while (l >= 0 || r < nums.length) {
if (l >= 0 && nums[l] == target) {
return start - l;
} else if (r < nums.length && nums[r] == target) {
return r - start;
}
l--;
r++;
}
return -1;
}
}
# 416. 分割等和子集
动态规划：
class Solution {
public boolean canPartition(int[] nums) {
// sum = sum/2
// nums[i]<=j dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]
// nums[i]>j = dp[i-1][j];
int n = nums.length;
int sum = 0;
int max = Integer.MIN_VALUE;
for (int i : nums) {
sum += i;
max = Math.max(max, i);
}
if (sum % 2 != 0) return false;
sum /= 2;
if (max > sum) return false;
boolean[][] dp = new boolean[n][sum+1];
for (int i = 0; i < n; i++) {
dp[i][0] = true;
}
for (int j = 1; j < sum; j++) {
if (nums[0] == j) {
dp[0][j] = true;
}
}
// System.out.println("sum:"+sum+";");
// System.out.println("array:"+Arrays.deepToString(dp));
for (int i = 1; i < n; i++) {
for (int j = 1; j <= sum; j++) {
if (nums[i] <= j) {
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
} else if (nums[i] > j) {
dp[i][j] = dp[i-1][j];
}
}
}
// System.out.println("array:"+Arrays.deepToString(dp));
return dp[n-1][sum];
}
}
# 516. 最长回文子序列
动态规划：
class Solution {
public int longestPalindromeSubseq(String s) {
// dp[i][j]
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n-1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (i == j) {
dp[i][j] = 1;
} else if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i+1][j-1] + 2;
} else if (s.charAt(i) != s.charAt(j)) {
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][n-1];
}
}
# 377. 组合总和 Ⅳ
暴力解：递归
class Solution {
public int combinationSum4(int[] nums, int target) {
if (target == 0) {
return 1;
} else if (target < 0) {
return 0;
}
int res = 0;
for (int n : nums) {
res += combinationSum4(nums, target-n);
}
return res;
}
}
记忆化递归（备忘录）：时间超过100%
class Solution {
private int[] dp;
public int combinationSum4(int[] nums, int target) {
dp = new int[target+1];
Arrays.fill(dp, -1);
return func(nums, target);
}
public int func(int[] nums, int target) {
if (target == 0) {
return 1;
} else if (target < 0) {
return 0;
}
if (dp[target] != -1) return dp[target];
int res = 0;
for (int n : nums) {
int next = target-n;
if (next < 0) continue;
res += (dp[next] = func(nums, next));
}
return res;
}
}
动态规划：状态压缩
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target+1];
// 题目是需要返回组合数，target为0时，是因为将target从大到小减小递归，最终到0
// 因此需要计数+1
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (i - num >= 0) {
dp[i] += dp[i-num];
}
}
}
return dp[target];
}
}
# 208. 实现 Trie (前缀树)
class Trie {
boolean end;
Trie[] next;
/** Initialize your data structure here. */
public Trie() {
next = new Trie[26];
end = false;
}
/** Inserts a word into the trie. */
public void insert(String word) {
Trie cur = this;
Trie[] list = cur.next;
for (char c : word.toCharArray()) {
if (list[c-'a'] == null) {
list[c-'a'] = new Trie();
}
cur = list[c-'a'];
list = cur.next;
}
cur.end = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Trie cur = this;
Trie[] list = cur.next;
for (char c : word.toCharArray()) {
if (list[c-'a'] == null) {
return false;
}
cur = list[c-'a'];
list = cur.next;
}
return cur.end;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
Trie cur = this;
Trie[] list = cur.next;
for (char c : prefix.toCharArray()) {
if (list[c-'a'] == null) {
return false;
}
cur = list[c-'a'];
list = cur.next;
}
return true;
}
}
两种模板trie树实现方式： 数组方式：
class Trie {
int N = 100009;
int[][] trie;
int[] count;
int index;
/** Initialize your data structure here. */
public Trie() {
trie = new int[N][26];
count = new int[N];
index = 0;
}
/** Inserts a word into the trie. */
public void insert(String word) {
int pos = 0;
for (int i = 0; i < word.length(); i++) {
int c = (int) (word.charAt(i)-'a');
if (trie[pos][c] == 0) {
trie[pos][c] = ++index;
}
pos = trie[pos][c];
}
count[pos]++;
// System.out.println(Arrays.deepToString(trie));
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
int pos = 0;
for (int i = 0; i < word.length(); i++) {
int c = (int) (word.charAt(i)-'a');
if (trie[pos][c] == 0) {
return false;
}
pos = trie[pos][c];
}
return count[pos] != 0;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
int pos = 0;
for (int i = 0; i < prefix.length(); i++) {
int c = (int) (prefix.charAt(i)-'a');
if (trie[pos][c] == 0) {
// System.out.println("pos:"+pos+"; c:"+(char)(c+'a'));
return false;
}
pos = trie[pos][c];
}
return true;
}
}
TrieNode方式：
class Trie {
class TrieNode {
boolean end;
TrieNode[] ns = new TrieNode[26];
}
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode p = root;
for (int i = 0; i < word.length(); i++) {
int c = (int) (word.charAt(i)-'a');
if (p.ns[c] == null) {
p.ns[c] = new TrieNode();
}
p = p.ns[c];
}
p.end = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode p = root;
for (int i = 0; i < word.length(); i++) {
int c = (int) (word.charAt(i)-'a');
if (p.ns[c] == null) {
return false;
}
p = p.ns[c];
}
return p.end;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode p = root;
for (int i = 0; i < prefix.length(); i++) {
int c = (int) (prefix.charAt(i)-'a');
if (p.ns[c] == null) {
return false;
}
p = p.ns[c];
}
return true;
}
}
# 363. 矩形区域不超过 K 的最大数值和
二维前缀和+二分查找，思路如下图：
class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
// 前缀和
int[][] ma = matrix;
int n = ma.length, m = ma[0].length;
int[][] pre = new int[n+1][m+1];
for (int r = 1; r <= n; r++) {
for (int c = 1; c <= m; c++) {
pre[r][c] = pre[r][c-1] + pre[r-1][c] - pre[r-1][c-1] + ma[r-1][c-1];
}
}
// 枚举 top bot
int res = Integer.MIN_VALUE;
for (int top = 1; top <= n; top++) {
for (int bot = top; bot <= n; bot++) {
TreeSet<Integer> ts = new TreeSet<>();
ts.add(0);
for (int c = 1; c <= m; c++) {
int right = pre[bot][c] - pre[top-1][c];
Integer left = ts.ceiling(right - k);
if (left != null) {
res = Math.max(res, right - left);
}
ts.add(right);
}
}
}
return res;
}
}
# 368. 最大整除子集
整除的传递性+动态规划：
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int[] dp = new int[n];
dp[0] = 1;
int max = 1;
for (int i = 1; i < n; i++) {
int div = nums[i];
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (div % nums[j] == 0) {
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
max = Math.max(max, dp[i]);
}
// System.out.println(Arrays.toString(dp));
// System.out.println(max);
List<Integer> res = new ArrayList<>();
int pre = 0;
for (int i = n-1; i >= 0 && max != 0; i--) {
if (pre == 0 && dp[i] == max) {
pre = nums[i];
max--;
res.add(nums[i]);
} else if (dp[i] == max && pre != 0 && pre % nums[i] == 0) {
max--;
pre = nums[i];
res.add(nums[i]);
}
}
return res;
}
}
go解法：
import "sort"
func largestDivisibleSubset(nums []int) []int {
n := len(nums)
sort.Ints(nums)
dp := make([]int, n)
dp[0] = 1
max := 1
for i := 1; i < n; i++ {
div := nums[i]
dp[i] = 1
for j := 0; j < i; j++ {
if div % nums[j] == 0 {
dp[i] = fMax(dp[i], dp[j]+1)
}
}
max = fMax(max, dp[i])
}
var res []int
pre := 0
for i := n-1; i >= 0 && max != 0; i-- {
if dp[i] == max && (pre % nums[i] == 0 || pre == 0) {
pre = nums[i]
max--;
res = append(res, nums[i])
}
}
return res
}
func fMax(a, b int) int {
if a > b {
return a
}
return b
}
动态规划，写法更好理解，算法逻辑与前面一致
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int[] dp = new int[n];
dp[0] = 1;
int maxSize = 1, maxIndex = 0, maxValue = nums[0];
for (int i = 1; i < n; i++) {
dp[i] = 1;
for (int j = i-1; j >= 0; j--) {
if (nums[i] % nums[j] == 0) {
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
if (dp[i] > maxSize) {
maxSize = dp[i];
maxIndex = i;
maxValue = nums[i];
}
}
List<Integer> res = new ArrayList<>();
for (int i = maxIndex; i >= 0 && maxSize > 0; i--) {
if (maxSize == dp[i] && maxValue % nums[i] == 0) {
res.add(nums[i]);
maxValue = nums[i];
maxSize--;
}
}
return res;
}
}
# 91. 解码方法
动态规划：
class Solution {
public int numDecodings(String s) {
int n = s.length();
if (s.charAt(0) == '0') return 0;
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
int di = 0;
if (s.charAt(i-1) != '0') {
di = dp[i-1];
}
int di2 = 0;
int s1 = (int) (s.charAt(i-1)-'0');
int s2 = (int) (s.charAt(i-2)-'0');
if ((s2 == 2 && s1 <= 6) || s2 == 1) {
di2 = dp[i-2];
}
dp[i] = di + di2;
}
return dp[n];
}
}
动态规划，空间优化，更优的代码：
class Solution {
public int numDecodings(String s) {
int p1 = 1, p2 = 0;
if (s.charAt(0) == '0') return 0;
for (int i = 0; i < s.length(); i++) {
int cur = 0;
if (i > 0 && Integer.valueOf(s.substring(i-1, i+1)) <= 26 && s.charAt(i-1) != '0') {
cur += p2;
}
if (s.charAt(i) != '0') {
cur += p1;
}
p2 = p1;
p1 = cur;
}
return p1;
}
}
# 781. 森林中的兔子
class Solution {
public int numRabbits(int[] answers) {
Map<Integer, Integer> map = new HashMap<>();
int n = answers.length;
for (int i = 0; i < n; i++) {
int cur = answers[i]+1;
map.put(cur, map.getOrDefault(cur, 0)+1);
}
int res = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int quantity = entry.getKey();
int rabbits = entry.getValue();
int multiple = rabbits / quantity;
int remainder = rabbits % quantity;
res += (multiple * quantity) + (remainder > 0 ? quantity : 0);
}
return res;
}
}
# 面试题 17.21. 直方图的水量
单调栈：
class Solution {
public int trap(int[] height) {
int n = height.length;
int res = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.empty() && height[i] > height[stack.peek()]) {
int cur = stack.pop();
if (stack.empty()) continue;
int left = stack.peek(), right = i;
res += (Math.min(height[left], height[right]) - height[cur]) * (right - left -1);
}
stack.push(i);
}
return res;
}
}
# 1006. 笨阶乘
双栈做法，但是代码写的太繁琐：
class Solution {
public int clumsy(int n) {
char[] ch = new char[]{'*', '/', '+', '-'};
Stack<Integer> sn = new Stack<>();
Stack<Character> sc = new Stack<>();
sc.push('+');
for (int cur = n, ci = 0; cur > 0; cur--) {
char symbol = sc.peek();
if (symbol == '*' || symbol == '/') {
sc.pop();
int num = sn.pop();
int res = 0;
if (symbol == '*') res = num * cur;
if (symbol == '/') res = num / cur;
sn.push(res);
} else {
sn.push(cur);
}
sc.push(ch[ci%4]);
ci++;
}
sc.pop();
int res = 0;
while (!sn.empty()) {
int cur = sn.pop();
char symbol = sc.pop();
if (symbol == '-') cur *= -1;
res += cur;
}
return res;
}
}
优化后的代码：
class Solution {
public int clumsy(int n) {
char[] ch = new char[]{'*', '/', '+', '-'};
Stack<Integer> sn = new Stack<>();
sn.push(n);
int chi = 0;
for (int cur = n-1; cur > 0; cur--) {
if (chi % 4 == 0) {
sn.push(sn.pop() * cur);
} else if (chi % 4 == 1) {
sn.push(sn.pop() / cur);
} else if (chi % 4 == 2) {
sn.push(cur);
} else if (chi % 4 == 3) {
sn.push(-cur);
}
chi++;
}
int res = 0;
while (!sn.empty()) {
res += sn.pop();
}
return res;
}
}
# ## 87. 扰乱字符串
暴力法，递归，超时：
class Solution {
public boolean isScramble(String s1, String s2) {
int n1 = s1.length();
int n2 = s2.length();
if (n1 != n2) return false;
int n = n1;
if (s1.equals(s2)) return true;
for (int i = 1; i < n; i++) {
String s1a = s1.substring(0,i);
String s1b = s1.substring(i,n);
String s2a = s2.substring(0,i);
String s2b = s2.substring(i);
String s3a = s2.substring(0, n-i);
String s3b = s2.substring(n-i);
if ((isScramble(s1a, s2a) && isScramble(s1b, s2b)) || (isScramble(s1a, s3b) && isScramble(s1b, s3a))) {
return true;
}
}
return false;
}
}
将递归转化为记忆化递归，可以AC，速度也不慢：
class Solution {
int[][][] cache;
int N = -1, Y = 1, EMPTY = 0;
String s1;
String s2;
public boolean isScramble(String _s1, String _s2) {
s1 = _s1;
s2 = _s2;
if (s1.equals(s2)) return true;
if (!check(s1, s2)) return false;
int n = s1.length();
cache = new int[n][n][n+1];
recursive(0, 0, n);
return cache[0][0][n] == Y;
}
private boolean recursive(int i, int j, int k) {
if (cache[i][j][k] != EMPTY) return cache[i][j][k] == Y;
String a = s1.substring(i, i+k);
String b = s2.substring(j, j+k);
if (a.equals(b)) {
cache[i][j][k] = Y;
return true;
}
if (!check(a, b)) {
cache[i][j][k] = N;
return false;
}
for (int p = 1; p < k; p++) {
if (recursive(i, j, p) && recursive(i+p, j+p, k-p)) {
cache[i][j][k] = Y;
return true;
}
if (recursive(i, k-p+j, p) && recursive(i+p, j, k-p)) {
cache[i][j][k] = Y;
return true;
}
}
cache[i][j][k] = N;
return false;
}
private boolean check(String s1, String s2) {
if (s1.length() != s2.length()) return false;
int n = s1.length();
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
int[] cnt1 = new int[26];
int[] cnt2 = new int[26];
for (int i = 0; i < n; i++) {
cnt1[c1[i]-'a']++;
cnt2[c2[i]-'a']++;
}
for (int i = 0; i < 26; i++) {
if (cnt1[i] != cnt2[i]) return false;
}
return true;
}
}
区间dp，待补充
← LeetCode 2 LeetCode 4 →