剑指 Offer II 002. 二进制加法

难度：简单

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = “11”, b = “10”
输出: “101”

示例 2:

输入: a = “1010”, b = “1011”
输出: “10101”

提示：每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 “0” ，就都不含前导零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//将两个字符串的末位分别相加，如有进位用temp标记，将结果插入一个新的字符串的首位类似于进栈
//注意，字符char-'0'的使用，若char为整型的字符形式，该计算结果得到其int值，如'6'-'0'=6(int)
//另有一种算法，将两字符串每位相加得到新字符串，再进行逐字符进位计算
class Solution {
    public String addBinary(String a, String b) {
        int longa = a.length() - 1 , longb = b.length()-1 , temp = 0;
        StringBuilder sb = new StringBuilder();
        while(longa>=0||longb>=0||temp!=0){
            int num1 = longa>=0?a.charAt(longa)-'0':0;
            int num2 = longb>=0?b.charAt(longb)-'0':0;
            int add = num1 + num2 + temp;
            temp = add/2;
            sb.insert(0,add%2);
            longa--;
            longb--;
        }
        return sb.toString();
    }
}

剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

难度简单114收藏分享切换为英文接收动态反馈

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

示例 1:

输入: n = 2
输出: [0,1,1]
解释:
0 —> 0
1 —> 1
2 —> 10

示例 2:

输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 —> 0
1 —> 1
2 —> 10
3 —> 11
4 —> 100
5 —> 101

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

//奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。
//偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。
//dp[i] = dp[i/2] + i % 2
//通过位运算进一步优化：
//i / 2 可以通过 i >> 1 得到；
//i % 2 可以通过 i & 1 得到；
//&是按位与，对应位都为1时该位得1，否则得0。
class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n+1];
        for(int i=0;i<=n;i++){
            ans[i] = ans[i>>1]+(i&1);
        }
        return ans;
    }
}

剑指 Offer II 005. 单词长度的最大乘积

难度中等122收藏分享切换为英文接收动态反馈

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

示例 1:

输入: words = [“abcw”,”baz”,”foo”,”bar”,”fxyz”,”abcdef”]
输出: 16
解释: 这两个单词为 “abcw”, “fxyz”。它们不包含相同字符，且长度的乘积最大。

示例 2:

输入: words = [“a”,”ab”,”abc”,”d”,”cd”,”bcd”,”abcd”]
输出: 4
解释: 这两个单词为 “ab”, “cd”。

示例 3:

输入: words = [“a”,”aa”,”aaa”,”aaaa”]
输出: 0
解释: 不存在这样的两个单词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//将字符串中字符出现情况用二进制数表示，即字符a~z对应二进制数第0~25位，哪个字符出现就将二进制数对应位置1。这样的话对于不含相同字符的字符串，它们的二进制表示进行与运算结果就为0，否则结果就不为0，位运算能大大加快算法速度。
//本解法运用位运算和与或算法结合，如binary[i] |=(1<<(words[i].charAt(j)-'a'));
class Solution {
    public int maxProduct(String[] words) {
        int len = words.length,ans=0;
        int[] binary = new int[len];
        for(int i=0;i<len;i++){
            for(int j=0;j<words[i].length();j++){
                binary[i] |=(1<<(words[i].charAt(j)-'a'));
            }
        }

        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                if((binary[i]&binary[j])==0) ans = Math.max(ans,(words[i].length()*words[j].length()));
            }
        }
        return ans;
    }
}

剑指 Offer II 007. 数组中和为 0 的三个数

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,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
//经典的双指针算法，固定一个数字i，从i+1到n-1下标中找到j和k，使得nums[i]+nums[j]+nums[k]=0
//本题关键在于去重，遍历nums时要去除相同数字。
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length-1;
        for(int i = 0;i<n-1;i++){
            if(i>0&&nums[i]==nums[i-1]) continue; //去重
            int j = i+1,k = n;
            while(j < k){
                int nownum = nums[i] + nums[j] + nums[k];
                if(nownum == 0){
                    List<Integer> temp = new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(nums[j]);
                    temp.add(nums[k]);
                    ans.add(temp);
                    while(j<k&&nums[j+1]==nums[j]) j++;  //去重
                    j++;
                    while(j<k&&nums[k-1]==nums[k]) k--;
                    k--;
                }else if(nownum<0){
                    j++;
                }else if(nownum>0){
                    k--;
                }
            }
        }
        return ans;
    }
}

