1. 两数之和（哈希表解法）

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

示例 1 ：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2 ：

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

示例 3 ：

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

提示：

1
2
3
4
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

哈希表解法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0 ; i < nums.length; i++){
            if( map.containsKey(target - nums[i])){
                return new int[]{map.get(target - nums[i]), i};
            }else{
                map.put( nums[i],i );
            }
        }
        return new int[0];
    }
}

2. 两数相加（模拟解法）

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

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

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

img

示例 1：

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

示例 2：

1
2
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

1
2
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

1
2
3
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

模拟解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0);
        ListNode cursor = root;
        int carry = 0;
        while(l1 != null || l2 != null || carry != 0) {
            int l1Val = l1 != null ? l1.val : 0;
            int l2Val = l2 != null ? l2.val : 0;
            int sumVal = l1Val + l2Val + carry;
            carry = sumVal / 10;
            
            ListNode sumNode = new ListNode(sumVal % 10);
            cursor.next = sumNode;
            cursor = sumNode;
            
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        
        return root.next;
    }
}

3. 无重复字符的最长子串（滑动窗口解法）

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

示例 1:

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

示例 2:

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

示例 3:

1
2
3
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

1
2
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

滑动窗口解法：

滑动窗口想象起来很简单，难的是实现过程，，滑动窗口需要搞清楚，什么时候滑动，从哪里滑动，滑动到哪里。我们用set集合来维护这样一个滑动窗口

  • 什么时候滑动，添加过程如果set集合有了该元素，就要开始滑动。
  • 从哪里滑动，就要知道set的开始位置，滑动就意味着set左边移除相应的元素
  • 滑动到哪里，左边每次滑动一位，右指针继续判断是否能继续向后滑动。

每次触发滑动，就可以根据左右指针来计算区间，注意左右指针此时代表的意义。左指针下表代表着左边第一个不重复的元素，但是特别注意，走完这次循环，left ++ ，就变成了左边第二个元素了，所以，remove的时候记得需要减回来。右指针代表着右边出现重复元素的第一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int strLengs = 0 ,left = 0,right = 0;
        //左指针指向窗口开始位置，但是left++后变成第二位置，所以移除时-1
        for( ; left < s.length() ; left++){
            if(left > 0){
                set.remove(s.charAt(left-1));
            }
            //注意移除掉窗口第一个元素后，此时left由之前表示第二位置变成左边界
            //右指针一直向后走，直到碰到重复元素
            for(; right < s.length() ; right++){
                if( set.contains(s.charAt(right)) )break;
                else set.add(s.charAt(right));
            }
            //记录下最大值，右指针是右窗口边界+1，左指针是窗口左边界
            strLengs = Math.max(strLengs,right-left);
        }
        return strLengs;
    }
}

4. 寻找两个正序数组的中位数（二分解法）

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

1
2
3
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

1
2
3
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

1
2
3
4
5
6
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

二分解法：

可以类比一个数组的二分，对于两个数组，我们同样用一条分割线去划分他，只需要满足红线左边元素数值<=红线右边所有元素数值。

由于两个数组都是有序的，一个数组内，分割线左边元素小于右边元素，不同数组之间，应该保证交叉小于等于关系成立。

image-20220725101137875

只要不满足交叉等于或小于，就要调整分割线位置

并且，对于，对于数组不等的情况，比如下边这个。因为根据两个数组长度我们可以确定中位数前边的个数，所以，我们只需要确定最短的分界线，直接拿总数一般减去较短数组的个数，能够防止越界。

试想一下，较长的数组在上边，我们确定他一半的位置，比较第二个数组的时候，可能会直接越界。

image-20220725101237808 
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
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length ){
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int m = nums1.length;
        int n = nums2.length;
        int total = (m + n + 1)/2;

        int left = 0,right = m;
        // 在 nums1 的区间 [0, leftLength] 里查找恰当的分割线，
        // 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]
        while(left < right){
            // i代表着在一个数组中左边的元素的个数
            // j就是第二个元素中左边的元素的个数
            int i = left + (right - left + 1)/2;
            int j = total - i;
            if(nums1[i - 1] > nums2[j]){
                right = i - 1;
            }else{
                left = i;
            }
        }
        
        int i = left;
        int j = total - i;
        //查找左边元素的最大值，右边元素的最小值，然后我们用最大值和最小值来找中位数。
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i-1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j-1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

        if((m + n)%2 == 1){
            return Math.max(nums1LeftMax,nums2LeftMax);
        }else{
            return  (double)(  (Math.max(nums1LeftMax,nums2LeftMax) + Math.min(nums1RightMin,nums2RightMin))  )/2 ;
        }
    }
}

5. 最长回文子串（动态规划）

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

提示：

1
2
1 <= s.length <= 1000
s 仅由数字和英文字母组成

看完题目，感觉和第三题 3. 无重复字符的最长子串 很类似，感觉是滑动窗口，但完全不一样。第三题要求的字串不重复，而回文子串是 自串像镜子一样对称

动态规划解法：

老样子，动态规划五部曲

  1. 确定dp数组（dp table）以及下标的含义

    这里我们dp定义为从字符串的起始位置i到结束位置j，包括边界，dp[i][j]的意思就是从字符串的起始位置i到结束位置j，是否是回文字符串。

  2. 确定递推公式

    所以我们可以得知 dp[i][j]是由dp[i+1][j-1]这个子串加上 s[i] == s[j] or i - j >3 这个条件推导出来的，其中， i - j >3 这个条件是如何的来的呢，这个是由于当 s[i] == s[j] ，此时，如果这个字串的长度为2 或者 3， 那么一定是 aa 或者 aba 这种形式，即不用再判断了。

    此外，这三个条件的顺序也有要求，比如，要先判断 s[i] == s[j] 然后再判断 i - j > 3 最后是，dp[i][j] =dp[i+1][j-1] ,并且，刚好防止数组溢出

  3. dp数组如何初始化

    我们可以确定，对角线元素均为true，实际上，我们可以不初始化这个元素，因为事实我们并没用到对角线元素

  4. 确定遍历顺序

    dp的便利顺序最难确定, 如何遍历。这里其实并不难，我们可以想一下，dp是由谁得来的， dp[i+1][j-1]，也就是说从表的左下得到的，其实可以画一下表，就明白他的遍历顺序了，需要一列一列的填充。

  5. 举例推导dp数组

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
class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if(len < 2)return s;

        boolean[][] dp = new boolean[len][len];

        for(int i = 0 ; i < len ; i++){
            dp[i][i] = true;
        }

        int begin = 0;
        int maxLen = 1;

        for(int j = 1 ; j < len ; j++){
            for(int i = 0 ; i < j ; i++){
                if(s.charAt(i) != s.charAt(j)){
                    dp[i][j] = false;
                }else{
                    if(j - i < 3){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }

                if(dp[i][j] == true && j - i + 1 > maxLen){
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }
}

方法二：中心扩展算法

我们仔细观察一下方法一中的状态转移方程：

可以发现，所有的状态在转移的时候的可能性都是唯一的。也就是说，我们可以从每一种边界情况开始「扩展」，也可以得出所有的状态对应的答案。

也就是说，从[i][i]往外扩展，比如是aba型的，就从[i][i]往外扩展 ，如果是aa型的，就从[i][i+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
class Solution {
    public String longestPalindrome(String s) {
        int strLen = s.length();
        if(strLen < 2)return s;

        int start = 0;
        int end = 0;

        for(int i = 0 ; i < strLen ; i++){
            int len1 = expanAroundCenter(s , i , i );
            int len2 = expanAroundCenter(s , i , i+1 );
            int len = Math.max(len1 , len2);
            if(len > end - start){
                //当为偶数个时，肯定是由len2的来的，所以，i一定是小的哪一个，计算起始长度时候，是i-长度的一半，要减去1.
                //当为奇数个，肯定是len1得来的，所以，i起始为 i-len/2，应为是奇数，向下取整，所以也可以先减一再除以2.
                //或者这样想，奇数个时，aba中心点是b，长度是3，b前后各有除去b /2个， abba型，第一个b是中心点，长度4，所以前边有（len-1）/2，后边有len/2个元素
                start = i - (len-1)/2;
                end = i + len/2;
            }
        }
        return s.substring(start,end + 1);
    }
    public int expanAroundCenter(String s , int left , int right){
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        //这里减一因为跳出循环的时候，left-- 成了-1,right++到了边界，所以计算个数多一个
        return right - left - 1;
    }
}

**方法三：马拉车算法 Manacher **

这个方法很简单，就是再中心扩展的基础上。 首先我们定义臂长f[i] 分别为每个下标的臂长。

  • 假如有 a b a c a b a ，假如有 以j 为对称中心， j的臂长是4 ， 所以 假如 i 到了倒数第二位b的位置，那一定有关于c的对称点 2* j - i ，f[2* j - i ]知道了，就不用从头算b的了，可以从前边拿去结果。但是，如果定义的 j 和 rMax（j的最大臂长位置），f[2* j - i ] 大于最大臂长了，我们无法确定这个对称中心外边的，所以要取两个最小值。

  • 然后就可以更新rMax 和新的j

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
class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        StringBuffer buffer = new StringBuffer("!#");
        for(int i = 0 ; i < len ; i++){
            buffer.append(s.charAt(i));
            buffer.append("#");
        }
        len = buffer.length();
        buffer.append("$");
        
        int[] f = new int[len];
        int iMax = 0 , rMax = 0 , start = 0 , end = 0;

        for(int i = 1 ; i < len ; i++){
            f[i] = i < rMax ? Math.min(rMax - i + 1, f[2 * iMax - i]) : 1;
            while(buffer.charAt(i + f[i]) == buffer.charAt(i - f[i]))f[i]++;
            if(i + f[i] - 1 > rMax){
                iMax = i;
                rMax = i + f[i] - 1;
            }
            if(2 * f[i] - 1 > end - start){
                start = i - f[i] + 1;
                end = i + f[i];
            }
        }

        StringBuffer res = new StringBuffer();
        for(int i = start ; i < end ; i++){
            if(buffer.charAt(i) !='#')res.append(buffer.charAt(i));
        }
        return res.toString();
    }
}

10. 正则表达式匹配（动态规划）

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

1
2
3
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

1
2
3
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

提示：

1
2
3
4
5
1 <= s.length <= 20
1 <= p.length <= 30
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

动态规划解法：

这个题比较难，关键在于动态规划的递推转换。

我们用 f[i][j]表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配。在进行状态转移时，我们考虑 p 的第 j 个字符的匹配情况：

如果 p 的第 j个字符是一个小写字母，那么我们必须在 s 中匹配一个相同的小写字母，即

image-20220725150214841

如果 p的第 j个字符是 *，那么就表示我们可以对 p 的第 j-1 个字符匹配任意自然数次。在匹配 0 次的情况下，我们有

image-20220725150257196

也就是我们「浪费」了一个字符 + 星号的组合，没有匹配任何 s 中的字符。

在匹配 1,2,3,⋯ 次的情况下，类似地我们有

image-20220725150326368

如果我们通过这种方法进行转移，那么我们就需要枚举这个组合到底匹配了 s 中的几个字符，会增导致时间复杂度增加，并且代码编写起来十分麻烦。我们不妨换个角度考虑这个问题：字母 + 星号的组合在匹配的过程中，本质上只会有两种情况：

  • 匹配 s 末尾的一个字符，将该字符扔掉，而该组合还可以继续进行匹配；

  • 不匹配字符，将该组合扔掉，不再进行匹配。

如果按照这个角度进行思考，我们可以写出很精巧的状态转移方程：

image-20220725150426447

这回到了动态规划五部曲：

确定了dp含义和推导顺序，接下来就是如何初始化，如何遍历。

方便起见，我们从1开始，所以字符串前边加入空格。

遍历顺序，从前往后，层层遍历，

初始化，f[0][0] = true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        s = " " + s;
        p = " " + p;
        boolean[][] f = new boolean[m+1][n+1];
        f[0][0] = true;
        for(int i = 0 ; i <= m ; i++){
            for(int j = 1 ; j <= n ; j++){
                if( j < n && p.charAt(j + 1) == '*')continue;
                if( p.charAt(j) != '*'){
                    f[i][j] = i > 0 && f[i-1][j-1] && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
                }else{
                    f[i][j] = (j > 1 && f[i][j-2]) || (i > 0 && f[i-1][j] && (p.charAt(j - 1) == s.charAt(i) || p.charAt(j - 1) == '.')); 
                }
            }
        }
        return f[m][n];
    }
}

11. 盛最多水的容器（双指针）

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

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

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

说明：你不能倾斜容器。

示例 1：

1658737424314

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

示例 2：

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

提示：

1
2
3
n == height.length
2 <= n <= 105
0 <= height[i] <= 104

双指针解法：

这个比较简单，要知道能盛水的最大值，一定是宽度越大越好，我们固定好最大的高，往中间逐渐寻找，并比较面积最大值。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxArea(int[] height) {
        int maxValue = 0;
        int left = 0,right = height.length - 1;
        while(left < right){
            maxValue = Math.max(maxValue,Math.min(height[left],height[right])*(right-left) );
            int useless = height[left] > height[right] ? right-- : left++;
        }
        return maxValue;
    }
}

15. 三数之和（排序+双指针）

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

1
2
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

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

示例 3：

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

提示：

1
2
0 <= nums.length <= 3000
-105 <= nums[i] <= 105

排序+双指针解法：

首先，我们查找三个数相加，要想优化算法，我们就要从找的过程下手，如过知道顺序，我们只需要根据两边数字，找一个合适的数字就可以。

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> list = new ArrayList<>();
        for(int i = 0 ; i < n ; i++){
            if(i > 0 && nums[i] == nums[i-1])continue;
            int l = i + 1 ,r = n - 1;
            int target = - nums[i];
            while(l < r){
                if(nums[l] + nums[r] == target){
                    List<Integer> temp = new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(nums[l]);
                    temp.add(nums[r]);
                    list.add(temp);
                    while( l < r && nums[l] == nums[l+1])l++;
                    while( l < r && nums[r] == nums[r-1])r--;
                    l++;r--;
                }else{
                    //这里想一下为什么r--不是l++，想一下含义就知道了
                    if(nums[l] + nums[r] > target)r--;
                    if(nums[l] + nums[r] < target)l++;
                }
            }
        }
        return list;
    }
}

17. 电话号码的字母组合（DFS）

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

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

img

示例 1：

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

示例 2：

