本文最后更新于 336 天前,其中的信息可能已经有所发展或是发生改变。
1. 两数之和
- 哈希表
- 遍历数组,同时用
HashMap
维护已出现过的数及其下标 - 若当前的数
nums[i]
满足target - nums[i]
曾经出现过,则直接返回 - 否则将其加入到哈希表中。
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> st = new HashMap<>();
for (int i = 0; i < nums.length; i ++) {
if (st.containsKey(target - nums[i])) {
return new int[]{st.get(target - nums[i]), i};
}
else st.put(nums[i], i);
}
return null;
}
}
2. 两数相加
- 链表
- 使用
res
维护链表,ans
指向res
头结点 - 遍历链表
l1
和l2
,取得当前节点的值分别为a
,b
,并用base
记录进位 - 则,新的
res
节点为a + b + base % 10
,base = (a + b + base) / 10
- 不断将
res
更新为res.next
,最后若base != 0
则补上进位即可
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode res = new ListNode();
ListNode ans = res;
int base = 0;
while (l1 != null || l2 != null) {
int a = l1 == null ? 0 : l1.val;
int b = l2 == null ? 0 : l2.val;
int sum = a + b + base;
base = sum / 10;
res.next = new ListNode(sum % 10);
res = res.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (base != 0) res.next = new ListNode(base);
return ans.next;
}
}
3. 无重复字符的最长子串
- 滑动窗口
- 维护一个集合或布尔数组,保存当前出现过的字符
- 设窗口左边界为
i
,右边界为j
,当前字符为s[j]
- 当出现重复字符时窗口左边界
i
向右移动,并不断将vis[i]
移除,直到vis[i] === s[j]
被排除 - 持续更新窗口最大长度
j - i + 1
即为答案
class Solution {
public int lengthOfLongestSubstring(String s) {
int ans = 0;
HashSet<Character> st = new HashSet<>();
for (int i = 0, j = 0; i < s.length(); i++) {
while (st.contains(s.charAt(i)) && j < i) {
st.remove(s.charAt(j++));
}
st.add(s.charAt(i));
ans = Math.max(ans, st.size());
}
return ans;
}
}
优化:
- 上述两种实现滑窗的方式都需要“持续性地移动边界”这个操作
- 不如换一种思路——使用
HashMap
来更新每个字符最近一次出现的索引 - 当我们遍历字符串
s
时,仍使用i
和j
来表示当前无重复字符子串的起始位置和结束位置,初始时i = j = 0
。 - 在每一步迭代中,检查当前字符
s[j]
是否已经在HashMap
中存在:- 如果存在,则更新左指针
i
移动到重复字符的下一个位置,保证左指针i
始终指向当前无重复字符子串的起始位置。
- 如果存在,则更新左指针
- 将
s[j]
其加入HashMap
中,并更新窗口最大长度j - i + 1
。 - 最后,右指针
j
向右移动一位,继续遍历字符串s
,直到右指针j
到达字符串的末尾 - 这样只需更新字符出现的索引即可,无需重复遍历。
class Solution {
public int lengthOfLongestSubstring(String s) {
int ans = 0;
HashMap<Character, Integer> vis = new HashMap<>();
int n = s.length();
int i = 0, j = 0;
while (i < n && j < n) {
if (vis.containsKey(s.charAt(j))) {
i = Math.max(vis.get(s.charAt(j)) + 1, i); // 更新索引,取较大值为新的左指针位置
}
vis.put(s.charAt(j), j);
ans = Math.max(ans, j - i + 1);
j ++;
}
return ans;
}
}
4. 寻找两个正序数组的中位数
- 暴力
- 合并两个有序数组,然后取中位数即可
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int[] nums = new int[n + m];
int idx = 0, idx1 = 0, idx2 = 0;
while (idx1 < n && idx2 < m) {
if (nums1[idx1] < nums2[idx2]) nums[idx ++] = nums1[idx1 ++];
else nums[idx ++] = nums2[idx2 ++];
}
while (idx1 < n) nums[idx ++] = nums1[idx1 ++];
while (idx2 < m) nums[idx ++] = nums2[idx2 ++];
if (((n + m) & 1) == 1) return nums[(n + m) >> 1];
else return (double)(nums[(n + m) >> 1] + nums[(n + m - 1) >> 1]) / 2;
}
}
5. 最长回文子串
- dp
- 在这种情况下,我们可以定义一个二维数组
dp
,其中dp[i][j]
表示从索引i
到索引j
的子串是否是回文。 - 根据回文的定义,我们可以得出以下状态转移方程:
dp[i][j] = true
,如果i == j
(单个字符是回文)dp[i][j] = true
,如果s[i] == s[j]
且dp[i + 1][j - 1] == true
(首尾字符相等且去掉首尾后的子串是回文)dp[i][j] = false
,其他情况
- 基于这个状态转移方程,我们可以使用动态规划来填充
dp
数组。然后,我们可以根据dp
数组找到最长回文子串。
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
String ans = "";
// // 单个字符或相同的两个是回文
for (int i = 0; i < n; i++) {
if (ans.length() <= 1) ans = s.substring(i, i + 1);
dp[i][i] = true;
if (i < n - 1 && s.charAt(i) == s.charAt(i + 1)) {
dp[i][i + 1] = true;
ans = s.substring(i, i + 2);
}
}
// 长度大于2的子串
for (int len = 3; len <= n; len ++) {
for (int i = 0; i <= n - len; i ++) {
int j = i + len - 1;
if (j - 1 >= 0 && s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
dp[i][j] = true;
ans = s.substring(i, j + 1);
}
}
}
return ans;
}
}
6. N 字形变换
-
模拟
-
首先排除特殊情况,当
numRows <= 1 || s.length() <= numRows
直接返回s
-
其他情况可以利用偏移量对字符坐标进行模拟,将结果存到二维数组中
若使用
StringBuilder
来构造模拟结果集,此时发现仅需要行数变化即可 -
则最终将结果集转换为字符串返回即可
class Solution {
public String convert(String s, int numRows) {
int n = s.length();
if (numRows <= 1 || n <= numRows) return s; // 特殊情况直接返回
int l = 0, d = 0; // l 记录当前所在行数,d 记录当前的方向
StringBuilder mp[] = new StringBuilder[numRows]; // 结果集
for (int i = 0; i < numRows; i ++) { // 初始化结果集,每一行都是一个 StringBuilder
mp[i] = new StringBuilder();
}
mp[0].append(s.charAt(0)); // 将第一个字符先加入
for (int i = 1; i < n; i ++) { // 从第二个字符开始遍历
if ((d == 0 && l == numRows - 1) || (d == 1 && l == 0)) d = 1 - d; // 判断方向改变条件
l += d == 0 ? 1 : -1;
mp[l].append(s.charAt(i));
}
StringBuilder ans = new StringBuilder();
for (StringBuilder st : mp) {
ans.append(st.toString());
}
return ans.toString();
}
}
7. 整数反转
- 模拟
- 循环倒除得到每一位,再反向乘加即可
- 最大值通过
Integer.MAX_VALUE
获取,最小值可以通过Integer.MIN_VALUE
获取 - 当
ans
大于最值除以 $10$ 的时候,下一步计算会溢出 - 由于输入的数在
Integer
范围内,可以证明,在计算结束前,不存在ans
超过最值的情况
class Solution {
public int reverse(int x) {
int ans = 0;
int maxn = Integer.MAX_VALUE / 10;
int minn = Integer.MIN_VALUE / 10;
while (x != 0) {
if (ans > maxn || ans < minn) return 0;
int t = x % 10;
ans = ans * 10 + t;
x /= 10;
}
return ans;
}
}
8. 字符串转换整数 (atoi)
- 模拟
- 首先去除空格,然后判断起始字符是否为
+
或-
- 判断溢出时,最大值通过
Integer.MAX_VALUE
获取,最小值可以通过Integer.MIN_VALUE
获取 - 当
ans
大于最值除以 $10$ 的时候,下一步计算会溢出 - 当
ans
等于最值除以 $10$ 的时候,用最值模 $10$ 的余数判断下一步计算是否溢出
class Solution {
public int myAtoi(String s) {
String st = s.trim();
int ans = 0;
boolean flag = false; // 结果符号: false 为 +,true 为 -
// 计算最值 / 10
int maxn = Integer.MAX_VALUE / 10;
int minn = Integer.MIN_VALUE / 10;
// 计算最值 % 10
int maxt = Integer.MAX_VALUE % 10;
int mint = Integer.MIN_VALUE % 10;
for (int i = 0; i < st.length(); i ++) {
char p = st.charAt(i);
if (p == '-' && i == 0) flag = true;
else if (p == '+' && i == 0) continue;
else if (p >= '0' && p <= '9') {
int t = p - '0';
// 判断是否溢出
if (flag && (- ans < minn || (- ans == minn && - t < mint))) return Integer.MIN_VALUE;
if (!flag && (ans > maxn || (ans == maxn && t > maxt))) return Integer.MAX_VALUE;
ans = ans * 10 + t;
}
else break;
}
if (flag) ans *= -1;
return ans;
}
}
9. 回文数
- 暴力
class Solution {
public boolean isPalindrome(int x) {
if (x < 0) return false;
int ans = 0;
int y = x;
while(x != 0) {
ans = ans * 10 + (x % 10);
x /= 10;
}
return y == ans;
}
}
10. 正则表达式匹配
- dp
- 状态表示:
- 状态
dp[i][j]
表示字符串s
的前i
个字符和字符规律p
的前j
个字符是否匹配。
- 状态
- 状态计算:
- 当
s
的第i
个字符和p
的第j
个字符相等,或者p
的第j
个字符为.
时说明当前字符匹配,即dp[i][j] = dp[i-1][j-1]
。 - 当
p
的第j
个字符为*
时,需要考虑两种情况,满足其一即匹配:*
匹配零个前面的元素,即dp[i][j] = dp[i][j-2]
。*
匹配一个或多个前面的元素时,要满足s.charAt(i) == p.charAt(j - 1) || s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'
,即dp[i][j] = dp[i-1][j]
。
- 当
- 初始化:
- 两者为空也为匹配,即
dp[0][0] = true
- 对于
p
,若p.charAt(i) == '*'
说明当前星号可以匹配前面的字符零次,即dp[0][i] = dp[0][i - 2]
。
- 两者为空也为匹配,即
class Solution {
public boolean isMatch(String s, String p) {
int n = s.length(), m = p.length();
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
for (int i = 1; i <= m; i ++) {
if (p.charAt(i - 1) == '*') dp[0][i] = dp[0][i - 2];
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
// i, j 从 1 开始,s, p 需要偏移 -1
if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
dp[i][j] = dp[i - 1][j - 1];
}
else if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'));
}
}
}
return dp[n][m];
}
}
11. 盛最多水的容器
- 双指针
- 设
l
为容器的左边界,r
为右边界,初始化l = 0, r = height.length - 1
- 当
height[l] < height[l + 1]
或height[r] < height[r - 1]
时,容器体积可能增大
class Solution {
public int maxArea(int[] height) {
int n = height.length;
int l = 0, r = n - 1;
int ans = Math.min(height[l], height[r]) * (n - 1);
while(l < r) {
// 优化:通过两个 while 快速找到大于等于当前最低边界的 l 和 r 所在位置,减少不必要的计算
int t = Math.min(height[l], height[r]);
while (l < r && height[l] <= t) l ++;
while (r > l && height[r] <= t) r --;
ans = Math.max(ans, Math.min(height[l], height[r]) * (r - l));
}
return ans;
}
}
12. 整数转罗马数字
- 模拟
- 按照题目规则转换
- 每次都选择尽量大的位数进行转换即可
public class Solution {
public String intToRoman(int num) {
int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < nums.length; i++) {
while (num >= nums[i]) {
stringBuilder.append(romans[i]);
num -= nums[i];
}
}
return stringBuilder.toString();
}
}
13. 罗马数字转整数
- 模拟
- 反过来模拟即可
- 从右至左,若当前罗马字母比右边的小,则说明需要减去,否则做加法即可
class Solution {
public int romanToInt(String s) {
int[] nums = {1000, 500, 100, 50, 10, 5, 1};
char[] romans = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};
int n = s.length();
int flag = getIdx(s.charAt(n - 1), romans);
int num = nums[flag];
for (int i = n - 2; i >= 0; i --) {
int t = getIdx(s.charAt(i), romans);
if (nums[t] < nums[flag]) num -= nums[t];
else num += nums[t];
flag = t;
}
return num;
}
private static int getIdx(char p, char[] romans) {
for (int i = 0; i < romans.length; i ++) {
if (p == romans[i]) return i;
}
return -1;
}
}
14. 最长公共前缀
- 模拟
- 初始化公共前缀为
res = strs[0]
- 从
i = 1
循环枚举strs[i]
判断是否满足strs[i].startsWith(res)
- 若不满足则循环找到
res
的字串,直到满足为止
class Solution {
public String longestCommonPrefix(String[] strs) {
String res = strs[0];
for (int i = 1; i < strs.length; i ++) {
while (!strs[i].startsWith(res)){
res = res.substring(0, res.length() - 1);
}
}
return res;
}
}
15. 三数之和
- 双指针
- 首先将数组从小到大排序,使得数组单调
- 则要寻找三数之和为 $0$,必须保证
nums[i] < 0
,左指针j = i + 1
,右指针k = n - 1
,即sum = nums[i] + nums[j] + nums[k]
- 当
sum < 0
说明nums[j]
太小,则指针j ++
- 当
sum > 0
说明nums[k]
太大,则指针k --
- 当
sum == 0
说明满足条件,此时需要将重复的nums[j]
和nums[k]
排除,即两个指针收缩,直到不再重复。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
List<List<Integer>> ans = new ArrayList<>();
// 排除特殊情况
if (n < 3) return ans;
Arrays.sort(nums);
for (int i = 0; i < n; i ++) {
// nums[i] > 0 之后不再存在满足条件的结果,直接返回
if (nums[i] > 0) return ans;
int j = i + 1, k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum < 0) j ++;
else if (sum > 0) k --;
else {
List<Integer> list = new ArrayList<>();
list.add(nums[i]); list.add(nums[j]); list.add(nums[k]);
ans.add(list);
// 收缩指针,去重
while (j + 1 <= k && nums[j] == nums[j + 1]) j ++;
while (j + 1 <= k && nums[k] == nums[k - 1]) k --;
j ++; k --;
}
}
// 去除重复的 nums[i]
while (i + 1 < n && nums[i + 1] == nums[i]) i ++;
}
return ans;
}
}
16. 最接近的三数之和
- 双指针
- 和上一题思路相近,不同的是我们需要维护一个
sum = nums[i] + nums[j] + nums[k]
和target
差值的最小值
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int flag = Integer.MAX_VALUE;
int ans = 0;
for (int i = 0; i < n; i++) {
int j = i + 1, k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
int t = Math.abs(sum - target);
if (t < flag) {
flag = t;
ans = sum;
}
if (sum < target) j ++;
else k --;
}
while (i + 1 < n && nums[i] == nums[i + 1]) i ++;
}
return ans;
}
}
17. 电话号码的字母组合
- DFS
- 递归的每一层视作对
digits[0]
所对应映射"xxx"
的枚举 - 每一层中,利用循环枚举
"xxx"
的每一位,然后继续递归 - 当递归的层数
u == digits.length()
时将当前累计的字符串加入答案列表并回溯
class Solution {
private static String vis[] = new String[]{
"", "", // 空出 0, 1 的位置
"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
public List<String> letterCombinations(String digits) {
List<String> ans = new ArrayList<>();
if (digits.length() == 0) return ans;
// res 记录当前累计的字符
StringBuilder res = new StringBuilder();
dfs(digits, 0, res, ans);
return ans;
}
private void dfs(String digits, int u, StringBuilder res, List<String> ans) {
// 满足长度 ans 添加 res 并返回
if (u == digits.length()) {
ans.add(res.toString());
return ;
}
int digit = digits.charAt(u) - '0';
String letters = vis[digit];
for (int i = 0; i < letters.length(); i ++) {
res.append(letters.charAt(i)); // 将枚举的 xxx 的第 i 个字符累计
dfs(digits, u + 1, res, ans); // 递归到 u + 1 层
res.deleteCharAt(res.length() - 1); // 恢复现场
}
}
}
18. 四数之和
- 双指针
- 三数之和基础上,枚举第一个数
nums[i]
,剩下三个数计算三数之和为target - nums[i]
- 注意数据范围会爆
int
- 有意思吗力扣出题人出这种脑瘫题目😅😅😅😅😅😅😅😅😅😅😅😅😅😅😅😅😅
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
// 排除特殊情况
if (n < 4) return ans;
Arrays.sort(nums);
for (int i = 0; i < n; i ++) {
int ftarget = target - nums[i];
for (int j = i + 1; j < n; j ++) {
int k = j + 1, l = n - 1;
while (k < l) {
long sum = (long)nums[j] + nums[k] + nums[l]; // 使用 long 类型存储和
if (sum < ftarget) k ++;
else if (sum > ftarget) l --;
else {
List<Integer> list = new ArrayList<>();
list.add(nums[i]); list.add(nums[j]); list.add(nums[k]); list.add(nums[l]);
ans.add(list);
while (k + 1 <= l && nums[k] == nums[k + 1]) k ++;
while (k + 1 <= l && nums[l] == nums[l - 1]) l --;
k ++; l --;
}
}
while (j + 1 < n && nums[j + 1] == nums[j]) j ++;
}
while (i + 1 < n && nums[i + 1] == nums[i]) i ++;
}
return ans;
}
}
19. 删除链表的倒数第 N 个结点
- 模拟
- 遍历一遍链表得到链表长度
size
- 特判:当
size <= 1
或n - size == 0
时返回null
- 遍历链表,当
idx == n - size - 1
说明下一个节点即为要删除的节点,直接修改指向即可
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int size = 0;
for (ListNode i = head; i != null; i = i.next) size ++;
if (size <= 1) return null;
if (n - size == 0) return head.next;
int idx = 0;
for (ListNode i = head; i != null; i = i.next) {
if (idx == size - n - 1) {
i.next = i.next.next;
}
idx ++;
}
return head;
}
}
优化:
- 双指针
- 为防止删除头结点的情况出现,利用
ListNode ans
指向head
- 设
ListNode
指针l
和r
都指向ans
- 将
r
先移动n + 1
的距离,然后再让l
和r
同时移动 - 当
r.next == null
说明l
位于要被删除节点的前一个节点 - 删除操作即为
l.next = l.next.next
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode ans = new ListNode();
ans.next = head;
ListNode l = ans, r = ans;
for (int i = 0; i < n + 1; i ++) r = r.next;
while (r != null) {
l = l.next; r = r.next;
}
l.next = l.next.next; // 删除操作
return ans.next;
}
}
20. 有效的括号
- 模拟
- 用一个栈维护当前存在的左括号
- 若
s.length()
为奇数则不可能匹配,否则遍历s
- 当前字符为左括号:直接进栈
- 当前字符为右括号:若栈为空或栈顶不匹配直接返回
false
,否则弹出栈顶 - 最后判断栈是否为空,若不为空说明还有剩余的左未匹配,返回
false
class Solution {
public boolean isValid(String s) {
if ((s.length() & 1) == 1) return false;
Stack<Character> st = new Stack<>();
for (char p : s.toCharArray()) {
if (p == '(') st.push(')');
else if (p == '[') st.push(']');
else if (p == '{') st.push('}');
else {
if (st.isEmpty()) return false;
if (p == ')' || p == ']' || p == '}') {
if (st.peek() == p) st.pop();
else return false;
}
}
}
return st.isEmpty();
}
}
21. 合并两个有序链表
- 模拟
- 比较节点的值,较小的尾插
- 有剩余的全部合并
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode ans = new ListNode();
ListNode st = ans;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
st.next = list1;
list1 = list1.next;
} else {
st.next = list2;
list2 = list2.next;
}
st = st.next;
}
st.next = list1 != null ? list1 : list2;
return ans.next;
}
}
22. 括号生成
- DFS
- 递归的每一层视作添加的括号类型
- 由于必须保证括号匹配,则必须满足起始括号为
(
- 添加
(
的数量l
必须满足l < n
,添加)
的数量r
必须满足r < l
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
dfs(ans, "", 0, 0, n);
return ans;
}
private void dfs(List<String> ans, String current, int l, int r, int n) {
// 满足长度返回
if (l + r == n * 2) {
ans.add(current);
return;
}
if (l < n) dfs(ans, current + "(", l + 1, r, n);
if (r < l) dfs(ans, current + ")", l, r + 1, n);
}
}
23. 合并 K 个升序链表
- 模拟
- 循环枚举链表数组里的链表,一一合并,时间复杂度 $\mathcal{O}(nk^2)$
- 特判,当
lists.length == 0
时返回null
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int n = lists.length;
if (n == 0) return null;
// 全部合并到 lists[0] 上面
ListNode ans = lists[0];
for (int i = 1; i < n; i ++) {
ans = mergeTwoLists(ans, lists[i]);
}
return ans;
}
// 合并两个链表
private static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode ans = new ListNode();
ListNode st = ans;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
st.next = list1;
list1 = list1.next;
} else {
st.next = list2;
list2 = list2.next;
}
st = st.next;
}
st.next = list1 != null ? list1 : list2;
return ans.next;
}
}
优化:
- 归并
- 用两两归并代替循环合并,时间复杂度 $\mathcal{O}(nk \log_2^k)$
- 每一轮的合并中,从第一个链表开始,将它与它后面的第
cnt
个链表合并,然后将合并结果存储在第一个链表的位置上。 - 然后继续从第一个链表开始,将它与它后面的第
2 * cnt
个链表合并,再将合并结果存储在第一个链表的位置上。 - 以此类推,直到所有链表都被合并即
cnt >= n
为止。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int n = lists.length;
if (n == 0) return null;
// 合并步长,每一轮合并后 cnt *= 2;
int cnt = 1;
while (cnt < n) {
// 两两合并
for (int i = 0; i + cnt < n; i += cnt * 2) {
lists[i] = mergeTwoLists(lists[i], lists[i + cnt]);
}
cnt *= 2;
}
// 最终全部合并到 lists[0]
return lists[0];
}
private static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode ans = new ListNode();
ListNode st = ans;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
st.next = list1;
list1 = list1.next;
} else {
st.next = list2;
list2 = list2.next;
}
st = st.next;
}
st.next = list1 != null ? list1 : list2;
return ans.next;
}
}
24. 两两交换链表中的节点
- 模拟
- 用一个
ListNode t
指向当前要交换的节点对中的左节点(下一次交换的前一个节点) - 则每次交换过程中,左右节点分别为
l = t.next, r = t.next.next
- 先用
t
指向r
,再用l
指向r
指向的节点完成l
替换r
- 再让
r
指向l
完成r
替换l
- 最后
t
指向l
,即下一次交换的前一个节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode ans = new ListNode();
ans.next = head;
ListNode t = ans;
while (t.next != null && t.next.next != null) {
ListNode l = t.next; // t -> l -> r -> k -> ...
ListNode r = t.next.next;
t.next = r; // t -> r
l.next = r.next; // l -> k
r.next = l; // r -> l
t = l; // r -> l(t) -> k -> ...
}
return ans.next;
}
}
25. K 个一组翻转链表
- 模拟
- 本质上就是修改链表节点指向
- 即,每组的第一个节点指向本组最后节点指向的节点
- 然后每组第一个节点后的节点依次指向前节点
如图:
k = 3
node1 -> node2 -> node3 -> node4 -> null
node1 -> node4
node2 -> node1
node3 -> node2
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode ans = new ListNode();
ans.next = head;
ListNode t = ans;
ListNode st = findNode(t, k);
while (t.next != null && st.next != null) {
ListNode l = t.next;
ListNode r = st.next;
// 修改节点指向
for (int i = 0; i < k; i++) {
ListNode temp = l.next;
l.next = r; // 每组第一个节点指向本组最后的节点指向的节点
r = l;
l = temp;
}
// 为下一次循环做准备
ListNode temp = t.next;
t.next = r;
temp.next = l;
t = temp;
st = findNode(t, k);
}
return ans.next;
}
// 找到每组最后一个节点
private ListNode findNode(ListNode t, int k) {
k --;
while (k-- > 0) {
if (t.next != null) t = t.next;
else break;
}
return t;
}
}
26. 删除有序数组中的重复项
- 模拟
- 由于数组单调且元素唯一,显然有
nums[i] < nums[i + 1]
- 设
idx
为去重后数组的下标,flag
当前维护的值 - 若
flag < nums[i]
说明元素不重复,则修改nums[idx ++] = nums[i]
即可
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
int idx = 0, flag = Integer.MIN_VALUE;
for (int i = 0; i < n; i ++) {
if (flag < nums[i]) {
flag = nums[i]; // 更新 flag
nums[idx ++] = nums[i];
}
}
return idx;
}
}
27. 移除元素
- 模拟
- 设
idx
为去重后的数组下标 - 若
nums[i] == val
直接跳过 - 否则直接修改
nums[idx ++] = nums[i]
即可
class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
int idx = 0;
for (int i = 0; i < n; i ++) {
if (nums[i] == val) continue;
nums[idx ++] = nums[i];
}
return idx;
}
}
28. 找出字符串中第一个匹配项的下标
- AC自动机
- 这道题非常的难啊!
- 既然出题人本意不想让我们循环暴力、直接调库或者KMP这种简单的算法
- 那我们只好按出题人的意思来了,直接祭大招好了😅😅😅
class Solution {
class Node {
Node[] children; // 子节点数组
Node fail; // 失败指针
List<Integer> indices; // 匹配成功的模式串在原字符串中的起始位置列表
public Node() {
children = new Node[26]; // 26个英文字母
fail = null;
indices = new ArrayList<>();
}
}
public int strStr(String haystack, String needle) {
if (needle.isEmpty()) {
return 0;
}
Node root = buildTrie(needle); // 构建Trie树
buildFailure(root); // 构建失败指针
Node curr = root;
for (int i = 0; i < haystack.length(); i++) {
char c = haystack.charAt(i);
curr = getNextState(curr, c); // 获取下一个状态
if (curr.indices.size() > 0) { // 匹配成功,返回模式串在原字符串中的起始位置
return i - needle.length() + 1;
}
}
return -1; // 未找到匹配的模式串
}
private Node buildTrie(String needle) {
Node root = new Node();
Node curr = root;
for (int i = 0; i < needle.length(); i++) {
char c = needle.charAt(i);
if (curr.children[c - 'a'] == null) {
curr.children[c - 'a'] = new Node();
}
curr = curr.children[c - 'a'];
}
curr.indices.add(0); // 将模式串的起始位置添加到当前节点的起始位置列表中
return root;
}
private void buildFailure(Node root) {
Queue<Node> queue = new LinkedList<>();
for (int i = 0; i < 26; i++) { // 初始化根节点的子节点的失败指针
if (root.children[i] != null) {
root.children[i].fail = root;
queue.offer(root.children[i]);
} else {
root.children[i] = root;
}
}
while (!queue.isEmpty()) {
Node curr = queue.poll();
for (int i = 0; i < 26; i++) {
if (curr.children[i] != null) {
Node child = curr.children[i];
Node fail = curr.fail;
while (fail != null && fail.children[i] == null) { // 失败指针回溯
fail = fail.fail;
}
child.fail = fail != null ? fail.children[i] : root; // 更新失败指针
child.indices.addAll(child.fail.indices); // 将失败指针节点的起始位置列表合并到当前节点
queue.offer(child);
}
}
}
}
private Node getNextState(Node curr, char c) {
while (curr != null && curr.children[c - 'a'] == null) { // 失败指针回溯
curr = curr.fail;
}
if (curr == null) {
return curr;
} else {
return curr.children[c - 'a'];
}
}
}
29. 两数相除
- 位运算
- 特殊情况:被除数
a
等于Integer.MIN_VALUE
且除数b
等于 $-1$ 时结果会溢出,直接返回Integer.MAX_VALUE
。 - 从第 $31$ 位开始逐位检查被除数
a
是否大于等于b
的左移结果(b << i)
。 - 如果被除数大于等于
(b << i)
,则执行以下操作:- 将被除数
a
减去(b << i)
,相当于从被除数中减去当前位的除数。 - 检查结果变量
res
是否大于Integer.MAX_VALUE - (1 << i)
,如果是,则结果溢出,直接返回Integer.MIN_VALUE
。 - 将结果变量
res
加上1 << i
,相当于将当前位的商加到结果中。
- 将被除数
- 循环结束后,返回结果变量
res
。
class Solution {
public int divide(int a, int b) {
if (a == 0) return 0;
if (a == Integer.MIN_VALUE && b == -1) return Integer.MAX_VALUE;
boolean flag = (a > 0) ^ (b > 0); // 判断符号是否相同,用于确定符号
a = Math.abs(a); b = Math.abs(b);
int res = 0;
for (int i = 31; i >= 0; i--) {
if ((a >>> i) - b >= 0) { // a >= (b << i)
a -= (b << i);
if (res > Integer.MAX_VALUE - (1 << i)) {
return Integer.MIN_VALUE;
}
res += (1 << i);
}
}
return flag ? -res : res;
}
}
30. 串联所有单词的子串
- 滑窗
- 用
StringBuilder
模拟窗口 - 当窗口长度
sb.length() == words.length * words[0].length()
需要判断是否满足 - 用
HashMap<String, Integer>
统计words
里面的单词及其词频 - 然后依次截取
sb
长度为words[0].length()
的片段,判断是否存在且频数照应 - 若满足条件,将下标加入答案中
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
int len = words.length * words[0].length(); // 计算目标子串的长度
int n = s.length();
StringBuilder sb = new StringBuilder(); // 用于存储当前窗口的子串
List<Integer> ans = new ArrayList<>();
HashMap<String, Integer> vis = new HashMap<>(); // 存储目标子串中每个单词的出现次数
for (int i = 0; i < words.length; i++) {
vis.put(words[i], vis.getOrDefault(words[i], 0) + 1);
}
for (int i = 0; i < n; i ++) {
if (sb.length() == len) sb.deleteCharAt(0); // 长度足够,删除最左侧的字符
sb.append(s.charAt(i)); // 将当前字符添加到窗口的子串中
if (sb.length() == len) {
HashMap<String, Integer> sbwords = new HashMap<>(vis);
// 检查当前窗口的子串是否符合要求
if (check(sb.toString(), sbwords, words[0].length())) ans.add(i - len + 1);
}
}
return ans;
}
private static boolean check(String sb, HashMap<String, Integer> sbwords, int cnt) {
// 以单词长度为步长,遍历当前窗口的子串
for (int i = 0; i < sb.length(); i += cnt) {
String res = sb.substring(i, i + cnt);
// 如果目标子串中包含当前单词
if (sbwords.containsKey(res)) {
int t = sbwords.get(res);
if (t > 0) sbwords.put(res, t - 1);
else return false;
}
else return false;
}
return true;
}
}