本文最后更新于 481 天前,其中的信息可能已经有所发展或是发生改变。
- 哈希表
- 遍历数组,同时用
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; |
| } |
| } |
- 链表
- 使用
res
维护链表,ans
指向 res
头结点
- 遍历链表
l1
和 l2
,取得当前节点的值分别为 a
,b
,并用 base
记录进位
- 则,新的
res
节点为 a + b + base % 10
,base = (a + b + base) / 10
- 不断将
res
更新为 res.next
,最后若 base != 0
则补上进位即可
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| 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; |
| } |
| } |
- 滑动窗口
- 维护一个集合或布尔数组,保存当前出现过的字符
- 设窗口左边界为
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; |
| } |
| } |
| 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; |
| } |
| } |
- 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); |
| } |
| } |
| |
| |
| 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; |
| } |
| } |
-
模拟
-
首先排除特殊情况,当 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; |
| StringBuilder mp[] = new StringBuilder[numRows]; |
| for (int i = 0; i < numRows; i ++) { |
| 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(); |
| } |
| } |
- 模拟
- 循环倒除得到每一位,再反向乘加即可
- 最大值通过
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; |
| } |
| } |
- 模拟
- 首先去除空格,然后判断起始字符是否为
+
或 -
- 判断溢出时,最大值通过
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; |
| |
| int maxn = Integer.MAX_VALUE / 10; |
| int minn = Integer.MIN_VALUE / 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; |
| } |
| } |
| 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; |
| } |
| } |
- 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 ++) { |
| |
| 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]; |
| } |
| } |
- 双指针
- 设
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) { |
| |
| 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; |
| } |
| } |
- 模拟
- 按照题目规则转换
- 每次都选择尽量大的位数进行转换即可
| 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(); |
| } |
| } |
- 模拟
- 反过来模拟即可
- 从右至左,若当前罗马字母比右边的小,则说明需要减去,否则做加法即可
| 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; |
| } |
| } |
- 模拟
- 初始化公共前缀为
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; |
| } |
| } |
- 双指针
- 首先将数组从小到大排序,使得数组单调
- 则要寻找三数之和为 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 ++) { |
| |
| 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 --; |
| } |
| } |
| |
| while (i + 1 < n && nums[i + 1] == nums[i]) i ++; |
| } |
| return ans; |
| } |
| } |
- 双指针
- 和上一题思路相近,不同的是我们需要维护一个
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; |
| } |
| } |
- DFS
- 递归的每一层视作对
digits[0]
所对应映射 "xxx"
的枚举
- 每一层中,利用循环枚举
"xxx"
的每一位,然后继续递归
- 当递归的层数
u == digits.length()
时将当前累计的字符串加入答案列表并回溯
| class Solution { |
| private static String vis[] = new String[]{ |
| "", "", |
| "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; |
| |
| StringBuilder res = new StringBuilder(); |
| dfs(digits, 0, res, ans); |
| return ans; |
| } |
| |
| private void dfs(String digits, int u, StringBuilder res, List<String> ans) { |
| |
| 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)); |
| dfs(digits, u + 1, res, ans); |
| res.deleteCharAt(res.length() - 1); |
| } |
| } |
| } |
- 双指针
- 三数之和基础上,枚举第一个数
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]; |
| 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; |
| } |
| } |
- 模拟
- 遍历一遍链表得到链表长度
size
- 特判:当
size <= 1
或 n - size == 0
时返回 null
- 遍历链表,当
idx == n - size - 1
说明下一个节点即为要删除的节点,直接修改指向即可
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| 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
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| 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; |
| } |
| } |
- 模拟
- 用一个栈维护当前存在的左括号
- 若
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(); |
| } |
| } |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| 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; |
| } |
| } |
- 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); |
| } |
| } |
- 模拟
- 循环枚举链表数组里的链表,一一合并,时间复杂度 O(nk2)
- 特判,当
lists.length == 0
时返回 null
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| class Solution { |
| public ListNode mergeKLists(ListNode[] lists) { |
| int n = lists.length; |
| if (n == 0) return null; |
| |
| 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; |
| } |
| } |
优化:
- 归并
- 用两两归并代替循环合并,时间复杂度 O(nklog2k)
- 每一轮的合并中,从第一个链表开始,将它与它后面的第
cnt
个链表合并,然后将合并结果存储在第一个链表的位置上。
- 然后继续从第一个链表开始,将它与它后面的第
2 * cnt
个链表合并,再将合并结果存储在第一个链表的位置上。
- 以此类推,直到所有链表都被合并即
cnt >= n
为止。
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| class Solution { |
| public ListNode mergeKLists(ListNode[] lists) { |
| int n = lists.length; |
| if (n == 0) return null; |
| |
| 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; |
| } |
| |
| 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; |
| } |
| } |
- 模拟
- 用一个
ListNode t
指向当前要交换的节点对中的左节点(下一次交换的前一个节点)
- 则每次交换过程中,左右节点分别为
l = t.next, r = t.next.next
- 先用
t
指向 r
,再用 l
指向 r
指向的节点完成 l
替换 r
- 再让
r
指向 l
完成 r
替换 l
- 最后
t
指向 l
,即下一次交换的前一个节点
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| 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; |
| ListNode r = t.next.next; |
| t.next = r; |
| l.next = r.next; |
| r.next = l; |
| t = l; |
| } |
| return ans.next; |
| } |
| } |
- 模拟
- 本质上就是修改链表节点指向
- 即,每组的第一个节点指向本组最后节点指向的节点
- 然后每组第一个节点后的节点依次指向前节点
如图:
| k = 3 |
| node1 -> node2 -> node3 -> node4 -> null |
| node1 -> node4 |
| node2 -> node1 |
| node3 -> node2 |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| 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; |
| } |
| } |
- 模拟
- 由于数组单调且元素唯一,显然有
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]; |
| nums[idx ++] = nums[i]; |
| } |
| } |
| return idx; |
| } |
| } |
- 模拟
- 设
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; |
| } |
| } |
- AC自动机
- 这道题非常的难啊!
- 既然出题人本意不想让我们循环暴力、直接调库或者KMP这种简单的算法
- 那我们只好按出题人的意思来了,直接祭大招好了
| class Solution { |
| class Node { |
| Node[] children; |
| Node fail; |
| List<Integer> indices; |
| |
| public Node() { |
| children = new Node[26]; |
| fail = null; |
| indices = new ArrayList<>(); |
| } |
| } |
| |
| public int strStr(String haystack, String needle) { |
| if (needle.isEmpty()) { |
| return 0; |
| } |
| |
| Node root = buildTrie(needle); |
| 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']; |
| } |
| } |
| } |
- 位运算
- 特殊情况:被除数
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); |
| if (res > Integer.MAX_VALUE - (1 << i)) { |
| return Integer.MIN_VALUE; |
| } |
| res += (1 << i); |
| } |
| } |
| return flag ? -res : res; |
| } |
| } |
- 滑窗
- 用
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; |
| } |
| } |