1
2
输入：digits = ""
输出：[]

示例 3：

1
2
输入：digits = "2"
输出：["a","b","c"]

提示：

1
2
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

DFS解法：

可以直接DFS算法

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
class Solution {
    public List<String> letterCombinations(String digits) {

        HashMap<Character,String> numMap = new HashMap<>();
        numMap.put('2',"abc");
        numMap.put('3',"def");
        numMap.put('4',"ghi");
        numMap.put('5',"jkl");
        numMap.put('6',"mno");
        numMap.put('7',"pqrs");
        numMap.put('8',"tuv");
        numMap.put('9',"wxyz");
        
        List<String> res = new ArrayList<>();
        int index = 0;
        StringBuffer buffer = new StringBuffer();

        if(digits.length() == 0)return res;
        dfs(res, numMap, digits, index,buffer);
        return res;
    }
    public void dfs(List<String> res , HashMap<Character,String> numMap , String digits, int index , StringBuffer buffer){
        if(index == digits.length()){
            res.add(buffer.toString());
        }else{
            String s = numMap.get(digits.charAt(index));
            for(int i = 0 ; i < s.length() ; i++){
                buffer.append(s.charAt(i));
                dfs(res,numMap,digits,index+1,buffer);
                buffer.deleteCharAt(index);
            }
        }
    }
}

19. 删除链表的倒数第 N 个结点(双指针)

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

img

示例 1：

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

示例 2：

1
2
输入：head = [1], n = 1
输出：[]

示例 3：

1
2
输入：head = [1,2], n = 1
输出：[1]

提示：

1
2
3
4
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

双指针解法：

这个比较优，通过两个指针，然后让前后两个指针相差n，等到后指针到达末尾，前指针就是需要删除的元素。

