算法刷题总结（全）

刷题总结

by lds 2023-9-5

文章目录

1.数组/字符串

1.1 合并两个有序数组【easy】

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int l = 0, r = 0;
        int[] temp = new int[m + n];
        int cur = 0;
        //int t = 0;
        while (l < m || r < n) {
            if (l == m) {
                cur = nums2[r++];
            }else if (r == n) {
                cur = nums1[l++];
            }else if (nums1[l] > nums2[r]) {
                cur = nums2[r++];
            }else {
                cur = nums1[l++];
            }
            temp[l + r - 1] = cur;
            //temp[t++] = cur; //这个地方或者这样写也是可以的！更好理解吧！
        }
        for (int i = 0; i < m + n; i++) {
            nums1[i] = temp[i];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

心得：

充分利用双指针的方法，以及两个数组排好序的前提
新建一个新的数组，很大程度降低了复杂度，这个一定要考虑到—很关键！

1.2 移除元素【easy】

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
1
2
3

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if (val != nums[fast]) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

心得：快慢指针的灵活运用！

1.3 删除有序数组中的重复项【easy】

给你一个 升序排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持一致。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
1
2
3

class Solution {
    public int removeDuplicates(int[] nums) {
        int fast = 0, slow = 0;
        while (fast < nums.length) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return slow + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

心得：快慢指针灵活运用！

1.4 删除有序数组中的重复项II【mid】

给你一个有序数组 nums ，请你** 原地** 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。
1
2
3

class Solution {
    public int removeDuplicates(int[] nums) {
        int slow = 0, fast = 0;
        int count = 0;
        while (fast < nums.length) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }else if (slow < fast && count < 2) {//这里slow < fast条件不可或缺！
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
            count++;
            if (fast < nums.length && nums[fast] != nums[fast - 1]) {
                count = 0;
            }
        }
        return slow + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

心得：

快慢指针
利用标志位count来记录重复的元素不能超过2！

1.5 多数元素【easy】

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3
1
2

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2
1
2

法一：

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        Map.Entry<Integer, Integer> majorityEntry = null;
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                majorityEntry = entry;
            }
        }
        return majorityEntry.getKey();
    }
}
//直接想到的就是创建哈希表，然后用hashmap存每个数字的出现次数，然后定义一个majorityEntry存最大的那个value,即可统计出来！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

法二：

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}
1
2
3
4
5
6

心得：

直接想到哈希表
想到排序、取巧的方法

1.6 大数相加—【美团面试手撕题目】

给定两个超过Integer的两个数字，用字符串存储，求它们相加之后的数，将结果同样用字符串存储！