剑指 Offer II 008. 和大于等于 target 的最短子数组

难度中等96收藏分享切换为英文接收动态反馈

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

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

示例 3：

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

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 minSubArrayLen(int target, int[] nums) {
        //设置初始最小值
        int min=Integer.MAX_VALUE;
        //初始化数组和
        int sum=0;
        //定义两个变量i、j(类似于滑动窗口的感觉)
        for(int i=0,j=0;j<nums.length;j++){
            //扩大窗口
            sum+=nums[j];
            while(i<=j && sum>=target){
                //更新最小值
                min=Math.min(min,j-i+1);
                //缩小窗口
                sum-=nums[i++];
            }
        }
        //若所有数组和都小于target,则返回0，否则返回更新值
        return min==Integer.MAX_VALUE?0:min;
    }
}

剑指 Offer II 009. 乘积小于 K 的子数组

难度中等119收藏分享切换为英文接收动态反馈

给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。

示例 1:

输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

示例 2:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//滑动窗口，一开始用双指针循环遍历计算总是出错
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int Start = 0,End = 0,ans= 0,tmpMulti = 1;

        for(; End<nums.length; End++){
            tmpMulti *= nums[End];

            // 积>=k则移动Start, 其他处理相同
            while(Start <= End && tmpMulti >= k){
                tmpMulti /= nums[Start++];
            }

            ans += End - Start + 1;
        }

        return ans;
    }
}

剑指 Offer II 010. 和为 k 的子数组

给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。

示例 1：

输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况

示例 2：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//一开始想用滑动窗口，但滑动窗口的数组中不能存在负数，因为这样将不能保证窗口移动时元素和是固定增大或减小的。因此改用前缀和
class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();  //分别代表前缀和，出现次数
        map.put(0,1);  //即不包含任何元素下的和为0的次数为1
        int pre = 0, ans = 0;
        for(int n : nums){
            pre += n;
            //getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值
            ans += map.getOrDefault(pre-k,0);  // 已知当前的前缀pre和之前某个前缀X，且要求pre-X=k，那么X=pre-k。X的出现次数就是此时以n结尾的子数组的合法次数
            map.put(pre,map.getOrDefault(pre,0)+1);
        }
        return ans;
    }
}

剑指 Offer II 011. 0 和 1 个数相同的子数组

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1：

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2：

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//前缀和+哈希表，难点在于理解题目和想到把0用-1表示
class Solution {
    public int findMaxLength(int[] nums) {
        int pre = 0,ans = 0;
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            //如果nums[i]==0，则改为0以求前缀和
            pre += nums[i]==0?-1:1;
            //前缀和为0，说明从第零位到当前位0和1数量相等，符合题目要求
            if(pre == 0) ans = i+1;
            //前缀和重复，那么这两个前缀和之间的数组一定是0，符合要求
            else if(map.containsKey(pre)) ans = Math.max(ans,i - map.get(pre));
            //前缀和未出现过，记录
            else map.put(pre,i);
        }
        return ans;
    }
}

剑指 Offer II 013. 二维子矩阵的和

给定一个二维矩阵 matrix，以下类型的多个请求：

  • 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

实现 NumMatrix 类：

  • NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化

  • int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。

  • 示例 1：

    img