其他解法比如遍历一次找到长度，然后删除，利用辅助栈等等。

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
/**
 * 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 res = new ListNode (0,head);
        ListNode first = head ;
        ListNode second = res;

        for(int i = 0 ; i < n ; i++){
            first = first.next;
        }

        while(first != null){
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return res.next;
    }
}

20. 有效的括号（辅助栈）

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：s = "(]"
输出：false

示例 4：

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

示例 5：

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

提示：

1
2
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

辅助栈解法：

这个要特别注意条件，比如只有一个】怎么办，取巧用了一个map，直接看包不包含键】，也就是【，有往栈中添加，没有就可以判断（判断栈为空，map不符合，直接返回false）。 最后，一定要看栈空了，才可以返回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
class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> map = new HashMap<>();
            map.put(')', '(');
            map.put(']', '[');
            map.put('}', '{');

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (map.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != map.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

21. 合并两个有序链表（顺序合并）

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

img

1
2
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

1
2
输入：l1 = [], l2 = []
输出：[]

示例 3：

1
2
输入：l1 = [], l2 = [0]
输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

迭代解法

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode node = new ListNode(0);
        ListNode res = node;
        while(list1!=null && list2 != null){
            if(list1.val > list2.val){
                node.next = list2;
                node = node.next;
                list2 = list2.next;
            }else{
                node.next = list1;
                node = node.next;
                list1 = list1.next;
            }
        }
        if(list1 != null)node.next = list1;
        if(list2 != null)node.next = list2;

        return res.next;
    }
}

22. 括号生成（回溯）

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= n <= 8

回溯解法

这个比较简单，还是老样子，统计左括号和右括号个数就行了，符合规则的肯定是左括号等于右括号等于N, 我们深度优先搜索一下，然后再回溯过来，去尝试增加右括号。最终层层回溯返回

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
class Solution {
    // Leetcode 22. Generate Parentheses
    // Backtracking
    // Time Complexity: Hard To Say
    // Space Complexity: Hard To Say
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtracking(n, result, 0, 0, "");
        return result;
    }

    private void backtracking(int n, List<String> result, int left, int right, String str) {
        if (right > left) {
            return;
        }
        if (left == n && right == n) {
            result.add(str);
            return;
        }

        if (left < n) {
            backtracking(n, result, left+1, right, str+"(");
        }

        if (right < left) {
            backtracking(n, result, left, right+1, str+")");
        }
    }
}

23. 合并K个升序链表（大顶堆）

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

1
2
输入：lists = []
输出：[]

示例 3：

1
2
输入：lists = [[]]
输出：[]

提示：

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4

优先级队列

可以利用大顶堆来做，合并N个链表，我们只管从大顶堆里拿最小节点就行

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
/**
 * 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) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>( (o1, o2) ->  o1.val - o2.val);
        ListNode res = new ListNode(0);
        ListNode cur = res;
        for(ListNode node : lists){
            if(node!=null)queue.add(node);
        }
        while (!queue.isEmpty()){
            cur.next = queue.poll();
            cur = cur.next;
            if(cur.next!=null)queue.add(cur.next);
        }
        return res.next;
    }
}

31. 下一个排列（两次遍历）

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

  • 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

  • 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
  • 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须** 原地 **修改，只允许使用额外常数空间。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

解题思路：

只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如 123456，将 5 和 6 交换就能得到一个更大的数 123465。

在尽可能靠右的低位进行交换，需要从后向前查找
将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换

将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列。

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
class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while(i >= 0 && nums[i] >= nums[i+1]){
            i--;
        }
        if(i >= 0){
            int j = nums.length - 1;
            while( j >= 0 && nums[i] >= nums[j]){
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

1
2
3
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

1
2
3
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

1
2
输入：s = ""
输出：0

提示：

  • 0 <= s.length <= 3 * 104
  • s[i] 为 '(' 或 ')'

动态规划

这个解法是比较不容易想出来的，

我们定义dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。我们将 dp 数组全部初始化为 0。因此我们可以知道以 ‘(’ 结尾的子串对应的 dp 值必定为 0 ，我们只需要求解 dp 数组中对应位置的值。

我们从前往后遍历字符串求解 dp 值，我们每两个字符检查一次：

  1. s[i]=‘)’ 且 s[i−1]=‘(’，也就是字符串形如 “……()”，我们可以推出：dp[i]=dp[i−2]+2

  2. s[i]=‘)’ 且 s[i−1]=‘)’，也就是字符串形如 “……))”，我们可以推出：
    如果 s[i−dp[i−1]−1]=‘(’，那么 dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int longestValidParentheses(String s) {
        int maxLength = 0;
        int[] dp = new int[s.length()];

        for(int i = 1 ; i < s.length() ; i++){
            if(s.charAt(i) == ')'){
                if(s.charAt(i-1) == '('){
                    dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
                }else if(i - dp[i-1] > 0 && s.charAt(i - dp[i-1] - 1) == '('){
                    dp[i] = dp[i-1] + ((i-dp[i-1]) >=2 ? dp[i-dp[i-1]-2] : 0)  +2;
                }
                maxLength = Math.max(maxLength, dp[i]);
            }
        }
        return maxLength;
    }
}

利用辅助栈解法：

方法二：栈
思路和算法

具体做法是我们始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：

对于遇到的每个 ( ，我们将它的下标放入栈中
对于遇到的每个 ) ，我们先弹出栈顶元素表示匹配了当前右括号：
如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
我们从前往后遍历字符串并更新答案即可。

需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，我们在一开始的时候往栈中放入一个值为 −1 的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int longestValidParentheses(String s) {
        int maxLength = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for(int i = 0 ; i < s.length() ; i++){
            if(s.charAt(i) == '('){
                stack.push(i);
            }else{
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }else{
                    maxLength = Math.max(maxLength, i - stack.peek() );
                }
            }
        }
        return maxLength;
    }
}

优化算法：

其实，我们不需要栈，从左到右只要 l < r ，就重新分段计数， l == r 就记录长度， 但是这样比如（（（），其实一直满足l > r ，这就需要从右边也走一次。

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
class Solution {
    public int longestValidParentheses(String s) {
        int l = 0 , r = 0;
        int maxLength = 0;
        for(int i = 0 ; i < s.length() ; i++){
            if(s.charAt(i) == '(')l++;
            if(s.charAt(i) == ')')r++;
            if(l < r){
                l = 0;
                r = 0;
            }
            if(l == r){
                maxLength = Math.max(maxLength,2*r);
            }
        }

        l = 0;
        r = 0;
        for(int i = s.length() - 1 ; i >= 0 ; i--){
            if(s.charAt(i) == '(')l++;
            if(s.charAt(i) == ')')r++;
            if(l > r){
                l = 0;
                r = 0;
            }
            if(l == r){
                maxLength = Math.max(maxLength,2*l);
            }
        }
        return maxLength;

    }
}

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

1
2
输入：nums = [1], target = 0
输出：-1

提示：

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -104 <= target <= 104

二分查找

将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.

4 5 6 7 8 9 1 2 3 ，一分为2 ，一半有序，

直接看中值和开头比较：

  • 中值大，则左边一定有序，在有序数组查找，看有序边界是否能涵盖target。涵盖就缩小右边界，不含直接出去，左边界
  • 中值小，则右边一定有序，同样查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int search(int[] nums, int target) {
        int l = 0 , r = nums.length - 1;
        while(l <= r){
            int mid = (l + r)/2;
            if(target == nums[mid])return mid;
            //这里特别注意这个等号，很细节，这是 因为mid向下取整，就有可能取到0。因为一定是旋转过的，左边的数大，如果放给下边判断，会找不到限制被放到左边数组，所以，要在上边把他往右去移动。
            if(nums[0] <= nums[mid]){ 
                if(target < nums[mid] && target >= nums[0]){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
            }else{
                if(target > nums[mid] && target <= nums[nums.length - 1]){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

1
2
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

1
2
输入：nums = [], target = 0
输出：[-1,-1]

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109

方法一：二分查找

分别二分查找左边界和右边界

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0 , right = nums.length - 1;
        int l = 0 ; int r = 0;
        while(left <= right){
            int mid = (left + right)/2;
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] >= target){
                right = mid - 1;
            }
        }
        l = right+1;
        left = 0;
        right = nums.length - 1;
        while(left <= right){
            int mid = (left + right)/2;
            if(nums[mid] <= target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }
        }
        r = left-1;
        if(r >= l && r < nums.length && nums[l] == target && nums[r] == target){
            return new int[]{l,r};
        }
        return new int[]{-1,-1};
    }
}

39. 组合总和（dfs）

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

1
2
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

1
2
输入: candidates = [2], target = 1
输出: []

提示：

  • 1 <= candidates.length <= 30
  • 1 <= candidates[i] <= 200
  • candidate 中的每个元素都 互不相同
  • 1 <= target <= 500
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        dfs(res,candidates,0,target,cur);
        return res;
    }

    public void dfs(List<List<Integer>> res , int[] candidates , int index , int target, List<Integer> cur){
        if(index == candidates.length )return;
        if(target == 0){
            res.add(new ArrayList<Integer>(cur));
            return;
        }
        dfs(res,candidates,index + 1,target,cur);
        if(target - candidates[index] >=0 ){
            cur.add(candidates[index]);
            dfs(res,candidates,index,target - candidates[index],cur);
            cur.remove(cur.size() - 1);
        }
    }
}

42. 接雨水（双指针）

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

示例 1：

img

1
2
3
输入：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 个单位的雨水（蓝色部分表示雨水）。

示例 2：

1
2
输入：height = [4,2,0,3,2,5]
输出：9

提示：

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

双指针解法：

思想上比较简单，我们先确定木桶装水的短板，左右指针同时寻找，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int trap(int[] height) {
        int left = 0 , right = height.length - 1;
        int lmax = 0 , rmax = 0;
        int ans = 0;
        while(left < right){
            lmax = Math.max( height[left] , lmax );
            rmax = Math.max( height[right] , rmax );
            if(lmax < rmax){
                ans += lmax - height[left];
                left++;
            }else{
                ans += rmax - height[right];
                right--;
            }
        }
        return ans;
    }
}

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同
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
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        dfs(res,cur,used,0,nums);
        return res;
    }

    public void dfs(List<List<Integer>> res , List<Integer> cur, boolean[] used, int index , int[] nums){
        if(index == nums.length){
            res.add(new ArrayList<Integer>(cur));
            return;
        }
        for(int i = 0 ; i <nums.length ; i++){
            if(!used[i]){
                cur.add(nums[i]);
                used[i] = true;
                dfs(res,cur,used,index+1,nums);
                used[i] = false;
                cur.remove(cur.size()-1);
            }
        }
    }
}

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

img

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

示例 2：

img

1
2
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

旋转法解题思路：

这个题有很多解题思路，一种是直接找到他的规律，他每个元素变换后的位置，直接交换，另外就是根据旋转法来做，直接顺时针旋转90°，就相当于水平翻转+主对角线反转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for(int i = 0 ; i < n/2 ; i++){
            for(int j = 0 ; j < n ; j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-i-1][j];
                matrix[n-i-1][j] = temp;
            }
        }
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < i ; j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

1
2
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

1
2
输入: strs = [""]
输出: [[""]]

示例 3:

1
2
输入: strs = ["a"]
输出: [["a"]]

提示：

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for(String str : strs){
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            //转换成String
            String key = new String(arr);
            //有key返回，没有的话返回默认
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        //map的所有value，直接转换成list
        return new ArrayList<List<String>>(map.values());
    }
}

53. 最大子数组和

给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。

示例 1：

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

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

示例 3：

1
2
输入：nums = [5,4,-1,7,8]
输出：23

提示：

1
2
3
1 <= nums.length <= 105
-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

动态规划算法：

其实有点贪心的思想，想办法要最大值，遇到小了直接抛弃

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0], pre = 0;
        for(int x : nums){
            pre = Math.max(x , pre + x);
            max = Math.max(max , pre);
        }
        return max;
    }
}

55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

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

示例 2：

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

提示：

1
2
1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105

56. 合并区间

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

示例 1：

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

示例 2：

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

提示：

1
2
3
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

代码

排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(o1,o2) -> o1[0] - o2[0]);
        List<int[]> list = new ArrayList<>();
        for(int i = 0 ; i < intervals.length ; i++){
            int left = intervals[i][0], right = intervals[i][1];
            if(list.size() == 0 || left > list.get(list.size()-1)[1]){
                list.add(new int[]{left,right});
            }else{
                list.get(list.size()-1)[1] = Math.max(list.get(list.size()-1)[1],right);
            }
        }
        return list.toArray(new int[list.size()][]);

    }
}

62. 不同路径（动态规划）

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

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

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

示例 1：

img

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

示例 2：

1
2
3
4
5
6
7
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
    1. 向右 -> 向下 -> 向下
    2. 向下 -> 向下 -> 向右
    3. 向下 -> 向右 -> 向下

示例 3：

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

示例 4：

1
2
输入：m = 3, n = 3
输出：6

提示：

1
2
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

动态规划五部曲：

  1. 确定dp数组和含义： dp[i][j]表示到坐标(i,j)位置的方法数
  2. 确定递推公式： 每次只能向下或者向右移动一步。也就是说，dp[i][j]等于dp[i-1][j]和dp[i][j-1]的和。
  3. 确定初始值：应为第一行和第一列只能是前边一个走过来，所以可以初始化dp[0][j]``dp[i][0] 均为 1
  4. 遍历顺序： 逐行遍历
  5. 返回值：要求计算右下角，dp[i][j]

代码

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

         for(int rows = 1 ; rows < m ; rows++){
             for(int columns = 1 ; columns < n ; columns++){
                dp[rows][columns] = dp[rows-1][columns] + dp[rows][columns-1];
             }
         }
         return dp[m-1][n-1];
    }
}

64. 最小路径和（动态规划）

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

img

示例 1：

1
2
3
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

1
2
输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

1
2
3
4
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

动态规划五部曲：

  1. 确定dp数组和含义： dp[i][j]表示到坐标(i,j)的最小和
  2. 确定递推公式： 每次只能向下或者向右移动一步。也就是说，dp[i][j]可由dp[i-1][j]和dp[i][j-1]最小值加上dp[i][j]。
  3. 确定初始值：题目给了m*n的矩阵，可以初始化dp[0][j]``dp[i][0]
  4. 遍历顺序： 逐行遍历
  5. 返回值：要求计算右下角，dp[i][j]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minPathSum(int[][] grid) {
        int rows = grid.length;
        int columns = grid[0].length;
        for(int i = 1 ; i < rows ; i++){
            grid[i][0] = grid[i-1][0] + grid[i][0];
        }      
        for(int i = 1 ; i < columns ; i++){
            grid[0][i] = grid[0][i-1] + grid[0][i];
        }
        for(int i = 1 ; i < rows ; i++){
            for(int j = 1 ; j < columns ; j++){
                grid[i][j] = Math.min(grid[i][j-1] , grid[i-1][j]) + grid[i][j];
            }
        }
        return grid[rows-1][columns-1];
    }
}

70. 爬楼梯（动态规划）

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

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

示例 1：

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

示例 2：

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

提示：

1
1 <= n <= 45

动态规划五部曲：

  1. 确定dp数组和含义： dp[i]表示在上第i台阶有多少种方法
  2. 确定递推公式： 每次一个台阶或者两个台阶，也就是说，dp[i]可由dp[i-1]和dp[i-2]相加得来。
  3. 确定初始值：题目既然给了n大于等于1，就无所谓dp[0]是1还是0了。只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。
  4. 遍历顺序： 从前往后
  5. 返回值：要求计算爬第n次多少方法，所以反回dp[n]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//优化版本，因为只关心最终结果，不关心中间台阶的方法数，直接维护前后两个数就行
class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[2];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n ; i++){
            int temp = dp[1];
            dp[1] = dp[0] + dp[1];
            dp[0] = temp;
        }
        return dp[1];
    }
}

72. 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例 1：

1
2
3
4
5
6
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

1
2
3
4
5
6
7
8
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成

方法一：动态规划

我们可以对任意一个单词进行三种操作：

  • 插入一个字符；
  • 删除一个字符；
  • 替换一个字符。

比如s1 和 s2，分为s[i] == s[j] 和不等的情况，等于直接往前找，不等就分三种情况，一种是在s2插入一个字符，一种是在s1删除一个字符，一种是s1,s2修改一个字符。

image-20220729115120665

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
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length() , n = word2.length();
        int[][] dp = new int[m+1][n+1];
        // 有一个字符串为空串
        if (n * m == 0) {
            return n + m;
        }
        for(int i = 0 ; i <= m ; i++){
            dp[i][0] = i;
        }
        for(int j = 0 ; j <= n ; j++){
            dp[0][j] = j;
        }

        for(int i = 1 ; i <= m ; i++){
            for(int j = 1 ; j <= n ; j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j-1] + 1 , Math.min(dp[i-1][j],dp[i][j-1]) + 1 );
                }
                
            }
        }
        return dp[m][n];
    }
}

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，**原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例 1：

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

示例 2：

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

提示：

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

进阶：

  • 你可以不使用代码库中的排序函数来解决这道题吗？
  • 你能想出一个仅使用常数空间的一趟扫描算法吗？

本题是经典的「荷兰国旗问题」

思路与算法

三指针法，【0, i-1】属于0 ， 【i,j-1】属于1 ， 【k+1，n-1】属于2；

image-20220729144526689 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void sortColors(int[] nums) {
        int i = 0 , j = 0 , k = nums.length - 1;
        //注意这个等于，有可能j++，而前边那个是1，后边是0，j++刚好碰到k--过，会直接出去
        while(j <= k){
            if(nums[j] == 0){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
                j++;
            }else if(nums[j] == 2){
                int temp = nums[k];
                nums[k] = nums[j];
                nums[j] = temp;
                k--;
            }else{
                j++;
            }
        }
    }
}

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

1
2
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例 2：

1
2
输入：s = "a", t = "a"
输出："a"

示例 3:

1
2
3
4
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

  • 1 <= s.length, t.length <= 105
  • s 和 t 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

解题思路

对于这道题，他的要求是t字符串中的字符要被S中包含，顺序并不要求，所以t字符串的总个数够了就行，就需要记录一下t每个字符的个数，即TMap。

另外就是对于S，要想找到最少的对应字符串区间，就需要动用两个指针来查找，为甚么这么说呢，因为要找最小区间，就要记录匹配的字符个数，开始的位置，当前位置。

比如 A B A A C B ， 记录开始指针j， 当前指针i ， 比如在i++的时候，我们把每个元素都加入sMap中去，然后去看对应的元素是否够t[i]，没有的元素肯定小于，有的元素有可能不够，所以cnt++,

然后遇到重复多余的，就需要排掉前边的那个字符，为什么不排掉一个呢，因为我们的sMap，记录了一大堆，要一直删除到比t(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
25
26
27
28
class Solution {
    public static String minWindow(String s, String t) {
        HashMap<Character,Integer> sm = new HashMap<>();
        HashMap<Character,Integer> tm = new HashMap<>();

        for(int i = 0 ; i < t.length() ; i++){
            char c = t.charAt(i);
            tm.put(c,tm.getOrDefault(c,0)+1);
        }
        int i = 0, j = 0, cnt= 0;
        String ans = new String();
        for(; i < s.length(); i++){
            sm.put(s.charAt(i),sm.getOrDefault(s.charAt(i),0)+1);
            if( sm.get(s.charAt(i)) <= tm.getOrDefault(s.charAt(i),0) ){
                cnt++;
            }
            while(j < s.length() && sm.getOrDefault(s.charAt(j),0) > tm.getOrDefault(s.charAt(j),0)){
                sm.put(s.charAt(j),sm.get(s.charAt(j))-1);
                j++;
            }
            if(cnt == t.length()){
                if( ans.length() == 0 || ans.length() > i - j + 1)
                    ans = s.substring(j,i+1);
            }
        }
        return ans;
    }
}

78. 子集

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

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

方法一：dfs解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();;
        dfs(res,nums,list,0);
        return res;
    }

    public void dfs(List<List<Integer>> res, int[] nums, List<Integer> list, int k){
        if(k == nums.length){
            res.add(new ArrayList<>(list));
            return;
        }
        list.add(nums[k]);
        dfs(res,nums,list,k+1);
        list.remove(list.size()-1);
        dfs(res,nums,list,k+1);
    }
}

方法二：

记原序列中元素的总数为 nn。原序列中的每个数字 a_ia
i

的状态可能有两种，即「在子集中」和「不在子集中」。我们用 11 表示「在子集中」，00 表示不在子集中，那么每一个子集可以对应一个长度为 nn 的 0/10/1 序列，第 ii 位表示 a_ia
i

是否在子集中。例如，n = 3n=3 ，a = { 5, 2, 9 }a={5,2,9} 时：

image-20220729205538068

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        int n = nums.length;

        for(int mask = 0 ; mask < (1<<n) ; mask++){
            list.clear();
            for(int i = 0 ; i < n ; i++){
                if( (mask & (1<<i)) != 0  ){
                    list.add(nums[i]);
                }
            }
            res.add(new ArrayList<Integer>(list));
        }
        return res;
    }
}

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

img

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

img

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

img

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

典型的DFS+剪枝

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
class Solution {
    public boolean exist(char[][] board, String word) {
        for(int i = 0 ; i < board.length ; i++){
            for(int j = 0 ; j < board[0].length ; j++){
                if(dfs(board,word,0,i,j))return true;
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word,int index, int x, int y){
        if(board[x][y] != word.charAt(index))return false;
        if(index == word.length() - 1)return true;
        
        char c = board[x][y];
        board[x][y] = '.';
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for(int i = 0 ; i < 4 ; i++){
            int nx = directions[i][0] + x;
            int ny = directions[i][1] + y;
            if(nx < 0 || nx >= board.length || ny < 0 || ny >= board[0].length || board[nx][ny] == '.')continue;
            if(dfs(board,word,index+1,nx,ny))return true;
        }
        board[x][y] = c;
        return false;
    }
}

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

img

1
2
3
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

img

1
2
输入： heights = [2,4]
输出： 4

提示：

  • 1 <= heights.length <=105
  • 0 <= heights[i] <= 104

方法一：暴力求解

会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int maxSize = 0;
        for(int i = 0 ; i < n ; i++){
            int h = heights[i];
            int left = i-1,right = i+1;
            for( ; left >= 0 ; left--){
                if(heights[left] < heights[i])break;
            }
            for(; right < heights.length ; right++){
                if(heights[right] < heights[i])break;
            }
            maxSize = Math.max(maxSize, (right - left - 1)*h );
        }
        return maxSize;

    }
}

方法二：利用单调栈+哨兵

该方法思路和一类似，只不过1不保存信息，二牺牲空间换时间。二的方式是，栈用来存储下标，每次遇到新元素小于以栈中顶部元素为下标的值，就说明，这个栈中的顶部这个元素，右边遇到瓶颈了，左边肯定没有瓶颈，所以计算最大面积，然后弹出元素，计算前边元素的最大面积，应为后边元素都是大于前边元素的，所以不用担心瓶颈问题。

特别注意，最后的时候，栈中还可能存在元素没有计算完，所以要加入一个一定最小的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] newHeights = new int[len+1];
        System.arraycopy(heights, 0, newHeights, 0, len);
        //加入哨兵
        newHeights[len] = -1;

        int maxSize = 0;
        Stack<Integer> stack = new Stack<>();
        for(int i = 0 ; i <= len ; i++){
            
            while(!stack.isEmpty() && newHeights[stack.peek()] > newHeights[i]){
                int index = stack.pop(); 
                int left = stack.isEmpty() ? -1 : stack.peek();
                maxSize = Math.max(maxSize , newHeights[index] * (i - left - 1) );
            }
            stack.push(i);
        }
        return maxSize;
    }
}

85. 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：

img

1
2
3
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：

1
2
输入：matrix = []
输出：0

示例 3：

1
2
输入：matrix = [["0"]]
输出：0

示例 4：

1
2
输入：matrix = [["1"]]
输出：1

示例 5：

1
2
输入：matrix = [["0","0"]]
输出：0

提示：

  • rows == matrix.length
  • cols == matrix[0].length
  • 1 <= row, cols <= 200
  • matrix[i][j] 为 '0' 或 '1'

算法思路

本质是暴力求解，先把每行连续1求一下最长width，然后从下往上，找一下对应上边所有的最大面积，注意要求一下最小的width，然后乘以高度，遍历全部。

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
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        if(m == 0)return 0;

        int[][] rowSum = new int[m][n];
    
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < n ; j++){
                if(matrix[i][j] == '1'){
                    rowSum[i][j] = (j == 0 ? 0 : rowSum[i][j-1] ) + 1;
                }
            }
        }


        int maxSize = 0;
        int minHigh = 0;
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < n ; j++){
                if(rowSum[i][j] == 0)continue;
                int width = rowSum[i][j];
                int area = width;
                for(int k = i - 1 ; k >=0 ; k-- ){
                    width = Math.min(width,rowSum[k][j]);
                    area = Math.max(area , width * (i - k + 1) );
                }
                maxSize = Math.max(maxSize,area);
            }
        }
        return maxSize;
    }
}

最佳解法：

如图， 我们算一下每一行中 ，列的最大和，这样对每一行求最大面积，每一行就类似84题，

image-20220730201034241 
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
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int maxSize = 0;

        if(m == 0)return 0;
        int[] height = new int[n+1];
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < n ; j++){
                if(matrix[i][j] == '1')height[j]++;
                else height[j] = 0;
            }
            height[n] = -1;
            maxSize = Math.max(maxArea(height),maxSize);
        }
        return maxSize;
    }

    public int maxArea(int[] height){
        int maxSize = 0;
        Stack<Integer> stack = new Stack<>();

        for(int i = 0 ; i < height.length ; i++){
            while(!stack.isEmpty() && height[stack.peek()] > height[i] ){
                int index = stack.pop();
                int left = stack.isEmpty() ? -1 : stack.peek();
                maxSize = Math.max(maxSize , (i - left - 1)*height[index]);
            }
            stack.push(i);
        }
        return maxSize;
    } 
}

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

img

示例 1：

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

示例 2：

1
2
输入：root = []
输出：[]

示例 3：

1
2
输入：root = [1]
输出：[1]

递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        inorder(root);
        return list;
    }
    public void inorder(TreeNode root){
        if(root == null)return;
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);
    }
}

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

img

1
2
输入：n = 3
输出：5

示例 2：

1
2
输入：n = 1
输出：1

提示：

  • 1 <= n <= 19

解析

用 f(i) 来表示从 1 到 i 这 i个节点构成的互不相同的二叉搜索树的数量，只要枚举 1到 i 这 i 个数作为根节点，把方案数累加就可以了。

假设当前选定的根节点是 j ，那么左子树的可能构造数就是 1 到 j - 1 这部分节点的构造方案数，也就是 f(j - 1)，右子树的话，是从 j + 1 到 i 这部分节点的构造方案数，因为构造数量只与节点数有关，所以右子树的方案数量就是 f(i - j) 。

这样状态转移方程就是image-20220730210254393

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;

        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= i; j++ ){
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }
}

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

img

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

示例 2：

img

1
2
3
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

  • 树中节点数目范围在[1, 104] 内
  • -231 <= Node.val <= 231 - 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
/**
 * 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 recur(root , Long.MIN_VALUE , Long.MAX_VALUE );
    }
    public boolean recur(TreeNode root , long min , long max){
        if(root == null)return true;
        if(root.val >= max || root.val <= min)return false;
        return recur(root.left,min,root.val) && recur(root.right,root.val,max);
    }
}

中序遍历法

同样也是广度优先搜索

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
/**
 * 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) {
        Stack<TreeNode> stack = new Stack<>();
        double lastVal = -Double.MAX_VALUE;
        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.val <= lastVal)return false;
            lastVal = root.val;
            root = root.right;      
        }
        return true;
    }
}

101. 对称二叉树

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

示例 1：

img

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

示例 2：

img

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

提示：

  • 树中节点数目在范围 [1, 1000] 内
  • -100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

递归法

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
/**
 * 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 isSymmetric(TreeNode root) {
        return recur(root.left , root.right);
    }
    public boolean recur(TreeNode left, TreeNode right){
        if(left == null && right==null)return true;
        if(left == null || right==null ||left.val != right.val)return false;

        return recur(left.left,right.right) && recur(left.right,right.left);
    }
}

迭代法：

迭代法也很简单，注意开始加入两次节点

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
/**
 * 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 isSymmetric(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode u = root , v = root;
        stack.push(u);
        stack.push(v);

        while(!stack.isEmpty()){
            u = stack.pop();
            v = stack.pop();

            if(u == null && v == null)continue;
            if(u == null || v == null || v.val != u.val)return false;
            
            stack.push(u.left);
            stack.push(v.right);

            stack.push(u.right);
            stack.push(v.left);
        }
        return true;
    }
}

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

img

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

示例 2：

1
2
输入：root = [1]
输出：[[1]]

示例 3：

1
2
输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

正常层序遍历

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
/**
 * 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) {
         Queue<TreeNode> queue = new LinkedList<TreeNode>();
         List<List<Integer>> res = new ArrayList<>();
         if(root==null)return res;
         queue.add(root);
         while(!queue.isEmpty()){
             int queueSize = queue.size();
             List<Integer> list = new ArrayList<>();
             for(int i = 0 ; i < queueSize ; i++){
                TreeNode node = queue.remove();
                if(node.left!=null)queue.add(node.left);
                if(node.right!=null)queue.add(node.right);
                list.add(node.val);
             }
             res.add(list);
         }
         return res;
    }
}

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

也是两种方法，一种是深度优先搜索，递归，一种是广度优先搜索。

深度优先搜索

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
/**
 * 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) {
        return dfs(root);
    }

    public int dfs(TreeNode root){
        if(root == null)return 0;
        return Math.max(dfs(root.left),dfs(root.right)) + 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
/**
 * 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) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null)return 0;
        queue.offer(root);
        int res = 0;
        while(!queue.isEmpty()){
            int len = queue.size();
            res++;
            while(len-- > 0){
                TreeNode node = queue.poll();
                if(node.left!=null)queue.offer(node.left);
                if(node.right!=null)queue.offer(node.right);
            }
        }
        return res;
    }
}

105. 从前序与中序遍历序列构造二叉树

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

示例 1:

img

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

示例 2:

1
2
输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

递归法

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

    public TreeNode recur(int[] preorder, int[] inorder , int pl , int pr , int il , int ir){
        if(pl > pr || il > ir)return null;
        int k = indexMap.get(preorder[pl]) - il;

        TreeNode root = new TreeNode(preorder[pl]);
        root.left = recur(preorder, inorder , pl + 1 , pl + k , il , il + k - 1);
        root.right = recur(preorder, inorder , pl + k + 1 , pr , il + k + 1 , ir);
        return root;
    }
}

迭代法

例子

我们以树

        3
       / \
      9  20
     /  /  \
    8  15   7
   / \
  5  10
 /
4

为例，它的前序遍历和中序遍历分别为

preorder = [3, 9, 8, 5, 4, 10, 20, 15, 7]
inorder = [4, 5, 8, 10, 9, 3, 15, 20, 7]

想一下，3是根节点，9是左节点，一直到4都是上个节点的左节点，因为前序是根左右，中序是左根右，去掉根，一直到和中序相同的都是左节点。同理，我们可以找到

1
2
3
4
5
6
7
8
9
        3
       / 
      9 
     /  
    8 
   / 
  5  
 /
4

然后遇到了10，我们维护一个栈，栈里都是没有右儿子的。然后从栈顶判断，挨个弹出inorder重复的元素，也就是我们现在左节点找完了，要找右节点。然后到了10，作为右节点。之后继续往外弹出9，然后拼接3的右边，还是同样的方式。

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
/**
 * 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 {
    private Map<Integer, Integer> indexMap;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]);
        int index = 0;
        stack.push(root);
        for(int i = 1 ; i < preorder.length ; i++){
            TreeNode node = stack.peek();
            if(node.val != inorder[index]){
                node.left = new TreeNode(preorder[i]);
                stack.push(node.left); 
            }else{
                while(!stack.isEmpty() && stack.peek().val == inorder[index]){
                    node = stack.pop();
                    index++;
                }
                node.right = new TreeNode(preorder[i]);
                stack.push(node.right);
            }
        }
        return root;
    }
}

114. 二叉树展开为链表

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

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

示例 1：

img

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

示例 2：

1
2
输入：root = []
输出：[]

示例 3：

1
2
输入：root = [0]
输出：[0]

提示：

  • 树中结点数在范围 [0, 2000] 内
  • -100 <= Node.val <= 100

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

这一题比较巧妙

比如

1
2
3
4
5
    1						
   / \
  2  5
 / \   \
3  4    6

要想遍历1便并且不占用空间，需要看看有没有左节点，右的话就遍历左节点的右节点，给他拼到右边树上

1
2
3
4
5
6
7
8
9
 1						
  \
   2 				
  / \
 3   4
      \
5
 \
  6
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
/**
 * 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) {
        TreeNode cur = root;
        while(cur != null){
            if(cur.left != null){
                TreeNode p = cur.left;
                while(p.right != null)p = p.right;
                p.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
}

121. 买卖股票的最佳时机

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

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

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

示例 1：

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

示例 2：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxProfit(int[] prices) {
        int minValue = Integer.MAX_VALUE;
        int max = 0;
        for(int i = 0 ; i < prices.length ; i++){
            minValue = Math.min(minValue, prices[i]);
            max = Math.max(max,prices[i] - minValue);
        }
        return max;

    }
}

124. 二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

img

1
2
3
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

img

1
2
3
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

  • 树中节点数目范围是 [1, 3 * 104]
  • -1000 <= Node.val <= 1000

最大路径是由什么构成， 根+左最大+右最大，找到这样一条路径就可以了。如何找，肯定是递归来找，找到左右两边的最大，这就是后序遍历了。

所以就可以设计后续遍历的算法

但是返回的时候，返回的是根节点的最大路径值，要算最大路径，就需要在递归中记录最大值，最大值也就是左+右+根。

递归反回 的是左、右的最大值

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
/**
 * 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 {
    int maxValue = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxValue;
    }

    public int dfs(TreeNode root){
        if(root == null)return 0;

        int left = Math.max(dfs(root.left) , 0);
        int right = Math.max(dfs(root.right) , 0);
        int value = root.val + left + right;
        maxValue = Math.max(maxValue , value);
        
        return root.val + Math.max(left,right);
    }
}

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

1
2
3
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

1
2
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

这道题看上去似乎就是暴力解法，但是要求能够O（n）,所以只能空间换时间，因此我们需要知道每个元素的前后是否有值，假设循环遍历，我们每次都找前边没有元素的，这样他肯定是开头的元素，然后找他后边有多少个顺序元素，统计最大值，所以我们只需要统计每个字符作为开头（也就是前边没有顺序元素）后边顺序元素的最大值就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0 ; i < nums.length ; i++){
            set.add(nums[i]);
        }

        int len = 0;
        for(int num : nums){
            if(!set.contains(num - 1)){
                int x = num + 1;
                while(set.contains(x))x++;
                len = Math.max(len, x - num);
            }
        }
        return len;
    }
}

136. 只出现一次的数字

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

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

1
2
输入: [2,2,1]
输出: 1

示例 2:

1
2
输入: [4,1,2,1,2]
输出: 4

直接异或

代码

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

139. 单词拆分

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

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

示例 1：

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

示例 2：

1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

1
2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅有小写英文字母组成
  • wordDict 中的所有字符串 互不相同

方法一：动态规划

比如leetcode这个字符，字典是leet和code

首先字典肯定哈希表，另外就是如何查找了，动态规划可以解

思路就是把 整个字符串分成三个部分， 0 j i ，然后0 - j 这部分是已知dp[i] ，并且判断后边的字符 i - j 这部分，如果在哈希表就说明dp[i]是true的；否则就是false；

这里要注意两地，边界条件，循环的边界 。 dp[0]肯定是true， 然后i 起始肯定是1，j的起始应该是0，应为比如leetcode，j要从0开始到i去截取字符，0和i-1都要取到，所以j从0开始。 i 可以等于边界，因为我们允许空字符串存在为true，后边相应延长，并且，这时的i-1代表数组的下标i， j的边界，小于i，并且不能等于，因为截取字符，i不包括，所以j不能等于i.

另外注意，这里找到就应该跳出，不是让全部遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<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()];
    }
}

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

img

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

img

1
2
3
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

img

1
2
3
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos 为 -1 或者链表中的一个 有效索引 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

哈希表法：

直接利用哈希表，存储每个元素，挨个判断是否出现过。

快慢指针

即兔子前边跑，每次2个，乌龟后边爬，每次一个，兔子速度始终比乌龟快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
/**
 * 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 , fast = head.next;

        while(slow != fast){
            if(fast == null || fast.next ==null)return false;
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }
}

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

img

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

img

1
2
3
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

img

1
2
3
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

还是快慢指针，不同的是，指针相遇的时候， a+n(b+c)=2(a+b) 所以就是， a = c+(n-1)(b+c) ,也就是说，从这一点开始，a+c=（n-1）(b+c)，正好让一个走起点，走a路程，一个继续走，走了c和n-1圈，又相遇在环的起点。

fig1 
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
/**
 * 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) {
        ListNode fast = head , slow = head;
        while( fast!= null && fast.next != null ){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                slow = head;
                while(fast != slow){
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

146. LRU 缓存

请你设计并实现一个满足 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) 的平均时间复杂度运行。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入
["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]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105 次 get 和 `put

这个解法需要继承LinkedHashMap ，不推荐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class LRUCache extends LinkedHashMap<Integer,Integer>{
    private int capacity;
    public LRUCache(int capacity) {
        super(capacity,0.75F,true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return super.getOrDefault(key,-1);
    }
    
    public void put(int key, int value) {
        super.put(key,value);
    }
    public boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest){
        return size() > capacity;
    }
}

哈希表 + 双向链表

这种需要我们自己构建链表，然后用Map,存储key和链表， 这样，插入的话，就是在Map，插入，并且构建链表头部，放在Map里。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class LRUCache {
    //创建双向链表类，这个类中要有key，value，因为我们淘汰过期值的时候是参照链表尾部淘汰，就要去对应的哈希表里删除，就要知道主键key
    class LinkNode{
        int key;
        int value;
        LinkNode pre;
        LinkNode next;
        LinkNode(){};
        LinkNode(int key,int value){this.key = key ; this.value = value;}
        LinkNode(int key,int value,LinkNode pre,LinkNode next){this.key = key; this.value = value; this.pre = pre; this.next = next;}
    }

    
    private int capacity;
    private int size;
    private LinkNode linkHead;
    private LinkNode linkend;
    private HashMap<Integer,LinkNode> map = new HashMap<>();

//定义两个头部尾部节点，方便查找
    public LRUCache(int capacity) {
        this.capacity = capacity;
        size = 0;
        linkHead = new LinkNode();
        linkend = new LinkNode();
        linkHead.next = linkend;
        linkend.pre = linkHead;
    }
    
    public int get(int key) {
        LinkNode node = map.get(key);
        if(node != null){
            moveToFirest(node);
            return node.value;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        LinkNode node = map.get(key);
        if(node != null){
            node.value = value;
            moveToFirest(node);
        }else{
            LinkNode newNode = new LinkNode(key,value);
            map.put(key,newNode);
            addFirest(newNode);
            size++;
            if(size > capacity){
                LinkNode tail = removeTail();
                map.remove(tail.key);
                size--;
            }
        }
    }
    
    public void removeNode(LinkNode node) {
        node.next.pre = node.pre;
        node.pre.next = node.next;
    }
    
    public void addFirest(LinkNode node) {
        node.pre = linkHead;
        node.next = linkHead.next;
        linkHead.next = node;
        node.next.pre = node;
    }

    public void moveToFirest(LinkNode node) {
        removeNode(node);
        addFirest(node);
    }
    public LinkNode removeTail() {
        LinkNode node = linkend.pre;
        removeNode(node);
        return node;
    }

}

/**
 * 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);
 */

