2022届秋招面试，大厂必问算法面试题
学长在这里准备了一百道LeetCode算法热题，本来准备分十天发完。后面想了一下马上就就月份了，早点更完学弟学妹们准备的时间也越多，鏖战一整晚整理出BATJ大厂常问一百道算法面试题，也在这里尽一些微薄之力
这里还有一份视频教程
直达地址：https://www.bilibili.com/video/BV1Vb4y1f7kK?p=2
老师也是讲的特别详细，对于刚入门学算法的学弟学妹完全能听懂！！！
1. 两数之和
思路一：暴力遍历所有组合
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[] {
i, j};
}
}
}
//没找到
return new int[] {
-1, -1};
}
}
思路二：利用map，key存储元素凑成target所需的差值，value存储元素下标
class Solution {
public int[] twoSum(int[] nums, int target) {
//value代表下标，key代表target与当前元素只差，即：target - nums[value]
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
return new int[] {
map.get(nums[i]), i};
} else {
map.put(target - nums[i], i);
}
}
//没找到
return new int[] {
-1, -1};
}
}
2. 两数相加
思路：直接模拟加法
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode cur1 = l1;
ListNode cur2 = l2;
//哑结点
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
//进位
int carry = 0;
while (cur1 != null || cur2 != null || carry != 0) {
int val1 = cur1 != null ? cur1.val : 0;
int val2 = cur2 != null ? cur2.val : 0;
int sum = val1 + val2 + carry;
int reminder = sum % 10;
carry = sum / 10;
//尾插法
ListNode tempNode = new ListNode(reminder);
cur.next = tempNode;
cur = cur.next;;
if (cur1 != null) cur1 = cur1.next;
if (cur2 != null) cur2 = cur2.next;
}
return dummy.next;
}
}
3. 无重复字符的最长子串
class Solution {
public int lengthOfLongestSubstring(String s) {
//窗口左右边界，左闭右开
int left = 0, right = 0;
//存储字符及其在窗口中的个数
Map<Character, Integer> window = new HashMap<>();
int maxLen = 0;
while (right < s.length()) {
//窗口扩大
char rightChar = s.charAt(right);
right++;
window.put(rightChar, window.getOrDefault(rightChar, 0) + 1);
//如果新加入窗口的字符个数大于1次，窗口应该收缩
while(window.get(rightChar) > 1) {
char leftChar = s.charAt(left);
left++;
window.put(leftChar, window.get(leftChar) - 1);
}
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}
}
4. 寻找两个正序数组的中位数
思路一：直接合并两个有序数组，根据数组长度求中位数。时间复杂为O(m+n)，空间复杂度为O(m+n)
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[] tempArr = new int[m + n];
int i = 0, j = 0;
int k = 0;
while(i < m && j < n) {
if (nums1[i] < nums2[j]) {
tempArr[k++] = nums1[i++];
} else {
tempArr[k++] = nums2[j++];
}
}
//nums1还有剩余
while (i < m) {
tempArr[k++] = nums1[i++];
}
//nums2还有剩余
while (j < n) {
tempArr[k++] = nums2[j++];
}
int midIndex = (m + n) / 2;
double mid = 0;
//长度为偶数
if ((m + n) % 2 == 0) {
mid = (tempArr[midIndex - 1] + tempArr[midIndex]) / 2.0;
} else {
mid = tempArr[midIndex];
}
return mid;
}
}
思路二：无需真正合并数组，先根据两个数组的长度确定中位数是合并后数组中的第几个数，然后根据规则将指向两个数组的下标移动对应次数就好。时间复杂为O(m+n)，空间复杂度为O(1)
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
//i, j分别表示nums1和nums2的分割线，i为[0, m]，j为[0, n];
//[0, i)表示nums1中已经遍历过的下标，对应j类似
int i = 0, j = 0;
//记录最新遍历的两个数
int newest = 0, secondNew = 0;
//奇数：中位数是第(m+n)/2 + 1个数（下标从1开始）
//偶数：中位数是第(m+n)/2和第(m+n)/2 + 1数的平均数（下标从1开始）
int cnt = (m + n) / 2 + 1;
for (int k = 0; k < cnt; k++) {
secondNew = newest;
// j >= n 表示指向nums2已经没有元素
if (j >= n || (i < m && nums1[i] < nums2[j])) {
newest = nums1[i];
i++;
} else {
newest = nums2[j];
j++;
}
}
//偶数
if ((m + n) % 2 == 0) {
return (newest + secondNew) / 2.0;
} else {
return newest;
}
}
}
终于说服自己
思路三：使用二分法直接在两个数组中找中位数分割线，使得nums1和nums2中分割线满足以下性质即可根据分割线左右的数来确定中位数：
前置：m = nums1.length，n = nums2.length。设i为nums1中分割线，则取值为[0, m]，表示分割线左侧元素下标为[0, i-1]，分割线右侧元素下标为[i, m-1]；设j为nums2中分割线，…。
-
m+n为偶数：i + j = (m + n )/2，为奇数：i + j = (m + n)/2 + 1。 -
分割线左侧元素小于等于分割线右侧元素。由于两个数组均为正序数组，则只需要要求：
nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i]；由于该条件等价于在[0, m]中找到最大的i使得nums1[i-1] <= nums2[j]，因此可以使用二分查找。（证明：假设我们已经找到了满足条件的最大i，使得nums1[i-1] <= nums2[j]，那么此时必有nums[i] > nums2[j]，进而有nums[i] > nums2[j-1]）
分割线找到后，若m+n为奇数，分割线左侧的最大值即为中位数；若为偶数，分割线左侧的最大值与分割线右侧的最小值的平均数即为中位数。时间复杂度：O(log(min(m, n)))，空间复杂度：O(1)
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 始终保证nums1为较短的数组，nums1过长可能导致j为负数而越界
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.length;
int n = nums2.length;
// m+n 为奇数，分割线要求左侧有 (m+n)/2 + 1 个元素
// m+n 为偶数，分割线要求左侧有 (m+n)/2 个元素
// 两种情况其实可以统一写作 (m+n+1)/2，表示对(m+n)/2向上取整
// 对整数来说，向上取整等于：(被除数 + (除数 - 1)) / 除数
// 也可以使用Math类中提供的库函数
int leftTotal = (m + n + 1) / 2;
int left = 0, right = m;
while (left < right) {
// +1 向上取整避免 left + 1 = right 时可能无法继续缩小区间而陷入死循环
int i = left + (right - left + 1) / 2;
int j = leftTotal - i;
//要找最大i，使得nums1[i-1] <= nums2[j]
//使用对立面缩小区间
if (nums1[i - 1] > nums2[j]) {
// [i+1, m]均不满足
right = i - 1;
} else {
// i满足说明[0, i-1]均不为满足条件的最大i，舍去以缩小区间
left = i;
}
}
//退出循环时left=right，表示最终nums1中分割线的位置
int i = left;
//nums2中分割线的位置
int j = leftTotal - left;
System.out.println(i);
//判断极端情况
int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1]; //nums1分割线左边没有元素
int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; //nums2分割线左边没有元素
int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i]; //nums1分割线右边没有元素
int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j]; //nums2分割线右边没有元素
if ((m + n) % 2 == 0) {
return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2.0;
} else {
return Math.max(nums1LeftMax, nums2LeftMax);
}
}
}
备注：这里使用的二分法和二分法查找x的平方根使用的方法很像，都是要查找满足条件的最大值。
5. 最长回文子串
思路：动态规划获取任意两个区间的子串是否为回文子串，如果是则记录开始下标和长度
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
int maxLen = 0;
int start = 0;
//dp[i][j]: 字符串s[i, j]是否为回文字符串
boolean[][] dp = new boolean[len][len];
for (int j = 0; j < len; j++) {
for (int i = 0; i <= j; i++) {
if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (j - i + 1 > maxLen) {
maxLen = j - i + 1;
start = i;
}
}
}
}
return s.substring(start, start + maxLen);
}
}
6. 正则表达式匹配
class Solution {
public boolean isMatch(String s, String p) {
int sLen = s.length();
int pLen = p.length();
//状态：dp[i][j] 表示s的前i个字符和p的前j个字符能否匹配，即 s[0, i-1] 和 p[0, j-1] 能否匹配
boolean[][] dp = new boolean[sLen + 1][pLen + 1];
//前置：i, j分别代表dp的横、纵下标，对应的s、p的下标都应减去1
//初始值：dp 默认都为flase
//dp[0][0] = true, 即s和p都为空
//dp[i][0] = false, 其中i >= 1, 即s不为空p为空
//dp[0][1] = false, 由于p[0]不能为*，s为空，p只有一个字符且不为'*'的情况下必然不能匹配成功
//s为空，p不为空且p[0, j-1]以'*'结尾时，还不能直接断定dp的值。
//因为'*'可以选择将它前面的字符匹配零次以消除'*'前面的字符。
//因此 dp[0][j] = dp[0][j - 2], j >= 2。若s为空，p不为空且 p[0, j-1] 不以'*'结尾，那么有：
//dp[0][j] = false, j >= 1。
dp[0][0] = true;
for (int j = 2; j < pLen + 1; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 2];
}
}
//状态转移：
//当 s[0, i-1] 和 p[0, j-1] 的末尾字符相等或p的末尾字符为'.'，则有：dp[i][j] = dp[i - 1][j - 1];
//当 p[0, j-1] 的末尾字符即 p[j - 1] 为'*'需要讨论：
// 若 s[i - 1] 与 p[j - 2] 相等，如：s(ab), p(cab*)，那么*可以选择将b 重复一次 则s末尾的b和p末尾的b*匹配抵消，
// 则有：dp[i][j] = dp[i - 1][j - 2]；
// 同时*也可以选择将b 重复多次 以匹配抵消s中最后一个b，此时p虽然也损失一个b但任然还剩多个b，可以将其看成b*
// 故有：dp[i][j] = dp[i - 1][j];
// 此外*也可以选择将b 去掉，故：dp[i][j] = dp[i][j - 2]
// 综上：dp[i - j] = dp[i - 1][j - 2] || dp[i - 1]dp[j] || dp[i][j - 2]
// 若 p[j - 2] 为 '.'，同上
// 若 s[i - 1] 与 p[j - 2] 不等且后者不为'.'，如：s(ab), p(eabd*)，那么*可以选择将d 去掉 ，
// 则有：dp[i][j] = dp[i][j - 2]
for (int j = 1; j < pLen + 1; j++) {
for (int i = 1; i < sLen + 1; i++) {
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) == '*') {
if (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
dp[i][j] = dp[i - 1][j -2] || dp[i - 1][j] || dp[i][j - 2];
} else {
dp[i][j] = dp[i][j - 2];
}
}
}
}
return dp[sLen][pLen];
}
}
7. 盛最多水的容器
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxArea = 0;
while (left < right) {
int width = right - left;
int high = Math.min(height[left], height[right]);
int area = width * high;
maxArea = Math.max(area, maxArea);
//左边小则直接去掉，因为它和右边剩余的任意一个元素组成的面积都不会比当前更大
if (height[left] < height[right]) {
left++;
//去掉右边
} else {
right--;
}
}
return maxArea;
}
}
8. 三数之和
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new LinkedList<>();
if (nums == null || nums.length < 3) {
return res;
}
//排序很重要
Arrays.sort(nums);
int len = nums.length;
for (int i = 0; i < len - 2; i++) {
//最后两个数不用判断
//三数之和一定大于0，后序必然不存在为0的组合
if (nums[i] > 0) break;
//去重
if (i > 0 && nums[i] == nums[i - 1]) continue;
// left right 表示了 i 的右侧闭合区间
int left = i + 1;
int right = len - 1;
while (left < right) {
int target = nums[i] + nums[left] + nums[right];
if (target == 0) {
res.add(Arrays.asList(new Integer[] {
nums[i], nums[left], nums[right]}));
//去重
while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (target < 0) {
left++;
} else if (target > 0) {
right--;
}
}
}
return res;
}
}
9. 电话号码的字母组合
回溯法即可
class Solution {
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() < 1) {
return res;
}
Map<Character, Character[]> map = new HashMap<>() {
{
put('2', new Character[] {
'a', 'b', 'c'});
put('3', new Character[] {
'd', 'e', 'f'});
put('4', new Character[] {
'g', 'h', 'i'});
put('5', new Character[] {
'j', 'k', 'l'});
put('6', new Character[] {
'm', 'n', 'o'});
put('7', new Character[] {
'p', 'q', 'r', 's'});
put('8', new Character[] {
't', 'u', 'v'});
put('9', new Character[] {
'w', 'x', 'y', 'z'});
}
};
StringBuilder track = new StringBuilder();
dfs(map, digits, 0, track);
return res;
}
//存放最终的结果
private List<String> res = new LinkedList<>();
//回溯法获取所有结果
private void dfs(Map<Character, Character[]> map, String digits, int index, StringBuilder track) {
if (digits.length() == index) {
res.add(track.toString());
return;
}
Character[] charArr = map.get(digits.charAt(index));
for (int i = 0; i < charArr.length; i++) {
//选择
track.append(charArr[i]);
dfs(map, digits, index+1, track);
//撤销选择
track.deleteCharAt(index);
}
}
}
10. 删除链表的倒数第 N 个结点
思路：快慢指针都指向头，快指针先移动n，接着快慢指针一起向后移动，直至快指针到达末尾，此时根据满指针即可删除倒数第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 removeNthFromEnd(ListNode head, int n) {
//删除的可能是头结点，所以需要哑结点
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode fast =dummyNode, slow = dummyNode;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
//删除结点
slow.next = slow.next.next;
return dummyNode.next;
}
}
11. 有效的括号
class Solution {
public boolean isValid(String s) {
Map<Character, Character> map = new HashMap<>() {
{
put(')', '(');
put('}', '{');
put(']', '[');
}
};
Deque<Character> stack = new LinkedList<>();
for(int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
//ch为左括号，直接入栈
if (!map.containsKey(ch)) {
stack.push(ch);
} else {
//ch为右括号，检查ch与栈顶元素是否配对
if (stack.isEmpty() || stack.pop() != map.get(ch)) {
return false;
}
}
}
//遍历完所有括号后，stack为空则说明有效
return stack.isEmpty();
}
}
12. 合并两个有序链表
迭代版：
/** * 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 l1, ListNode l2) {
ListNode dummyNode = new ListNode(-1);
ListNode temp = dummyNode;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
temp.next = l1;
l1 = l1.next;
} else {
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
if (l1 != null) temp.next = l1;
if (l2 != null) temp.next = l2;
return dummyNode.next;
}
}
递归版：编写递归程序时一定不要用自己脑袋去模拟递归栈，而是要根据已知函数定义来写代码
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//base case
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
13. 括号生成
思路：对于只有一种括号的情况，要生成合法括号字符串只需要满足：
-
左边的的括号数不多于括号对数
-
右边的括号数不多于左边的括号数
因此，只需要用回溯法生成所有组合，然后除去不符合条件的即可
class Solution {
public List<String> generateParenthesis(int n) {
char[] candidates = new char[] {
'(', ')'};
StringBuilder track = new StringBuilder();
dfs(candidates, track, n, 0, 0);
return res;
}
private List<String> res = new LinkedList<>();
//left, right 分别记录当前track中左括号和右括号的数量
private void dfs(char[] candidates, StringBuilder track, int n, int left, int right) {
//去除不符合条件的结果，剪枝
if (left > n || right > left) return;
if (track.length() == 2*n) {
res.add(track.toString());
return;
}
for (int i = 0; i < candidates.length; i++) {
//选择
track.append(candidates[i]);
if (candidates[i] == '(') {
dfs(candidates, track, n, left + 1, right);
} else if (candidates[i] == ')') {
dfs(candidates, track, n, left, right + 1);
}
//撤销
track.deleteCharAt(track.length() - 1);
}
}
}
14. 合并K个升序链表
思路一：循环依次合并链表
思路二：两两归并
/** * 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) {
if (lists == null || lists.length == 0) {
return null;
}
return mergeKLists(lists, 0, lists.length - 1);
}
//合并数组中下标在[left, right]之间的链表
private ListNode mergeKLists(ListNode[] lists, int left, int right) {
if (left == right) {
return lists[left];
}
int mid = left + (right - left) / 2;
ListNode leftList = mergeKLists(lists, left, mid);
ListNode rightList = mergeKLists(lists, mid + 1, right);
return mergeTwoList(leftList, rightList);
}
private ListNode mergeTwoList(ListNode l1, ListNode l2) {
ListNode dummyNode = new ListNode(-1);
ListNode temp = dummyNode;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
temp.next = l1;
l1 = l1.next;
} else {
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
if (l1 != null) temp.next = l1;
if (l2 != null) temp.next = l2;
return dummyNode.next;
}
}
思路三：优先队列
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
//优先队列，小的链表结点位于队列前
Queue<ListNode> pq = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
pq.offer(lists[i]);
}
}
ListNode dummyNode = new ListNode(-1);
ListNode temp = dummyNode;
while (!pq.isEmpty()) {
ListNode minNode = pq.poll();
temp.next = minNode;
temp = minNode;
if (minNode.next != null) {
pq.offer(minNode.next);
}
}
return dummyNode.next;
}
}
15. 下一个排列
简单来说，对于数字排列来说字典顺序可以理解为升序。
class Solution {
public void nextPermutation(int[] nums) {
int len = nums.length;
//从右往左找找第一对升序数的位置，i指向较大元素
int i = len - 1;
while (i >= 1 && nums[i] <= nums[i - 1]) {
i--;
}
//存在升序对时：
//最坏情况下，交换升序对 nums[i - 1]、 nums[i]即可找到下一个排列;
//好点的情况下，升序对右侧（低位）可能存在 nums[k] 大于 nums[i - 1]，那么交换他们即可;
if (i >= 1) {
for (int k = len - 1; k >= i; k--) {
if (nums[k] > nums[i - 1]) {
swap(nums, k, i - 1);
break;
}
}
}
reverse(nums, i, len - 1);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int i, int j) {
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
}
16. 最长有效括号
思路：利用栈存储下标，方便计算有效括号子串长度。
- 首先将
-1入栈垫底 - 当字符为
'('，直接将下标入栈 - 当字符为
')'，弹出栈顶元素，若此时栈不为空，说明配对成功，然后用’)‘下标减去此时栈顶元素下标即为当前有效括号子串长度；若此时栈为空，说明未配对成功，直接将’)'下标入栈垫底。
class Solution {
public int longestValidParentheses(String s) {
Deque<Integer> stack = new LinkedList<>();
stack.push(-1);
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else if (s.charAt(i) == ')'){
stack.pop();
// ) 配对成功
if (!stack.isEmpty()) {
maxLen = Math.max(maxLen, i - stack.peek());
// ) 配对失败
} else {
stack.push(i);
}
}
}
return maxLen;
}
}
17. 搜索旋转排序数组
思路：可知旋转后的数组分为前后两段，都为升序，且前面一段始终大于后面一段。可以利用二分法，始终拿 nums[mid] 和 nums[right] 比较然后缩小范围，具体如下：
- 若
nums[mid]小于nums[right]， 说明 mid 位于后半段，那么nums[mid, right]有序； - 若
nums[mid]大于nums[right]， 说明 mid 位于前半段，那么nums[left, mid]有序。找到有序区间后可以根据target值快速缩小区间。
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
//跳出循环时，left、 right 相邻，且都可能为target
while (left + 1 < right) {
int mid = left + (right - left) / 2;
//找到了
if (nums[mid] == target) {
return mid;
// mid 位于后半段上升段
} else if (nums[mid] < nums[right]) {
// target 位于[mid, right]之间
if (target >= nums[mid] && target <= nums[right]) {
left = mid;
} else {
right = mid;
}
// mid 位于前半段上升段
} else if (nums[mid] > nums[right]) {
// target 位于 [left, mid]之间
if (target >= nums[left] && target <= nums[mid]) {
right = mid;
} else {
left = mid;
}
}
// 由于 left + 1 < right，且nums不包含重复数，故不可能出现nums[mid] == nums[right]的情况
}
if (nums[left] == target) return left;
if (nums[right] == target) return right;
return -1;
}
}
18. 在排序数组中查找元素的第一个和最后一个位置
思路：带边界二分查找，利用 while (left + 1 < right)容易处理边界条件。
class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums.length <= 0) return new int[] {
-1, -1};
//左边界
int left = searchBorder(nums, target, Border.LEFT);
if (left == -1) return new int[] {
-1, -1};
//右边界
int right = searchBorder(nums, target, Border.RIGHT);
return new int[] {
left, right};
}
private int searchBorder(int[] nums, int target, Border border) {
int left = 0;
int right = nums.length - 1;
//跳出循环时，left、 right 相邻，且都可能为target
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
//查找左边界
if (border == Border.LEFT) {
right = mid;
//查找右边界
} else if (border == Border.RIGHT) {
left = mid;
}
} else if (nums[mid] > target) {
right = mid;
} else if (nums[mid] < target) {
left = mid;
}
}
//没找到
if (nums[left] != target && nums[right] != target) {
return -1;
}
//查找左边界，优先返回左边元素
if (border == Border.LEFT) {
return nums[left] == target ? left : right;
//查找右边界，优先返回右边元素
} else if (border == Border.RIGHT) {
return nums[right] == target ? right : left;
} else {
throw new IllegalArgumentException("非法选项");
}
}
}
//使用枚举代替静态变量
enum Border {
LEFT, RIGHT
}
19. 组合总和
思路：回溯法
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
LinkedList<Integer> track = new LinkedList<>();
Arrays.sort(candidates); //排序后可实现进一步剪枝
dfs(candidates, track, target, 0);
return res;
}
private List<List<Integer>> res = new LinkedList<>();
private void dfs(int[] candidates, LinkedList<Integer> track, int target, int start) {
//不会再出现target小于0的情况
//base case
if (target == 0) {
res.add(new LinkedList<>(track));
return;
}
//通过start改变可选列表
for (int i = start; i < candidates.length; i++) {
//由于此时candidates是有序的，candidates[i] 后面的元素都大于target，直接忽略
if (target - candidates[i] < 0) {
break;
}
track.offerLast(candidates[i]);
dfs(candidates, track, target - candidates[i], i);
track.pollLast();
}
}
}
20. 接雨水
推荐一种不使用单调栈而是使用备忘录的解法：
思路一：在左边找大于等于当前高度的最大值，右边也找大于等于当前高度的最大值，两者取最小值再减去当前高度即为当前下标所能接的雨水量。
class Solution {
public int trap(int[] height) {
if (height == null || height.length <= 2) {
return 0;
}
int len = height.length;
//分别记录元素左边和右边的最大值
int[] leftMax = new int[len];
int[] rightMax = new int[len];
//最左边元素左边的最大值
leftMax[0] = height[0];
//最右边元素右边的最大值
rightMax[len - 1] = height[len - 1];
for (int i = 1; i < len; i++) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
for (int i = len - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
int area = 0;
for (int i = 1; i < len - 1; i++) {
area += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return area;
}
}
思路二：单调栈
class Solution {
public int trap(int[] height) {
if (height == null || height.length <= 2) {
return 0;
}
//用来存储元素下标
Deque<Integer> stack = new LinkedList<>();
int area = 0;
for (int i = 0; i < height.length; i++) {
while(!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop();
if (stack.isEmpty()) {
break;
}
int width = i - stack.peek() - 1;
int high = Math.min(height[stack.peek()], height[i]) - height[top];
area += width * high;
}
//入栈
stack.push(i);
}
return area;
}
}
21. 全排列
思路：典型回溯法
class Solution {
public List<List<Integer>> permute(int[] nums) {
LinkedList<Integer> track = new LinkedList<>();
boolean[] visited = new boolean[nums.length];
dfs(nums, track, visited);
return res;
}
private List<List<Integer>> res = new LinkedList<>();
private void dfs(int[] nums, LinkedList<Integer> track, boolean[] visited) {
//base case
if (track.size() == nums.length) {
res.add(new LinkedList<>(track));
return;
}
for (int i = 0; i < nums.length; i++) {
//剪枝
if (visited[i]) continue;
// 选择
track.offerLast(nums[i]);
visited[i] = true;
dfs(nums, track, visited);
//撤销选择
track.pollLast();
visited[i] = false;
}
}
}
22. 旋转图像
思路：（技巧题，记住就好）
- 先沿对角线翻转
- 然后每一行按中间元素翻转
class Solution {
public void rotate(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
for (int i = 0; i < row; i++) {
for (int j = i + 1; j < row; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
for (int i = 0; i < row; i++) {
int left = 0;
int right = col - 1;
while (left < right) {
int temp = matrix[i][left];
matrix[i][left] = matrix[i][right];
matrix[i][right] = temp;
left++;
right--;
}
}
}
}
23. 字母异位词分组
思路：根据字母异位词定义可知：
- 互为异位词的字符串根据字符排序后得到的字符串相同；
- 互为异位词的字符串中各个字符的出现次数相同。
因此有两种方法：排序法、计数法。
排序法：
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] strArr = str.toCharArray();
Arrays.sort(strArr);
String orderStr = new String(strArr);
List<String> list = map.getOrDefault(orderStr, new LinkedList<>());
list.add(str);
map.put(orderStr, list);
}
return new ArrayList<List<String>>(map.values());
}
}
计数法：
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
//统计str中字符出现次数
int[] count = new int[26];
for (int i = 0; i < str.length(); i++) {
count[str.charAt(i) - 'a']++;
}
//拼接key
StringBuilder sb = new StringBuilder();
for (int i = 0; i < count.length; i++) {
if (count[i] > 0) {
sb.append('a' + i);
sb.append(count[i]);
}
}
String key = sb.toString();
List<String> list = map.getOrDefault(key, new LinkedList<>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
23. 最大子序和
思路：动态规划
class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
//以当前位置结尾的子数组的最大和
int[] dp = new int[len];
//base case
dp[0] = nums[0];
int max = dp[0];
//转移方程：若dp[i - 1] 大于 0， dp[i] = dp[i - 1] + nums[i];否则 dp[i] = nums[i];
for (int i = 1; i < len; i++) {
if (dp[i - 1] > 0) {
dp[i] = dp[i - 1] + nums[i];
} else {
dp[i] = nums[i];
}
max = Math.max(max, dp[i]);
}
return max;
}
}
以上代码可以看出当前状态只与前一个状态相关，故可以将 空间复杂度由O(n) 降到O(1):
class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
int sum = nums[0];
int max = sum;
for (int i = 1; i < len; i++) {
if (sum > 0) {
sum = sum + nums[i];
} else {
sum = nums[i];
}
max = Math.max(max, sum);
}
return max;
}
}
24. 跳跃游戏
思路一：动态规划，推荐
class Solution {
public boolean canJump(int[] nums) {
int len = nums.length;
//起始位置能否跳至当前位置
boolean[] dp = new boolean[len];
//base case
dp[0] = true;
//转移方程：i前面所有的点只要有一个能跳到当前结点就说明当前结点可达
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && (j + nums[j] >= i)) {
dp[i] = true;
break;
}
}
}
return dp[len - 1];
}
}
思路二：贪心，时间复杂度更低，多数靠死记硬背。如果能用动态规划就尽量用动规，超时了再说
class Solution {
public boolean canJump(int[] nums) {
int len = nums.length;
//目前从起点能调到的最远位置
int maxFar = 0;
for (int i = 0; i <= maxFar; i++) {
if (nums[i] + i > maxFar) {
maxFar = nums[i] + i;
}
if (maxFar >= (len - 1)) {
return true;
}
}
return false;
}
}
26. 合并区间
class Solution {
public int[][] merge(int[][] intervals) {
int len = intervals.length;
//按照 左 边界排序
Arrays.sort(intervals, (arr1, arr2) -> arr1[0] - arr2[0]);
int[][] res = new int[len][2];
//i指向新区间的第一个小区间，k为合并后的新区间个数
int i = 0, k = 0;
while (i < len) {
int left = intervals[i][0];
//合并区间的过程就是修改right的过程
int right = intervals[i][1];
//寻找可以合并的区间并完成合并
int j = i + 1;
while (j < len && right >= intervals[j][0]) {
right = Math.max(right, intervals[j][1]);
j++;
}
//存储新区间的范围
res[k][0] = left;
res[k][1] = right;
k++;
i = j;
}
return Arrays.copyOf(res, k);
}
}
27. 不同路径
思路：动态规划
-
状态：从起点到当前结点的不同路径数。
-
转移方程：起点到当前点的不同路径数
dp[i][j]等于：起点到当前结点相邻左结点dp[i][j - 1]和相邻上结点dp[i - 1][j]不同路径数之和。 -
base case：第0行
dp[0][x]和0列dp[x][0]都为1，前者只能通过其相邻左节点到达，后者只能通过相邻上结点到达。
class Solution {
public int uniquePaths(int m, int n) {
//状态
int dp[][] = new int[m][n];
//base case
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
dp[i][0] = 1;
}
//转移方程
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
return dp[m - 1][n - 1];
}
}
28. 最小路径和
思路：动态规划，和上一题相似。
-
状态：起点到当前结点的最小路径和
-
转移方程：起点到当前结点最小路径和
dp[i][j]等于：min(起点到其相邻左结点最小路径和dp[i][j - 1]，起点到其相邻上结点最小路径和dp[i - 1][j]) + 当前结点值grid[i][j] -
base case:
dp[0][0] = grid[0][0]; 第一行dp[0][x]都为其相邻左结点dp[0][x -1]+ 自身结点值grid[0][x],x >= 1;第一列dp[x][0]都为其相邻上结点dp[x - 1][0]+ 自身结点值grid[x][0],x >= 1。
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
//从左上角到i, j的最短路径和
int[][] dp = new int[m][n];
//base case
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int i = 1; i < n; i++) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
//转移方程
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp [i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
}
29. 爬楼梯
思路：动态规划
-
状态：从第0个台阶跳到当前台阶的不同方式
-
转移方程：第0个台阶到当前台阶的不同方式
dp[i]等于：第0个台阶到当前台阶下面两个台阶的不同方式之和(dp[i - 1] + dp[i - 2]) -
base case:
dp[0] = dp[1] = 1
class Solution {
public int climbStairs(int n) {
//状态：从第0个台阶跳到当前台阶的不同方式
int[] dp = new int[n + 1];
//base case
dp[0] = 1;
dp[1] = 1;
//转移方程
for (int i = 2; i < n + 1; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
30. 编辑距离
思路：动态规划
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
//word1 前m个字符和 word2 前n个字符之间的编辑距离，z
int[][] dp = new int[m + 1][n + 1];
//base case
dp[0][0] = 0;
for (int i = 1; i < m + 1; i++) {
dp[i][0] = i;
}
for (int i = 1; i < n + 1; i++) {
dp[0][i] = i;
}
//状态转移
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
//最后一个字符相等
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
//不等则分别进行 替换、删除word1中最后一个字符，或在word1最后插入一个字符，取代价最小的一个
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
}
}
}
return dp[m][n];
}
}
31. 颜色分类
思路：将 2 往后放，0 往前放，剩余的1自然就放好了。
- 使用双指针：left、right 分别指向待插入的 0 和 2 的位置，初始 left 指向数组头，right 指向数组尾部。
- 从头开始遍历数组，若当前位置数为 2 则与 right 所指向元素互换，然后 right 左移，直到当前位置元素不为2；
- 当前位置元素若为 0 则 和 left 所指元素互换，然后 left 右移。随后接着遍历，直到 和 right相遇。
class Solution {
public void sortColors(int[] nums) {
int left = 0;
int right = nums.length - 1;
for (int i = 0; i <= right; i++) {
//将2往后放
while (i <= right && nums[i] == 2) {
swap(nums, i, right);
right--;
}
//将0往前放
if (nums[i] == 0) {
swap(nums, i, left);
left++;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
32. 最小覆盖子串
思路：标准滑动窗口
class Solution {
public String minWindow(String s, String t) {
//记录 t 中字符在 window 中的出现频次
Map<Character, Integer> window = new HashMap<>();
//记录 t 中各个字符的频次
Map<Character, Integer> need = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
}
//窗口边界，左闭右开
int left = 0, right = 0;
// t 中字符在 window 中已经匹配的个数
int match = 0;
//最小子串的起始位置和长度
int start = 0, minLen = Integer.MAX_VALUE;
while (right < s.length()) {
//窗口扩张（右边界右移）
char rightChar = s.charAt(right);
right++;
//如当前 rightChar 是 t 中的字符
if (need.containsKey(rightChar)) {
// window 中对应次数加 1
window.put(rightChar, window.getOrDefault(rightChar, 0) + 1);
// 仅当 rightChar 在 window 中的频次 小于等于 t 中的频次时才说明新匹配了一个字符(想想t中某个字符出现多次的情况)
if (window.get(rightChar).compareTo(need.get(rightChar)) <= 0) {
match++;
}
}
//如果 window 中已经包含了 t 中所有字符
while (match == t.length()) {
int tempLen = right - left;
if (tempLen < minLen) {
minLen = tempLen;
start = left;
}
//收缩窗口（左边界右移）
char leftChar = s.charAt(left);
left++;
if (need.containsKey(leftChar)) {
if (window.get(leftChar).compareTo(need.get(leftChar)) <= 0) {
match--;
}
window.put(leftChar, window.get(leftChar) - 1);
}
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
}
33. 子集
思路：典型回溯法
lass Solution {
public List<List<Integer>> subsets(int[] nums) {
LinkedList<Integer> track = new LinkedList<>();
dfs(nums, track, 0);
return res;
}
private List<List<Integer>> res = new LinkedList<>();
private void dfs (int[] nums, LinkedList<Integer> track, int start) {
res.add(new LinkedList<>(track));
//通过start来控制当前可以选择的列表
for (int i = start; i < nums.length; i++) {
//选择
track.offerLast(nums[i]);
dfs(nums, track, i + 1);
//撤销选择
track.pollLast();
}
}
}
// {1, 2, 3}对应递归树:
// []
// 1 2 3
// 12 13 23
// 123
34. 单词搜索
思路：直接回溯
class Solution {
public boolean exist(char[][] board, String word) {
boolean[][] visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == word.charAt(0)) {
if (dfs(board, word, 0, visited, i, j)) {
return true;
}
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int index, boolean[][] visited, int row, int col) {
//base case
if (word.length() == index) {
return true;
}
if (!isValid(board, row, col)) {
return false;
}
if (visited[row][col]) {
return false;
}
if (board[row][col] != word.charAt(index)) {
return false;
}
//标记访问过的位置
visited[row][col] = true;
boolean res = dfs(board, word, index + 1, visited, row + 1, col) ||
dfs(board, word, index + 1, visited, row, col + 1) ||
dfs(board, word, index + 1, visited, row - 1, col) ||
dfs(board, word, index + 1, visited, row, col - 1);
//撤销标记
visited[row][col] = false;
return res;
}
private boolean isValid(char[][] board, int row, int col) {
if (row >= 0 && row < board.length && col >= 0 && col < board[0].length) {
return true;
} else {
return false;
}
}
}
35. 柱状图中最大的矩形
思路：单调递增栈，依次遍历数组，大于等于栈顶元素直接入栈，小于则弹栈并计算一次面积。
class Solution {
public int largestRectangleArea(int[] heights) {
int len = heights.length;
int[] newHeight = new int[len + 2];
//将 heights 复制到 newHeight，同时将首尾各填充一个 -1
newHeight[0] = -1;
newHeight[len - 1] = -1;
for (int i = 1; i <= len; i++) {
newHeight[i] = heights[i - 1];
}
int maxArea = 0;
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < newHeight.length; i++) {
//出栈
while (!stack.isEmpty() && newHeight[stack.peek()] > newHeight[i]) {
int high = newHeight[stack.pop()];
int width = i - stack.peek() - 1; // 下标 [stack.peek() + 1, i - 1] 对应元素都 大于等于 high
int area = high * width;
maxArea = Math.max(area, maxArea);
}
//入栈
stack.push(i);
}
return maxArea;
}
}
36. 最大矩形
思路：如下图，分别获取以每一行为底的柱状图，并计算当前柱状图所能围城的最大矩形面积，最后取最大值。
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length <= 0 || matrix[0].length <= 0) {
return 0;
}
int row = matrix.length;
int col = matrix[0].length;
int maxArea = 0;
//根据二维矩阵获取柱状图对应数组
int[] tempHeight = new int[col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == '1') {
tempHeight[j] += 1;
} else {
tempHeight[j] = 0;
}
}
maxArea = Math.max(maxArea, largestRectangleArea(tempHeight));
}
return maxArea;
}
//84. 柱状图中最大的矩形
private int largestRectangleArea(int[] nums) {
int len = nums.length;
int[] newHeight = new int[len + 2];
newHeight[0] = -1;
newHeight[len + 1] = -1;
for (int i = 0; i < len; i++) {
newHeight[i + 1] = nums[i];
}
int maxArea = 0;
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < newHeight.length; i++) {
while (!stack.isEmpty() && newHeight[stack.peek()] > newHeight[i]) {
int high = newHeight[stack.pop()];
int width = i - stack.peek() - 1;
int area = high * width;
maxArea = Math.max(area, maxArea);
}
stack.push(i);
}
return maxArea;
}
}
37. 二叉树的中序遍历
非递归解法：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
TreeNode temp = root;
Deque<TreeNode> stack = new LinkedList<>();
while (temp != null || !stack.isEmpty()) {
while (temp != null) {
stack.push(temp); // 加入栈
temp = temp.left; // 到最左边结点停止
}
temp = stack.pop(); // 访问栈顶元素
res.add(temp.val);
temp = temp.right; //下一个遍历的元素是temp的右子树的最左边结点
}
return res;
}
}
38. 不同的二叉搜索树
思路：动态规划
class Solution {
public int numTrees(int n) {
// 由小到大的 n 个结点所能组成的不同二叉搜索树个数
int[] dp = new int[n + 1];
//base case
dp[0] = 1;
dp[1] = 1;
//状态转移 dp[i] = dp[0]dp[i - 1] + dp[1]dp[i - 2] ... + ... dp[i - 1]dp[0]，即：sum(dp[j - 1] + dp[i - j]), j从1到i
for (int i = 2; i < n + 1; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}
39. 验证二叉搜索树
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
//二叉搜索树的每个结点都有一个上下界（除了根节点）
private boolean isValidBST(TreeNode node, TreeNode low, TreeNode high) {
//base case
if (node == null) {
return true;
}
//base case
if (low != null && node.val <= low.val) return false;
if (high != null && node.val >= high.val) return false;
boolean ret = isValidBST(node.left, low, node) && isValidBST(node.right, node, high);
return ret;
}
}
40. 对称二叉树
class Solution {
public boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
private boolean isMirror(TreeNode node1, TreeNode node2) {
if (node1 == null && node2 == null) {
return true;
}
// 联系前面的判断，此处表示只有一个为null
if (node1 == null || node2 == null) {
return false;
}
return (node1.val == node2.val) && isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
}
}
41. 二叉树的层序遍历
思路：使用队列。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
if (root == null) {
return res;
}
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
// 当前层的结点数目
int size = queue.size();
List<Integer> rowList = new LinkedList<>();
// 每个结点出队时，只要孩子结点不为空就加入队列
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
rowList.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
res.add(rowList);
}
return res;
}
}
42. 二叉树的最大深度
思路：递归，根据定义编写代码。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
public int maxDepth(TreeNode root) {
//base case
if (root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}
43. 从前序与中序遍历序列构造二叉树
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
//base case
if (preStart > preEnd || inStart > inEnd) {
return null;
}
int rootVal = preorder[preStart];
// 该步骤可以通过map优化
int index = findIndexInoreder(rootVal, inorder);
int leftCnt = index - inStart;
TreeNode root = new TreeNode(rootVal);
root.left = build(preorder, preStart + 1, preStart + leftCnt, inorder, inStart, index - 1);
root.right = build(preorder, preStart + leftCnt + 1, preEnd, inorder, index + 1, inEnd);
return root;
}
private int findIndexInoreder(int rootVal, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
if (rootVal == inorder[i]) {
return i;
}
}
throw new IllegalArgumentException("can not find :" + rootVal);
}
}
通过Map优化：
class Solution {
// 通过 map 存储中序序列中各个元素在数组中的下标
private Map<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
//base case
if (preStart > preEnd || inStart > inEnd) {
return null;
}
int rootVal = preorder[preStart];
int index = map.get(rootVal);
int leftCnt = index - inStart;
TreeNode root = new TreeNode(rootVal);
root.left = build(preorder, preStart + 1, preStart + leftCnt, inorder, inStart, index - 1);
root.right = build(preorder, preStart + leftCnt + 1, preEnd, inorder, index + 1, inEnd);
return root;
}
}
44. 二叉树展开为链表
思路：递归：向将左右孩子分别展平，然后先将展平后的左子树连接右孩子上，再将展平后的右子树连接上。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
public void flatten(TreeNode root) {
flat(root);
}
private TreeNode flat(TreeNode root) {
//base case
if (root == null) {
return null;
}
// 先分别将左右子树展平并返回头结点
TreeNode left = flat(root.left);
TreeNode right = flat(root.right);
// 将左子树置为空
root.left = null;
// 先将展平后的左子树连接在右孩子上
root.right = left;
// 找到右子树的最右一个结点
TreeNode temp = root;
while (temp.right != null) {
temp = temp.right;
}
// 连接展平后的右子树
temp.right = right;
return root;
}
}
45. 买卖股票的最佳时机
思路：动态规划。
股票买卖问题通用解法：
状态：dp[i][k][0]，在第i天结束时，允许交易k次的情况下，最终不持有股票能获得的最大利润；dp[i][k][1]，在第i天结束时，允许交易k次的情况下，最终持有股票能获得的最大利润。
base case：dp[-1][k][0] = 0、dp[-1][k][1] = -Infinity；dp[i][0][0] = 0、dp[i][0][1] = -Infinity。其中dp[-1][k][1] = dp[i][0][1] = -Infinity 表示在没有进行股票交易时不允许持有股票。备注：Java中可以用Integer.MIN_VALUE来表示-Infinity。
转移方程：dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])；dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])。前者表示：第i天不持有股票可能是前一天就不持有，或者前一天持有但今天卖出去了。后者表示：第i天持有股票可能是前一天就持有，或者前一天不持有但今天买入了。（这里选择买入时消耗一次交易机会）
最终最大利润是dp[len - 1][k][0]，因为结束时持有 0 份股票的收益一定大于持有 1 份股票的收益。其中len表示prices数组长度。
根据通用解法有：
dp[i][k][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])；
dp[i][k][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i]) = max(dp[i - 1][1][1], -prices[i])，其中 dp[i][0][0] = 0。其中 k始终为1，可以简化：
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
// dp[i][0] 表示第i天，不持有股票获得的最大收益（允许交易一次）
// dp[i][1] 表示第i天，持有股票获得的最大收益
int[][] dp = new int[len][2];
// base case
// 第0天不持有股票所能获得的最大利润
dp[0][0] = 0;
// 第0天持有股票所能获得的最大利润
dp[0][1] = -prices[0];
// 状态转移
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
}
// 肯定是不持有股票时利润最大
return dp[len - 1][0];
}
}
由于第i天的最大收益只和第i - 1天的最大收益相关，空间复杂度可以由O(n)降到O(1)。空间优化：
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
//base case
int dp0 = 0;
int dp1 = -prices[0];
//状态转移
for (int i = 1; i < len; i++) {
dp0 = Math.max(dp0, dp1 + prices[i]);
dp1 = Math.max(dp1, -prices[i]);
}
return dp0;
}
}
46. 二叉树中的最大路径和
思路：递归
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
public int maxPathSum(TreeNode root) {
maxSumToDescendant(root);
return maxPathSum;
}
//先初始化为最小值
private int maxPathSum = Integer.MIN_VALUE;
// 结点到 子孙（不一定包含叶子结点） 结点的最大路径和（最少为其自身一个结点）
private int maxSumToDescendant(TreeNode root) {
if (root == null) {
return 0;
}
// 小于0则认为对最大路径和没有贡献
int left = Math.max(0, maxSumToDescendant(root.left));
int right = Math.max(0, maxSumToDescendant(root.right));
maxPathSum = Math.max(maxPathSum, left + root.val + right);
return root.val + Math.max(left, right);
}
}
47. 最长连续序列
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int maxLen = 0;
for (int num : nums) {
// 找到包含 num 的连续序列的下边界
if (set.contains(num - 1)) {
continue;
}
// 找到下边界后开始计算长度
int len = 1;
while (set.contains(num + 1)) {
len++;
num++;
}
maxLen = Math.max(maxLen, len);
}
return maxLen;
}
}
48. 只出现一次的数字
思路：位运算，每个元素依次异或。
i ^ 0 = i;
i ^ i = 0;
且异或满***换律和结合律。
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) {
res = res ^ num;
}
return res;
}
}
49. 单词拆分
思路：动态规划
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>();
for (String str : wordDict) {
set.add(str);
}
int len = s.length();
// 状态： s 中前 i 个字符能否拆分成功
boolean[] dp = new boolean[len + 1];
// base case
dp[0] = true;
// 状态转移
// s[0, i]能否被分割取决于:区间[j, i]是否属于set和dp[j]的值(前j个字符 [0, j - 1] 能否被分割)，j <= i
for (int i = 1; i < len + 1; i++) {
for (int j = 0; j < i; j++) {
if (set.contains(s.substring(j, i)) && dp[j]) {
dp[i] = true;
break;
}
}
}
return dp[len];
}
}
50. 环形链表
思路：快慢指针，若慢指针最终追上快指针说明有环
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
public boolean hasCycle(ListNode head) {
//没有或只有一个结点说明没有环
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
51. 环形链表 II
思路：快慢指针，快慢指针相遇后，慢指针回到头，快慢指针步伐一致一起移动，相遇点即为入环点
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
public ListNode detectCycle(ListNode head) {
// 没有结点或只有一个非自环结点
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
//快指针从第一次相交点下一个节点开始移动, 慢指针重新从头开始移动
fast = fast.next; //注意
slow = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
// 相遇点即为入环点
return fast;
}
}
return null;
}
}
52. LRU 缓存机制
class LRUCache {
// 用 map 我们可以实现常数复杂度的get，但无法记录各个页面的先后顺序。
// 因此引入双向链表来记录页面先后顺序。
private Map<Integer, Node> map;
private Node head;
private Node tail;
private int capacity;
private int size = 0;
public LRUCache(int capacity) {
this.map = new HashMap<>();
this.head = new Node(-1, -1);
this.tail = new Node(-1, -1);
head.next = tail;
tail.pre = head;
this.capacity = capacity;
}
public int get(int key) {
if (map.containsKey(key)) {
Node temp = map.get(key);
moveToHead(temp);
return temp.val;
} else {
return -1;
}
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node temp = map.get(key);
temp.val = value;
moveToHead(temp);
} else {
if (size >= capacity) {
Node tempTail = removeTail();
int tempKey = tempTail.key;
map.remove(tempKey);
size--;
}
Node newNode = new Node(key, value);
map.put(key, newNode);
addHead(newNode);
size++;
}
}
private void moveToHead(Node node) {
removeNode(node);
addHead(node);
}
private Node removeTail() {
Node temp = tail.pre;
removeNode(temp);
return temp;
}
private void removeNode(Node node) {
node.next.pre = node.pre;
node.pre.next = node.next;
}
private void addHead(Node node) {
node.next = head.next;
node.pre = head;
head.next = node;
node.next.pre = node;
}
}
class Node {
Node pre;
Node next;
int key;
int val;
Node(int key, int val) {
this.key = key;
this.val = val;
}
}
/** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */
53. 排序链表
思路：O(nlogn)的复杂度实现排序可以考虑 归并 或 快速 排序。
归并排序:
/** * 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 sortList(ListNode head) {
return mergeSort(head);
}
private ListNode mergeSort(ListNode head) {
// base case
if (head == null || head.next == null) {
return head;
}
ListNode mid = getMidNode(head);
ListNode temp = mid.next;
mid.next = null;
ListNode l1 = mergeSort(head);
ListNode l2 = mergeSort(temp);
return merge(l1, l2);
}
// 快慢指针找中点
private ListNode getMidNode(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
// 合并两个链表
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode temp = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
temp.next = l1;
l1 = l1.next;
} else {
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
if (l1 != null) {
temp.next = l1;
} else if (l2 != null) {
temp.next = l2;
}
return dummy.next;
}
}
快速排序:
class Solution {
public ListNode sortList(ListNode head) {
return quickSort(head, null);
}
// start, end 之间进行快速排序，左闭右开
private ListNode quickSort(ListNode start, ListNode end) {
// base case
if (start == end || start.next == end) {
return start;
}
// 选择第一个结点为pivot
ListNode pivot = start;
// left, right 都指向pivot
ListNode left = pivot, right = pivot;
// 遍历 pivot 之后，end之前的所有结点，将小于 pivot 的放到 pivot 之前；否者放到 pivot 后面
ListNode cur = pivot.next;
while (cur != end) {
// 下面的插入操作会修改 cur.next
ListNode next = cur.next;
if (cur.val < pivot.val) {
cur.next = left;
left = cur;
} else {
right.next = cur;
right = cur;
}
cur = next;
}
// 重要，将操作好的链表的末尾指向 end
right.next = end;
ListNode pre = quickSort(left, pivot);
ListNode post = quickSort(pivot.next, end);
// 重要，前后两段链表通过 pivot 连接起来
pivot.next = post;
return pre;
}
}
54. 乘积最大子数组
class Solution {
public int maxProduct(int[] nums) {
int len = nums.length;
// 状态： dp[i][0]:以下标i结尾的子数组的最大乘积
// dp[i][1]:以下标i结尾的子数组的最小乘积
int[][] dp = new int[len][2];
//base case
dp[0][0] = nums[0];
dp[0][1] = nums[0];
int max = nums[0];
for (int i = 1; i < len; i++) {
if (nums[i] > 0) {
dp[i][0] = Math.max(nums[i], nums[i] * dp[i - 1][0]);
dp[i][1] = Math.min(nums[i], nums[i] * dp[i - 1][1]);
} else {
dp[i][0] = Math.max(nums[i], nums[i] * dp[i - 1][1]);
dp[i][1] = Math.min(nums[i], nums[i] * dp[i - 1][0]);
}
max = Math.max(max, dp[i][0]);
}
return max;
}
}
55. 最小栈
class MinStack {
/** initialize your data structure here. */
private Deque<Integer> stack;
// 用额外一个栈存储最小值
private Deque<Integer> minstack;
public MinStack() {
stack = new LinkedList<>();
minstack = new LinkedList<>();
}
public void push(int val) {
stack.push(val);
if (minstack.isEmpty() || val < minstack.peek()) {
minstack.push(val);
} else {
minstack.push(minstack.peek());
}
}
public void pop() {
stack.pop();
minstack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minstack.peek();
}
}
/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */
56. 相交链表
思路：指向两个链表的指针一起分别向后移，如果没有剩余元素就移动到另一条链表，然后继续后移。如果有交点，相遇时就不为null。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode lA = headA, lB = headB;
while (lA != lB) {
lA = lA == null ? headB : lA.next;
lB = lB == null ? headA : lB.next;
}
return lA;
}
}
57. 多数元素
思路一：用map记录每个元素的出现次数：
class Solution {
public int majorityElement(int[] nums) {
int threshold = nums.length / 2;
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
if (map.get(num) > threshold) {
return num;
}
}
throw new IllegalArgumentException("majority element not exist!");
}
}
思路二：排序：
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
思路三：摩尔投票，很简单：记录当前字符和出现频次，如果字符相同则频次加1，否则减1，减1后若频次为0则直接更换当前字符和频次。
class Solution {
public int majorityElement(int[] nums) {
int curElement = nums[0];
int cnt = 1;
for (int i = 1; i < nums.length; i++) {
if (curElement == nums[i]) {
cnt++;
} else {
cnt--;
if (cnt == 0) {
curElement = nums[i];
cnt = 1;
}
}
}
return curElement;
}
}
58. 打家劫舍
思路：动态规划
class Solution {
public int rob(int[] nums) {
int len = nums.length;
//状态： dp[i] 表示 有i间房屋时可以偷窃的最大金额
int[] dp = new int[len + 1];
//base case
dp[0] = 0;
dp[1] = nums[0];
int max = nums[0];
for (int i = 2; i < len + 1; i++) {
// 第 i - 1 个房间 可以偷， 也可以不偷
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
max = Math.max(max, dp[i]);
}
return max;
}
}
59. 岛屿数量
思路：DFS。
- 对于二维矩阵中象成一个对每个节点来说，他有上、下、左、右四个邻居，可以将每个岛屿都看成一个图。
- 从任意一个陆地进入开始遍历，遍历完1次就代表发现了一个岛屿。 注：图不像树那样是有向的，遍历可能会访问重复结点，一般需要用额外结构表示结点是否已经被访问过。此题可以直接在矩阵上将1修改为2表示结点已经访问过。
在原矩阵中标记是否访问过：
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid, int row, int col) {
//base case
if (!inArea(grid, row, col)) {
return;
}
if (grid[row][col] != '1') {
return;
}
//已访问
grid[row][col] = '2';
dfs(grid, row + 1, col);
dfs(grid, row - 1, col);
dfs(grid, row, col + 1);
dfs(grid, row, col - 1);
}
private boolean inArea(char[][] grid, int row, int col) {
return row >= 0 && row < grid.length &&
col >= 0 && col < grid[0].length;
}
}
使用额外空间标记是否已经访问过：
class Solution {
// 标记是否访问过
private boolean[][] visited;
public int numIslands(char[][] grid) {
int row = grid.length;
int col = grid[0].length;
visited = new boolean[row][col];
int cnt = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
dfs(grid, i, j);
cnt++;
}
}
}
return cnt;
}
private void dfs (char[][] grid, int i, int j) {
if (!inArea(grid, i, j)) {
return;
}
if (grid[i][j] != '1' || visited[i][j]) {
return;
}
visited[i][j] = true;
dfs(grid, i + 1, j);
dfs(grid, i, j + 1);
dfs(grid, i - 1, j);
dfs(grid, i, j - 1);
}
private boolean inArea(char[][] grid, int row, int col) {
return row >= 0 && row < grid.length &&
col >= 0 && col < grid[0].length;
}
}
60. 反转链表
思路一：迭代法：
/** * 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 reverseList(ListNode head) {
//始终指向当前结点的前一个结点
ListNode pre = null;
//当前结点
ListNode cur = head;
while (cur != null) {
//用来保存当前结点的下一个结点
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
思路二：递归（锻炼递归思维）：
首先给出函数定义，如此题：ListNode reverseList(ListNode head)
- 反转以head为头结点的链表
- 返回反转后链表的头结点
不要用脑袋去模拟递归栈，根据函数的定义去处理递归的子问题，即具体到一个结点要做的事情
确定base case
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}
//base case, 当链表只有一个结点时退出递归
if (head.next == null) {
return head;
}
/** * 具体到头结点来说，反转当前链表只需要两步： * 1.反转以head.next为头的链表 * 2.将head插入head.next为头的链表反转之后的链表末尾 */
ListNode vhead = reverseList(head.next); //根据递归函数定义，返回反转之后的链表头
//反转之后head.next位于链表尾部，将head插入head.next之后
head.next.next = head;
head.next = null;
return vhead;
}
}
61. 课程表
思路：根据题意可知：当课程之间不存在 环状 循环依赖时，便能完成所有课程的学习，反之则不能。因此可以将问题转换成： 判断有向图中是否存在环。使用 拓扑排序法 ：
- 构建 入度表：记录每个结点的入度数；
- 构建 邻接表：记录每个结点的后继结点；
- 将入度为0的结点加入队列，开始遍历；
- 当一个结点出队时，将其后继结点的入度数减1，若减1后入度为0则将后继结点也加入队列；
- 当所有入度为0的结点都已经出队时，检查是否还有入度不为0的结点，存在则说明不可能完成所有课程的学习。
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer, Integer> indegreeMap = new HashMap<>();
Map<Integer, List<Integer>> postsMap = new HashMap<>();
// 初始化 入度表, 邻接表
for (int i = 0; i < numCourses; i++) {
indegreeMap.put(i, 0);
postsMap.put(i, new LinkedList<>());
}
for (int[] temp : prerequisites) {
int cur = temp[1];
int post = temp[0];
// 统计后继结点入度
indegreeMap.put(post, indegreeMap.getOrDefault(post, 0) + 1);
// 建立 邻接表
postsMap.get(cur).add(post);
}
Deque<Integer> queue = new LinkedList<>();
// 向队列中加入入度为0的结点
for (Integer key : indegreeMap.keySet()) {
if (indegreeMap.get(key) == 0) {
queue.offer(key);
}
}
// 出队
while (!queue.isEmpty()) {
Integer cur = queue.poll();
List<Integer> posts = postsMap.get(cur);
for (Integer post : posts) {
// 将后继结点入度减1
indegreeMap.put(post, indegreeMap.get(post) - 1);
// 将减1后入度为0，且存在后继的后继结点加入队列
if (indegreeMap.get(post) == 0) {
queue.offer(post);
}
}
}
for (Integer key : indegreeMap.keySet()) {
if (indegreeMap.get(key) > 0) {
return false;
}
}
return true;
}
}
62. 实现 Trie (前缀树)
class Trie {
private Node root;
/** Initialize your data structure here. */
public Trie() {
root = new Node();
}
/** Inserts a word into the trie. */
public void insert(String word) {
Node temp = root;
for (int i = 0; i < word.length(); i++) {
if (temp.children[word.charAt(i) - 'a'] == null) {
temp.children[word.charAt(i) - 'a'] = new Node();
}
temp = temp.children[word.charAt(i) - 'a'];
}
temp.isEnd = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Node temp = root;
for (int i = 0; i < word.length(); i++) {
if (temp.children[word.charAt(i) - 'a'] == null) {
return false;
}
temp = temp.children[word.charAt(i) - 'a'];
}
return temp.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
Node temp = root;
for (int i = 0; i < prefix.length(); i++) {
if (temp.children[prefix.charAt(i) - 'a'] == null) {
return false;
}
temp = temp.children[prefix.charAt(i) - 'a'];
}
return true;
}
}
class Node {
boolean isEnd = false;
Node[] children = new Node[26];
}
/** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */
63. 数组中的第K个最大元素
思路：基于快速排序的选择方法。每次partition即可确定一个元素的位置 mid，如果当前mid的位置小于len - k，则下一次的partition区间就为[mid + 1, right]，反之则为[left, mid + 1]，直到mid = len - k。
class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
int left = 0;
int right = len - 1;
while (true) {
int mid = partition(nums, left, right);
if (mid == (len - k)) {
return nums[mid];
} else if (mid < (len - k)) {
left = mid + 1;
} else if (mid > (len - k)) {
right = mid - 1;
}
}
}
private Random random = new Random(47);
// 将 大于等于 pivot 的值放在 pivot 右边，小于 pivot 的放在 pivot 左边
private int partition(int[] nums, int left, int right) {
int randIndex = left + random.nextInt(right - left + 1);
swap(nums, left, randIndex);
int pivot = nums[left];
while (left < right) {
// 在右边找一个小于 pivot 的值填至 left
while (left < right && nums[right] >= pivot) {
right--;
}
if (left < right) {
swap(nums, left, right);
left++;
}
// 在左边找一个大于等于 pivot 的值填至 right
while (left < right && nums[left] < pivot) {
left++;
}
if (left < right) {
swap(nums, left, right);
right--;
}
}
nums[left] = pivot;
return left;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
64. 最大正方形
class Solution {
public int maximalSquare(char[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
// 以 matrix[i][j] 为右下角的正方形的最大边长
int[][] dp = new int[row][col];
int maxLen = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
//base case
if (i == 0 || j == 0) {
dp[i][j] = matrix[i][j] - '0';
// 转移方程：取 左、上、左上 三个dp值的最小值加1
} else if (matrix[i][j] == '1') {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
maxLen = Math.max(maxLen, dp[i][j]);
}
}
return maxLen * maxLen;
}
}
65. 翻转二叉树
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return root;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
66. 回文链表
思路：快慢指针找到中点，反转后半部分，然后依次比较，最后要记得还原链表
/** * 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 boolean isPalindrome(ListNode head) {
//没有或只有一个结点
if (head == null || head.next == null) {
return true;
}
ListNode mid = getMidNode(head);
ListNode rHead = reverse(mid.next);
//切断
mid.next = null;
ListNode lTemp = head;
ListNode rTemp = rHead;
//右半部分链表长度小于等于左半部分链表长度
while (rTemp != null) {
if (lTemp.val != rTemp.val) {
return false;
}
lTemp = lTemp.next;
rTemp = rTemp.next;
}
//还原
mid.next = reverse(rHead);
return true;
}
//对于偶数个结点和奇数个结点，slow都位于右部分的前一个结点
private ListNode getMidNode(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
//反转链表
private ListNode reverse(ListNode head) {
ListNode pre = null, cur = head, next = head;
while (cur != null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
- 推荐使用
slow = head;fast = head.next;的方式使用快慢指针 - 该方式下，结点个数为奇数，
slow指向中点；结点个数为偶数，slow指向左边中点
67. 二叉树的最近公共祖先
思路：后序遍历演变而来，若找到其中一个结点就自底向上返回。若p、q互不为对方子树中的结点，p、q最终会在某个结点相遇，该节点就为最近公共祖先；否则p或q即为最近公共结点。
class Solution {
//重要已知：p != q
// p 和 q 均存在于给定的二叉树中。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
}
68. 除自身以外数组的乘积
如果元素中不含 0 就很简单：先遍历一遍数组求出所有元素的 总乘积，第二次遍历数组只需要用 总乘积 除以当前元素即可得到其他各元素的乘积。
思路：由于这里元素是可能为0的，那么可以通过两个备忘录，分别记录当前元素 左侧所有元素乘积 和 右侧所有元素乘积，然后两者对应坐标元素相乘即可。
class Solution {
public int[] productExceptSelf(int[] nums) {
int len = nums.length;
int[] l_product = new int[len];
int[] r_product = new int[len];
// 左侧所有元素乘积
l_product[0] = 1;
for (int i = 1; i < len; i++) {
l_product[i] = nums[i - 1] * l_product[i - 1];
}
// 左侧所有元素乘积
r_product[len - 1] = 1;
for (int i = len - 2; i >= 0; i--) {
r_product[i] = nums[i + 1] * r_product[i + 1];
}
int[] res = new int[len];
for (int i = 0; i < len; i++) {
res[i] = l_product[i] * r_product[i];
}
return res;
}
}
由于题目进阶要求 常数空间复杂度（输出数组不被视为额外空间，也就是上面代码中的res）。
思路：我们其实可以先只存储 左侧所有元素乘积：
class Solution {
public int[] productExceptSelf(int[] nums) {
int len = nums.length;
int[] res = new int[len];
res[0] = 1;
for (int i = 1; i < len; i++) {
res[i] = nums[i - 1] * res[i - 1];
}
int r_product = 1;
for (int i = len - 1; i >= 0; i--) {
res[i] = res[i] * r_product;
r_product = nums[i] * r_product;
}
return res;
}
}
69. 滑动窗口最大值
求窗口中的最大值肯定很简单，但是如何在窗口向右滑动时（最左边元素出窗，最右边有新元素进窗）快速（ O(n) ）求出新的最大值？
思路：使用单调队列（由大到小）记录当前窗口中的最大值以及候选最大值
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
int[] maxs = new int[len - k + 1];
int j = 0;
for (int i = 0 ; i < len; i++) {
if (i < k - 1) {
offer(nums[i]);
} else {
offer(nums[i]);
maxs[j++] = max();
poll(nums[i - k + 1]);
}
}
return maxs;
}
private Deque<Integer> queue = new LinkedList<>();
//保证队列头始终是当前窗口中的最大值，后面是次大值（如果存在）
private void offer(int e) {
//将队列尾部小于新元素的候选值全部出队
while (!queue.isEmpty() && e > queue.peekLast()) {
queue.pollLast();
}
queue.offer(e);
}
//当 出窗口的元素是当前最大值时更新队列
private void poll(int e) {
if (e == queue.peek()) {
queue.poll();
}
}
private int max() {
return queue.peek();
}
}
70. 搜索二维矩阵 II
思路：从右上角开始，target小于当前值则该列可以被排除，target大于当前值则该行可以被排除
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int row = matrix.length;
int col = matrix[0].length;
int i = 0;
int j = col - 1;
while (i < row && j >= 0) {
if (target < matrix[i][j]) {
j--;
} else if (target > matrix[i][j]) {
i++;
} else if (target == matrix[i][j]) {
return true;
}
}
return false;
}
}
71. 会议室 II(NO)
72. 完全平方数
class Solution {
public int numSquares(int n) {
// dp[i] : 组成和为 i 的最少完全平方数个数
// base case: dp[0] = 0;
int[] dp = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
// 最大值即为i
dp[i] = i;
// 转移方程
for (int j = 1; i - j*j >= 0; j++) {
dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
}
}
return dp[n];
}
}
73. 移动零
思路一：双指针，i 指向 非0 元素的下一个待插入位置，j 遍历数组，每次遇到 非0 元素就插入 i 指向的位置并一起向后移动，最后将 i 及其后面全部补0即可。
class Solution {
public void moveZeroes(int[] nums) {
int len = nums.length;
int i = 0; // i 指向 非0 元素的下一个待插入位置
// j 一直向后遍历，每次遇到 非0 元素就插入i指向的位置并一起向后移动
for (int j = 0; j < len; j++) {
if (nums[j] != 0) {
nums[i++] = nums[j];
}
}
// i 及其后面全部补0即可
for ( ; i < len; i++) {
nums[i] = 0;
}
}
}
思路二：双指针，i 指向 非0 元素的下一个待插入位置，j 遍历数组，每次遇到 非0 元素就与 i 指向元素交换并一起向后移动，最后[0, i)之前全部为非0元素，(i, j)之间全部为 0。
class Solution {
public void moveZeroes(int[] nums) {
int len = nums.length;
int i = 0; // i 指向 非0 元素的下一个待插入位置
// 每次遇到 非0 元素就与 i 指向元素交换并一起向后移动
for (int j = 0; j < len; j++) {
if (nums[j] != 0) {
swap(nums, i, j);
i++;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
74. 寻找重复数
该题最简单的思路便是使用set，但题目要求空间复杂度为O(1)。另外一种简单思路是使用排序，然后检查重复数即可，但题目又要求时间复杂度为O(nlogn)，且不能修改原数组。面试时我们应该询问面试官 时间 和 空间复杂度 要求之后再确定具体使用的方法。
思路一：快慢指针，建议先刷：141. 环形链表、142. 环形链表 II。
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = nums[slow];
while (slow != fast) {
fast = nums[nums[fast]];
slow = nums[slow];
}
fast = nums[slow];
slow = 0;
while (slow != fast) {
fast = nums[fast];
slow = nums[slow];
}
return slow;
}
}
思路二：将所有元素放置在其值减1的下标位置。如：1 应该放置在 0 位置，3 应该放置在 2 位置，这样，重复的元素至少有一个无法放置在对应位置。
class Solution {
public int findDuplicate(int[] nums) {
int len = nums.length;
for (int i = 0; i < len - 1; i++) {
// 如果元素的 值 和 下标 不匹配，则将其交换至对的位置
while ((nums[i] - 1) != i) {
// 如果发现待交换的两个元素相同则直接返回 如：[3,1,3,4,2]
if (nums[i] == nums[nums[i] - 1]) {
return nums[i];
}
swap(nums, i, nums[i] - 1);
}
}
// 通常，最后一个元素为重复元素
return nums[len - 1];
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
备注：该方法修改了原来的数组。时间复杂度为O(n)，因为每个元素至多交换一次，空间复杂度为O(1)。
75. 二叉树的序列化与反序列化
思路一：使用先序遍历进行序列化（dfs）
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "#";
}
String leftSerial = serialize(root.left);
String rightSerial = serialize(root.right);
return root.val + "," + leftSerial + "," + rightSerial;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] strs = data.split(",");
Deque<String> queue = new LinkedList<>();
for (String str : strs) {
queue.offer(str);
}
return deserialize(queue);
}
private TreeNode deserialize(Deque<String> queue) {
String rootVal = queue.poll();
if (rootVal.equals("#")) {
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(rootVal));
root.left = deserialize(queue);
root.right = deserialize(queue);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
思路二：使用层次遍历进行序列化（bfs）
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
Deque<TreeNode> queue = new LinkedList<>();
StringBuilder sb = new StringBuilder();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode temp = queue.poll();
if (temp != null) {
sb.append(temp.val).append(",");
queue.offer(temp.left);
queue.offer(temp.right);
} else {
sb.append("#").append(",");
}
}
System.out.println(sb.toString());
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] strs = data.split(",");
Deque<TreeNode> queue = new LinkedList<>();
int i = 0;
if (strs[i].equals("#")) return null;
TreeNode root = new TreeNode(Integer.parseInt(strs[i++]));
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode temp = queue.poll();
String leftVal = strs[i++];
String rightVal = strs[i++];
if (!leftVal.equals("#")) {
TreeNode leftChild = new TreeNode(Integer.parseInt(leftVal));
temp.left = leftChild;
queue.offer(leftChild);
}
if (!rightVal.equals("#")) {
TreeNode rightChild = new TreeNode(Integer.parseInt(rightVal));
temp.right = rightChild;
queue.offer(rightChild);
}
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
76. 最长递增子序列
思路：动态规划
状态：以当前字符结尾的字符串中最长递增子序列的长度
转移方程：dp[i] = max(dp[j] + 1, dp[i])，其中j < i 且 nums[j] < nums[i]
base case：dp[i] = 1
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
// dp[i] 表示以当前字符结尾的字符串中最长递增子序列的长度
int[] dp = new int[len];
int maxLen = 0;
for (int i = 0; i < len; i++) {
//base case
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
}
77. 删除无效的括号
思路：回溯法
class Solution {
public List<String> removeInvalidParentheses(String s) {
// 左括号和右括号最少需要移除的个数
int leftRemove = 0, rightRemove = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
leftRemove++;
} else if (s.charAt(i) == ')') {
//存在左括号则消去一个
if (leftRemove > 0) {
leftRemove--;
} else if (leftRemove == 0) {
rightRemove++;
}
}
}
StringBuilder track = new StringBuilder();
dfs(s, 0, track, 0, 0, leftRemove, rightRemove);
return new ArrayList<>(res);
}
private Set<String> res = new HashSet<>();
private void dfs(String s, int index, StringBuilder track, int leftCnt, int rightCnt, int leftRemove, int rightRemove) {
if (s.length() == index) {
if (leftRemove == 0 && rightRemove == 0) {
res.add(track.toString());
}
return;
}
char ch = s.charAt(index);
// 选择1：删除当前字符
if (ch == '(' && leftRemove > 0) {
dfs(s, index + 1, track, leftCnt, rightCnt, leftRemove - 1, rightRemove);
} else if (ch == ')' && rightRemove > 0) {
dfs(s, index + 1, track, leftCnt, rightCnt, leftRemove, rightRemove - 1);
}
// 选择2：保留当前字符
track.append(ch);
if (ch == '(' ) {
dfs(s, index + 1, track, leftCnt + 1, rightCnt, leftRemove, rightRemove);
} else if (ch == ')' && leftCnt > rightCnt) {
dfs(s, index + 1, track, leftCnt, rightCnt + 1, leftRemove, rightRemove);
} else if (ch != '(' && ch != ')') {
dfs(s, index + 1, track, leftCnt, rightCnt, leftRemove, rightRemove);
}
track.deleteCharAt(track.length() - 1);
}
}
78. 最佳买卖股票时机含冷冻期
思路：动态规划
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int[][] dp = new int[len][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], (i >= 2 ? dp[i - 2][0] : 0) - prices[i]);
}
return dp[len - 1][0];
}
}
79. 戳气球
思路：动态规划。推荐题解：[这个菜谱, 自己在家也能做] 关键思路解释
class Solution {
public int maxCoins(int[] nums) {
int len = nums.length;
// 前后两位各插入1
int[] newNums = new int[len + 2];
newNums[0] = 1;
newNums[len + 1] = 1;
for (int i = 0; i < len; i++) {
newNums[i + 1] = nums[i];
}
//dp[i][j] 代表 戳爆开区间 (i, j) 中的气球所能取得的最大值
//默认值都为0，base case: dp[i][j] = 0, j - i < 3
int[][] dp = new int[len + 2][len + 2];
for (int size = 3; size <= len + 2; size++) {
//开区间起始位置
for (int start = 0; start <= len + 2 - size; start++) {
int max = 0;
//列举最后一个被戳爆的气球为 newNums[k]的所有情况, K属于[start + 1, start + size - 1)，找到最大值
for (int k = start + 1; k < start + size - 1; k++) {
max = Math.max(max, dp[start][k] + dp[k][start + size - 1] + newNums[start] * newNums[k] * newNums[start + size - 1]);
}
dp[start][start + size - 1] = max;
}
}
return dp[0][len + 1];
}
}
80. 零钱兑换
思路：动态规划。
class Solution {
public int coinChange(int[] coins, int amount) {
//状态：dp[i] 表示凑够i需要的最少硬币数
int[] dp = new int[amount + 1];
//求最小值，先初始为足够大。(若能凑成，最多需要amount枚硬币)
Arrays.fill(dp, amount + 1);
//base case
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
//当前背包（总金额）若能装下物品（硬币面额）
if (i >= coins[j]) {
dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]);
}
}
}
return dp[amount] >= amount + 1 ? -1 : dp[amount];
}
}
81. 打家劫舍 III
思路：后序遍历 + 动态规划
推荐题解：树形 dp 入门问题（理解「无后效性」和「后序遍历」）
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
public int rob(TreeNode root) {
int[] temp = steal(root);
return Math.max(temp[0], temp[1]);
}
//返回以当前结点为根节点的二叉树的根节点偷或不偷所能获得的最大值
private int[] steal(TreeNode node) {
if (node == null) {
return new int[] {
0, 0};
}
int[] left = steal(node.left);
int[] right = steal(node.right);
//dp[0]表示当前节点不被偷，dp[1]表示偷
int[] dp = new int[2];
//当前不被偷，那么子结点偷或不偷都可以，取最大的和即可
dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
//当前结点被偷，子结点都不能偷
dp[1] = node.val + left[0] + right[0];
return dp;
}
}
82. 比特位计数
思路: n & (n - 1)表示将 n 最后一位 1 置为 0:
class Solution {
public int[] countBits(int num) {
int[] res = new int[num + 1];
for (int i = 0; i <= num; i++) {
res[i] = hamming(i);
}
return res;
}
private int hamming(int n) {
int cnt = 0;
//每次将最后一个1置0
while (n != 0) {
n = n & (n - 1);
cnt++;
}
return cnt;
}
}
动态规划:
任何一个数的汉明重量等于将其最后一位 1 置 0 的数的汉明重量加1，可考虑用动态规划。
class Solution {
public int[] countBits(int num) {
//每个数的汉明重量
int[] dp = new int[num + 1];
//base case
dp[0] = 0;
for (int i = 1; i <= num; i++) {
dp[i] = dp[i & (i - 1)] + 1;
}
return dp;
}
}
83. 前 K 个高频元素
思路一：快速排序的应用，和第K大元素类似
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
int len = map.size();
int[][] freq = new int[len][2];
int i = 0;
for (int key : map.keySet()) {
freq[i][0] = key;
freq[i][1] = map.get(key);
i++;
}
int index = 0;
int left = 0, right = len - 1;;
int pos = len - k;
while (true) {
index = partition(freq, left, right);
if (index == pos) {
break;
} else if (index < pos) {
left= index + 1;
} else if (index > pos) {
right = index - 1;
}
}
int[] res = new int[k];
int cnt = 0;
for (int j = pos; j < len; j++) {
res[cnt++] = freq[j][0];
}
return res;
}
private Random random = new Random(47);
private int partition(int[][] nums, int left, int right) {
int rand = left + random.nextInt(right - left + 1);
swap(nums, left, rand);
int pivot = nums[left][1];
int temp = nums[left][0];
while (left < right) {
while (left < right && pivot <= nums[right][1]) {
right--;
}
if (left < right) {
swap(nums, left, right);
left++;
}
while (left < right && pivot > nums[left][1]) {
left++;
}
if (left < right) {
swap(nums, left, right);
right--;
}
}
nums[left][1] = pivot;
nums[left][0] = temp;
return left;
}
private void swap(int[][] nums, int i, int j) {
int[] temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
思路二：优先队列（大顶堆）
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
PriorityQueue<Integer> pqueue = new PriorityQueue<>((e1, e2) -> map.get(e2) - map.get(e1));
for (int key : map.keySet()) {
pqueue.offer(key);
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = pqueue.poll();
}
return res;
}
}
84. 字符串解码
思路：栈，思路简单，关键在于字符串拼接顺序的细节问题。
class Solution {
public String decodeString(String s) {
Deque<String> stack = new LinkedList<>();
for (int i = 0; i < s.length(); i++) {
String str = s.substring(i, i + 1);
if (str.equals("]")) {
//拼接 [] 之间的字符，这里得到的是逆序，不用反转
StringBuilder strSB = new StringBuilder();
while (!stack.peek().equals("[")) {
strSB.append(stack.pop());
}
//弹出 [
stack.pop();
//拼接 [ 之前的重复次数
StringBuilder reTimesSB = new StringBuilder();
while (!stack.isEmpty() && isDigit(stack.peek())) {
reTimesSB.append(stack.pop());
}
//根据重复次数拼接字符串，反转后转为整型
int reTimes = Integer.parseInt(reTimesSB.reverse().toString());
StringBuilder sb = new StringBuilder();
while (reTimes > 0) {
sb.append(strSB);
reTimes--;
}
//新字符串入栈
stack.push(sb.toString());
} else {
stack.push(str);
}
}
StringBuilder res = new StringBuilder();
while (!stack.isEmpty()) {
res.append(stack.pop());
}
//由于之前的字符拼接都是逆序的，反转后再返回
return res.reverse().toString();
}
//首字符是否为数字
private boolean isDigit(String str) {
char ch = str.charAt(0);
return ch >= '0' && ch <= '9';
}
}
85. 除法求值
86. 根据身高重建队列
87. 分割等和子集
推荐题解：「手画图解」416.分割等和子集 | 记忆化递归 思路详解
思路一：dfs
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 == 1) {
return false;
}
int target = sum / 2;
return dfs(nums, 0, 0, target);
}
private boolean dfs(int[] nums, int index, int sum, int target) {
//base case
if (nums.length == index) {
if (sum == target) {
return true;
} else {
return false;
}
}
//对于任意一个数，可与选或者不选
return dfs(nums, index + 1, sum + nums[index], target) ||
dfs(nums, index + 1, sum, target);
}
}
用例超时：
[100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,99,97]
思路二：dfs + 备忘录
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 == 1) {
return false;
}
int target = sum / 2;
return dfs(nums, 0, 0, target);
}
// 备忘录：也可用一个二维数组，一维表示元素和sum，一维表示当前索引index
private Map<String, Boolean> map = new HashMap<>();
private boolean dfs(int[] nums, int index, int sum, int target) {
if (nums.length == index) {
if (sum == target) {
return true;
} else {
return false;
}
}
//描述一个子问题的两个变量是 sum 和 index，组成 key 字符串
String key = sum + "&" + index;
if (map.containsKey(key)) {
return map.get(key);
}
boolean ret = dfs(nums, index + 1, sum + nums[index], target) ||
dfs(nums, index + 1, sum, target);
map.put(key, ret);
return ret;
}
}
思路三：所有 target 绝对值大于 元素总和 或 元素总和 不为 偶数 显然不能拆分；问题等价于能否找到一组元素的和为所有元素总和的一半。（01背包问题：可选物品有限）
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 == 1) {
return false;
}
//背包容量
int target = sum / 2;
//物品个数
int len = nums.length;
//状态：dp[m][n]表示背包容量为 m，有 前 n 个物品（ [0, n-1]共n个 ）时能否装满背包
boolean[][] dp = new boolean[target + 1][len + 1];
// base case
// dp[0][0] = true, 不选即满
// dp[0][i] = true, i >= 1; 表示容量为0，有1个及以上个物品时可认为不选即满，固可以填满
// dp[i][0] = false, i >= 1; 表示容量 大于等于 1时，没有物品可选则无法填满
for (int i = 0; i < len + 1; i++) {
dp[0][i] = true;
}
for (int i = 1; i < target + 1; i++) {
for (int j = 1; j < len + 1 ; j++) {
// 如果不能装下前j个物品中的最后一个
if (i < nums[j - 1]) {
dp[i][j] = dp[i][j - 1];
// 能装下，可以选择装或者不装
} else if (i >= nums[j - 1]) {
dp[i][j] = dp[i][j - 1] || dp[i - nums[j - 1]][j - 1];
}
}
}
return dp[target][len];
}
}
88. 路径总和 III
提示：路径并非是一条向下的直线，可以是折线。如root = [10,5,-3,3,2,null,11,3,0,null,1], targetSum = 8中[5, 3]和[5, 3, 0]都符合条件。
推荐题解：对前缀和解法的一点解释
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
public int pathSum(TreeNode root, int targetSum) {
pathSum(root, 0, targetSum);
return cnt;
}
private int cnt = 0;
private Map<Integer, Integer> map = new HashMap<>() {
{
//前缀树为0的结点个数是一个
put(0, 1);
}
};
// 前序遍历 + 回溯
private void pathSum(TreeNode node, int prefixSum, int targetSum) {
if (node == null) {
return;
}
// 当前结点的前缀和
prefixSum += node.val;
// 和当前结点前缀和 之差 为targetSum 的（父、祖先）结点即可满足条件
cnt += map.getOrDefault(prefixSum - targetSum, 0);
// 选择，使得子结点可以使用当前结点的前缀和
map.put(prefixSum, map.getOrDefault(prefixSum, 0) + 1);
pathSum(node.left, prefixSum, targetSum);
pathSum(node.right, prefixSum, targetSum);
// 撤销选择，使得兄弟结点无法使用当前结点的前缀和
map.put(prefixSum, map.get(prefixSum) - 1);
}
}
89. 找到字符串中所有字母异位词
思路：滑动窗口
class Solution {
public List<Integer> findAnagrams(String s, String p) {
//记录窗口中目标字符的出现次数
Map<Character, Integer> window = new HashMap<>();
//记录目标子串中每个字符出现的次数
Map<Character, Integer> need = new HashMap<>();
for (int i = 0; i < p.length(); i++) {
char ch = p.charAt(i);
need.put(ch, need.getOrDefault(ch, 0) + 1);
}
//记录已经匹配的目标字符数
int match = 0;
//窗口区间，左闭右开
int left = 0, right = 0;
List<Integer> res = new LinkedList<>();
while (right < s.length()) {
//窗口扩张（右边界右移）
char rightChar = s.charAt(right);
right++;
//如果当前字符是目标字符
if (need.containsKey(rightChar)) {
window.put(rightChar, window.getOrDefault(rightChar, 0) + 1);
//当 window 中 rightChar 的个数 小于等于 need 中 rightChar 的数量时
if (window.get(rightChar).compareTo(need.get(rightChar)) <= 0) {
match++;
}
}
//当窗口中已经包含所有目标字符
while(match == p.length()) {
//如果此时窗口大小刚好等于目标字符串长度，说明窗口内容刚好为目标字符串的异位词
if (right - left == p.length()) {
res.add(left);
}
//收缩窗口（左边界右移），直到window不再包含所有目标字符
char leftChar = s.charAt(left);
left++;
if (need.containsKey(leftChar)) {
if (window.get(leftChar).compareTo(need.get(leftChar)) <= 0) {
match--;
}
window.put(leftChar, window.get(leftChar) - 1);
}
}
}
return res;
}
}
90. 找到所有数组中消失的数字
思路一：使用map记录各个元素出现的频次，然后依次获取 [1, n] 出现的频次，频次为0则说明没有出现。此时空间复杂度为O(n)。面试时我们应该询问面试官 时间 和 空间复杂度 要求之后再确定具体使用的方法。
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
List<Integer> res = new LinkedList<>();
for (int i : nums) {
map.put(i, map.getOrDefault(i, 0) + 1);
}
for (int i = 1; i <= nums.length; i++) {
if (!map.containsKey(i)) {
res.add(i);
}
}
return res;
}
}
思路二：将所有元素放置在其值减1的下标位置。如：1 应该放置在 0 位置，3 应该放置在 2 位置，这样一轮处理后所有 值 与 下标 差值不为1 的 下标加1 即为未出现的元素。
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
// 如果元素的 值 和 下标 不匹配，则将其交换至对的位置
while (nums[i] - 1 != i) {
// 如果发现待交换的两个元素相同则跳过
if (nums[i] == nums[nums[i] - 1]) {
break;
}
swap(nums, i, nums[i] - 1);
}
}
List<Integer> res = new LinkedList<>();
for (int i = 0; i < len; i++) {
// 值 与 下标 不对应，下标加1 即为未出现的元素
if (nums[i] - 1 != i) {
res.add(i + 1);
}
}
return res;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
京公网安备 11010502036488号