输入:
[“NumMatrix”,”sumRegion”,”sumRegion”,”sumRegion”][[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

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
//通过右下角记录一个子矩阵的和
//pre[i][j]记录的是（0，0）到（i，j）的子矩阵的元素和
//为方便计算，pre的第一行和第一列初始化为0
class NumMatrix {

    private int[][] pre;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length,n = matrix[0].length;
        pre = new int[m+1][n+1];
        //记录每行元素的前缀和
        for(int i =0;i<m;i++){
            int count = 0;
            for(int j =0;j<n;j++){
                count += matrix[i][j];
                //上一行对应子矩阵和加上本行元素和
                pre[i+1][j+1] = pre[i][j+1] + count;
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return pre[row2+1][col2+1] - pre[row2+1][col1] - pre[row1][col2+1] + pre[row1][col1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

juzhen.png

image.png

这破题想了半天。

剑指 Offer II 014. 字符串中的变位词

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

示例 1：

输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).

示例 2：

输入: s1= “ab” s2 = “eidboaoo”
输出: False

这题关键是看清题意，只要是s2中有一个子串，跟s1的长度和字符相等就行了，且无关顺序。

我想复杂了，以为s1中有一部分是s2的字串也行，又想了半天。。。

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 checkInclusion(String s1, String s2) {
        //只需要记录26个英文字母
        int[] arr1 = new int[26];
        int[] arr2 = new int[26];
        //s1>s1，显然无解
        if(s1.length()>s2.length()) return false;
        //把每个字符转为数字记录，只要s1和s2的字符种类和数量相等，就符合题目要求了
        for(int i =0;i<s1.length();i++){
            arr1[s1.charAt(i)-'a']++;
            arr2[s2.charAt(i)-'a']++;
        }
        if(Arrays.equals(arr1,arr2)) return true;
        //滑动窗口，右侧加入，左侧移除，窗口大小始终不变（s1长度）
        for(int i=s1.length();i<s2.length();i++){
            arr2[s2.charAt(i)-'a']++;
            arr2[s2.charAt(i-s1.length())-'a']--;
            if(Arrays.equals(arr1,arr2)){
                return true;
            }
        }
        return false;
    }
}

剑指 Offer II 015. 字符串中的所有变位词

难度 中等

给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

变位词 指字母相同，但排列不同的字符串。

示例 1：

输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的变位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的变位词。

示例 2：

输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的变位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的变位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的变位词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//这题就是把上一题的只求一个解变为求多个解，可以说一模一样了
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] s1 = new int[26];
        int[] p1 = new int[26];//子字符串
        List<Integer> ans = new ArrayList<Integer>();
        if(s.length()<p.length()) return ans; //特例
        for(int i=0;i<p.length();i++){  //初始化两个数组，设置固定窗口大小
            s1[s.charAt(i)-'a']++;
            p1[p.charAt(i)-'a']++;
        }
        if(Arrays.equals(s1,p1)) ans.add(0);
        for(int i=p.length();i<s.length();i++){
            s1[s.charAt(i-p.length())-'a']--;
            s1[s.charAt(i)-'a']++;
            if(Arrays.equals(s1,p1)) ans.add(i-p.length()+1);  //窗口滑动，符合条件的获取索引
        }
        return ans;
    }
}

剑指 Offer 59 - I. 滑动窗口的最大值

难度 困难

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: 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

提示：

你可以假设 k 总是有效的，在输入数组 不为空 的情况下，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
25
26
27
28
29
30
31
//没用过java队列Queue，查了半天没找到读取队尾元素的方法，感觉真不如用List
//难点在于元素入队和出队时的判断以及整个流程的理解
//设定双端队列 deque 实现非严格递减的单调队列，队首就是当前滑窗内的最大元素
//1 - 当出滑窗的元素恰好是单调队列的队头元素，一起出栈
//2 - 让所有小于新加入元素的单调队列元素出队，新元素入队
//3 - 形成滑窗后，取队首元素加入结果 res
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayList<Integer> sbqueue = new ArrayList<Integer>();
        int[] ans = new int[nums.length-k+1];
        //因为直接进入循环，low<0时，只初始化sbabqueue，不进行结果写入。
        int low = 1-k, high=0, i=0;
        while(high<nums.length){
            //判断滑窗的low端是否是最大的元素，是的话一起出队，不是的话不用管。
            if(low>=1&&nums[low-1]==sbqueue.get(0)) sbqueue.remove(0);
            while(!(sbqueue.size()==0)&&sbqueue.get(0)<nums[high]) sbqueue.remove(0);//小于nums[high]的元素出队
            while(!(sbqueue.size()==0)&&sbqueue.get(sbqueue.size()-1)<nums[high]) //小于nums[high]的元素出队sbqueue.remove(sbqueue.size()-1);
            //此时的high指针进队
            sbqueue.add(nums[high]);
            //输出要求int[]，所以要多维护一个i变量
            if(low>=0) {
                ans[i]=sbqueue.get(0);
                i++;
            };
            //窗口移动
            low++;
            high++;
        }
        return ans;
    }
}