148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

img

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

示例 2：

img

1
2
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

1
2
输入：head = []
输出：[]

提示：

  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -105 <= Node.val <= 105

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

第一种，利用大顶堆

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
/**
 * 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) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>( (o1 ,o2) -> o1.val - o2.val);
        ListNode node = head;
        while(node!=null){
            queue.add(node);
            node = node.next;
        }

        ListNode res = new ListNode(0);
        node = res;
        while(!queue.isEmpty()){
            node.next = queue.poll();
            node = node.next;
        }
        node.next = null;
        return res.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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * 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 sortList(head,null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if(head == null)return head;
        if(head.next == tail){
            head.next = null;
            return head;
        }
        ListNode fast = head, slow = head;
        while(fast != tail){
            fast = fast.next;
            slow = slow.next;
            if(fast != tail){
                fast = fast.next;
            }
        }

        ListNode mid = slow;
        ListNode list1 = sortList(head,mid);
        ListNode list2 = sortList(mid,tail);
        ListNode sorted = merge(list1,list2);
        return sorted;
    }

    public ListNode merge(ListNode list1, ListNode list2) {
        ListNode res = new ListNode(0);
        ListNode head = res;
        while(list1 != null && list2!=null){
            if(list1.val <= list2.val){
                res.next = list1;
                list1 = list1.next;
                res = res.next;
            }else{
                res.next = list2;
                list2 = list2.next;
                res = res.next;
            }
        }
        if(list1 != null)res.next = list1;
        if(list2 != null)res.next = list2;
        return head.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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/**
 * 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) {
        if(head == null)return head;

        int len = 0;
        ListNode node = head;
//首先需要知道链表的长度
        while(node != null){
            node = node.next;
            len++;
        }
//然后定义返回节点
        ListNode res = new ListNode(0);
        res.next = head;
//subLen每次左移一位（即sublen = sublen*2） ，这层循环是规定每次的长度 *2 
        for(int subLen = 1 ; subLen < len ; subLen <<= 1){
            ListNode pre = res;
            ListNode cur = res.next;  // curr用于记录拆分链表的位置

            //这层循环是按照subLen长度的进行两两分割合并
            while(cur != null){
                ListNode list1_head = cur;//备份节点头
                for(int i = 1 ; i < subLen && cur !=null && cur.next != null; i++){
                    cur = cur.next;
                }//取出相应sublen长的链表
                ListNode list2_head = cur.next; //下一个就是链表2的头节点
                cur.next = null;		//切断
                cur = list2_head;		//给cur重新赋值跑起来

                for(int i = 1 ; i < subLen && cur !=null && cur.next != null; i++){
                    cur = cur.next;
                }//同样sublen长的链表
                ListNode next = null;//要备份这个位置，让上边两个合并，应为可能遇到cur为空，就需要判断
                if(cur != null){	//如果cur不为空，就需要让next接着后边走，并且截断
                    next = cur.next;
                    cur.next = null;
                }

                ListNode mergeNode = merge(list1_head,list2_head);
                pre.next = mergeNode; //合并之后拼接
                while(pre.next != null){
                    pre = pre.next;		//需要到拼接的末尾
                }
                cur = next;		//继续后边的合并
            }
        }
        return res.next;  
    }



    public ListNode merge(ListNode list1, ListNode list2) {
        ListNode res = new ListNode(0);
        ListNode head = res;
        while(list1 != null && list2!=null){
            if(list1.val <= list2.val){
                res.next = list1;
                list1 = list1.next;
                res = res.next;
            }else{
                res.next = list2;
                list2 = list2.next;
                res = res.next;
            }
        }
        if(list1 != null)res.next = list1;
        if(list2 != null)res.next = list2;
        return head.next;
    }
}

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

示例 1:

1
2
3
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

1
2
3
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

  • 1 <= nums.length <= 2 * 104
  • -10 <= nums[i] <= 10
  • nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

动态规划

dp[i]如果仅有前边最大值和当前值的话，就可能出现正负号最大，就需要也记录最小值，就是负的最大值，同时统计最大最小值，最终统计最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProduct(int[] nums) {
        int len = nums.length;
        int[] dpMax = new int[len];
        int[] dpMin = new int[len];
        dpMax[0] = nums[0];
        dpMax[0] = nums[0];
        int res = nums[0];
        for(int i = 1 ; i < len ; i++){
            dpMax[i] = Math.max(dpMax[i-1]*nums[i], Math.max(dpMin[i-1]*nums[i],nums[i]));
            dpMin[i] = Math.min(dpMin[i-1]*nums[i], Math.min(dpMax[i-1]*nums[i],nums[i]));
            res = Math.max(Math.max(dpMax[i],dpMin[i]) , res);
        }
        return res;
    }
}

缩减版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxProduct(int[] nums) {
        int res = nums[0] , preMax = nums[0], preMin = nums[0];
        for(int i = 1 ; i < nums.length ; i++){
            int curMax = preMax , curMin = preMin;
            curMax = Math.max(preMax*nums[i],Math.max(nums[i],preMin*nums[i]));
            curMin = Math.min(preMin*nums[i],Math.min(nums[i],preMax*nums[i]));
            preMax = curMax;
            preMin = curMin;
            res = Math.max(res,curMax);
        }
        return res;
    }
}

155. 最小栈

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

实现 MinStack 类:

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

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
["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.

提示：

  • -231 <= val <= 231 - 1
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 104 次

辅助栈

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
class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;

    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    }
    
    public void pop() {
        xStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return xStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

img

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

  • intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
  • skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

img

1
2
3
4
5
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

img

1
2
3
4
5
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

img

1
2
3
4
5
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 1 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listA 和 listB 没有交点，intersectVal 为 0
  • 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

哈希表法最简单，直接找就行

双指针法最好，节省空间

该方法利用了 你吹过吹过的晚风，那我们一定能相拥 ， 利用 两个链表分三块，一块链表A的a,一块B链表的b,一块AB公共的c，c有可能为null，那么a+c+b=b+c+a，前边是A走过的，后边是B走过的。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

169. 多数元素

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

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

示例 1：

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

示例 2：

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

提示：

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

哈希表法 时间空间都是O(n)

排序 排序取中间值， 时间nlog(n) 空间O(logn)

随机化

分治

区间平分，那么一定有一半的众数满足要求，每次比较最多的那个，选中就行

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
class Solution {
    public int majorityElement(int[] nums) {
        return majorityElementDac(nums , 0 , nums.length-1 );
    }

    public int majorityElementDac(int[] nums , int left , int right) {
        if(left == right)return nums[left];

        int mid = (right - left)/2 + left;

        int majorA = majorityElementDac(nums , left , mid);
        int majorB = majorityElementDac(nums , mid + 1, right);

        if(majorA == majorB)return majorA;

        int majorACount = coutnMajorityElement(nums , majorA , left , right);
        int majorBCount = coutnMajorityElement(nums , majorB , left , right);

        return majorACount > majorBCount ? majorA : majorB;
    }

    public int coutnMajorityElement(int[] nums , int num ,int left , int right) {
        int count = 0;
        for(int i = left ; i <= right ; i++){
            if(nums[i] == num)count++;
        }
        return count;
    }
}

Boyer-Moore 投票算法

简单说，就是我们记录状态，比如776644 ，我们令count= 0，遇到7，选取7为众数，计数，遇到不是7的抵消，count–,count为0时重新选择众数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int majorityElement(int[] nums) {
        int count = 1 , candidate = nums[0]; 
        for(int i = 1 ; i < nums.length ; i++){
            if(nums[i] == candidate){
                count++;
            }else{
                if(count == 0){
                    candidate = nums[i];
                    count++;
                }else{
                    count--;
                }
            }
        }
        return candidate;
    }
}

198. 打家劫舍

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

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

示例 1：

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

示例 2：

1
2
3
4
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(len == 1)return nums[0];
        if(len == 2)return Math.max(nums[0],nums[1]);

        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i = 2 ; i < len ; i++){
            dp[i] = Math.max(dp[i-2] + nums[i] ,dp[i-1]);
        }
        return dp[len-1];
    }
}

简单版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(len == 1)return nums[0];
        if(len == 2)return Math.max(nums[0],nums[1]);

        int[] dp = new int[2];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i = 2 ; i < len ; i++){
            int temp = dp[1];
            dp[1] = Math.max(dp[0] + nums[i] ,dp[1]);
            dp[0] = temp;
        }
        return dp[1];
    }
}

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 '0' 或 '1'

算法思路：

遍历所有节点，然后遇到1就开始dfs，把这块岛屿全变成0，接着往后搜索。

深度优先搜索

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
class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int count = 0;
        for(int i = 0 ; i < m ;i++){
            for(int j = 0 ; j < n ;j++){
                if(grid[i][j] == '1'){
                    dfs(grid, i , j);
                    count++;
                }
            }
        }
        return count;
    }

    public void dfs(char[][] grid , int x , int y){
        int m = grid.length;
        int n = grid[0].length;

        if(x < 0 || y < 0 || x >= m || y >= n || grid[x][y] == '0')return;

        grid[x][y] = '0';
        dfs(grid, x-1 ,y);
        dfs(grid, x+1 ,y);
        dfs(grid, x ,y+1);
        dfs(grid, x ,y-1);
    }
}

广度优先搜索

和深度差不多，就是采用队列存放一块岛屿上的节点，然后清0；

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

img

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

示例 2：

img

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

示例 3：

1
2
输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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;
    }
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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) {
        if(head == null || head.next == null)return head;
        //这个就是为了找到节点末尾，用来层层返回头部
        ListNode newHead = reverseList(head.next);
        //这个就是让  a -> b 节点，变成 a <- b   
        head.next.next = head;
        //这个是让  a <- b ，a 的节点往前清空，这里不怕清空，因为递归过来，上一层有前节点的值
        head.next = null;
        return newHead;
    }
}

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

  • 1 <= numCourses <= 105
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同

深度优先搜索

首先明确几个概念 入度，出度， 入度就是指向该节点，出度就是从该节点指向外边节点，这里的出度就是每门课程都是那些课程的先决条件。

1.首先我们需要建立一个出度表，也就是说，我们从每个节点出发搜索，搜索过程置位1，如果遇到1，就说明有环路。失败

2.然后每个节点判断，正在搜索的就是1，搜索过的为2，未搜索为0。

3.以该节点出度遍历搜索。看是否能碰到1 ，碰不到就没问题，就给2.回溯给2.搜索完毕。

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
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    int[] visit;
    boolean isValid = true;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        visit = new int[numCourses];
        for(int i = 0 ; i < numCourses ; i++){
            list.add(new ArrayList<>());
        }
        //学info[0]之前要先学info[1],所以info[1]指向info[0],
        //所以在info[1]的ArrayList中存储它指向哪个科目
        for(int[] info : prerequisites){
            list.get(info[1]).add(info[0]);
        }

        for(int i = 0 ; i < numCourses ; i++){
            if(visit[i] == 0)dfs(i);//如果是未搜索的科目，则深搜
        }

        return isValid;
    }


    public void dfs(int v){
        visit[v] = 1;
        for(int w : list.get(v)){
            if(visit[w] == 0){
                dfs(w);
                if (!isvaild)return;
            }
            else if(visit[w] == 1){
                isValid = false;//如果指向的某一学科在搜索中，则有环，标记isVaild
                return;
            }
        }
        visit[v] = 2;//因为该科目已经完成深搜，所以标记它的状态未搜索过
    }
}

广度优先搜索

这个算法思路就是统计入度和出度，然后从入度为0 的加入队列 中，然后把这门课学了，把以这门客为基础所有的课程入度-1，如果为0，这门课就可以学习了，加入队列，不为0就不管。等着该门课要求的所有课程学完（学完最后一门必修就可以学他了），再学习他。 然后统计一共学习个数量，在和总课程比较

出度， 该课程是那些门的基础课

入读，该课程有几门必修课

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
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    int[] inDegree;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //初始化 出度 集合
        for(int i = 0 ; i < numCourses ; i++){
            list.add(new ArrayList<>());
        }
//添加出度，并且统计入度
        inDegree = new int[numCourses];
        for(int[] info : prerequisites){
            list.get(info[1]).add(info[0]);
            inDegree[info[0]]++;
        }
//把 入度 为 0 的加入队列，也就是这门课我可以直接学，那就直接学了。看看最后谁没学，就知道有没有环
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0 ; i < numCourses ; i++){
            if(inDegree[i] == 0){
                queue.add(i);
            }
        }
//统计学习的课程数，并且循环加入队列中入度为0 的课程，找到这个课程的出度，也就是 以该课程为必修课的 课程， 然后让这些课程的必修课减去1
        int visited = 0;
        while(!queue.isEmpty()){
            visited++;
            int u = queue.poll();
            for(int v : list.get(u)){
                inDegree[v]--;
                if(inDegree[v] == 0){
                    queue.add(v);
                }
            }
        }
        return visited == numCourses;
    }
}

208. 实现 Trie (前缀树)

**Trie**（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

  • 1 <= word.length, prefix.length <= 2000
  • word 和 prefix 仅由小写英文字母组成
  • insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

前缀树，定义结构体，26个英文字符，加上是否是结尾，然后插入就从每个字母往深得插入，查找也是。

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
48
49
class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for(int i = 0 ; i < word.length(); i++){
            int index = word.charAt(i) - 'a';
            if(node.children[index] == null){
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return  node != null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for(int i = 0 ; i < prefix.length(); i++){
            int index = prefix.charAt(i) - 'a';
            if(node.children[index] == null)return null;
            node = node.children[index];
        }
        return node;
    }

}

/**
 * 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);
 */

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