import java.util.*;
public class Main {
    public static void main(String[] args) {
        //Scanner in = new Scanner(System.in);
        //int a = in.nextInt();
        //System.out.println(a);
        String a = "45678654325698765435"; 
        String b = "754636745356536";
        StringBuilder str = new StringBuilder();
        int len1 = a.length() - 1;
        int len2 = b.length() - 1;
        int carry = 0;
        while (len1 >= 0 || len2 >= 0 || carry != 0) {
            int m = len1 < 0 ? 0 : a.charAt(len1--) - '0';
            int n = len2 < 0 ? 0 : b.charAt(len2--) - '0';
            int res = m + n + carry;
            carry = res / 10;
            str.append(res % 10);
        }
        System.out.println(str.reverse().toString());
    }
     
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

心得：

字符串以及StringBuilder的灵活运用
进位（res / 10）、个位（res % 10）的灵活使用

1.7 轮转数组【mid】

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
1
2
3
4
5
6

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
1
2
3
4
5

class Solution {
    public void rotate(int[] nums, int k) {
        int[] temp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int j = (i + k) % nums.length;
            temp[j] = nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = temp[i];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

心得：

旋转数组（往右平移数组），本质就是一个元素取模运算！！
想到新建数组，空间换时间，用取模之后的数作为新数组索引！

1.8 买卖股票的最佳时机【easy】

股票问题，参考labuladong：一个方法团灭 LeetCode 股票买卖问题 | labuladong 的算法小抄

easy-leetcode：121. 买卖股票的最佳时机 - 力扣（LeetCode）

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
1
2
3
4

public class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        int minprice = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            }else {
                maxprofit = Math.max(maxprofit, prices[i] - minprice);
            }
        }
        return maxprofit;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

labuladong动态规划：

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i - 1 == -1) {
                // base case
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            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[n - 1][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

心得：

一次遍历：充分利用抛售日在购买日之后的这个条件，维护一个最小值的价格，在之后都去比较得到的利润是否是最大的即可！

1.9 买卖股票的最佳时机II【mid】

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的最大利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。
1
2
3
4
5

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i == 0) {
            //base case   
                dp[i][0] = 0; //0表示收益
                dp[i][1] = -prices[i]; //1表示买入后的剩余
                continue;
            }
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

labuladong主题思路：

这个问题的「状态」有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（即之前说的 rest 的状态，我们不妨用 1 表示持有，0 表示没有持有）。然后我们用一个三维数组就可以装下这几种状态的全部组合：

dp[i][k][0 or 1]
0 <= i <= n - 1, 1 <= k <= K
n 为天数，大 K 为交易数的上限，0 和 1 代表是否持有股票。
此问题共 n × K × 2 种状态，全部穷举就能搞定。

for 0 <= i < n:
    for 1 <= k <= K:
        for s in {0, 1}:
            dp[i][k][s] = max(buy, sell, rest)
1
2
3
4
5
6
7
8
9

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
              max( 今天选择 rest,        今天选择 sell       )
              
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              max( 今天选择 rest,         今天选择 buy         )

1
2
3
4
5
6

特殊解法–贪心方法：122. 买卖股票的最佳时机 II - 力扣（LeetCode）

public class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            int diff = prices[i] - prices[i - 1];
            if (diff > 0) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

1.10 跳跃游戏【mid】

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
1
2
3

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
1
2
3

贪心：

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int farthest = 0;
        for (int i = 0; i < n - 1; i++) {
            // 不断计算能跳到的最远距离
            farthest = Math.max(farthest, i + nums[i]);
            // 可能碰到了 0，卡住跳不动了
            if (farthest <= i) {
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

如果某一个作为起跳点的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为起跳点
可以对每一个能作为起跳点的格子都尝试跳一次，把能跳到最远的距离不断更新
如果可以一直跳到最后，就成功了
链接：https://leetcode.cn/problems/jump-game/solutions/24322/55-by-ikaruga/

心得：

转变思路，去求能到达的最远距离，如果最远距离大于最大长度，则说明可以跳到最后，否则不可以！

1.11 数组左右之和相等【笔试题】

有一个整数数组，请该数组中找到一个元素，使其左侧所有元素相加的和等于右侧所有元素相加的和，该元素的下标即为中心下标。
如果中心下标位于数组最左端，那么左侧数之和视为0，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标，返回-1。

示例1
输入输出示例仅供调试，后台判题数据一般不包含示例
输入	 	
[1,7,3,6,5,6]
输出	 	
3

说明
中心下标是3。
左侧数之和sum=nums[0]+nums[1]+nums[2]=1+7+3=11，右侧数之和sum=nums[4]+nums[5]=5+6=11，二者相等。
1
2
3
4
5
6
7
8
9
10

public class Solution {
    public int pivotIndex(int[] nums) {
        int totalSum = 0;
        int leftSum = 0;

        // 计算数组的总和
        for (int num : nums) {
            totalSum += num;
        }

        // 遍历数组，找到中心下标
        for (int i = 0; i < nums.length; i++) {
            // 当前元素的右侧和等于总和减去左侧和和当前元素值
            if (leftSum == totalSum - leftSum - nums[i]) {
                return i;
            }
            // 更新左侧和
            leftSum += nums[i];
        }

        // 不存在中心下标
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

心得：

利用左右总和这个思路去求解非常好！

1.12 找出字符串中第一个匹配项的下标【easy】【字符串匹配】【KMP】

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
1
2
3
4

使用内置函数substring（）

class Solution {
    public int strStr(String haystack, String  ) {
        int len1 = haystack.length(), len2 = needle.length();
        for (int i = 0; i <= len1 - len2; i++) {
            String temp = haystack.substring(i, i + len2);
            if (temp.equals(needle)) {
                return i;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

使用内置函数indexOf（）

class Solution {
    public int strStr(String haystack, String needle) {
            return haystack.indexOf(needle);
    }
}
1
2
3
4
5

使用KMP标准思想

//经典KMP算法，好好体会过程！KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if (m == 0) {return 0;}
        if (n == 0) {return -1;}
        int i = 0, j = 0;
        while (i < n - m + 1) {
            while (i < n && haystack.charAt(i) != needle.charAt(j)) {
                i++;
            }
            if (i == n) { //两个都是字符串，没有首字母相等！
                return -1;
            }
            i++;
            j++;
            while (i < n && j < m && haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            }
            if (j == m) {
                return i - j; //找到相等得字符串了，回退到相等得初始位置！
            }else {   //这里就是利用到了回退，i回退到初始位置得下一个位置，j回退到初始位置！！好好理解雅！
                i -= j - 1;
                j = 0;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

心得：

好好体会KMP，要能手撕出来！这种while书写方式真的很优雅，很舒服！

2.双指针

2.2 验证回文串【easy】

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。
1
2
3

class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isLetterOrDigit(c)) {
                sb.append(c);
            }
        }
        int left = 0, right = sb.length() - 1;
        while (left < right ) {
            if (sb.charAt(left) == sb.charAt(right)) {
                left++;
                right--;
            }else {
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

心得：

记住字符串几个方法：String s; char c;
s.toLowerCase()、Character.toLowerCase(c)、Character.isLetterOrDigit()、Character.isLetter()、Character.isDigit();

2.4 两数之和-输入有序数组【mid】

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
1
2
3

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left <= right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1}; //注意看题目，下标是从1开始的！
            }else if (sum < target) {
                left++;
            }else if (sum > target) {
                right--;
            }
        }
        return new int[]{-1, -1};
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.5 盛最多水的容器

见下文接雨水问题

3.滑动窗口

3.2 无重复字符的最长字串【mid】

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
1
2
3

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int res = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            window.put(c, window.getOrDefault(c, 0) + 1);
            while (window.get(c) > 1) {
                char d = s.charAt(left);
                window.put(d, window.get(d) - 1);
                left++;
            }
            //注意这个位置是right -left，而不是right - left + 1， 因为虽然right++了，但是取的c是加之前的值！
            res = Math.max(res, right - left);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

心得：

**熟记滑动窗口的基本框架，labuladong的方法！**同时注意边界条件！

4.矩阵

5.哈希表

5.2 LRU缓存【mid】

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
1
2
3
4
5

class LRUCache {
    LinkedHashMap<Integer, Integer> map;
    int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<>();
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            makeNew(key);
            return map.get(key);
        }else {
            return -1;
        }

    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.put(key, value);
            makeNew(key);
            return;
        }
        if (map.size() >= capacity) {
            int oldKey = map.keySet().iterator().next(); //链表头最久未使用key
            map.remove(oldKey);
        }
        map.put(key, value);
    }
    public void makeNew(int key) {
        int value = map.get(key);
        map.remove(key);
        map.put(key, value);
    }
}

/**
 * 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);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

百度一面手撕
①LinkedHashMap的妙用
②oldestKey = map.keySet().iterator().next();// 链表头部就是最久未使用的 key

心得：

LinkedHashMap的妙用就是用于建立LRU这种数据结构，应为其内部是双向链表，保证了插入的顺序，所以可以保证利用类似makeNew的函数使用更新！
map.keySet().iterator().next(); 的妙用！

6.栈

6.1 有效的括号【easy】

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true
1
2

示例 2：

输入：s = "()[]{}"
输出：true
1
2

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if(n % 2 == 1){
            return  false;
        }
        Map<Character, Character> map = new HashMap<Character, Character>() {{
            // 将 })] 作为key
            put('}', '{');
            put(']', '[');
            put(')', '(');
        }};
        // 新建一个栈
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            // 如果c是 })], 则判断， 否则说明是({[ , 直接入栈
            if(map.containsKey(c)){
                // stack.peek() 获取栈顶元素
                if(stack.isEmpty() || stack.peek() != map.get(c)){
                    return false;
                }
                // 将栈顶移除(先进后出，栈顶是最接近 c 的左括号)
                stack.pop();
            }else{
                // 说明c是({[ , 直接入栈
            stack.push(c);
        }
        }
        return stack.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

心得：

碰到匹配相关的操作，想到栈这个数据结构！！
遇到“( { ["入栈，否则利用哈希表的存储映射来判断”）} ]“是否存在以及是否匹配！

6.3 最小栈【mid】

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;
    public MinStack() {
        stack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }
    
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || minStack.peek() > val) {
            minStack.push(val);
        }else {
            minStack.push(minStack.peek());
        }
    }
    //或者也可以用下边的方式，都一样，但是下边感觉好一点，思路清晰！多用Math.min()这种内置函数简化程序！
   	public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty()) {
            minStack.push(val);
        }else {
            minStack.push(Math.min(val, minStack.peek()));
        }
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

心得：

用两个栈来实现最小栈，最小栈的顶部一直维护当前栈的最小值！
多用Math.min()这种内置函数简化程序！

6.4 逆波兰表达式求值【mid】

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
1
2
3

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
1
2
3

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        for (String token : tokens) {
            if ("+-*/".contains(token)) {
                int a = stack.pop();
                int b = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(a + b);
                        break;
                    case "-":
                        stack.push(b - a);
                        break;
                    case "*":
                        stack.push(a * b);
                        break;
                    case "/":
                        stack.push(b / a);
                }
            }else {
                stack.push(Integer.parseInt(token)); //String转int的方法为：Integer.parseInt()，注意函数的拼法！
            }
        }
        return stack.pop();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

心得：

这个题目比较常见，比较经典的方法就是碰见数字入栈，碰见加减乘除运算，并将结果再入栈！
switch-case语句的使用。

6.5 输入字符串，求所有可能的出栈顺序【深信服笔试】

这个用栈方法好好体会，采用递归+回溯的方式

import java.util.*;
public class Main {
    public static void traverse(List<String> result, String input, Stack<Character> stack, String output, int k) {
        if (input.isEmpty() && stack.isEmpty() && output.length() == k) {
            result.add(output);
            return;
        }
        //栈不为空，可以出栈
        if (!stack.isEmpty()) {
            char top = stack.pop();
            traverse(result, input, stack, output + top, k);
            stack.push(top); //相当于回溯操作！！
        }
        //字符未全部入栈，即入栈
        if (!input.isEmpty()) {
            char next = input.charAt(0);
            stack.push(next);
            traverse(result, input.substring(1), stack, output, k);
            stack.pop(); //相当于回溯操作！！
        }
    }
    
    public static void main(String[] args) {
        String input = "abc";
        int k = input.length();
        List<String> list = new ArrayList<>();
        Stack<Character> stack = new Stack<>();
        traverse(list, input, stack, "", k);
        for (String sequence : list) {
            System.out.println(sequence);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

7.链表

7.3 合并两个有序链表【mid】

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
1
2
3

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode p1 = list1, p2 = list2;
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while (p1 != null && p2 != null) {
            if (p1.val > p2.val) {
                p.next = p2;
                p2 = p2.next;
            }else {
                p.next = p1;
                p1 = p1.next;
            }
            p = p.next;
        }
        if (p1 != null) {
            p.next = p1;
        }
        if (p2 != null) {
            p.next = p2;
        }
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

7.4 复制带随机指针的链表【mid】

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
1
2

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
       Map<Node, Node> map = new HashMap<>();
       for (Node p = head; p != null; p = p.next) { //利用HashMap先构建映射
           if (!map.containsKey(p)) {
               map.put(p, new Node(p.val));
           }
       }
       for (Node p = head; p != null; p = p.next) { //利用HashMap再构建链接
           if (p.next != null) {   //默认的构造函数，p的next和random都是null，所以对于null的next和random不用理会即可！
               map.get(p).next = map.get(p.next);
           }
           if (p.random != null) {
               map.get(p).random = map.get(p.random);
           }
       }
       return map.get(head); 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

心得：

巧妙地利用HashMap，先利用其构造映射关系，再利用其构造连接关系！

7.5 反转链表-给定区间【mid】

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
1
2

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]
1
2

/**
 * 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 reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            head = reverseN(head, right);
            return head;
        }
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
    ListNode successor = null;
    public ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = successor;
        return last;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

心得：

充分利用递归思想，两轮递归！其次掌握反转前N个节点的方法，与之相结合！
这道题目可以好好体会递归，思路清晰！既然递归就要注意边界条件！

8.二叉树

8.1 二叉搜索树第k小问题【mid】

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：root = [3,1,4,null,2], k = 1
输出：1
1
2


 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;
      }
  }
public class Solution {
    int res = 0;
    int count = 0;
    public int kthSmallest(TreeNode root, int k) {
        if (root == null) return 0;
        traverse(root, k);
        return res;
    }
    public void traverse(TreeNode root, int k) {
        if (root == null) return;
        traverse(root.left, k);
        count++;
        if (count == k) {
            res = root.val;
            return;
        }
        traverse(root.right, k);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

心得：

遇到二叉搜索树，最先想到其中序遍历的结果就是从小到大排序，对这个要敏感！！

8.3 相同的树【easy】

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：p = [1,2,3], q = [1,2,3]
输出：true
1
2

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }else if (p != null && q == null) {
            return false;
        }else if (p == null && q != null) {
            return false;
        }else if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

心得：

纯递归问题，想一想每一步的操作是怎样的，把每一步的思维打通，那么所有的步骤就是一样的！

8.5 对称二叉树【easy】

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：root = [1,2,2,3,4,4,3]
输出：true
1
2

class Solution {
    public boolean isSymmetric(TreeNode root) {
        boolean check = getResult(root.left, root.right);
        return check;
    }
    public boolean getResult(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left != null && right == null) {
            return false;
        }
        if (left == null && right != null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        boolean check = getResult(left.left, right.right) && getResult(left.right, right.left);
        return check;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

8.6 从前序遍历和中序遍历中构造二叉树【mid】

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
1
2

/**
 * 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 {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }

        return findNode(preorder, 0, preorder.length, inorder,  0, inorder.length);  // 前闭后开
    }

    public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
        // 参数里的范围都是前闭后开
        if (preBegin >= preEnd || inBegin >= inEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(preorder[preBegin]);  // 找到前序遍历的第一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定前序数列的个数
        root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,
                            inorder, inBegin, rootIndex);
        root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd,
                            inorder, rootIndex + 1, inEnd);

        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

心得：

递归千万不要忘了base case，即边界条件！除此之外左闭右开这个也要原则要保持不变！
每一次递归的本质是找到左边的下一个根节点和右边的下一个根节点，重复往返即可！
确定一个唯一二叉树，可以用中序+后序，或者是前序+中序，重点是先去确定根节点，再根据根节点找左右子树！

8.7 从中序和后序遍历构造二叉树【mid】

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
1
2

/**
 * 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 {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int inEnd = inorder.length, postEnd = postorder.length;
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return traverse(inorder, 0, inEnd, postorder, 0, postEnd); //左闭右开
    }
    public TreeNode traverse(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        if (inBegin >= inEnd || postBegin >= postEnd) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postEnd - 1]);
        int index = map.get(postorder[postEnd - 1]);
        int lenOfRight = inEnd - index;
        root.left = traverse(inorder, inBegin, index, postorder, postBegin, postEnd - lenOfRight);
        root.right = traverse(inorder, index + 1, inEnd, postorder, postEnd - lenOfRight, postEnd - 1);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

或者：

/**
 * 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 {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; ++i) {
            map.put(inorder[i], i);
        }
        return constructTree(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    public TreeNode constructTree(int[] inorder, int inbegin, int inend, int[] postorder, int pobegin, int poend) {
        if (inbegin >= inend || pobegin >= poend) {
            return null;
        }
        int rootIndex = map.get(postorder[poend - 1]);
        TreeNode root = new TreeNode(inorder[rootIndex]);
        int lenOfLeft = rootIndex - inbegin;
        root.left = constructTree(inorder, inbegin, rootIndex, postorder, pobegin, pobegin + lenOfLeft);
        root.right = constructTree(inorder, rootIndex + 1, inend, postorder, pobegin + lenOfLeft, poend - 1);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

这两个区别就在于看你相求lenOfLeft还是lenOfRight的长度！

心得：

利用中序+后序的方式解决，注意好边界条件即可！

8.8 填充每一个结点的下一个右侧结点指针II

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
1
2
3
4
5
6

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。
1
2
3

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root == null) return null; //这个不能丢！要有这个判断！！
        Queue<Node> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()) {
            int len = que.size();
            Node pre = null; //这个用的很妙！放的位置也很好！
            while (len > 0) {
                Node node = que.poll();
                if (pre != null) {
                    pre.next = node;
                }
                pre = node;
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
                len--;
            }
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

心得：

BFS去遍历！采用标准BFS遍历模板！
注意：让每一层的遍历之间增加指针连接，所以在层遍历地方增加代码，然后增添一个指针pre，用来指向每层的每个位置，初始的时候每个节点next已经置为null，所以不需要再给每个节点置为null，只关心让他们之间产生连接就可以！
这个pre指针用的很妙，放的位置很好！

8.9 二叉树展开为链表【mid】

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
1
2

/**
 * 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) {
        if (root == null) return;
        //整体思路有点像归并排序的递归！都是利用的“后序遍历”解决的！！好好体会！
        flatten(root.left);
        flatten(root.right);
        //这个时候左右子树都已经flatten了，只去考虑最后一步就行！（后序遍历就只去考虑最后一步，前序遍历只去考虑第一步！）
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = null;
        root.right = left;
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        p.right = right;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

心得：

整体思路有点像归并排序的递归！都是利用的“后序遍历”解决的！！好好体会！ flatten(root.left);
flatten(root.right);
//这个时候左右子树都已经flatten了，只去考虑最后一步就行！（后序遍历就只去考虑最后一步，前序遍历只去考虑第一步！）
后续遍历方式解决问题！！碰到递归这种问题很好解决！

9.图

10.回溯

什么是回溯算法？

其实回溯算法和我们常说的 DFS 算法非常类似，本质上就是一种暴力穷举算法。回溯算法和 DFS 算法的细微差别是**：回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」！**

回溯算法框架：解决一个回溯问题，实际上就是一个决策树的遍历过程，站在回溯树的一个节点上，你只需要思考 3 个问题：

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。

3、结束条件：也就是到达决策树底层，无法再做选择的条件。

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
 
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
1
2
3
4
5
6
7
8
9
10

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。

需要注意：回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。如：O(N!)

对于回溯问题，有几种形式：一般是标准子集\组合\排列问题

1、形式一、元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式。
以组合为例，如果输入 nums = [2,3,6,7]，和为 7 的组合应该只有 [7]。

2、形式二、元素可重不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次。
以组合为例，如果输入 nums = [2,5,2,1,2]，和为 7 的组合应该有两种 [2,2,2,1] 和 [5,2]。

3、形式三、元素无重可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次。

经典案例如下：

10.1 组合问题-元素无重不可复选【mid】

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
1
2
3
4
5
6
7
8
9
10

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(n, res, track, k, 1);
        return res;
    }
    public void backtrack(int n, List<List<Integer>> res, LinkedList<Integer> track, int k, int start) {
        if (track.size() == k) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = start; i <= n; i++) {
            track.add(i);
            backtrack(n, res, track, k, i + 1);
            track.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

10.2 子集-元素无重不可复选【mid】

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
1
2

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, res, track, 0);
        return res;
    }
    public void backtrack(int[] nums, List<List<Integer>> res, LinkedList<Integer> track, int start) {
        res.add(new LinkedList<>(track));
        for (int i = start; i < nums.length; i++) {
            track.add(nums[i]);
            backtrack(nums, res, track, i + 1);
            track.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

10.4 子集/组合（元素可重不可复选）

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> track = new LinkedList<>();
        Arrays.sort(nums);//要让相同的元素放在一起，必须先进行排序！
        //除此之外要搞清楚什么时候要used数组什么时候不用，当要进行排列的时候（即要倒回去遍历前面的数）才要用used数组！
        backtrack(nums, res, track, 0);
        return res;
    }
    public void backtrack(int[] nums, List<List<Integer>> res, LinkedList<Integer> track, int start) {
        res.add(new LinkedList<>(track));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i - 1] == nums[i]) { //这里要用i > start而不是i > 0！因为要用每一层的起始点为开始，start为每一层的起始点，0则是第一层的起始点！
                continue;
            }
            track.add(nums[i]);
            backtrack(nums, res, track, i + 1);
            track.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

心得：

对于可重，一定要先对数组进行排序！！

10.6 排列（元素可重不可复选）

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> track = new LinkedList<>();
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        backtrack(nums, res, track, used);
        return res;
    }
    public void backtrack(int[] nums, List<List<Integer>> res, LinkedList<Integer> track, boolean[] used) {
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) {
                // 如果前面的相邻相等元素没有用过，则跳过，这里边这个 !used[i - 1] 很巧妙
                // [1,2,2'] 和 [1,2',2] 应该只被算作同一个排列，但被算作了两个不同的排列。所以现在的关键在于，如何设计剪枝逻辑，把这种重复去除掉？答案是，保证相同元素在排列中的相对位置保持不变。比如说 nums = [1,2,2'] 这个例子，我保持排列中 2 一直在 2' 前面。
                continue;
            }
            if (used[i]) {
                continue;
            }
            track.add(nums[i]);
            used[i] = true;
            backtrack(nums, res, track, used);
            track.removeLast();
            used[i] = false;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

标准全排列算法之所以出现重复，是因为把相同元素形成的排列序列视为不同的序列，但实际上它们应该是相同的；而如果固定相同元素形成的序列顺序，当然就避免了重复。

那么反映到代码上，你注意看这个剪枝逻辑：

// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
    // 如果前面的相邻相等元素没有用过，则跳过
    continue;
}
// 选择 nums[i]
1
2
3
4
5
6

当出现重复元素时，比如输入 nums = [1,2,2’,2’‘]，2’ 只有在 2 已经被使用的情况下才会被选择，同理，2’’ 只有在 2’ 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。

10.7 子集/组合（元素无重可复选）

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> track = new LinkedList<>();
        int trackSum = 0;
        backtrack(candidates, target, res, track, trackSum, 0);
        return res;
    }
    public void backtrack(int[] candidates, int target, List<List<Integer>> res, LinkedList<Integer> track, int trackSum, int start) {
        if (trackSum == target) {
            res.add(new LinkedList<>(track));
            return;
        }
        if (trackSum > target) {
            return; //这个不要忘记写！！当总和大于当前值，就没必要继续往下遍历了，直接返回退出就行！
        }
        for (int i = start; i < candidates.length; i++) { //这里要从start开始，不然会出现重复的情况！第一列的向下遍历都能遍历到，第二列的遍历的话就只能第二个数及之后的数字了！
            trackSum += candidates[i];
            track.add(candidates[i]);
            backtrack(candidates, target, res, track, trackSum, i); //这里要写i而不是i + 1，因为每个元素可重复使用！！
            trackSum -= candidates[i];
            track.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

10.8 排列（元素无重可复选）

力扣上没有类似的题目，我们不妨先想一下，nums 数组中的元素无重复且可复选的情况下，会有哪些排列？

比如输入 nums = [1,2,3]，那么这种条件下的全排列共有 3^3 = 27 种：

[
[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],
[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],
[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]
]
标准的全排列算法利用 used 数组进行剪枝，避免重复使用同一个元素。如果允许重复使用元素的话，直接放飞自我，去除所有 used 数组的剪枝逻辑就行了。

那这个问题就简单了，代码如下：

class Solution {

    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();

    public List<List<Integer>> permuteRepeat(int[] nums) {
        backtrack(nums);
        return res;
    }

    // 回溯算法核心函数
    void backtrack(int[] nums) {
        // base case，到达叶子节点
        if (track.size() == nums.length) {
            // 收集叶子节点上的值
            res.add(new LinkedList(track));
            return;
        }

        // 回溯算法标准框架
        for (int i = 0; i < nums.length; i++) {
            // 做选择
            track.add(nums[i]);
            // 进入下一层回溯树
            backtrack(nums);
            // 取消选择
            track.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

10.9 电话号码的字母组合【mid】

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
1
2

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new LinkedList<>();
        if (digits.length() == 0) return res;
        StringBuilder sb = new StringBuilder();
        Map<Character, String> map = new HashMap<>(){{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(res, map, digits, sb, 0);
        return res;
    }
    public void backtrack(List<String> res, Map<Character, String> map, String digits, StringBuilder sb, int start) {
        if (sb.length() == digits.length()) {
            res.add(sb.toString());
            return;
        }
        for (int i = start; i < digits.length(); i++) {
            String str = map.get(digits.charAt(i));
            for (char c: str.toCharArray()) {
                sb.append(c);
                backtrack(res, map, digits, sb, i + 1);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

心得：

hash + 回溯
本质还是回溯，只不过再回溯模板的横向遍历基础上的下边再加一个循环！
注意：sb.deleteCharAt()这个方法要熟悉！

10.10 括号生成【mid】

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
1
2

示例 2：

输入：n = 1
输出：["()"]
1
2

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n == 0) return res;
        StringBuilder track = new StringBuilder();
        backtrack(res, track, n, n);
        return res;
    }
    public void backtrack(List<String> res, StringBuilder track, int left, int right) {
        if (left > right) return; //对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量!所以剩下的left一定要小于right！
        if (left < 0 || right < 0) return;
        if (left == 0 && right == 0) {
            res.add(track.toString());
            return;
        }
        track.append("(");
        backtrack(res, track, left - 1, right);
        track.deleteCharAt(track.length() - 1);

        track.append(")");
        backtrack(res, track, left, right - 1);
        track.deleteCharAt(track.length() - 1);

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

心得：

一个「合法」括号组合的左括号数量一定等于右括号数量，这个很好理解。
对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0…i] 中左括号的数量都大于或等于右括号的数量!所以剩下的left一定要小于right！
利用StringBulider作为track进行回溯！

10.11 不连续的1的所有字符串【地平线笔试】

写一个函数，输入是长度n，要求找到所有的长度为n的且不能出现连续1的二级制字符串(由01组成)，并给出实现的算法复杂度

要求:时间复杂度越低越好

输入描述
N是一个正整数
输出描述
所有满足要求字符串的集合，通过空格分隔结果
1
2
3
4

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        int n = 3;
        List<String> result = findNonConsecutiveOnes(n);
        for (String str : result) {
            System.out.print(str + " ");
        }
    }

    public static List<String> findNonConsecutiveOnes(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, "", n, false);
        return result;
    }

    private static void backtrack(List<String> result, String str, int n, boolean hasOne) {
        if (str.length() == n) {
            result.add(str);
            return;
        }

        if (hasOne) {
            backtrack(result, str + "0", n, false);
        } else {
            backtrack(result, str + "0", n, false);//回溯法的这里之后可以理解为后撤，所以这两个语句可以理解为并列！
            backtrack(result, str + "1", n, true);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

心得：

backtrack(result, str + "0", n, false);//回溯法的这里之后可以理解为后撤，所以这两个语句可以理解为并列！
backtrack(result, str + "1", n, true);
本质思路：出现“1”就放“0”，没出现就并列的放“0”或“1”，用has这个boolean类型变量判断是否出现“1”和“0”！

11.二分查找

12.动态规划

12.1 劫舍问题

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
1
2
3
4

class Solution {
    public int rob(int[] nums) {
        int N = nums.length;
        int[] dp = new int[N + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= N; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]); //这里nums[i - 1],而不是nums[i]，一定注意，因为i是取到N的！
        }
        return dp[N];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

12.2 不同路径-走格子问题

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：m = 3, n = 7
输出：28
1
2

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

12.3 爬楼梯问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
1
2
3
4
5

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11

12.4 分发巧克力，求最小周长【顺丰笔试】

小丽明天要出去和同学春游。她准备带上总面积恰好为n的巧克力板(简化起见将巧克力板视为平面图形，忽略它的厚度，只考虑面积)去和同学们一起分享。出于美感的考虑，小丽希望她带上的巧克力板都是边长为整数的正方形;另一方面出于便携性考虑，小丽希望这些巧克力板的周长之和尽可能小。请你帮小丽找出可能的最小周长!
换句话说，小丽需要你帮忙找出k个小正方形巧克力板，边长分别为 aq,az……ak，使得其面积之和，即∑1≤i≤ka?，恰好为要求的总面积为n;同时，使得总周长，即Σ1

输入描述
一行，1个整数n，表示小丽希望带上的巧克力板总面积。1≤n≤50000

输出描述
输出一行一个整数表示可能的最小周长

样例输入
11
样例输出
20
1
2
3
4
5
6
7
8
9
10

import java.util.Arrays;

public class ChocolateBoard {
    public static void main(String[] args) {
        int n = 11;
        int result = findMinPerimeter(n);
        System.out.println(result);
    }

    public static int findMinPerimeter(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 4 * j);
            }
        }

        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

心得：

定义一个数组dp，dp[i]表示总面积为i的巧克力板的最小周长。然后，我们可以通过以下的递推公式来计算dp[i]的值：

dp[i] = mindp[i], (dp[i - j * j] + 4 * j) for j in [1, sqrt(i)] 其中，j表示当前正方形巧克力板的边长。

12.5 取到不相邻数之和的最大值【地平线笔试】

小红拿到了一个数组。她想取一些不相邻的数，使得取出来的数之和尽可能大。你能帮帮她吗?

输入描述
第一行输入一个正整数n，代表数组长度第二行输入n个正整数ai，代表整个数组。

输出描述
不相邻的数的最大和。

示例1
输入输出示例仅供调试，后台判题数据一般不包含示例
输入	 	
4
2 6 4 1
输出
7
1
2
3
4
5
6
7

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        if (n == 1) {
            System.out.println(arr[0]);
            return;
        } else if (n == 2) {
            System.out.println(Math.max(arr[0], arr[1]));
            return;
        }

        int[] dp = new int[n];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);

        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);
        }

        System.out.println(dp[n - 1]);

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

心得：

DP[i] 应该是存储 DP[0] 到DP[i] 不相邻的数组最大值的。边界条件：dp[0] = arr[0], d[1] = arr[1]!
那么，DP[i]的值应该取决于它前面不相邻数组的最大值，要么是DP[i-1] 的不相邻数组，要么是DP[i-2] 再加上它自身，所以推导出，DP[i] = max(DP[i-1], DP[i-2]+DP[i]) 。
本质还是递推公式推到和边界条件确认！！

12.6 零钱兑换【mid】

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
1
2
3

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); //总数为amount的金额，最多使用金额为1的零钱凑amount次，因此amount + 1是最大的数值，为什么这里不用Integer.MAX_VALUE，因为后面有1 + dp[i - coin]，容易造成整型溢出的问题！
        dp[0] = 0;//注意书写位置！不能在Arrays.fill()之前！
        for (int i = 0; i < dp.length; i++) {
            for (int coin: coins) {
                if (i - coin < 0) {
                    continue;
                }
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }

        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

心得：

凑零钱是非常经典的动态规划问题，好好体会！
动态规划注意三个核心：①dp[i]代表含义 ②状态转移方程 ③边界条件

12.7 单词拆分【mid】

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
1
2
3

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

心得：

好好理解状态转移方程：dp[i]=dp[j] && check(s[j..i−1])
利用hash这种数据结构来快速判断某个元素是否在一个集合中！

13.排序相关—【归并】【快排】

13.1 快排【经常考察的题】【一定掌握】【不稳定】

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]
1
2

class Solution {
    public int[] sortArray(int[] nums) {
        int left = 0, right = nums.length - 1;
        quickSort(nums, left, right);
        return nums;
    }

    public void quickSort(int[] nums, int left, int right) {
        int i = left, j = right;
        if (left >= right) return;
        int allow = nums[left];
        while (i < j) {
            while (i < j && nums[j] >= allow) { //划重点！这里一定要先看左边再看右边！不能交换位置！
                j--;
            }
            while (i < j && nums[i] <= allow) {
                i++;
            }
            if (i < j) { 这里i < j不能丢！
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }
        nums[left] = nums[i];
        nums[i] = allow;
        quickSort(nums, left, j - 1); //此时这个地方为j - 1，因为j已经排好序了，不能有j！！
        quickSort(nums, j + 1, right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

13.2 归并排序【同样重要！！！】【稳定】

class Solution {
    public int[] sortArray(int[] nums) {
        int[] temp = new int[nums.length];
        int left = 0, right = nums.length - 1;
        mergeSort(nums, temp, left, right);
        return nums;
    }
    public void mergeSort(int[] nums, int[] temp, int left, int right) {
        if (left < right) { //这个条件别忘了！！
            int mid = (left + right) / 2;
            mergeSort(nums, temp, left, mid);
            mergeSort(nums, temp, mid + 1, right);
            merge(nums, temp, left, mid, right);
        }
    }
    public void merge(int[] nums, int[] temp, int left, int mid, int right) {
        int i = 0;
        int high = mid + 1;
        int low = left;
        while (low <= mid && high <= right) {
            if (nums[low] < nums[high]) {
                temp[i++] = nums[low++];
            }else {
                temp[i++] = nums[high++];
            }
        }
        while (low <= mid) {
            temp[i++] = nums[low++];
        }
        while (high <= right) {
            temp[i++] = nums[high++];
        }
        for (int m = 0; m < i; m++) {
            nums[left + m] = temp[m]; //注意这里的写法！
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

心得：

无论快排还是归并排序，都是利用的递归的方式来求解的！所以一定都得注意它们的边界条件，例如if (left >= right)！
对于快排，要先看右边再看左边，while大循环下边的判断语句不能丢！
对于归并，首先新建立了临时数组作为存储，其次在算法最后将临时数组赋值给原数组时注意边界写法！

13.3 冒泡排序【稳定】

public class demo_sort {
    public static void main(String[] args) {
        //冒泡排序算法
        int[] numbers=new int[]{1,5,8,2,3,9,4};
        //需进行length-1次冒泡
        for(int i=0;i<numbers.length-1;i++)
        {
            for(int j=0;j<numbers.length-1-i;j++)
            {
                if(numbers[j]>numbers[j+1])
                {
                    int temp=numbers[j];
                    numbers[j]=numbers[j+1];
                    numbers[j+1]=temp;
                }
            }
        }
        System.out.println("从小到大排序后的结果是:");
        for(int i=0;i<numbers.length;i++)
            System.out.print(numbers[i]+" ");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

14.矩阵

14.1 螺旋矩阵【mid】【快手手撕原题】

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new LinkedList<>();
        int row = matrix.length, col = matrix[0].length;
        //边界条件
        int left = 0, right = col - 1, top = 0, down = row - 1;
        while (col * row > res.size()) {
            for (int i = left; i <= right && col * row > res.size(); i++) {
                res.add(matrix[top][i]);
            }
            for (int i = top + 1; i < down && col * row > res.size(); i++) {
                res.add(matrix[i][right]);
            }
            for (int i = right; i >= left && col * row > res.size(); i--) {
                res.add(matrix[down][i]);
            }
            for (int i = down - 1; i > top && col * row > res.size(); i--) {
                res.add(matrix[i][left]);
            }
            left++;
            right--;
            top++;
            down--;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

心得：

写好四个边界条件，再去写四个循环，这个写循环的过程很爽，思路也很清晰！
注意的是while循环下的for循环语句，其条件判定不能少col * row > res.size()，因为while循环下可能执行的执行的其col * row就可能小于res.size()！

14.2

15.最大/小堆（优先级队列）

15.1 最小堆数组【笔试题】

给定整数数组nums和整数k，请返回数组中第k个最大的元素。
请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素，使用最小堆解决

示例1
输入输出示例仅供调试，后台判题数据一般不包含示例
输入	复制	
[41,59,13,87,40,37],3
输出	复制	
41

示例2
输入输出示例仅供调试，后台判题数据一般不包含示例
输入	 	
[9,6，6，4，3，3，2，2,1],3
输出	 	
6
1
2
3
4
5
6
7
8
9
10
11
12
13

import java.util.PriorityQueue;

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 创建一个最小堆，默认创建就是最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        // 将数组元素添加到最小堆
        for (int num : nums) {
            minHeap.add(num);
            
            // 如果最小堆的大小超过k，移除堆顶元素，保持堆的大小为k
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        
        // 返回堆顶元素即为第k个最大元素
        return minHeap.peek();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

心得：

碰到这种第k大/第k小的问题想到PriorityQueue，定义最大/最小堆的技巧就是：看题目要第k大，就定义最小堆，要第k小，就定义最大堆！
同时也要注意后面的那种编程风格，用for-each语句，先添加，等到数组大于预期时就poll，好好体会！

16.区间问题

16.1 合并区间【mid】【招银面试】

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
1
2
3

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
1
2
3

class Solution {
    public int[][] merge(int[][] intervals) {
        LinkedList<int[]> res = new LinkedList<>();
        Arrays.sort(intervals, (a, b) -> (a[0] - b[0]));
        res.add(intervals[0]);
        //int count = 1; //变形的解法
        for (int i = 1; i < intervals.length; i++) {
            int[] curArr = intervals[i];
            int[] lastArr = res.getLast(); //LinkedList引用的方法有getLast和getFirst函数！
            if (curArr[0] <= lastArr[1]) {
                lastArr[1] = Math.max(curArr[1], lastArr[1]);//这个地方一定要用curArr[1]和lastArr[1]的最大值！
            }else {
                res.add(curArr);
                //count++;
            }
        }
        return res.toArray(new int[0][]); //这里放引用数据类型！
    }
}
//招银网络科技做了一点变形，计算对应的不同区间的数量！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

心得：

很好的思路：将每个数组的初始值进行排序！然后逐个遍历去找到end的最大值！
其中list.toArray(new int[0] [])，括号里要放引用数据类型，这里是二维数组，所以就要写二维数组！
注意：lastArr[1] = Math.max(curArr[1], lastArr[1]);//这个地方一定要用curArr[1]和lastArr[1]的最大值!

17.接雨水问题

17.1 盛最多水的容器【mid】

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
1
2
3

示例 2：

输入：height = [1,1]
输出：1
1
2

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int res = 0;
        while (left < right) {
            int curArea = Math.min(height[left], height[right]) * (right - left);
            res = Math.max(curArea, res);
            if (height[left] < height[right]) { //移动较小的那个高度即可！
                left++;
            }else {
                right--;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

心得：

接雨水问题！双指针移动！           
 if (height[left] < height[right]) { //移动较小的那个高度即可！
                left++;
            }else {
                right--;
            }
1
2
3
4
5
6

17.2 接雨水【hard】

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
1
2
3

class Solution {
    public int trap(int[] height) {
        int res = 0;
        int n = height.length;
        int[] l_max = new int[n];
        int[] r_max = new int[n];
        //base case
        l_max[0] = height[0];
        r_max[n - 1] = height[n - 1];
        for (int i = 1; i < n; i++) {
            l_max[i] = Math.max(height[i], l_max[i - 1]);
        }
        for (int i = n - 2; i >= 0; i--) {
            r_max[i] = Math.max(height[i], r_max[i + 1]);
        }
        for (int i = 1; i < n - 1; i++) { //注意：左右两边肯定是不会存水的，所以遍历的区间是1~n-1
            res += Math.min(l_max[i], r_max[i]) - height[i];
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

对于任意一个i，能够装的水为：（重点）

water[i] = min(
          //左边最高的柱子
           max(height[0..i]),
          // 右边最高的柱子
           max(height[i..end])
        ) - height[i]
1
2
3
4
5
6

心得：

动态规划+预数组方式求解！空间换时间解决！！

18.数学

18.1 回文数【easy】

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

通过数学方式解决：

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || x % 10 == 0 && x != 0){
            return false;
        }
        return x == get(x);
    }
    private int get(int x){
        int ans = 0;
        while (x > 0){
            ans = ans * 10 + x % 10;
            x /= 10;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

通过转化字符串双指针的方式求解：

class Solution {
    public boolean isPalindrome(int x) {
        String str = String.valueOf(x);
        int len = str.length();
        int left = 0, right = len - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }else {
                left++;
                right--;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

心得：

通过数学的这种方式好非常熟练，怎么取个位？取除个位数字？翻转数字？

18.2 阶乘后的0【easy】

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1：

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
1
2
3

class Solution {
    public int trailingZeroes(int n) {
        int res = 0;
        int diversion = 5;
        while (n >= diversion) {
            res += n / diversion;
            diversion *= 5;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11

数学思路：

首先，两个数相乘结果末尾有 0，一定是因为两个数中有因子 2 和 5，也就是说，问题转化为：n! 最多可以分解出多少个因子 2 和 5？

最多可以分解出多少个因子 2 和 5，主要取决于能分解出几个因子 5，因为每个偶数都能分解出因子 2，因子 2 肯定比因子 5 多得多。

那么，问题转化为：n! 最多可以分解出多少个因子 5？难点在于像 25，50，125 这样的数，可以提供不止一个因子 5，不能漏数了。

这样，我们假设 n = 125，来算一算 125! 的结果末尾有几个 0：

首先，125 / 5 = 25，这一步就是计算有多少个像 5，15，20，25 这些 5 的倍数，它们一定可以提供一个因子 5。

但是，这些足够吗？刚才说了，像 25，50，75 这些 25 的倍数，可以提供两个因子 5，那么我们再计算出 125! 中有 125 / 25 = 5 个 25 的倍数，它们每人可以额外再提供一个因子 5。

够了吗？我们发现 125 = 5 x 5 x 5，像 125，250 这些 125 的倍数，可以提供 3 个因子 5，那么我们还得再计算出 125! 中有 125 / 125 = 1 个 125 的倍数，它还可以额外再提供一个因子 5。

这下应该够了，125! 最多可以分解出 25 + 5 + 1 = 31 个因子 5，也就是说阶乘结果的末尾有 31 个 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

心得：

数学的方式求5的因数，有5 / 25 / 125 ···等

18.3 加一-数学方法（取模、进位等操作）

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
1
2
3

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] = digits[i] % 10;
            if (digits[i] != 0) return digits;
        }
        //考虑进位操作！
        digits = new int[n + 1];
        digits[0] = 1;
        return digits;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

心得：

考虑末尾是9和不是9的数即可，充分利用取模运算，理解题目本意
注意99， 999， ···这种特殊情况，直接new一个新数组，0位置1即可！

18.4 x的算术平方根【easy】

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去。

**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2
1
2

class Solution {
    public int mySqrt(int x) {
        int left = 0, right = x;
        int res = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if ((long)mid * mid <= x) { //注意这里一定要用long强制转换，否则超出限制超时！
                res = mid;
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

心得：

利用二分查找的方式去找合适的值！很巧妙！

18.5 实现Pow（x， n）【mid】

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
1
2

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100
1
2

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return n < 0 ? 1.0 / getResult(x, -n) : getResult(x, n);
    }
    public double getResult(double x, int k) {
        if (k == 0) {
            return 1.0;
        }
        double res = getResult(x, k / 2); //类似于后续遍历！
        return k % 2 == 0 ? res * res : res * res * x;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：O(log⁡n)，即为递归的层数。

空间复杂度：O(log⁡n)，即为递归的层数。这是由于递归的函数调用会使用栈空间。

心得：

递归的方式求解，类似与后续遍历的方式求解！

19.多线程相关

19.1 用两个线程交替打印`1a2b3c···`【Momenta面试原题】

利用notify（）和wait（）方法实现：

public class Solution1 {


    private static final Object lock=new Object();

    private static final char[] nub="123456789".toCharArray();

    private static final char[] abc="abcdefghi".toCharArray();


    public static void main(String[] args){

        new Thread(()->{
            synchronized(lock){
                for(char n:nub){
                    System.out.println(n);
                    try {
                        lock.notify();//先唤醒另一个线程
                        lock.wait();//让出锁
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                //lock.notify();
            }
        }).start();


        new Thread(()->{
            synchronized (lock){
                for(char a:abc){
                    System.out.println(a);
                    try {
                        lock.notify();
                        lock.wait();
                    }catch (InterruptedException e){
                        e.printStackTrace();
                    }
                }
                //lock.notify();

            }
        }).start();

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

20.位运算

20.1 二进制求和【easy】

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

输入:a = "11", b = "1"
输出："100"
1
2

示例 2：

输入：a = "1010", b = "1011"
输出："10101"
1
2

class Solution {
    public String addBinary(String a, String b) {
        int p1 = a.length() - 1, p2 = b.length() - 1;
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        while (p1 >= 0 || p2 >= 0 || carry != 0) {
            int num1 = p1 >= 0 ? a.charAt(p1--) - '0' : 0; //p1和p2不要忘记减一！！
            int num2 = p2 >= 0 ? b.charAt(p2--) - '0' : 0;
            int res = num1 + num2 + carry;
            carry = res / 2; //如果是十进制就/10
            res = res % 2;   //如果是十进制就%10，这是书写不同进制最常用的方法！
            sb.append(res);  //对于StringBulilder来说res不用转换为String！
        }
        return sb.reverse().toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

心得：

对于不同进制，最大的区别就是取模和整除的数字不同而已！！
p1和p2指针不要忘记减一！！

20.2 颠倒二进制位【easy】

颠倒给定的 32 位无符号整数的二进制位。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

示例 1：

输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
1
2
3
4

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32 && n != 0; i++) {
            res |= (n & 1) << (31 - i);
            n >>>= 1;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11

心得：

注意 n & 1 这个判定条件，这条语句取的是最右边的数，当最右边为1时结果为1，最右边为0时结果为0，取到最后一位后然后让其左移31-i位和res进行或操作！！最后n再把最右边的一位移除即可，重复循环!
经典位操作，好好体会！

20.3 位1的个数【easy】

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 3 中，输入表示有符号整数 -3。

示例 1：

输入：n = 00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
1
2
3

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            if ((n & 1) == 1) {
                count++;
            }
            n >>>= 1;
        }
        return count;
        
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14

心得：

注意 n & 1 的巧妙用法！！

20.4 只出现一次的数字【easy】

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]
输出：1
1
2

比较直接想到的解法就是利用HashMap的方式来求解：

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int res = 0;
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            if (entry.getValue() == 1) {
                res = entry.getKey();
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

但是题目要求线性时间复杂度来求解，所以可以利用更巧妙的异或运算来求解！

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9

心得：

a ^ a = 0, a ^ b = 1, 0 ^ a = a !注意0和任意数字异或结果为数字本身！
注意异或这种巧妙地方法！

code.cn/problems/add-binary/?envType=study-plan-v2&envId=top-interview-150)

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

输入:a = "11", b = "1"
输出："100"
1
2

示例 2：

输入：a = "1010", b = "1011"
输出："10101"
1
2

class Solution {
    public String addBinary(String a, String b) {
        int p1 = a.length() - 1, p2 = b.length() - 1;
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        while (p1 >= 0 || p2 >= 0 || carry != 0) {
            int num1 = p1 >= 0 ? a.charAt(p1--) - '0' : 0; //p1和p2不要忘记减一！！
            int num2 = p2 >= 0 ? b.charAt(p2--) - '0' : 0;
            int res = num1 + num2 + carry;
            carry = res / 2; //如果是十进制就/10
            res = res % 2;   //如果是十进制就%10，这是书写不同进制最常用的方法！
            sb.append(res);  //对于StringBulilder来说res不用转换为String！
        }
        return sb.reverse().toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

心得：

对于不同进制，最大的区别就是取模和整除的数字不同而已！！
p1和p2指针不要忘记减一！！

20.2 颠倒二进制位【easy】

颠倒给定的 32 位无符号整数的二进制位。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

示例 1：

输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
1
2
3
4

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32 && n != 0; i++) {
            res |= (n & 1) << (31 - i);
            n >>>= 1;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11

心得：

注意 n & 1 这个判定条件，这条语句取的是最右边的数，当最右边为1时结果为1，最右边为0时结果为0，取到最后一位后然后让其左移31-i位和res进行或操作！！最后n再把最右边的一位移除即可，重复循环!
经典位操作，好好体会！

20.3 位1的个数【easy】

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 3 中，输入表示有符号整数 -3。

示例 1：

输入：n = 00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
1
2
3

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            if ((n & 1) == 1) {
                count++;
            }
            n >>>= 1;
        }
        return count;
        
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14

心得：

注意 n & 1 的巧妙用法！！

20.4 只出现一次的数字【easy】

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]
输出：1
1
2

比较直接想到的解法就是利用HashMap的方式来求解：

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int res = 0;
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            if (entry.getValue() == 1) {
                res = entry.getKey();
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

但是题目要求线性时间复杂度来求解，所以可以利用更巧妙的异或运算来求解！

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9

心得：

a ^ a = 0, a ^ b = 1, 0 ^ a = a !注意0和任意数字异或结果为数字本身！
注意异或这种巧妙地方法！

相关阅读:
GPT引领前沿与应用突破之GPT4科研实践技术与AI绘图
 【Maven学习】3.9 实验九：继承
 JAVA SPI
[附源码]SSM计算机毕业设计江苏人才信息管理系统JAVA
获取商品历史价格返回值说明
 2023-9-8 求组合数(四)
【剑指 Offer 66. 构建乘积数组】（很巧妙）
2019阿里java面试题
 C#调用Windows API实现自定义打印纸张大小
 唯一索引、普通索引
原文地址：https://blog.csdn.net/weixin_45564943/article/details/133911039

算法刷题总结（全）

刷题总结

文章目录

1.数组/字符串

1.1 合并两个有序数组【easy】

1.2 移除元素【easy】

1.3 删除有序数组中的重复项【easy】

1.4 删除有序数组中的重复项II【mid】

1.5 多数元素【easy】

1.6 大数相加—【美团面试手撕题目】

1.7 轮转数组【mid】

1.8 买卖股票的最佳时机【easy】

1.9 买卖股票的最佳时机II【mid】

1.10 跳跃游戏【mid】

1.11 数组左右之和相等【笔试题】

2.双指针

2.5 盛最多水的容器

3.滑动窗口

4.矩阵

5.哈希表

6.栈

6.5 输入字符串，求所有可能的出栈顺序【深信服笔试】

7.链表

7.4 复制带随机指针的链表【mid】

7.5 反转链表-给定区间【mid】

8.二叉树

9.图

10.回溯

经典案例如下：

10.4 子集/组合（元素可重不可复选）

10.6 排列（元素可重不可复选）

10.7 子集/组合（元素无重可复选）

10.8 排列（元素无重可复选）

10.11 不连续的1的所有字符串【地平线笔试】

11.二分查找

12.动态规划

12.4 分发巧克力，求最小周长【顺丰笔试】

12.5 取到不相邻数之和的最大值【地平线笔试】

13.排序相关—【归并】【快排】

13.1 快排【经常考察的题】【一定掌握】【不稳定】

13.2 归并排序【同样重要！！！】【稳定】

13.3 冒泡排序【稳定】

14.矩阵

14.1 螺旋矩阵【mid】【快手手撕原题】

15.最大/小堆（优先级队列）

15.1 最小堆数组【笔试题】

16.区间问题

16.1 合并区间【mid】【招银面试】

17.接雨水问题

18.数学

18.2 阶乘后的0【easy】

19.多线程相关

19.1 用两个线程交替打印1a2b3c···【Momenta面试原题】

20.位运算

19.1 用两个线程交替打印`1a2b3c···`【Momenta面试原题】