剑指 Offer II 016. 不含重复字符的最长子字符串

难度 中等

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

输入: s = “”
输出: 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//s 由英文字母、数字、符号和空格组成，所以不能用转数字的方法了
//方法还是滑动窗口，用List<Character>直接把难度降低一个档次
//需要注意的是循环方式，窗口滑动时机
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left=0,right=0,max=0;
        List<Character> list=new ArrayList<Character>();
        
        for(;right<s.length();right++){
            //出现重复字符，从左边开始一直删，直到把跟下一个字符重复的删掉
            while(left<right&&list.contains(s.charAt(right))){
                list.remove(0);
                left++;
            }
            list.add(s.charAt(right));
            max=max>(right-left)?max:right-left+1;
        }
        
        return max;
    }
}

剑指 Offer II 017. 含有所有字符的最短字符串

难度困难

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。

如果 s 中存在多个符合条件的子字符串，返回任意一个。

注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”
解释：最短子字符串 “BANC” 包含了字符串 t 的所有字符 ‘A’、’B’、’C’

示例 2：

输入：s = “a”, t = “a”
输出：”a”

示例 3：

输入：s = “a”, t = “aa”
输出：””
解释：t 中两个字符 ‘a’ 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

提示：

  • 1 <= s.length, t.length <= 105
  • s 和 t 由英文字母组成
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
class Solution {
    public String minWindow(String s, String t) {
        //这个哈希表用于保存遍历S过程中,滑动窗口内的有效值
        HashMap<Character,Integer> window = new HashMap<>();
        //这个哈希表用于保存t内所有字符，及其个数
        HashMap<Character,Integer> need = new HashMap<>();
        int count=0,left=0,right=0,anslen=Integer.MAX_VALUE;
        String ans = null;
        //初始化map，window未开始使用，只录入有效字符，不计次数
        for(int i = 0;i<t.length();i++){
            window.put(t.charAt(i),0);
            need.put(t.charAt(i),need.getOrDefault(t.charAt(i),0)+1);
        }
        //开始遍历
        for(;right<s.length();right++){
            //如果窗口右边界是有效字符
            if(window.containsKey(s.charAt(right))){
                //录入map
                window.put(s.charAt(right),window.get(s.charAt(right))+1);
                //如果新加入的字符数目小于等于t中那个字符数量,更新count值
                if(window.get(s.charAt(right))<=need.get(s.charAt(right))) count++;
            }
            //左侧边界缩小
            while(left<right){
                //如果左边界字符不是我们要找的字符直接移动
                if(!window.containsKey(s.charAt(left))){
                    left++;
                }
                //如过是我们要找的字符，但是窗口内已经包含多余的了，就可以放掉最左边的那个
                else if(window.get(s.charAt(left))>need.get(s.charAt(left))){
                    window.put(s.charAt(left),window.get(s.charAt(left))-1);
                    left++;
                }else{
                    break;
                }
            }
            //如果count是t的字符长度，并且窗口长度小于上一次长度就记录下来
            if(count==t.length()&&anslen>right-left+1){
                ans = s.substring(left,right+1);
                anslen = right-left+1;
            }
        }
        return ans==null?"":ans;
    }
}

剑指 Offer II 018. 有效的回文

难度 简单

给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。

本题中，将空字符串定义为有效的 回文串 。

示例 1:

输入: s = “A man, a plan, a canal: Panama”
输出: true
解释：”amanaplanacanalpanama” 是回文串

示例 2:

输入: s = “race a car”
输出: false
解释：”raceacar” 不是回文串

提示：

  • 1 <= s.length <= 2 * 105
  • 字符串 s 由 ASCII 字符组成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//一开始就想用双指针，但是想到有大小写差异和字符掺杂在里面