1
2
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

1
2
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

利用快速排序思想，在递归中，遇到分割值（左边小于该值，右边大于该值，该数组下标后边排序位置不动）下标大于 leng-K，说明太大了，要往左递归，小于leng-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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {

    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    public int quickSelect(int[] arr, int left, int right, int k) {
        int parIndex = randomPartition(arr, left, right);
        if (parIndex == k) {
            return arr[parIndex];
        } else {
            return parIndex < k ? quickSelect(arr, parIndex + 1, right, k) : quickSelect(arr, left, parIndex - 1, k);
        }
    }


    public int randomPartition(int[] arr, int left, int right) {
        int random = new Random().nextInt(right - left + 1) + left;
        swap(arr, random, left);
        return partition(arr, left, right);
    }


    public int partition(int[] arr , int left , int right){
        //设置基准值，从前往后比较，把小于基准放左边，大于放右边，index需要交换的，也就是大于基准的第一个值，
        int pivot = left;
        int index = pivot + 1;
        for(int i = index ; i <= right ; i++){
            if(arr[i] <= arr[pivot]){
                swap(arr , i , index); 
                index++;
            }
        }
        //最后把基准值放在中间，左边是小于等于基准，右边大于基准
        swap(arr , index - 1 , pivot);
        //反回该基准值为边界，两边递归
        return index - 1;
    }


    public void swap(int[] arr , int x , int y){
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
}

大顶堆

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
class Solution {
    public int findKthLargest(int[] nums, int k) {

        int len = nums.length;
        buildMaxHeap(nums, len);
        for (int i = len - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --len;
            heapify(nums, 0, len);
        }
        return nums[0];


    }

    private void buildMaxHeap(int[] arr, int len) {
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    private void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

221. 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：

img

1
2
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

img

1
2
输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

1
2
输入：matrix = [["0"]]
输出：0

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] 为 '0' 或 '1'

动态规划

这个题的要求是找最大正方形，所以我们只要找到边长就可以了，找到边长最好的办法，动态规划，dp[i][j]代表i行j列这个位置的最大边长，所以一个正方行的最大边长取决于上边的那些都为1

image.png

就是说，

1
2
3
if (grid[i - 1][j - 1] == '1') {
    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length , n = matrix[0].length;
        int[][] dp = new int[m][n];


        int res = 0;
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < n ; j++){
                if(matrix[i][j] == '1'){
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = Math.min(dp[i-1][j] , Math.min(dp[i][j-1] , dp[i-1][j-1]) ) + 1;
                    }
                    res = Math.max(res , dp[i][j]);
                }
            }
        }
        return res*res;
    }
}

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