//看了一些题解知道了toLowerCase()和Character.isLetterOrDigit()两个降维打击的函数。。
class Solution {
    public boolean isPalindrome(String s) {
        int left=0,right=s.length()-1;
        //大写全变成小写
        s = s.toLowerCase();
        while(left<right){
            //Character.isLetterOrDigit()判断是否是字母数字
            while(left<right&&!Character.isLetterOrDigit(s.charAt(left))){
                left++;
            }
            while(left<right&&!Character.isLetterOrDigit(s.charAt(right))){
                right--;
            //如果不一样，直接false
            if(s.charAt(left)!=s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

剑指 Offer II 019. 最多删除一个字符得到回文

难度简单

给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

示例 1:

输入: s = “aba”
输出: true

示例 2:

输入: s = “abca”
输出: true
解释: 可以删除 “c” 字符 或者 “b” 字符

示例 3:

输入: s = “abc”
输出: false

提示:

  • 1 <= s.length <= 105

  • s 由小写英文字母组成

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 validPalindrome(String s) {
        int left=0,right=s.length()-1;
        while(left<right&&s.charAt(left)==s.charAt(right)){
            left++;
            right--;
        }
        return valid(left+1,right,s)||valid(left,right-1,s);
    }
    public boolean valid(int l,int r,String s) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

剑指 Offer II 020. 回文子字符串的个数

难度 中等

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”

示例 2：

输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示：

  • 1 <= s.length <= 1000
  • s 由小写英文字母组成
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
    //真tm妙
/*
        中心扩散
        遍历字符串，取每一个字符为一个回文子串的中心
        按照回文串的要求向两边扩散，统计回文串个数
        上述情况 只有当回文子串的中心只有一个字符时可行
        所以还需考虑回文子串中心有两个字符时的情况
        可以在遍历的时候，取每个字符计数的同时
        再取该字符与下一个字符同时作为中心，向两边扩散统计回文串个数
    */
class Solution {
    public int countSubstrings(String s) {
        int ans = 0;
        for(int i=0;i<s.length();i++){
            ans+= count(i,i,s);
            ans+= count(i,i+1,s);
        }
        return ans;
    }
    
    public int count(int i,int j,String s){
        int cnt = 0;
        while(i>=0&&j<s.length()){
            if(s.charAt(i)==s.charAt(j)){
                cnt++;
                i--;
                j++;
            }else{
                break;
            }
        }
        return cnt;
    }
}

剑指 Offer II 021. 删除链表的倒数第 n 个结点

难度中等69收藏分享切换为英文接收动态反馈

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

示例 1：

img

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

示例 2：

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

示例 3：

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

提示：

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

进阶：能尝试使用一趟扫描实现吗？

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.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

//让q指针先走n步,然后p,q指针同时走,当q指针走到表尾时,p指针指向的就是倒数第n个元素
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode *p=head,*q=head,*o=head;
    for(int i=0;i<n;i++){
        p=p->next;
    }
    while(p!=NULL){
        p=p->next;
        o=q;
        q=q->next;
    }
    //应对只有一个节点的情况
    if(q==head){
        head = head->next;
        return head;
    }
    //删除节点
    o->next=q->next;
    return head;
}

剑指 Offer II 022. 链表中环的入口节点

难度中等

给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

示例 1：

img

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

示例 2：

img

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

示例 3：

img

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

提示：

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
//也可以直接用哈希表遍历，判断是否有重复，contains解决。但是快慢指针第一次见，学习一下
//这题就难在理解数学模型
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head,slow=head;
        if(head == null || head.next == null) return null;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow) break;
        }
        if(fast!=slow) return null;
        slow = head;
        while(slow!=fast){
            slow=slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

题目【判断链表是否有环】中使用到了快慢指针法，但只能保证 slow 和 fast 指针在环中的某一个节点相遇，那么如何通过快慢指针找到入口节点呢？

假设 fast 指针和 slow 指针在 Z 点相遇，此时 fast 指针走过的距离为 a+b+n(b+c)(其实 n 为快指针在环中走的圈数)，slow 指针走过的距离为 a+b，因为 fast 指针速度为 slow 指针速度的两倍，所以 a+b+n(b+c) = 2(a+b)，可得出 a=(n-1)(b+c)+c，其中 (b+c) 为链表环形部分的长度

上式说明什么？如果 fast 和 slow 相遇时，我们让 slow 回到起点 X 处，再让 slow 和 fast 以相同的速度(每次走一步)往后移动，当 slow 向后移动 a 步时，fast 走了 (n-1) 圈外加向后移了 c 步，所以 slow 和 fast 会相遇在 Y 点(环形入口点)
原文链接：https://blog.csdn.net/oneby1314/article/details/108471577

剑指 Offer II 024. 反转链表

难度简单

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000
  1. 链表为空，返回头节点
  2. 定义两个结点 pre 为 null ，cur指向头节点
  3. 遍历链表时，定义临时结点存放 cur 的下一结点，同时让 cur 指向 pre
  4. 因为要向后遍历，pre 向后移到 cur 的位置，cur 移到刚刚定义的临时结点位置 （达到链表反转效果） …（以此循环）
  5. 最后因 cur == null 跳出循环， pre 在cur 的前一位，所以返回 pre 即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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==nul||head.next==null) return head;
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode temp = cur.next;  //临时节点，记录cur.next方便第四步衔接
            cur.next = pre;  //把当前节点连同数据接到pre前面（倒置）
            pre = cur;  //pre吸收cur
            cur = temp;
        }
        return pre;
    }

剑指 Offer II 025. 链表中的两数相加

难度中等

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

示例1：

img

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3：

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

提示：

  • 链表的长度范围为[1, 100]
  • 0 <= node.val <= 9
  • 输入数据保证链表代表的数字无前导 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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> q1 = new ArrayDeque<>();
        Deque<Integer> q2 = new ArrayDeque<>();
        ListNode s1=l1,s2=l2,ans=null;
        while(s1!=null){
            q1.push(s1.val);
            s1=s1.next;
        }
        while(s2!=null){
            q2.push(s2.val);
            s2=s2.next;
        }
        int carry=0;  //进位标记
        while(!q1.isEmpty()||!q2.isEmpty()||carry!=0){
            int num1 = q1.isEmpty()?0:q1.pop();
            int num2 = q2.isEmpty()?0:q2.pop();
            int add = num1+num2+carry;
            carry = add/10;
            int cur = add%10;
            ListNode temp = new ListNode(cur);
            temp.next = ans;
            ans=temp;  //把新数字加到链表第一位
        }
        return ans;
    }
}

剑指 Offer II 026. 重排链表

难度中等90收藏分享切换为英文接收动态反馈

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：

1
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

img

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

示例 2:

img

输入: head = [1,2,3,4,5]
输出: [1,5,2,4,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
/**
 * 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 void reorderList(ListNode head) {
        if(head==null)return;
        ListNode f = head, s=head;
        //快慢指针寻找链表中点
        while(f.next!=null&&f.next.next!=null){
            s=s.next;
            f=f.next.next;
        }
        //反转后半段链表（f为反转后后半段头指针)
        ListNode t =s.next;
        f= null;
        while(t!=null){//这段很重要
            t=s.next;
            s.next = f;
            f = s;
            s = t;
        }
        s=head;
        //拼接前后两端链表
        while(s!=null){ //这段太妙了
            t = s.next;
            s.next = f;
            s = f;
            f = t;
        }
    }
}

剑指 Offer II 027. 回文链表

难度简单96收藏分享切换为英文接收动态反馈

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：

img

输入: head = [1,2,3,3,2,1]
输出: true

示例 2：

img

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

//先快慢指针找到中间节点；
//原地反转后半部分链表；
//依次比较前半部分链表与反转后的后半部分链表；
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null) return true;
        //快慢指针寻找中点
        ListNode s=head,t=head;
        while(t.next!=null&&t.next.next!=null){
            s=s.next;
            t=t.next.next;
        }

        //反转后半部分链表
        t=s.next;
        ListNode pre = null;
        while(t!=null){
            s=t.next;
            t.next = pre;
            pre = t;
            t=s;
        }

        //两段链表逐位比较
        s=head;
        while(pre!=null){
            if(pre.val!=s.val){
                return false;
            }
            pre=pre.next;
            s=s.next;
        }
        return true;
    }
}

剑指 Offer II 028. 展平多级双向链表

难度中等61收藏分享切换为英文接收动态反馈

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。

示例 1：

输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：

输入的多级列表如下图所示：

扁平化后的链表如下图：

示例 2：

输入：head = [1,2,null,3]
输出：[1,3,2]
解释：

输入的多级列表如下图所示：

1—-2—-NULL
|
3—-NULL

示例 3：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

class Solution {
    public Node flatten(Node head) {
        dfs(head);
        return head;
    }

    public Node dfs(Node head){
        Node last = null;
        Node cur = head;
        while(cur!=null){
            Node next = cur.next;
            if(cur.child!=null){
                //有child，深度优先遍历
                Node childLast=dfs(cur.child);
                next = cur.next;
                cur.next = cur.child;
                cur.child.prev=cur;
                //next有地址时，把child前后两端黏到中间去
                if(next!=null){
                    childLast.next = next;
                    next.prev = childLast;
                }
                cur.child = null;
                last = childLast;
            }else{
                //没有child，直接记录最后一位
                last = cur;
            }

            cur = next;
        }
        return last;
    }
}

剑指 Offer II 029. 排序的循环链表

难度中等

给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。

给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。

如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

示例 1：

img

输入：head = [3,4,1], insertVal = 2
输出：[3,4,1,2]
解释：在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。

示例 2：

输入：head = [], insertVal = 1
输出：[1]
解释：列表为空（给定的节点是 null），创建一个循环有序列表并返回这个节点。

示例 3：

输入：head = [1], insertVal = 0
输出：[1,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
53
54
55
/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;

    public Node() {}

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

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

class Solution {
    public Node insert(Node head, int insertVal) {
        Node cur = null;
        Node next = null;
        Node rhead = null;
        //处理head为空的情况
        if(head == null){
            head = new Node(insertVal);
            head.next = head;
            return head;
        }

        //循环找到最小的节点（单调断点），即真头节点
        cur = head;
        next = head.next;
        while(cur.val <= next.val){
            cur = cur.next;
            next = next.next;
            if(cur == head) break;
        }
        rhead = next;

        //从断点开始遍历，找到适合插入的位置
        while(next.val<insertVal){
            cur = next;
            next = next.next;
            if(next == rhead) break;
        }

        //插入节点
        cur.next = new Node(insertVal);
        cur = cur.next;
        cur.next = next;
        return head;
    }
}

剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

难度中等60收藏分享切换为英文接收动态反馈

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构：

  • insert(val)：当元素 val 不存在时返回 true ，并向集合中插入该项，否则返回 false 。
  • remove(val)：当元素 val 存在时返回 true ，并从集合中移除该项，否则返回 false 。
  • getRandom：随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。

示例 :

输入: inputs = [“RandomizedSet”, “insert”, “remove”, “insert”, “getRandom”, “remove”, “insert”, “getRandom”][[], [1], [2], [2], [], [1], [2], []]
输出: [null, true, false, true, 2, true, false, 2]
解释:
RandomizedSet randomSet = new RandomizedSet(); // 初始化一个空的集合
randomSet.insert(1); // 向集合中插入 1 ， 返回 true 表示 1 被成功地插入

randomSet.remove(2); // 返回 false，表示集合中不存在 2

randomSet.insert(2); // 向集合中插入 2 返回 true ，集合现在包含 [1,2]

randomSet.getRandom(); // getRandom 应随机返回 1 或 2

randomSet.remove(1); // 从集合中移除 1 返回 true 。集合现在包含 [2]

randomSet.insert(2); // 2 已在集合中，所以返回 false

randomSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 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
40
41
42
43
44
45
46
class RandomizedSet {

    Map<Integer,Integer> map;
    List<Integer> arr;
    int size;
    static Random rd = new Random();
    /** Initialize your data structure here. */
    public RandomizedSet() {
        map = new HashMap<>();
        arr = new ArrayList<>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(map.containsKey(val)) return false;
        arr.add(val);
        map.put(val,size++);
        return true;
    }
    
    //当需要删除元素时，利用map获取元素的下标
    //然后将最后一个元素覆盖该下标元素，并删除最后一个元素
    public boolean remove(int val) {
        if(!map.containsKey(val))return false;
        int index = map.get(val);
        int lastnum = arr.get(--size);
        arr.set(index,lastnum);
        map.put(lastnum,index);
        map.remove(val);
        arr.remove(size);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        return arr.get(rd.nextInt(size));
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

剑指 Offer 35. 复杂链表的复制

难度 中等

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

img

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

  1. 复制一个新的节点在原有节点之后，如 1 -> 2 -> 3 -> null 复制完就是 1 -> 1 -> 2 -> 2 -> 3 - > 3 -> null
  2. 从头开始遍历链表，通过 cur.next.random = cur.random.next 可以将复制节点的随机指针串起来，当然需要判断 cur.random 是否存在
  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
40
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        for(Node node = head;node!=null;node = node.next.next){
            Node copy = new Node(node.val);
            copy.next = node.next;
            node.next = copy;
        }

        //node.next.random是被复制的node的random，node.random.next是node.random被复制的那份数据
        for(Node node = head;node!=null;node = node.next.next){
            if(node.random!=null){
                node.next.random = node.random.next;
            }
        }

        //分离拷贝节点和原节点，变成1->2->3和1'->2'->3'两个链表，后者就是答案
        Node ans = head.next;
        for(Node node = head,temp = null;node != null&&node.next != null;){
            temp = node.next;
            node.next = node.next.next;
            node = temp;
        }

        return ans;
    }
}