img

1
2
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

img

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

示例 3：

1
2
输入：root = []
输出：[]

提示：

  • 树中节点数目范围在 [0, 100] 内
  • -100 <= Node.val <= 100

递归

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
/**
 * 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 null;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        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
/**
 * 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 null;

        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        while(!list.isEmpty()){

            TreeNode node = list.poll();
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            if(node.right!=null)list.add(node.right);
            if(node.left!=null)list.add(node.left);
        }
        return root;
    }
}

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

img

1
2
输入：head = [1,2,2,1]
输出：true

示例 2：

img

1
2
输入：head = [1,2]
输出：false

提示：

  • 链表中节点数目在范围[1, 105] 内
  • 0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

一种超级简单的解法，就是放到数组里去判断。

第二种解法：递归

第三种空间O(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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * 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) {

        ListNode firstHalf = endOfFirstHalf(head);
        ListNode secondStart = reverse(firstHalf.next);

        ListNode p1 = head;
        ListNode p2 = secondStart;
        boolean res = true;
        while(res && p2 != null){
            if(p1.val != p2.val)res = false;
            p1 = p1.next;
            p2 = p2.next;
        }
        
        firstHalf.next = reverse(secondStart);
        return res;

    }

    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode nextTemp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nextTemp;
        }
        return pre;
    }

    public ListNode endOfFirstHalf(ListNode head){
        ListNode fast = head , slow = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

img

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

img

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

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

提示：

  • 树中节点数目在范围 [2, 105] 内。
  • -109 <= Node.val <= 109
  • 所有 Node.val 互不相同 。
  • p != q
  • p 和 q 均存在于给定的二叉树中。

递归，这道题的解法，想一下P Q 的可能性，一共有两种。 比如说在这个节点的左右部分，或者是P是这个节点，P是左边或者右边子孩子。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode ans;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root , p , q);
        return this.ans;
    }


    public boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null)return false;

        boolean lSon = dfs(root.left , p ,q);
        boolean rSon = dfs(root.right , p ,q);
//如果遇到那两种情况，就记录根基点
        if( (lSon &&rSon) ||  ((root.val == p.val || root.val == q.val) && (lSon || rSon)) ){
            ans = root;
        }
        //递归返回，返回的就是 是否在左边，右边，或者当前节点就是p 或者 q  
        return lSon || rSon || (root.val == p.val || root.val == q.val);
    }
}

238. 除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请不要使用除法，且在 O(*n*) 时间复杂度内完成此题。

示例 1:

1
2
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

1
2
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

左右前缀积和后缀积， 左后相乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] prefix = new int[len];
        int[] suffix = new int[len];

        prefix[0] = 1;
        suffix[len - 1] = 1;
        for(int i = 1 ; i < len ; i++){
            prefix[i] = prefix[i-1] * nums[i-1];
        }

        for(int j = len - 2 ; j >= 0 ; j-- ){
            suffix[j] = suffix[j+1] * nums[j+1];
        }

        int[] res = new int[len];
        for(int i = 0 ; i < len ; i++){
            res[i] = suffix[i] * prefix[i];
        }
        return res;
    }
}

空间优化

1,把后缀乘积用res代替，2，前缀乘积用K代替，不保存，直接和res（后缀积）相乘结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] prefix = new int[len];

        int[] res = new int[len];

        prefix[0] = 1;
        res[len - 1] = 1;


        for(int j = len - 2 ; j >= 0 ; j-- ){
            res[j] = res[j+1] * nums[j+1];
        }

        int k = 1;
        for(int i = 1 ; i < len ; i++){
            k = k * nums[i-1];
            res[i] = res[i] * k;
        }
        return res;
    }
}

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

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

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

用队列解决，队列解决不超时的要点就是移除队列顶部元素，要同时把下标放进去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {

        int len = nums.length;
        PriorityQueue<int[]> queue = new PriorityQueue<>( (o1, o2) -> o2[0] == o1[0] ? o1[1] - o2[1] : o2[0] - o1[0]    );


        for(int i = 0 ; i < k ; i++){
            queue.add(new int[]{nums[i],i});
        }

        int [] res = new int[len - k + 1];

        res[0] =  queue.peek()[0];

        for(int i = k ; i < nums.length ; i++){
            queue.add(new int[]{nums[i],i});
            while( queue.peek()[1] <= i - k)queue.poll();
            res[i-k+1] =  queue.peek()[0];
        }
        
        return res;
    }
}

利用队列维护，简单来说，队列长度为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
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {

        int len = nums.length;
        Deque<Integer> queue = new LinkedList<>();


        for(int i = 0 ; i < k ; i++){
            while(!queue.isEmpty() && nums[i] >= nums[queue.peekLast()] ){
                queue.pollLast();
            }
            queue.addLast(i);
        }

        int [] res = new int[len - k + 1];

        res[0] =  nums[queue.peekFirst()];

        for(int i = k ; i < nums.length ; i++){
            while(!queue.isEmpty() && nums[i] >= nums[queue.peekLast()] ){
                queue.pollLast();
            }
            queue.addLast(i);
            while(queue.peekFirst() <= i-k)queue.pollFirst();

            res[i-k+1] =  nums[queue.peekFirst()];
        }
        
        return res;
    }
}

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例 1：

img

1
2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

img

1
2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -109 <= matrix[i][j] <= 109
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • -109 <= target <= 109

直接查找省略

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        
        for(int i = 0 ; i < m ; i++){
            int left = 0 , right = n - 1;
            while(left <= right){
                int mid = left + (right - left)/2;
                if(matrix[i][mid] > target) right = mid - 1;
                else if(matrix[i][mid] < target) left = mid + 1;
                else if(matrix[i][mid] == target)return true;
            }
        }
        return false;   
    }
}

Z型查找，右上角或者左下角查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        int i = 0 , j = n - 1;

        while( j >= 0 && i < m ){
            if(matrix[i][j] == target)return true;
            if(matrix[i][j] < target)i++;
            else if(matrix[i][j] > target)j--;
        }
        return false;   
    }
}

279. 完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

1
2
3
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

1
2
3
输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

  • 1 <= n <= 104

动态规划， 无非就是遍历一下，看一下 j * j ，然后加上多少等于这个值， 这个加上的值可从dp里边找，然后最后取个最小值，就可以了，记得+1

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for(int i = 1 ; i < n+1 ; i++){
            int minn = Integer.MAX_VALUE;
            for(int j = 1 ; j * j <= i ; j++){
                minn = Math.min(minn , dp[i - j*j]);
            }
            dp[i] = minn+1;
        }
        return dp[n];
    }
}

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

1
2
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

1
2
输入: nums = [0]
输出: [0]

提示:

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

双指针，一个指向前边0，一个往后找非0的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public void moveZeroes(int[] nums) {
        int len = nums.length;

        int left = 0 , right = 0;

        while(right < len){
            if(nums[right] != 0){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
            }
            right++;
        }
    }
}

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

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

示例 2：

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

提示：

  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

进阶：

  • 如何证明 nums 中至少存在一个重复的数字?
  • 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

二分

既然n+1个数，范围是【1，n】，那我直接从【1，n】挑数字，比如2，统计n+1个数，小于等于2的有多少，如果前边没有重复，那么一定是2个，如果小于，一定在后边，大于，就在前边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int findDuplicate(int[] nums) {
        int len = nums.length;
        int left = 0 , right = len - 1;
        int res = 0;
        

        while(left <= right){
            int mid = (left + right) >> 1;
            int count = 0;
            for(int i = 0 ; i < len ; i++){
                if(nums[i] <= mid)count++;
            }

            if(count <= mid)left = mid + 1;
            else{
                res = mid;
                right = mid - 1;
            }
        }
        return res;
    }
}

快慢指针，类比环形链表

  • 时间复杂度：O(n)O(n)。「Floyd 判圈算法」时间复杂度为线性的时间复杂度。
  • 空间复杂度：O(1)O(1)。我们只需要常数空间存放若干变量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0 ,fast = 0;
        //要想明白这里给的是初始下标0 ，fast 和 slow 代表的是值
        do{
            fast = nums[fast];
            fast = nums[fast];
            slow = nums[slow];
        }while(slow != fast);

        slow = 0;
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

297. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：

img

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

示例 2：

1
2
输入：root = []
输出：[]

示例 3：

1
2
输入：root = [1]
输出：[1]

示例 4：

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

提示：

  • 树中结点数在范围 [0, 104] 内
  • -1000 <= Node.val <= 1000

通过次数174,428

提交次数299,780

利用bfs

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * 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 null;
        StringBuffer buffer = new StringBuffer();
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node == null){
                buffer.append("null,");
            }else{
                buffer.append(node.val+",");
                queue.add(node.left);
                queue.add(node.right);
            }
        }
        buffer.setLength(buffer.length() - 1);
        return buffer.toString();
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null)return null;
        String[] dataArray = data.split(",");
        Deque<TreeNode> deque = new LinkedList<>();
        TreeNode res = new TreeNode(Integer.valueOf(dataArray[0]));
        deque.add(res);
        int i = 1;
        while(i < dataArray.length){
            TreeNode node = deque.poll();
            
            if(!dataArray[i].equals("null")){
                node.left = new TreeNode(Integer.valueOf(dataArray[i]));
                deque.add(node.left);
            }

            if(++i >= dataArray.length)break;

            if(!dataArray[i].equals("null")){
                node.right = new TreeNode(Integer.valueOf(dataArray[i]));
                deque.add(node.right);
            }
            i++;
        }
        return res;
    }
}

// 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));

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

进阶：

  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int lengthOfLIS(int[] nums) {
        //dp的含义就是，以i为下标，前边最大的递增序列长度
        int len = nums.length;
        int[] dp = new int[len];
        int res = 1;
        dp[0] = 1;
        for(int i = 1 ; i < len ; i++){
            //特别注意这个给值，为什么要给1，想一下，4，10，4，3，8，9  比如dp  就是该 1 2 1 1 2 3  
            //但是我们遍历，要取dp最大值+1,这个没问题，但是如果没有呢，就是这个数是个小的，那就是0了，所以给个初始1.
            dp[i] = 1;
            for(int j = 0 ; j < i ; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i] , dp[j] + 1); 
                }
            }
            res = Math.max(res , dp[i]);
        }
        return res;

    }
}

贪心+二分

这个题代码思路， 比如 4 10 4 3 8 9 ，贪心就是

1
2
3
4
5
6
7
4
4  10  
4  10
3  10 		
3  8		//可能疑问为什么不是 3  8  10  ，注意，这里10 3 什么的就是个占位，代表前边有个小的数，后边如果来了更多大数，就可以用上去
3  8  9  		// 3   8    ， 8  代替了10  ，如果后边来了个9  就可以接着算上9，如果没有，那也没关系，应为8就代表了10 ，升子序列长度为2

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
class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = 1, n = nums.length;

        int[] arr = new int[n + 1];
        arr[1] = nums[0];

        for(int i = 1 ; i < n ; i++){
            if(nums[i] > arr[len]){
                arr[++len] = nums[i];
            }else{
                int left = 1 , right = len;
                while(left <= right){
                    int mid = (left + right) >> 1;
                    if(nums[i] <= arr[mid]){
                        right = mid - 1;
                    }else{
                        left = mid + 1;
                    }
                }
                arr[left] = nums[i];
            }
        }
        return len;
    }
}

301. 删除无效的括号

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

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

示例 2：

1
2
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：

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

提示：

  • 1 <= s.length <= 25
  • s 由小写英文字母以及括号 '(' 和 ')' 组成
  • s 中至多含 20 个括号

方法一：回溯 + 剪枝

回溯，就是挨个去掉括号然后往下看看对不对。那就要知道要去什么括号，首先要要知道左括号和右括号应该移除的个数

回溯：

for循环开始，我们挨个去掉位置i的括号往下回溯。可能有人好奇，为什要有一个for循环，直接去掉不行嘛，注意，这里去括号方法很多种，比如(a)())()，就可以是(a)()() 或者 (a())()，所以要尝试以每个下标开始去除。

回溯出去的条件：如果去除括号最后发现lremove 和 rremove 都为0 ，就说明去除括号完成了，检验一下合法性。

for(循环注意)

如果遇到((()只需要去除第一个括号往后遍历，不需要对每个遍历。所以遇到后边字符相同，并且不是第一个的时候，直接跳过。

如果遇到要去除的lremove 和 rremove 加起来小于剩余长度，就需要返回。

然后尝试去掉左括号、右括号。前提是lremove 、 rremove 大于0

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
48
49
50
51
52
class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int len = s.length();
        int lremove = 0 , rremove = 0;

        for(int i = 0 ; i < len ; i++){
            if(s.charAt(i) == '(')lremove++;
            if(s.charAt(i) == ')'){
                if(lremove > 0)lremove--;
                else rremove++;
            }
        }

        List<String> list = new ArrayList<>();

        recur(list , s ,  lremove , rremove , 0);
        return list;
    }

    public void recur(List<String> list , String str ,  int lremove , int rremove , int start){
        if(lremove == rremove && lremove == 0){
            if(isValid(str)){
                list.add(str);
            }
            return;
        }

        for(int i = start ; i < str.length() ; i++){
            if(start != i && str.charAt(i) == str.charAt(i-1))continue;
            if(str.length() - i < lremove + rremove)return;

            if(lremove > 0 && str.charAt(i) == '(' ){
                recur(list , str.substring(0,i) + str.substring(i+1)  ,  lremove-1 , rremove , i);
            }
            if(rremove > 0 && str.charAt(i) == ')' ){
                recur(list , str.substring(0,i) + str.substring(i+1)  ,  lremove , rremove-1 , i);
            }
        }
    }

    public boolean isValid( String str ){
        int left = 0 , right = 0;
        for(int i = 0 ; i < str.length() ; i++){
            if(str.charAt(i) == '(')left++;
            if(str.charAt(i) == ')'){
                right++;
                if(right > left)return false;
            }
        }
        return true;
    }
}

方法二：广度优先搜索
思路与算法

注意到题目中要求最少删除，这样的描述正是广度优先搜索算法应用的场景，并且题目也要求我们输出所有的结果。我们在进行广度优先搜索时每一轮删除字符串中的 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
34
35
36
37
38
39
40
class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> ans = new ArrayList<>();
        Set<String> currSet = new HashSet<>();

        currSet.add(s);

        while(true){
            for(String str : currSet){
                if(isValid(str)){
                    ans.add(str);
                }
            }
            if(ans.size() > 0)return ans;

            Set<String> nextSet = new HashSet<>();
            for(String str : currSet){
                for(int i = 0 ; i < str.length(); i++){
                    if(i > 0 && s.charAt(i) == str.charAt(i-1))continue;
                    if(str.charAt(i) == '(' || str.charAt(i) == ')'){
                        nextSet.add(str.substring(0,i) + str.substring(i+1));
                    }
                }
            }
            currSet =  nextSet;
        }
    }

    public boolean isValid(String str){
        int count = 0;
        for(int i = 0 ; i < str.length() ; i++){
            if(str.charAt(i) == '(')count++;
            if(str.charAt(i) == ')'){
                count--;
                if(count < 0)return false;
            }
        }
        return count == 0;
    }
}

309. 最佳买卖股票时机含冷冻期

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

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

1
2
3
输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

1
2
输入: prices = [1]
输出: 0

提示：

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000

方法一：动态规划

我们把每天的状态分为三种：

  • 持有：有可能昨天就持有，也有可能昨天不持有，今天刚买入的 dp[i][0] = Math.max(dp[i-1][2] - prices[i] , dp[i-1][0])
  • 冷却：一定是昨天持有，今天卖掉 dp[i][1] = dp[i-1][0] + prices[i];
  • 不持有：有可能昨天就不持有，也有可能昨天卖掉的，今天还不能买，就不持有了 dp[i][2] = Math.max(dp[i-1][2] , dp[i-1][1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][3];

        dp[0][0] = -prices[0];

        for(int i = 1 ; i < len ; i++){
            dp[i][0] = Math.max(dp[i-1][2] - prices[i] , dp[i-1][0]);
            dp[i][1] = dp[i-1][0] + prices[i];
            dp[i][2] = Math.max(dp[i-1][2] , dp[i-1][1]);
        }
        return Math.max(dp[len-1][1], dp[len-1][2]);
    }
}

我们发现每天的状态之和前边一天有关，直接省略空间做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int preHave = -prices[0] , preColling = 0 , preWithout = 0;

        for(int i = 1 ; i < len ; i++){
            int curHave = Math.max(preWithout - prices[i] , preHave);
            int curColling = preHave + prices[i];
            int curWithout = Math.max(preWithout , preColling);
            preHave = curHave;
            preColling = curColling;
            preWithout = curWithout;
        }
        return Math.max(preColling , preWithout);
    }
}

312. 戳气球

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

示例 1：

1
2
3
4
5
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

示例 2：

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

提示：

  • n == nums.length
  • 1 <= n <= 300
  • 0 <= nums[i] <= 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maxCoins(int[] nums) {
        int len = nums.length;
        int[][] dp = new int[len+2][len+2];
        int[] val = new int[len+2];
        val[0] = val[len + 1] = 1;
        for(int i = 1 ; i <= len ; i++){
            val[i] = nums[i-1];
        }

        for(int i = len-1 ; i >=0 ; i--){
            for(int j = i+2 ; j <= len+1 ; j++){
                for(int k = i+1 ; k < j ; k++){
                    int sum = val[k] * val[i] * val[j];
                    sum += dp[i][k] + dp[k][j];
                    dp[i][j] = Math.max(dp[i][j] , sum);
                }
            }
        }
        return dp[0][len+1];
    }
}

322. 零钱兑换

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

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

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

示例 1：

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

示例 2：

1
2
输入：coins = [2], amount = 3
输出：-1

示例 3：

1
2
输入：coins = [1], amount = 0
输出：0

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

动态规划

如果最后（包含）一枚是1，那么11-1=10 ，我们就需要知道兑换10所需的最少硬币数量dp[10]。
如果最后（包含）一枚是2，11-2=9，我们就需要知道兑换9所需的最少硬币数量dp[9]。
如果最后（包含）一枚是5，11-5=6，我们就需要知道兑换6所需的最少硬币数量dp[6]。
然后我们取出dp[10]，dp[9]，dp[6]三个值中的最小值，加上我们刚才拿出的那一枚硬币，就得出了兑换11的答案，这就是状态转移的过程。
那么问题来了，dp[10]，dp[9]，dp[6]这些值是怎么得到的呢？
其实就是重复上面的步骤，例如我们要知道dp[10]的值，也是分三种情况：10-1=9，10-2 = 8， 10-5= 5，以此类推。。。
这样如果知道了dp[0-10]的状态值，问题就解决了。我们采用自下而上的方式依次记录兑换0至11这些金额所需要的硬币最少组合值。

1
2
总共金额     0   1	2	3	4	5	6	7	8	9	10	11
最少硬币	0	1	1	2	2	1	2	2	3	3	2	3

求dp[1]的时候，很简单，结果肯定是1。
求dp[2]的时候，分别计算刚才提高的三种情况（1，2，5三种硬币），分别求2-1=1，2-2=0，2-5=-3（比当前金额大的硬币可以忽略）即dp[1],dp[0]中的最小值，然后+1就是dp[2]的结果。同理，dp[3],dp[4]…dp[11]都可以求出来了。

接下来，就看代码怎么写了，
第一步：如果需要记录这12个数，我们就需要一个长度为12的数组来记录每一个值的状态。
第二步：处理标记0-amount金额的状态，遍历coins里的所有硬币去计算出最少硬币数。
第三步：返回状态值，处理无法兑换的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp , amount + 1);
        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] , 1+dp[i-coins[j]]);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

337. 打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

img

1
2
3
输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

img

1
2
3
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：

  • 树的节点数在 [1, 104] 范围内
  • 0 <= Node.val <= 104

动态规划

0 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
/**
 * 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 {
    //每个节点都可以选中或者不选中，选中f,不选中g
    Map<TreeNode , Integer> f = new HashMap<>();
    Map<TreeNode , Integer> g = new HashMap<>();
    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root , 0) , g.getOrDefault(root , 0));
    }

    public void dfs(TreeNode root){
        if(root == null)return;
        dfs(root.left);
        dfs(root.right);
        f.put(root , root.val + g.getOrDefault(root.left , 0) + g.getOrDefault(root.right , 0));
        g.put(root , Math.max(g.getOrDefault(root.left , 0) , f.getOrDefault(root.left , 0)) + Math.max(g.getOrDefault(root.right , 0) , f.getOrDefault(root.right , 0)));
    }

}
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
/**
 * 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 {
    //每个节点都可以选中或者不选中，选中f,不选中g
    Map<TreeNode , Integer> f = new HashMap<>();
    Map<TreeNode , Integer> g = new HashMap<>();
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0] , res[1]);
    }

    public int[] dfs(TreeNode root){
        if(root == null)return new int[]{0,0};
        int[] l = dfs(root.left);
        int[] r = dfs(root.right);
        int select = root.val + l[1] + r[1];
        int noSelect = Math.max(l[0] , l[1]) + Math.max(r[0] , r[1]);
        return new int[]{select,noSelect};
    }


}

338. 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

1
2
3
4
5
6
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

示例 2：

1
2
3
4
5
6
7
8
9
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

提示：

  • 0 <= n <= 105

进阶：

  • 很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
  • 你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

动态规划： 高位去掉看地位。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n+1];
        int highBit = 0;
        for(int i = 1 ; i <= n ; i++){
            if( (i & (i-1)) == 0){
                highBit = i;
            }
            res[i] = res[i-highBit] + 1;
        }
        return res;
    }
}

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

1
2
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

1
2
输入: nums = [1], k = 1
输出: [1]

提示：

  • 1 <= nums.length <= 105
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

方法一：小根堆

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
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<int[]> pq = new PriorityQueue<>( (o1,o2) -> o1[1] - o2[1]);
        for(Map.Entry<Integer , Integer> entry : map.entrySet()){
            int num = entry.getKey() , count = entry.getValue();
            if(pq.size() == k){
                if(pq.peek()[1] < count){
                    pq.poll();
                    pq.add(new int[]{num , count});
                }
            }else{
                pq.add(new int[]{num , count});
            }
        }
        int[] res = new int[k];
        for(int i = 0 ; i < k ; i++){
            res[i] = pq.poll()[0];
        }
        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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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);
        }
        List<int[]> list = new ArrayList<>();
        for(Map.Entry<Integer , Integer> entry : map.entrySet()){
            int num = entry.getKey() , count = entry.getValue();
            list.add(new int[]{num , count});
        }
        int[] res = new int[k];

        quickSort(list , 0 , list.size()-1 , k-1); 
        for(int i = 0 ; i < k ; i++){
            res[i] = list.get(i)[0];
        }
        return res;
    }

    public void quickSort(List<int[]> list , int left , int right , int k){
        if(left < right){
            int randomPartitionIndex = randomPartition(list , left , right);
            if(randomPartitionIndex - left > k){
                quickSort(list , left , randomPartitionIndex - 1 , k);
            }else if(randomPartitionIndex - left == k){

            }else{
                quickSort(list , randomPartitionIndex + 1, right , k);
            }
        }
    }
    public int randomPartition(List<int[]> list , int left , int right){
        int random = new Random().nextInt(right - left + 1) + left;
        Collections.swap(list , left , random);
        return partition(list , left , right);
    }
    public int partition(List<int[]> list , int left , int right){
        int pivot = left;
        int index = pivot + 1;
        for(int i = index ; i <= right ; i++){
            if(list.get(i)[1] > list.get(pivot)[1]){
                Collections.swap(list, index , i);
                index++;
            }
        }
        Collections.swap(list, index - 1 , pivot);
        return index - 1;
    }
}

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

1
2
输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

1
2
输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

1
2
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

1
2
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

  • 1 <= s.length <= 30
  • s 由小写英文字母、数字和方括号 '[]' 组成
  • s 保证是一个 有效 的输入。
  • s 中所有整数的取值范围为 [1, 300]
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
class Solution {
    public String decodeString(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuffer res = new StringBuffer();
        for(int i = 0 ; i < s.length() ; i++){
            if(s.charAt(i) != ']')stack.push(s.charAt(i));
            else{
                StringBuffer buffer = new StringBuffer();
                while(stack.peek() != '['){ 
                    buffer.append(stack.pop());
                }
                stack.pop();
                int x = 0 , beishu = 1;;
                while(!stack.isEmpty() && stack.peek() >= '0' && stack.peek() <= '9'){
                    x += (stack.pop() - '0') * beishu;
                    beishu *= 10;
                }
                buffer.reverse();
                StringBuffer temp  = new StringBuffer(buffer);
                for(int j = 0 ; j < x-1 ; j++){
                    buffer.append(temp);
                }
                String str = buffer.toString();
                for(int y = 0 ; y < str.length() ; y++){
                    stack.push(str.charAt(y));
                }
            }
        }
        while(!stack.isEmpty()){
            res.append(stack.pop());
        }
        res.reverse();
        return res.toString();
    }
}

399. 除法求值

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

示例 1：

1
2
3
4
5
6
输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]

示例 2：

1
2
输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出：[3.75000,0.40000,5.00000,0.20000]

示例 3：

1
2
输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.50000,2.00000,-1.00000,-1.00000]

提示：

  • 1 <= equations.length <= 20
  • equations[i].length == 2
  • 1 <= Ai.length, Bi.length <= 5
  • values.length == equations.length
  • 0.0 < values[i] <= 20.0
  • 1 <= queries.length <= 20
  • queries[i].length == 2
  • 1 <= Cj.length, Dj.length <= 5
  • Ai, Bi, Cj, Dj 由小写英文字母与数字组成

方法一：并查集

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int len = equations.size();
        UnionFind unionFind = new UnionFind(len*2);
        HashMap<String , Integer> map = new HashMap<>(2*len);
        int index = 0;
        for(int i = 0 ; i < len ; i++){
            String str1 = equations.get(i).get(0);
            String str2 = equations.get(i).get(1);
            if(!map.containsKey(str1)){
                map.put(str1 , index);
                index++;
            }
            if(!map.containsKey(str2)){
                map.put(str2 , index);
                index++;
            }
            unionFind.union(map.get(str1) , map.get(str2) , values[i]);
        }
        len = queries.size();
        double[] res = new double[len];
        for(int i = 0 ; i < len ; i++){
            String str1 = queries.get(i).get(0);
            String str2 = queries.get(i).get(1);
            Integer id1 = map.get(str1);
            Integer id2 = map.get(str2);
            if(id1 == null || id2 == null )res[i] = -1.0d;
            else res[i] = unionFind.isConnected(id1, id2);
        }
        return res;
    }


    private class UnionFind{
        private int[] parent;
        private double[] weight;
        
        public UnionFind(int n){
            this.parent = new int[n];
            this.weight = new double[n];
            for(int i = 0 ; i < n ; i++){
                parent[i] = i;
                weight[i] = 1.0d;
            }
        }
        public void union(int x , int y , double value){
            int rootX = find(x);
            int rootY = find(y);
            if(rootX == rootY)return;
            parent[rootX] = rootY;
            weight[rootX] = weight[y] * value / weight[x];
        }
        public int find(int index){
            if(index != parent[index]){
                int origin = parent[index];
                parent[index] = find(origin);
                weight[index] *= weight[origin];
            }
            return parent[index];
        }
        public double isConnected(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return weight[x] / weight[y];
            } else {
                return -1.0d;
            }
        }
    }
}

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

1
2
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

  • 1 <= people.length <= 2000
  • 0 <= hi <= 106
  • 0 <= ki < people.length
  • 题目数据确保队列可以被重建

方法一：排序

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people , (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);
        List<int[]> res = new ArrayList<>();
        for(int i = 0 ; i < people.length ; i++){
            res.add(people[i][1] , people[i]);
        }
        return res.toArray(new int[res.size()][]);
    }
}

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

1
2
3
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

方法一：动态规划

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
class Solution {
    public boolean canPartition(int[] nums) {
        int len = nums.length , sum = 0 , target = 0 , maxNum = 0; 
        for(int num : nums){
            sum += num;
            maxNum = Math.max(maxNum , num);
        }
        target = sum/2;
        if(len < 2 || ((sum & 1) != 0) || target < maxNum)return false;
        
        boolean[][] dp = new boolean[len][target+1];
        for(int i = 0 ; i < len ; i++){
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;

        for(int i = 1 ; i < len ; i++){
            for(int j = 1 ; j <= target ; j++){
                if(j < nums[i])dp[i][j] = dp[i-1][j];
                else dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]];
            }
        }
        return dp[len-1][target];
    }
}

省略空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean canPartition(int[] nums) {
        int len c= nums.length , sum = 0 , target = 0 , maxNum = 0; 
        for(int num : nums){
            sum += num;
            maxNum = Math.max(maxNum , num);
        }
        target = sum/2;
        if(len < 2 || ((sum & 1) != 0) || target < maxNum)return false;
        
        boolean[] dp = new boolean[target+1];
        dp[0] = true;

        for(int i = 1 ; i < len ; i++){
            for(int j = target ; j >= 0 ; j--){
                if(j >= nums[i]) dp[j] |= dp[j-nums[i]];
            }
        }
        return dp[target];
    }
}

437. 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

img

1
2
3
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

1
2
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示:

  • 二叉树的节点个数的范围是 [0,1000]
  • -109 <= Node.val <= 109
  • -1000 <= targetSum <= 1000

方法一：dfs

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
class Solution {
    
    public int pathSum(TreeNode root, long targetSum) {
        if (root == null) {
            return 0;
        }

        int res = rootSum(root, targetSum);
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);
        return res;
    }

    public int rootSum(TreeNode root, long targetSum) {
        int ret = 0;

        if (root == null) {
            return 0;
        }
        int val = root.val;
        if (val == targetSum) {
            ret++;
        } 

        ret += rootSum(root.left, targetSum - val);
        ret += rootSum(root.right, targetSum - val);
        return ret;
    }
}

方法二：前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<Long, Integer>();
        prefix.put(0L, 1);
        return dfs(root, prefix, 0, targetSum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = 0;
        curr += root.val;

        ret = prefix.getOrDefault(curr - targetSum, 0);
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        ret += dfs(root.left, prefix, curr, targetSum);
        ret += dfs(root.right, prefix, curr, targetSum);
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

        return ret;
    }
}

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

1
2
3
4
5
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

1
2
3
4
5
6
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

  • 1 <= s.length, p.length <= 3 * 104
  • s 和 p 仅包含小写字母

方法一：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int pLen = p.length() , sLen = s.length();
        List<Integer> res = new ArrayList<>();
        if(pLen > sLen)return res;

        int[] sCount = new int[26];
        int[] pCount = new int[26];

        for(int i = 0 ; i < pLen ; i++){
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }
        if(Arrays.equals(sCount , pCount))res.add(0);

        for(int i = 0 ; i < sLen-pLen ; i++){
            sCount[s.charAt(i) - 'a']--;
            sCount[s.charAt(i+pLen) - 'a']++;
            if(Arrays.equals(sCount , pCount))res.add(i+1);
        }
        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
28
29
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int pLen = p.length() , sLen = s.length();
        List<Integer> res = new ArrayList<>();
        if(pLen > sLen)return res;

        int[] count = new int[26];
        for(int i = 0 ; i < pLen ; i++){
            count[s.charAt(i) - 'a']++;
            count[p.charAt(i) - 'a']--;
        }
        int diff = 0;
        for(int i = 0 ; i < 26 ; i++){
            if(count[i] != 0)diff++;
        }
        if(diff == 0)res.add(0);

        for(int i = 0 ; i < sLen-pLen ; i++){
            if(count[s.charAt(i) - 'a'] == 1)diff--;
            else if(count[s.charAt(i) - 'a'] == 0)diff++;
            count[s.charAt(i) - 'a']--;
            if(count[s.charAt(i+pLen) - 'a'] == -1)diff--;
            else if(count[s.charAt(i+pLen) - 'a'] == 0)diff++;
            count[s.charAt(i+pLen) - 'a']++;
            if(diff == 0)res.add(i+1);
        }
        return res;
    }
}

448. 找到所有数组中消失的数字

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

1
2
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例 2：

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

提示：

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n

进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

方法一：虚拟哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int len = nums.length;
        for(int num : nums){
            int x = (num-1) % len;
            nums[x] += len;
        }
        List<Integer> res = new ArrayList<>();
        for(int i = 0 ; i < len ; i++){
            if(nums[i] <= len){
                res.add(i+1);
            }
        }
        return res;
    }
}

461. 汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

1
2
3
4
5
6
7
输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2：

1
2
输入：x = 3, y = 1
输出：1

提示：

  • 0 <= x, y <= 231 - 1

方法一：统计个数

方法二：Brian Kernighan算法

a = 10100 b = a-1 = 10011 a和b相与消去最后一位1

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int hammingDistance(int x, int y) {
        int s = x^y , count = 0;
        while(s != 0){
            s &= (s-1);
            count++;
        }
        return count;
    }
}

494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

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

提示：

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

方法一：深度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    int count;
    public int findTargetSumWays(int[] nums, int target) {
        recur(nums , target , 0 , 0);
        return count;
    }
    public void recur(int[] nums , int target , int index , int sum){
        if(sum == target && index == nums.length)count++;
        if(index == nums.length)return;
        recur(nums , target , index+1 , sum+nums[index]);
        recur(nums , target , index+1 , sum-nums[index]);
    }
}

方法二：动态规划

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
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // （sums - 负数） - 负数 = target  
        //  负数 = (sums - target)/2
        // dp[i][j] , 0 - i 中和为 j ， dp[n][neg]：
        // dp[0][j] = 0   j = 0 : 1  ,j >= 1 : 0;
        //dp[i][j]     i下标的数为num， 我们选不选，如果 j < num，不可以选择，dp[i][j] = dp[i-1][j];
        // 大于可以选  dp[i-1][j]   dp[i-1][j-num]
        int sum = 0 , len = nums.length , neg , diff;
        for(int num : nums){
            sum += num;
        }
        diff = sum - target;
        if(diff < 0 || diff % 2 != 0)return 0;
        neg = diff/2;
        int[][] dp = new int[len+1][neg+1];  
        dp[0][0] = 1;      
        for(int i = 1 ; i <= len ; i++){
            for(int j = 0 ; j <= neg ; j++){
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1]){
                    dp[i][j] += dp[i-1][j - nums[i-1]];
                }
            }
        }
        return dp[len][neg];
    }
}

省略空间,注意从后往前

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0 , len = nums.length , neg , diff;
        for(int num : nums){
            sum += num;
        }
        diff = sum - target;
        if(diff < 0 || diff % 2 != 0)return 0;
        neg = diff/2;
        int[] dp = new int[neg+1];  
        dp[0] = 1;
        for(int num : nums){
            for(int j = neg ; j >= num ; j--){
                dp[j] += dp[j - num];
            }
        }
        return dp[neg];
    }
}

538. 把二叉搜索树转换为累加树

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：

img

1
2
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

1
2
输入：root = [0,null,1]
输出：[1,null,1]

示例 3：

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

示例 4：

1
2
输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

  • 树中的节点数介于 0 和 104 之间。
  • 每个节点的值介于 -104 和 104 之间。
  • 树中的所有值 互不相同 。
  • 给定的树为二叉搜索树。

方法一：深度优先

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root != null){
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            TreeNode left = convertBST(root.left);
            return root;
        }
    }
}

543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

1
2
3
4
5
    1
   / \
  2   3
 / \     
4   5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int res;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res;
    }

    public int dfs(TreeNode root){
        if(root == null)return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        res = Math.max(res , left + right);
        return Math.max(left , right) + 1;
    }
}

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

方法一：枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for(int end = 0 ; end < nums.length ; end++){
            int sum = 0;
            for(int start = end ; start >= 0 ; start--){
                sum += nums[start];
                if(sum == k)count++;
            }
        }
        return count;
    }
}

方法二：前缀和

我们令前缀和为f[i]，就可以知道，f[j] + k = f[i]；所以我们可以哈希存前缀和，前缀和一样的就个数加1.要想求个数，我们把前缀和+k = 当前f[i]的所有个数统计一下就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        HashMap<Integer , Integer> map = new HashMap<>();
        map.put(0,1);
        int pre = 0;
        for(int i = 0 ; i < nums.length ; i++){
            pre += nums[i];
            if(map.containsKey(pre - k)){
                count += map.get(pre - k);
            }
            map.put(pre , map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

581. 最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

示例 1：

1
2
3
输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums.length <= 104
  • -105 <= nums[i] <= 105

进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？

方法一：排序对照

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        int[] sotrNum = Arrays.copyOfRange(nums , 0 , len);
        Arrays.sort(sotrNum);
        int left = 0 , right = len - 1;
        while(left < len && nums[left] == sotrNum[left])left++;
        if(left == len)return 0;
        while(right >= 0 && nums[right] == sotrNum[right])right--;
        return right - left + 1;
    }
}

方法二：寻找需要排序数组的边界

从左到右寻找right，只要满足左边最大值大于当前，就说明，当前这个点要排序，是右边界，然后往后继续找。

从右往左找left，如果当前值小与之前的最小值，说明这个点要排序，是左边界，继续往后找，并且不能更换最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        int maxNum = Integer.MIN_VALUE , right = -1;
        int minNum = Integer.MAX_VALUE , left = len-1;
        for(int i = 0 ; i < len ; i++){
            if(maxNum > nums[i]){
                right = i;
            }else{
                maxNum = nums[i];
            }
            if(minNum < nums[len - i - 1]){
                left = len - i - 1;
            }else{
                minNum = nums[len - i - 1];
            }
        }
        return right == -1 ? 0 : right - left + 1;
    }
}

617. 合并二叉树

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

img

1
2
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：

1
2
输入：root1 = [1], root2 = [1,2]
输出：[2,2]

提示：

  • 两棵树中的节点数目在范围 [0, 2000] 内
  • -104 <= Node.val <= 104

方法一：深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null)return root2;
        if(root2 == null)return root1;

        TreeNode res = new TreeNode(root1.val += root2.val);
        res.left = mergeTrees(root1.left , root2.left);
        res.right = mergeTrees(root1.right , root2.right);
        return res;
    }
}

621. 任务调度器

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的 最短时间 。

示例 1：

1
2
3
4
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。

示例 2：

1
2
3
4
5
6
7
8
输入：tasks = ["A","A","A","B","B","B"], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
诸如此类

示例 3：

1
2
3
4
输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
输出：16
解释：一种可能的解决方案是：
     A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A

提示：

  • 1 <= task.length <= 104
  • tasks[i] 是大写英文字母
  • n 的取值范围为 [0, 100]

方法一：贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int leastInterval(char[] tasks, int n) {
       //统计每个任务出现的次数，找到出现次数最多的任务
       int[] hash = new int[26];
       for(int i = 0; i < tasks.length; ++i) {
           hash[tasks[i] - 'A'] += 1;
       }
       Arrays.sort(hash);
       //因为相同元素必须有n个冷却时间，假设A出现3次，n = 2，任务要执行完，至少形成AXX AXX A序列（X看作预占位置）
       //该序列长度为
       int minLen = (n+1) *  (hash[25] - 1) + 1;

       //此时为了尽量利用X所预占的空间（贪心）使得整个执行序列长度尽量小，将剩余任务往X预占的空间插入
       //剩余的任务次数有两种情况：
       //1.与A出现次数相同，比如B任务最优插入结果是ABX ABX AB，中间还剩两个空位，当前序列长度+1
       //2.比A出现次数少，若还有X，则按序插入X位置，比如C出现两次，形成ABC ABC AB的序列
       //直到X预占位置还没插满，剩余元素逐个放入X位置就满足冷却时间至少为n
       for(int i = 24; i >= 0; --i){
           if(hash[i] == hash[25]) ++ minLen;
       }
       //当所有X预占的位置插满了怎么办？
       //在任意插满区间（这里是ABC）后面按序插入剩余元素，比如ABCD ABCD发现D之间距离至少为n+1，肯定满足冷却条件
       //因此，当X预占位置能插满时，最短序列长度就是task.length，不能插满则取最少预占序列长度
       return Math.max(minLen, tasks.length);
   }

647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

1
2
3
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

1
2
3
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

  • 1 <= s.length <= 1000
  • s 由小写英文字母组成

方法一：中心扩展法

注意，选择中心点，并不是len个，比如a a ，我们可以选择a a中间的作为中心点。这样的点有len - 1个，所以一共是2*len-1个

我们指定left , right 分别代表两个初始位置，如果为奇数长度，正好指向中心，偶数，就指向左右。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int countSubstrings(String s) {
        int len = s.length();
        int res = 0;
        for(int center  = 0 ; center  < len * 2 - 1 ; center ++){
            int left = center /2;
            int right = left + center % 2;
            while(left >= 0 && right < len && s.charAt(left) == s.charAt(right)){
                res++;
                left--;
                right++;
            }
        }
        return res;
    }
}

方法二：Manacher算法

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
class Solution {
    public int countSubstrings(String s) {
        int len = s.length();
        StringBuffer buffer = new StringBuffer("$#");
        for(int i = 0 ; i < len ; i++){
            buffer.append(s.charAt(i));
            buffer.append("#");
        }
        len = buffer.length();
        buffer.append("!");
        int[] f = new int[len];

        int iMax = 0 , rMax = 0, ans = 0;
        for(int i = 1 ; i < len ; i++){
            f[i] = i < rMax ? Math.min(rMax - i + 1 , f[2 * iMax - i]) : 1;
            while(buffer.charAt(i + f[i]) == buffer.charAt(i - f[i]))f[i]++;

            if(i + f[i] - 1 > rMax){
                iMax = i;
                rMax = i + f[i] - 1;
            }
            ans += f[i] / 2;
        }
        return ans;
    }
}

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1
2
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

1
2
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

1
2
输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100

方法一：暴力，在每一个当天温度往后找，没有就是0

方法二：单调栈

要是知道每一天后边最大温度，我们只要维护一个单调栈，把每天的下标加进去，并且让这个栈从顶到底是增大的，这样我们遇到大于栈顶温度的时候，就知道栈顶下标的后边最大温度的下标，相减获得天数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[len];
        for(int i = 0 ; i < len  ; i++){
            while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
                int index = stack.pop();
                res[index] = i - index;
            }
            stack.push(i);
        }
        return res;
    }
}