406. 根据身高重建队列

代码随想录 (programmercarl.com)

难度中等

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

输入：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：

输入：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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        int len = people.length;
        // int[][] que = new int[len][2];

        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });

        LinkedList<int[]> que = new LinkedList<>();

        for (int[] p : people) {
            //p[1]及插入位置，在那个位置插入p数组，一定是同数据的第一个。
            //因为已经按大小排好序，所以在这个位置插入不会对已有排序产生影响。
            que.add(p[1],p);
        }

        return que.toArray(new int[people.length][]);
    }
}

450. 删除二叉搜索树中的节点

难度 中等

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

  1. 首先找到需要删除的节点；
  2. 如果找到了，删除它。

示例 1:

img

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0
输出: []

代码随想录 (programmercarl.com)

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
/**
 * 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 deleteNode(TreeNode root, int key) {
        root = delete(root,key);
        return root;
    }

    public TreeNode delete(TreeNode node,int val){
        if(node==null) return null;
        //这两个条件判断，直接找到符合条件的节点，即node.val==val
        if(node.val>val){
            node.left = delete(node.left,val);
        }else if(node.val<val){
            node.right = delete(node.right,val);
        }else{
            //找到节点后，判断节点是否有子节点，如果只有一个，直接把另一条连上去完事
            if(node.right==null){
                return node.left;
            }
            if(node.left==null){
                return node.right;
            }
            //如果有两个子节点，则找到当前节点右节点的最左边的节点，替换当前节点，再把那个接待你删除就好了
            TreeNode temp = node.right;
            while(temp.left!=null){
                temp = temp.left;
            }
            node.val = temp.val;
            node.right = delete(node.right,node.val);
        }
        return node;
    }
}

115. 不同的子序列

难度 困难

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

输入：s = “rabbbit”, t = “rabbit”
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

输入：s = “babgbag”, t = “bag”
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 “bag” 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag

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

为啥状态方程是： s[i] == t[j] 时 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

s[i] != t[j] 时 dp[i][j] = dp[i-1][j]

先看s[i] == t[j] 时，以s = "rara" t = "ra" 为例，当i = 3, j = 1时，s[i] == t[j]。

此时分为2种情况，s串用最后一位的a + 不用最后一位的a。

如果用s串最后一位的a,那么t串最后一位的a也被消耗掉，此时的子序列其实=dp[i-1][j-1]

如果不用s串最后一位的a，那就得看"rar"里面是否有"ra"子序列的了，就是dp[i-1][j]

所以 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

再看s[i] != t[j] 比如 s = "rarb" t = "ra" 还是当i = 3, j = 1时，s[i] != t[j]

此时显然最后的b想用也用不上啊。所以只能指望前面的"rar"里面是否有能匹配"ra"的

所以此时dp[i][j] = dp[i-1][j]
*/

class Solution {
    public int numDistinct(String s, String t) {
        int lens = s.length(),lent = t.length();
        int[][] dp = new int[lens+1][lent+1];
        for(int i = 0;i<=lens;i++){
            dp[i][0] = 1;
        }
        for(int i = 1; i <=lens;i++){
            for(int j = 1;j <= lent;j++){
                if(s.charAt(i-1)==t.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[lens][lent];
    }
}