第1天 整数

[不会] 剑指 Offer II 001. 整数除法

剑指 Offer II 001. 整数除法
方法一：注意溢出，一个一个减。

class Solution {
    public int divide(int a, int b) {
        int ans = 0;
        int flag = 0;
        if (a == Integer.MIN_VALUE && b == -1)
            return Integer.MAX_VALUE;
        if(a>0) {
            flag += 1;
            a = -a;
        }
        if(b>0) {
            flag += 1;
            b = -b;
        }
        while(a<=b){
            a -= b;
            ans++;
        }
        return flag==1?-ans:ans;
    }
}

方法二：位运算，类似快速幂，一半一半减。

class Solution {
    public int divide(int a, int b) {
        int ans = 0;
        int flag = 0;
        if (a == Integer.MIN_VALUE && b == -1)
            return Integer.MAX_VALUE;
        if(a>0) {
            flag += 1;
            a = -a;
        }
        if(b>0) {
            flag += 1;
            b = -b;
        }
        while(a<=b){
            int base = b;
            int count = 1;
            // 一次最多减不到一半，不然乘2就越界了
            while(a-base<=base){
                base <<= 1;
                count <<= 1;
            }
            a -= base;
            ans += count;
        }
        return flag==1?-ans:ans;
    }
}

[不会] 剑指 Offer II 002. 二进制加法

剑指 Offer II 002. 二进制加法
方法一：数字电路位运算，注意~(AB) != ~A ~B，a非b非 等于 (a 或 b)非

a	b	c	out	up
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

out = ~a~bc + ~a~cb + ~b~ca + abc
up = ~abc + ~bac + ~cab + abc

class Solution {
    /**
    out = ~(a|b)c + ~(a|c)b + ~(b|c)a + abc
    up = ~abc + ~bac + ~cab + abc
     */
    public String addBinary(String a, String b) {
        int aLen = a.length(), bLen = b.length();
        int aIndex = aLen-1, bIndex = bLen-1;
        int ci = 0, out = 0;
        StringBuilder sb = new StringBuilder();
        while(aIndex>=0 || bIndex>=0){ // 不是&&
            int ai = aIndex>=0 ? a.charAt(aIndex--)-'0' : 0, 
                bi = bIndex>=0 ? b.charAt(bIndex--)-'0' : 0;
            out = ~ai&~bi&ci | ~ai&~ci&bi | ~ci&~bi&ai | ai&bi&ci;
            ci = ~ai&bi&ci | ai&~bi&ci | ai&bi&~ci | ai&bi&ci;
            sb.append(out);
        }
        if(ci==1) sb.append(ci);
        return sb.reverse().toString();
    }
}

方法二：直接使用加法。

out = sum>=2 ? sum-2 : sum;
ci = sum>=2 ? 1 : 0;

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

剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
线性时间 O(n) 内用一趟扫描，要求算法的空间复杂度为 O(n)
方法一：dfs，1从右往左一个一个移动，时间复杂度是n，空间复杂度也是n吧？

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n+1];
        dfs(n,1,1,ans);
        return ans;
    }

    void dfs(int n, int num, int count, int[] ans){
        if(num > n) return;
        ans[num] += count;
        dfs(n,num<<1|1, count+1,ans);
        dfs(n,num<<1|0, count,ans);
    }
}

方法二：如果是偶数，则左移一位还是偶数，1的个数一样100->10。如果是101则是->10+(101&1)。

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;
    }
}

第 2 天 整数

[M][不会] 剑指 Offer II 004. 只出现一次的数字

剑指 Offer II 004. 只出现一次的数字
线性时间复杂度，不使用额外空间
每位出现次数对3取于便可筛选。00->01->10->00。为了表示3，要用两位二进制，分为two和one。最终结果为one，因为只有一次是01，刚好只有01的one是1.

n	two	one	ntwo	none
0	0	0	0	0
0	0	1	0	1
0	1	0	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	0	0

#这样最好，否则就要从two开始分，不好想，如果从n开始分不太好总结公式
one = ~n&~two&one | n&~two&~one
#这样发现不好合并
if n is 0:
	one = one
elif n is 1:
	if two is 0:
		one = ~one
	elif two is 1:
		one = one

计算完one 01->00->10->01（此时two没有变），two和one调换位置10->00->01->10和one的计算方法一样

class Solution {
    public int singleNumber(int[] nums) {
        // one = ~n&~two&one | n&~two&~one
        int one=0, two=0;
        for (int i:nums){
            one = ~i&~two&one | i&~two&~one;
            two = ~i&~one&two | i&~one&~two;
        }
        return one;
    }
}

[M][不会] 剑指 Offer II 005. 单词长度的最大乘积

剑指 Offer II 005. 单词长度的最大乘积
把字符串表示为数字，int有32位，包含26个字母（不计次数），第0位是a是否出现。。。则abc为111，def为111000。

class Solution {
    public int maxProduct(String[] words) {
        int len = words.length;
        int[] nums = new int[len];
        for(int i=0;i<len;i++){
            int wlen = words[i].length();
            for(int j=0;j<wlen;j++){
                nums[i] |= 1<<(words[i].charAt(j)-'a');
            }
        }

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

剑指 Offer II 006. 排序数组中两个数字之和

剑指 Offer II 006. 排序数组中两个数字之和
方法一：经典twoSum，用map保存下target-nums[i]。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // <index, target-numbers[i]>
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        int len = numbers.length;
        int i=0;
        for(;i<len;i++){
            if(map.get(numbers[i])!=null){
                break;
            }
            map.put(target-numbers[i], i);
        }
        return new int[]{map.get(numbers[i]),i};
    }
}

方法二：twoSum是无序的，这里有序的用map效果不太好，直接双指针。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i=0,j=numbers.length-1;
        while(true){
            if(numbers[i]+numbers[j]>target) j--;
            else if(numbers[i]+numbers[j]<target) i++;
            else break;
        }
        return new int[]{i,j};
    }
}

第 3 天 数组

[M][不会] 剑指 Offer II 007. 数组中和为 0 的三个数

剑指 Offer II 007. 数组中和为 0 的三个数
双层twoSum无法解决去重问题，需要使用hashSet，所以直接排序后使用双指针。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        int len = nums.length;
        for(int i=0;i<len-2;i++){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int target = 0-nums[i];
            int j=i+1,k=len-1;
            while(j<k){
                if(nums[j]+nums[k]==target){
                    ans.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    // 无论如何都要j++，否则会一直卡到相加不等于target，但j也不前进
                    // 这部分也不能放到外边，否则不相等时左右指针都会移动
                    while(j<k){
                        j++;
                        if(nums[j]!=nums[j-1]){
                            break;
                        }
                    }
                    while(j<k){
                        k--;
                        if(nums[k]!=nums[k+1]){
                            break;
                        }
                    }
                }else if(nums[j]+nums[k]<target){
                    j++;
                }else{
                    k--;
                }
            }
        }
        return ans;
    }
}

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

剑指 Offer II 008. 和大于等于 target 的最短子数组
如果实现O(n)，尝试实现O(n log(n)) 时间复杂度
方法一：双指针/滑动窗口，右边移动，大了则移动左边。时间复杂度O(n)。
滑动窗口统一写法，动right循环left。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int len = nums.length;
        int left=0,right=0;
        int ans=Integer.MAX_VALUE,sum=0;
        while(right<len){
            sum += nums[right];
            while(left<=right && sum>=target){
                ans = Math.min(ans, right-left+1);
                sum -= nums[left];
                left++;
            }
            right++;
        }
        return ans==Integer.MAX_VALUE ? 0 : ans;
    }
}

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int len = nums.length;
        int left=0,right=0;
        int ans=Integer.MAX_VALUE,sum=0;
        while(right<len){
            // System.out.println(sum+" "+left+" "+right);
            while(right<len && sum<target){
                sum += nums[right];
                right++;
            }
            while(left<=right && sum>=target){
                sum -= nums[left];
                left++;
                ans = Math.min(ans, right-left+1);
            }
        }
        return ans==Integer.MAX_VALUE ? 0 : ans;
    }
}

方法二：二分查找+前缀和，从第i个开始，则target为target+sum[i-1]，因为sum[i]代表前i个，包括了i。

[M][不会] 剑指 Offer II 009. 乘积小于 K 的子数组

剑指 Offer II 009. 乘积小于 K 的子数组
滑动窗口：在刚由大变小时（移动left），表明刚刚的长度是最大的，进行计数，及n+…+1=(1+n)*n/2。
在一直小时，移动right，若整个数组乘起来都小，再计数。
当然也存在重复，例如1-3和2-5，在计算2-5时要减去2-3的内容。

最后发现，正常滑动窗口，每次新的增加就是长度。相当于是把上面的过程分成1+2+3.。。对于重复计算去除2-3，滑动到2时right在4，新增加的3即4、3-4,2-4.

相当于基于新增加的来新增，right添加了一个3，则对应的是3,、32、31，所以不会重复

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int len = nums.length;
        int left = 0, right = 0;
        int product=1, ans=0;
        while(right<len){
            product *= nums[right];
            while(left<=right && product>=k){
                product /= nums[left];
                left++;
            }
            ans += right-left+1;
            right++;
        }
        return ans;
    }
}

第 4 天 数组

[M][不会] 剑指 Offer II 010. 和为 k 的子数组

剑指 Offer II 010. 和为 k 的子数组
方法一：前缀和+双循环O(n^2)

class Solution {
    public int subarraySum(int[] nums, int k) {
        int len = nums.length, res=0;
        // preSum[i]不包含i，得第left到right则是preSum[right]-preSum[left]
        int[] preSum = new int[len+1];
        for(int i=1;i<=len;i++){
            preSum[i] = preSum[i-1]+nums[i-1];
        }
        for(int left=0;left<len;left++){
            for(int right=left+1;right<len+1;right++){
                if(preSum[right]-preSum[left]==k) res++;
            }
        }
        return res;
    }
}

方法二：因为只关注次数，不关注具体解。一次遍历，到第right个时，应该找从right-1开始出发往前，有多少个和为k-nums[right]的。但此时记录的是前缀和sum，因此不能这么看。

假设线段ABC，到当前C前缀和为AC=sum，假设B为目标点，则BC=k，AB就是sum-k，因此只需要找前缀和中有多少个sum-k。
有一种特殊情况,第一个数就sum==k此时搜索的是前缀和是0的有多少，但此时map中没东西，加的也是0，所以要先初始化一个(0,1)

class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        int sum=0, res=0;
        map.put(0,1);
        for(int num : nums){
            sum += num;
            res += map.getOrDefault(sum-k,0);
            map.put(sum, map.getOrDefault(sum,0)+1);
        }
        return res;
    }
}

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

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

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

可以把0当做-1，求最长的连续子数组和为0的长读，即k=0。前缀和为0则代表0和1个数相等。假设ABC，C为当前点和为sum，B点同上题则为sum-k。此时只用保存最左边的即可，因为要的是最长距离BC。

class Solution {
    public int findMaxLength(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
        int sum = 0, res = 0, num = 0;
        int len = nums.length;
        map.put(0,-1);
        for(int i=0;i<len;i++){
            num = nums[i];
            sum += num==1 ? 1 : -1;
            if(map.containsKey(sum)){
                // 0011则到index==3时又到0，对应第一个0的index为-1，则直接3-(-1)
                res = Math.max(res, i-map.get(sum));
            } else {
                map.put(sum, i);
            }
        }
        return res;
    }
}

剑指 Offer II 012. 左右两边子数组的和相等

剑指 Offer II 012. 左右两边子数组的和相等
简单前缀和，遍历到i用前缀和相减判断左右是否相等。

class Solution {
    public int pivotIndex(int[] nums) {
        int len = nums.length;
        int allSum = 0, res=-1, sum=0;
        for(int i=0;i<len;i++) allSum += nums[i];
        for(int i=0;i<len;i++){
            if(sum==allSum-sum-nums[i]){
                res = i;
                break;
            }
            sum += nums[i];
        }
        return res;
    }
}

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

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

class NumMatrix {

    // 二维前缀和，设四个角为
    //AB   preSum = OB+OC-OA+ABCD (ABCD共是一格)
    //CD   ans = OD-OB-OC+OA (ABCD各是一格)
    int[][] preSum;

    public NumMatrix(int[][] matrix) {
        int height = matrix.length;
        int width = matrix[0].length;
        // 外面加一层0，方便处理边上的sum
        preSum = new int[height+1][width+1];
        preSum[1][1] = matrix[0][0];
        for(int i=2;i<=height;i++) preSum[i][1] = preSum[i-1][1]+matrix[i-1][0];
        for(int i=2;i<=width;i++) preSum[1][i] = preSum[1][i-1]+matrix[0][i-1];
        for(int i=2;i<=height;i++){
            for(int j=2;j<=width;j++){
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1];
            }
        }
        // for(int i=0;i<=height;i++){
        //     for(int j=0;j<=width;j++){
        //         System.out.print(preSum[i][j]+" ");
        //     }
        //     System.out.println();
        // }
    }
    

    public int sumRegion(int row1, int col1, int row2, int col2) {
        //System.out.println(preSum[row2+1][col2+1]+" "+preSum[row1][col2]+" "+preSum[row2][col1]+" "+preSum[row1][col1]);
        // 注意这里的加1与否
        return preSum[row2+1][col2+1]-preSum[row1][col2+1]-preSum[row2+1][col1]+preSum[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);
 */

第 5 天 字符串

[M][不会] 剑指 Offer II 014. 字符串中的变位词

剑指 Offer II 014. 字符串中的变位词
利用定长滑动窗口，要考虑到s2子串和s1是等长的，只需要考虑这两个数组里的是否相等。
还可以在保证count 的值不为正的情况下，去考察是否存在一个区间，其长度恰好为 s1.len。用一个cnt保存方便写代码

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int targetLen = s1.length(), s2Len = s2.length(), left = 0, right = 0;
        if(targetLen>s2Len){
            return false;
        }
        //放到一个数组里好操作
        int[] count = new int[26];
        for(int i=0;i<targetLen;i++) count[s1.charAt(i)-'a']--;
        for(;right<s2Len;right++) {
            int x = s2.charAt(right)-'a';
            count[x]++;
            while(count[x]>0){
                count[s2.charAt(left)-'a']--;
                left++;
            }
            if(right-left+1==targetLen) return true;
        }
        return false;
    }
}

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

剑指 Offer II 015. 字符串中的所有变位词
同上一题。

class Solution {
    public List<Integer> findAnagrams(String p, String s) {
        int sLen = s.length(), pLen = p.length(), left = 0, right = 0;
        List<Integer> res = new ArrayList<>();
        int[] cnt = new int[26];
        for(int i=0;i<sLen;i++) cnt[s.charAt(i)-'a']--;
        for(;right<pLen;right++){
            int x = p.charAt(right)-'a';
            cnt[x]++;
            while(cnt[x]>0){
                cnt[p.charAt(left)-'a']--;
                left++;
            }
            if(right-left+1==sLen) res.add(left);
        }
        return res;
    }
}

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

剑指 Offer II 016. 不含重复字符的最长子字符串
方法一：同上题。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int len=s.length(), res=0, left=0, right=0;
        for(;right<len;right++){
            char c = s.charAt(right);
            map.put(c, map.getOrDefault(c,0)+1);
            while(map.get(c)>1){
                map.put(s.charAt(left), map.get(s.charAt(left))-1);
                left++;
            }
            res = Math.max(res,right-left+1);
        }
        return res;
    }
}

方法二：由于这里的最多出现次数是1，所以保存的信息可以不用之前那么多。hash中只用记录当前字符出现的位置，如果出现过，则让其+1与现在的left边界比较。若前者大，说明内部重复了，左边界应更新为上次出现的后一位，若后者大，说明上次出现在这次统计的字符串范围外。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int len=s.length(), res=0, left=0, right=0;
        for(;right<len;right++){
            if(map.get(s.charAt(right))!=null){
                left = Math.max(left, map.get(s.charAt(right))+1);
            }
            map.put(s.charAt(right), right);
            res = Math.max(res,right-left+1);
        }
        return res;
    }
}

第 6 天 字符串

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

剑指 Offer II 017. 含有所有字符的最短字符串
条件列举版：

class Solution {
    public String minWindow(String s, String t) {
        // 例子为 t = "ABC"
        int[] cnt = new int[52], targetCnt = new int[52];
        int left=0, right=0, sLen=s.length(), tLen=t.length(), rLen=0, resL=Integer.MAX_VALUE;
        String res = "";
        for(char c : t.toCharArray()) targetCnt[TI(c)]++;
        for(;left<sLen;left++){
            int x = TI(s.charAt(left));
            if(targetCnt[x]>0){
                break;
            }
        }
        for(right=left;right<sLen;right++){
            int x = TI(s.charAt(right));
            cnt[x]++;
            // 1.属于t
            if(targetCnt[x]>0){
                if(cnt[x]<=targetCnt[x]){
                    // 1.1.没超过限制
                    rLen++;
                }else{
                    // System.out.println(s.charAt(right));
                    // 1.2.超过限制
                    if(rLen==tLen){
                        // 1.2.1.已经找全
                        if(s.charAt(left)==s.charAt(right)){
                            // System.out.println("-----"+s.charAt(left));
                            // 1.2.1.1.左右相等，说明不用保持最左边界了,"ADBECEBA"->"CEBA"
                            // 找到新的起始位置
                            while(cnt[TI(s.charAt(left))]>targetCnt[TI(s.charAt(left))]){
                                cnt[TI(s.charAt(left))]--;
                                left++;
                            }
                            // System.out.println("left is "+left);
                        }
                        // 1.2.1.2.虽然找全，但左右不等，仍需要保存左边界，"ADBECEB"
                    }else{
                        // 1.2.2.还没找全，但重复了，尝试缩短左边，"ADBEB"不变和"DBEB"->"B"
                        while(cnt[TI(s.charAt(left))]>targetCnt[TI(s.charAt(left))]){
                            cnt[TI(s.charAt(left))]--;
                            left++;
                        }
                    }
                }
            }else{
                // 2.不属于t，仍然继续往右
            }
            if(rLen==tLen){
                // 已找全，放到这里保证1.1和1.2.1.1都能计算
                if(right-left+1<resL){
                    resL = right-left+1;
                    res = s.substring(left,right+1);
                }
                resL = Math.min(resL, right-left+1);
            }
        }
        return res;
    }

    private int TI(char c){
        if(c>='a' && c<='z'){
            return c-'a';
        }
        return c-'A'+26;
    }
}

简化版：

class Solution {
    public String minWindow(String s, String t) {
        // 例子为 t = "ABC"
        int[] cnt = new int[52], targetCnt = new int[52];
        int left=0, right=0, sLen=s.length(), tLen=t.length(), rLen=0, resL=Integer.MAX_VALUE;
        String res = "";
        for(char c : t.toCharArray()) targetCnt[TI(c)]++;
        for(;left<sLen;left++){
            int x = TI(s.charAt(left));
            if(targetCnt[x]>0){
                break;
            }
        }
        for(right=left;right<sLen;right++){
            int x = TI(s.charAt(right));
            cnt[x]++;
            // 1.属于t
            if(targetCnt[x]>0){
                if(cnt[x]<=targetCnt[x]){
                    // 1.1.没超过限制
                    rLen++;
                }else{
                    // 1.2.超过限制
                    while(cnt[TI(s.charAt(left))]>targetCnt[TI(s.charAt(left))]){
                        cnt[TI(s.charAt(left))]--;
                        left++;
                    }
                }
            }
            if(rLen==tLen){
                // 已找全，放到这里保证1.1和1.2都能计算
                if(right-left+1<resL){
                    resL = right-left+1;
                    res = s.substring(left,right+1);
                }
                resL = Math.min(resL, right-left+1);
            }
        }
        return res;
    }

    private int TI(char c){
        if(c>='a' && c<='z'){
            return c-'a';
        }
        return c-'A'+26;
    }
}

剑指 Offer II 018. 有效的回文

剑指 Offer II 018. 有效的回文
简单双指针

class Solution {
    public boolean isPalindrome(String s) {
        int len = s.length(), left=0, right=len-1;
        char[] cs = s.toCharArray();
        while(left<right){
            int xl=TI(cs[left]), xr=TI(cs[right]);
            if(xl==-1){
                left++;
                continue;
            }
            if(xr==-1){
                right--;
                continue;
            }
            if(xl==xr){
                left++;
                right--;
                continue;
            }
            return false;
        }
        return true;
    }

    private int TI(char c) {
        if(c>='a'&&c<='z') return c-'a'+10;
        if(c>='A'&&c<='Z') return c-'A'+10;
        if(c>='0'&&c<='9') return c;
        return -1;
    }
}

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

剑指 Offer II 019. 最多删除一个字符得到回文
直接从两头开始，用跳过一个的方法遇到的问题太多

// AXBBA判断X右边，ABBXA判断X左边，
// ABXCBA的X在中间，ABXCDCBA同第一种情况
// 但类似ABAAB和BAABA就无法判断

因此使用递归方法，但要考虑一次容错，因此把这次容错放到主函数中，左右不等时调用没有容错的函数，这个函数中若左右不等返回错误。

class Solution {
    public boolean validPalindrome(String s) {
        int left=0, right=s.length()-1;
        while(left<right){
            if(s.charAt(left)==s.charAt(right)){
                left++;
                right--;
            }else{
                return valid(s,left+1,right)||valid(s,left,right-1);
            }      
        }
        return true;
    }

    private boolean valid(String s, int left, int right){
        while(left<right){
            if(s.charAt(left)!=s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

[M][不会][Manacher 算法] 剑指 Offer II 020. 回文子字符串的个数

剑指 Offer II 020. 回文子字符串的个数
方法一：双循环+动态规划，n^2的双循环。

class Solution {
    public int countSubstrings(String s) {
        // dp[i][j] 代表i到j是否是回文
        // dp[i][j] = s[i]==s[j] && (j-i<=1 || dp[i+1][j-1])
        // j-i==-1表示是aa，后者dp为false
        int left = 0, len = s.length(), right=0, res=0;
        boolean[][] dp = new boolean[len][len];
        // 得到值需要左下的参数，而left<=right，所以表格的左下角无法取值
        // 此时可以先从下一行行左扫，也可以从左一列列上扫
        for(;right<len;right++){
            for(left=right;left>=0;left--){
                // 放在前面防止越界
                if(s.charAt(left)==s.charAt(right)&&(right-left<=1 || dp[left+1][right-1])){
                    dp[left][right] = true;
                    res++;
                }
            }
        }
        return res;
    }
}

方法二：中心拓展n^2。中心可以是一个或者两个，所以一共有n+n-1个即2n-1个中心。

编号i	中心L	中心R
0	0	0
1	0	1
2	1	1
3	1	2
4	2	2
所以L=floor(i/2)，R=L+(i%2)。

class Solution {
    public int countSubstrings(String s) {
        int len = s.length(), L=0, R=0, res=0;
        for(int i=0;i<2*len;i++){
            L = i/2;
            R = L+(i%2);
            while(L>=0 && R<len && s.charAt(L)==s.charAt(R)){
                res++;
                L--;
                R++;
            }
        }
        return res;
    }
}

方法三：Manacher 算法
参考 Manacher 算法 - SegmentFault 思否
首先在字符串之间包括首位插入’#'，使字符串长度成为奇数。
设f[i]为第i个字符的最大回文半径（包括中心位置+1）。求解过程维护最大回文中心iMax和对应最大右边界rMax。

第i位回文字符串长度=f[i]-1。
如果当前是’#'，两边不等f[i]为1，两边相等则是3，对应的长度分别是0、2。如果当前是字符，则其半径至少为2，再扩为4，对应长度为1、3。若具体数学证明也可得长度=f[i]-1。

mx 代表以 id 为中心的最长回文的右边界，j<=id是i关于id的对称点。又i+j=2id，所以j=2id-i。
若i<=mx，则f[i]=MIN(mx-i+1, f[2*id-i])，这部分证明在末尾。简单理解，若j的半径在mx内部，说明i的也在内部；若j的半径超出了mx，则保留mx内部的部分。
若j>mx，则初始化为1。
之后进行中心扩展，s[i-f[i]]==s[i+f[i]]则进行扩展，在整个字符串左右加上’$‘和’!'，防止越界。

如何计算回文串的数量：

1. 对于’#'在中间的，两边不等则f[i]=1，count=0；两边相等则f[i]=3，count=1。count=(f[i]-1)/2。
2. 对于字符在中间的，两边不等则f[i]=2，count=1；两边相等则f[i]=4，count=2。count=f[i]/2。
3. 合起来就是f[i]/2，int直接截断了。

证明：
4. 若j的回文在mx外，即取mx-i+1，想要i的长度和j相等。如果i可以向右扩展，说明j的左半部分应该等于i的右半部分，则id也可以扩展，因此冲突，此情况下O(1)计算出了长度。

5. 若j的回文在mx内，即取f[2id-i]，i的长度和j相等。说明j的左部分无法加入和j的右部分不等，根据对称，说明i的也不等，因此也无法扩展，O(1)确定了f[i]。
6. 若重合，即mx-i+1==f[2id-i]，此时也无法确定，左右继续扩展。
复杂度分析：
时间复杂度：O(n)。即 Manacher 算法的时间复杂度，由于最大回文右端点 只会增加而不会减少，故中心拓展进行的次数最多为 O(n)，此外我们只会遍历字符串一次，故总复杂度为 O(n)。

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        StringBuffer t = new StringBuffer("$#");
        for (int i = 0; i < n; ++i) {
            t.append(s.charAt(i));
            t.append('#');
        }
        n = t.length();
        t.append('!');

        int[] f = new int[n];
        int iMax = 0, rMax = 0, res = 0;
        for(int i=1; i<n; i++){
            f[i] = i<=rMax ? Math.min(f[2*iMax-i], rMax-i+1) : 1;
            while(t.charAt(i-f[i])==t.charAt(i+f[i])) f[i]++;
            if(i+f[i]-1>rMax){
                iMax = i;
                rMax = i+f[i]-1;
            }
            res += f[i]/2;
        }
        return res;
    }
}

第 7 天 链表

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

剑指 Offer II 021. 删除链表的倒数第 n 个结点
三指针一遍扫描，一前一后一中间

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode nhead = new ListNode();
        ListNode pre=nhead, cur=head, post=head;
        nhead.next = head;
        for(int i=1;i<=n;i++){
            post = post.next;
        }
        while(post!=null){
            post = post.next;
            cur = cur.next;
            pre = pre.next;
        }
        pre.next = cur.next;
        return nhead.next;
    }
}

[M][不会] 剑指 Offer II 022. 链表中环的入口节点

剑指 Offer II 022. 链表中环的入口节点
O(1)空间

最极限情况，slow刚刚好紧挨着在fast的后面，那slow走一圈时，fast走两圈，即一定能在slow的第一圈相遇

# 走了n圈
fast = a+n(b+c)+b = a+(n+1)b+nc
任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。
因此，我们有
a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)
此时一个新的指针从起点开始出发，slow也同时出发，
a=c+(n−1)(b+c)，n可以取1、2、3等，
说明最终新的指针走过了a后，slow刚好也走到了交接点。

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

剑指 Offer II 023. 两个链表的第一个重合节点

剑指 Offer II 023. 两个链表的第一个重合节点
双指针p1，p2。设非公共段位a、b，公共段为c。
p1走过的路为a+c+b，p2走的为b+a+c，最终会在这点相遇。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode oriA = headA, oriB = headB;
        while(headA!=headB){
            if(headA==null){
                headA = oriB;
                headB = headB.next; // 不可能同时null，因为直接跳出循环
            }else if(headB==null){
                headB = oriA;
                headA = headA.next;
            }else{
                headA = headA.next;
                headB = headB.next;
            }
        }
        return headB;
    }
}

第 8 天 链表

[不会] 剑指 Offer II 024. 反转链表

剑指 Offer II 024. 反转链表
迭代或递归两种方式
方法一：迭代

/**
 * 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;
        // length >= 2
        ListNode pre = null, cur = head, post = cur.next;
        while(cur!=null){
            cur.next = pre;
            pre = cur;
            cur = post;
            if(cur!=null){
                post = cur.next;
            }
        }
        return pre;
    }
}

方法二：递归

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode post = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return post;
    }
}

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

剑指 Offer II 025. 链表中的两数相加
不能对列表中的节点进行翻转。
方法一：反转链表+整数加法

/**
 * 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) {
        l1 = reverse1(l1);
        l2 = reverse2(l2);
        ListNode ans = new ListNode(), cur = ans;
        int up = 0;
        while(l1!=null && l2!=null){
            int add = (l1.val+l2.val+up)%10;
            up = (l1.val+l2.val+up)/10;
            cur.next = new ListNode(add);
            cur = cur.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        l1 = l1==null ? l2 : l1;
        while(l1!=null){
            int add = (l1.val+up)%10;
            up = (l1.val+up)/10;
            cur.next = new ListNode(add);
            cur = cur.next;
            l1 = l1.next;
        }
        if(up>0) cur.next = new ListNode(up);
        cur = ans;
        ans = ans.next;
        cur.next = null;
        return reverse1(ans);
    }

    private ListNode reverse1(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode pre=null, cur=head, nex=cur.next;
        while(cur!=null){
            cur.next = pre;
            pre = cur;
            cur = nex;
            if(cur!=null){
                nex = cur.next;
            }
        }
        return pre;
    }

    private ListNode reverse2(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode nhead = reverse2(head.next);
        head.next.next = head;
        head.next = null;
        return nhead;
    }
}

方法二：不能对列表中的节点进行翻转。 使用栈+整数加法。

/**
 * 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) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        while(l1!=null){
            s1.push(l1.val);
            l1 = l1.next;
        }
        while(l2!=null){
            s2.push(l2.val);
            l2 = l2.next;
        }
        ListNode ans = new ListNode(), cur = ans;
        int up = 0;
        while(!s1.isEmpty() && !s2.isEmpty()){
            int temp = s1.pop()+s2.pop()+up;
            int add = temp%10;
            up = temp/10;
            cur.next = new ListNode(add);
            cur = cur.next;
        }
        s1 = s1.isEmpty() ? s2 : s1;
        while(!s1.isEmpty()){
            int temp = s1.pop()+up;
            int add = temp%10;
            up = temp/10;
            cur.next = new ListNode(add);
            cur = cur.next;
        }
        if(up>0) cur.next = new ListNode(up);
        cur = ans;
        ans = ans.next;
        cur.next = null;
        return reverse1(ans);
    }
    private ListNode reverse1(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode pre=null, cur=head, nex=cur.next;
        while(cur!=null){
            cur.next = pre;
            pre = cur;
            cur = nex;
            if(cur!=null){
                nex = cur.next;
            }
        }
        return pre;
    }

    private ListNode reverse2(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode nhead = reverse2(head.next);
        head.next.next = head;
        head.next = null;
        return nhead;
    }
}

[M] 剑指 Offer II 026. 重排链表

剑指 Offer II 026. 重排链表
原链表截断+反转+合并

/**
 * 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) {
        ListNode l1 = head, l2 = head.next, cur1 = l1, cur2 = l2;
        int cnt = 1;
        while(cur2!=null){
            cur2 = cur2.next;
            cnt++;
        }
        int len1 = (cnt+1)/2;
        for(int i=0;i<len1-1;i++) cur1 = cur1.next;
        cur2 = cur1.next;
        cur1.next = null;
        l2 = cur2;
        combine2first(l1, reverse(l2));
    }

    private void combine2first(ListNode first, ListNode second) {
        ListNode l1 = first, l2 = second, nex1, nex2;
        while(l2!=null){
            nex1 = l1.next;
            nex2 = l2.next;
            l1.next = l2;
            l2.next = nex1;
            l1 = nex1;
            l2 = nex2;
        }
    }

    private ListNode reverse(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode nhead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return nhead;
    }
}

第 9 天 链表

剑指 Offer II 027. 回文链表

剑指 Offer II 027. 回文链表
O(n) 时间复杂度和 O(1) 空间复杂度。
找中点->反转后部分->比较->反转回后部分

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

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

 /*
// 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) {
        if(head==null || head.next==null && head.child==null) return head;
        flattenCur(head);
        // Node cur = head;
        // while(cur!=null){
        //     System.out.println((cur.prev==null ? null : cur.prev.val)+ " " + cur.val+" "+
        //         (cur.next==null ? null : cur.next.val));
        //     cur = cur.next;
        // }
        return head;
    }

    private Node flattenCur(Node head) {
        Node pre = null, cur = head, nex = cur.next;
        // if(cur.next==null && cur.child==null) return cur;
        while(cur!=null){
            // System.out.println(cur.val);
            if(cur.child!=null){
                cur.next = cur.child;
                cur.child.prev = cur;
                Node child = cur.child;
                cur.child = null; // 要清空
                cur = flattenCur(child);
                // System.out.println("--cur--"+cur.val);
                // System.out.println("--nex--"+nex.val);
                cur.next = nex;
                if(nex!=null) nex.prev = cur;
            }
            pre = cur;
            cur = nex;
            if(cur!=null) nex = cur.next;
        }
        // System.out.println("--ret--"+pre.val);
        return pre;
    }
}

[U][M] 剑指 Offer II 029. 排序的循环链表

剑指 Offer II 029. 排序的循环链表
边界不好处理

/*
// 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 insertNode = new Node(insertVal), cur = head, nex;
        insertNode.next = insertNode;
        if(head==null){
            head = insertNode;
            return head;
        }
        nex = cur.next;
        while(nex!=head){
            if((insertVal>=cur.val && insertVal<=nex.val) ||
                    (cur.val>nex.val && (insertVal>=cur.val || insertVal<=nex.val))){
                    //[3,4,1]&2       [3,4,1]&6
                break;
            }
            cur = nex;
            nex = nex.next;
        }
        cur.next = insertNode;
        insertNode.next = nex;
        return head;
    }
}

第 10 天 哈希表

[M][未自己写] 剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

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

 /*
        数组+map
        利用数组维护所有插入的元素
        map记录插入的元素在数组中的下标
        即key为插入的val value为val在数组中的index
        当需要删除元素时，利用map获取元素的下标
        然后将最后一个元素覆盖该下标元素，并删除最后一个元素
        同时需要利用map维护变化

        执行用时：20 ms, 在所有 Java 提交中击败了99.94%的用户
        内存消耗：90.1 MB, 在所有 Java 提交中击败了12.34%的用户
    */
    Map<Integer, Integer> map;
    List<Integer> arr;
    int size;
    static Random rd = new Random();

    public RandomizedSet() {
        map = new HashMap<>();
        arr = new ArrayList<>();
    }
    
    public boolean insert(int val) {
        if(map.containsKey(val)) return false;
        arr.add(val);
        map.put(val, size++);
        return true;
    }
    
    public boolean remove(int val) {
        if(!map.containsKey(val)) return false;
        int index = map.get(val);       // 获取val的下标index
        int lastNum = arr.get(--size);  // 获取最后一个元素last
        arr.set(index, lastNum);  // 利用last覆盖index
        map.put(lastNum, index);  // 改变map中last的index
        map.remove(val);    // 删除map中的val
        arr.remove(size);   // 删除最后一个元素
        return true;
    }
    
    public int getRandom() {
        return arr.get(rd.nextInt(size));
    }

[U][M] 剑指 Offer II 031. 最近最少使用缓存

剑指 Offer II 031. 最近最少使用缓存
hash+双向链表
get要O(1)，只能选数组或hash，数组的范围要和key的大小关联，因此选hash。
put要O(1)，维护一个链表，每次更新后就把它放到头部，删除时删最后一个，因此使用双向链表。
当满时，直接把最后一个中的值改变，不需要重新创建node。

class LRUCache {

    int length, maxLength;
    Node head, tail;
    HashMap<Integer, Node> map;

    class Node{
        Node pre, next;
        int key, val;
        public Node(){}
        public Node(int key, int val){
            this.key = key;
            this.val = val;
        }

        public static void move2first(Node head, Node node){
            Node preNode=node.pre, nextNode=node.next;
            preNode.next = nextNode;
            nextNode.pre = preNode;
            node.next = head.next;
            node.pre = head;
            head.next.pre = node;
            head.next = node;
        }
    }

    public LRUCache(int capacity) {
        this.maxLength = capacity;
        this.length = 0;
        this.head = new Node(-1,-1);
        this.tail = new Node(-1,-1);
        this.map = new HashMap<Integer, Node>();
        this.head.next = this.tail;
        this.tail.pre = this.head;
    }
    
    public int get(int key) {
        Node node = map.get(key);
        if(node==null){
            return -1;
        }
        Node.move2first(head, node);
        return node.val;
    }
    
    public void put(int key, int value) {
        Node node = map.get(key);
        if(node==null){
            if(length<maxLength){
                node = new Node(key,value);
                node.next = head.next;
                node.pre = head;
                head.next.pre = node;
                head.next = node;
                length++;
                map.put(key, node);
            }else{
                map.remove(tail.pre.key);
                tail.pre.key = key;
                tail.pre.val = value;
                map.put(key, tail.pre);
                Node.move2first(head, tail.pre);
            }
        }else{
            node.val = value;
            Node.move2first(head, 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);
 */

剑指 Offer II 032. 有效的变位词

剑指 Offer II 032. 有效的变位词
过慢

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()){
            return false;
        }
        Map<Character, Integer> map = new HashMap<>();
        int len = s.length(), flag=0, position=0;
        for(int i=0;i<len;i++){
            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
        }
        for(position=0;position<len;position++){
            if(s.charAt(position)!=t.charAt(position)) flag=1;
            map.put(t.charAt(position),map.getOrDefault(t.charAt(position),0)-1);
            if(map.get(t.charAt(position))<0){
                break;
            }
        }
        return flag==1&&position==len;
    }
}

第 11 天 哈希表

[M] 剑指 Offer II 033. 变位词组

剑指 Offer II 033. 变位词组
方法一：太慢

class Solution {
    /*
    根据每个字母的数量生成map的key,value指向一个List
    */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List> map = new HashMap<>();
        for(String s : strs){
            String key = generateKey(s);
            if(map.get(key)==null){
                List<String> list = new ArrayList<>();
                list.add(s);
                map.put(key, list);
                continue;
            }
            map.get(key).add(s);
        }
        List<List<String>> ans = new ArrayList<>();
        for (String key : map.keySet()) ans.add(map.get(key));
        return ans;
    }

    private String generateKey(String s) {
        int[] count = new int[26];
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<s.length();i++) count[s.charAt(i)-'a']++;
        for(int i=0;i<26;i++) sb.append(('a'+i)+String.valueOf(count[i]));
        return sb.toString();
    }
}

方法二：直接排序key

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String,ArrayList<String>> map=new HashMap<>();
        for(String s:strs){
            char[] ch=s.toCharArray();
            Arrays.sort(ch);
            String key=String.valueOf(ch);
            if(!map.containsKey(key)) map.put(key,new ArrayList<>());
            map.get(key).add(s);
        }
        return new ArrayList(map.values());
    }
}

剑指 Offer II 034. 外星语言是否排序

剑指 Offer II 034. 外星语言是否排序

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int size = words.length;
        if(size==1) return true;
        Map<Character, Integer> V = new HashMap<>();
        for(int i=0;i<26;i++) V.put(order.charAt(i),26-i);
        for(int i=0;i<size-1;i++){
            if(!gt(words[i],words[i+1],V)) {
                return false;
            }
        }
        return true;
    }

    private boolean gt(String a, String b, Map<Character, Integer> V){
        int al=a.length(), bl=b.length();
        int len = Math.min(al,bl);
        for(int i=0;i<len;i++){
            if(V.get(a.charAt(i))>V.get(b.charAt(i))){
                return true;
            }else if(V.get(a.charAt(i))<V.get(b.charAt(i))){
                return false;
            }else{
                continue;
            }
        }
        if(al>len) return false;
        return true;
    }
}

[M] 剑指 Offer II 035. 最小时间差

剑指 Offer II 035. 最小时间差
方法一：算时差时转为分钟。

class Solution {
    public int findMinDifference(List<String> timePoints) {
        if(timePoints.size()>24*60-1) return 0;
        String[] array = timePoints.toArray(new String[timePoints.size()]);
        Arrays.sort(array, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return Integer.valueOf(o1.substring(0,2)) == Integer.valueOf(o2.substring(0,2))
                     ? Integer.valueOf(o1.substring(3)) - Integer.valueOf(o2.substring(3))
                     : Integer.valueOf(o1.substring(0,2)) - Integer.valueOf(o2.substring(0,2));
            }
        });
        int ans = 24*60;
        for(int i=0;i<timePoints.size()-1;i++){
            int temp = computeDif(array[i],array[i+1]);
            if(temp==0) return 0;
            ans = Math.min(temp,ans);
        }
        int temp = computeDif(array[timePoints.size()-1],array[0]);
        ans = Math.min(temp,ans);
        return ans;
    }

    private int computeDif(String a, String b) {
        int ah = Integer.valueOf(a.substring(0,2)), bh = Integer.valueOf(b.substring(0,2)),
            am = Integer.valueOf(a.substring(3)), bm = Integer.valueOf(b.substring(3));
        int ami = ah*60+am, bmi = bh*60+bm;
        if(ami>bmi){
            return bmi+24*60-ami;
        }
        return bmi-ami;
    }
}

方法二：直接一开始就转为分钟。

class Solution {
    public int findMinDifference(List<String> timePoints) {
        if (timePoints.size() > 24 * 60) {
            return 0;
        }
        List<Integer> mins = new ArrayList<>();
        for (String t : timePoints) {
            String[] time = t.split(":");
            mins.add(Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]));
        }
        Collections.sort(mins);
        mins.add(mins.get(0) + 24 * 60);
        int res = 24 * 60;
        for (int i = 1; i < mins.size(); ++i) {
            res = Math.min(res, mins.get(i) - mins.get(i - 1));
        }
        return res;
    }
}

第 12 天 栈

[M] 剑指 Offer II 036. 后缀表达式

剑指 Offer II 036. 后缀表达式

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(String token : tokens){
            if(token.equals("+")){
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a+b);
            }else if(token.equals("-")){
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a-b);
            }else if(token.equals("*")){
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a*b);
            }else if(token.equals("/")){
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a/b);
            }else{
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}

[M] 剑指 Offer II 037. 小行星碰撞

剑指 Offer II 037. 小行星碰撞
方法一：用栈模拟

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> s = new Stack<>();
        int len = asteroids.length;
        for(int i=0;i<len;i++){
            int cur = asteroids[i];
            // if(s.isEmpty()){
            //     s.push(cur);
            // }else{
            while(!s.isEmpty()){
                int last = s.peek();
                if(last>0&&cur<0){
                    s.pop();
                    if(last+cur==0){
                        cur = 0;
                        break;
                    }else if(last+cur>0){
                        cur = last;
                        continue;
                    }else{
                        continue;
                    }
                }else{
                    break;
                }
            }
            if(cur!=0) s.push(cur);
            // }
        }

        int anslen = s.size();
        int[] ans = new int[anslen];
        for(int i=0;i<anslen;i++){
            ans[i] = s.pop();
        }
        int left=0,right=anslen-1;
        while(left<right){
            int temp = ans[left];
            ans[left] = ans[right];
            ans[right] = temp;
            left++;
            right--;
        }
        return ans;
    }
}

[U][M] 剑指 Offer II 038. 每日温度

剑指 Offer II 038. 每日温度
方法一：从前往后栈模拟，两个栈保存信息，速度慢。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> temperatureStack = new Stack<>();
        Stack<Integer> dayStack = new Stack<>();
        int len = temperatures.length;
        int[] ans = new int[len];
        for(int i=0;i<len;i++){
            int cur = temperatures[i];
            // if(temperatureStack.isEmpty()){
            //     temperatureStack.push(cur);
            //     dayStack.public(i);
            // }else{
            while(!temperatureStack.isEmpty()&&temperatureStack.peek()<cur){
                temperatureStack.pop();
                int index = dayStack.pop();
                ans[index] = i-index;
            }
            temperatureStack.push(cur);
            dayStack.push(i);
            // }
        }
        return ans;
    }
}

方法二：只用一个栈保存时间信息即可，并且用deque来保存代替stack。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> dayStack = new LinkedList<>();
        int len = temperatures.length;
        int[] ans = new int[len];
        for(int i=0;i<len;i++){
            int cur = temperatures[i];
            while(!dayStack.isEmpty()&&temperatures[dayStack.peek()]<cur){
                int index = dayStack.pop();
                ans[index] = i-index;
            }
            dayStack.push(i);
        }
        return ans;
    }
}

第 13 天 栈

[U][H] 剑指 Offer II 039. 直方图最大矩形面积

剑指 Offer II 039. 直方图最大矩形面积
来自评论区对于此题单调栈的理解

看了别人的答案想了半天才明白……其实可以把这个想象成锯木板，如果木板都是递增的那我很开心，如果突然遇到一块木板i矮了一截，那我就先找之前最戳出来的一块（其实就是第i-1块），计算一下这个木板单独的面积，然后把它锯成次高的，这是因为我之后的计算都再也用不着这块木板本身的高度了。再然后如果发觉次高的仍然比现在这个i木板高，那我继续单独计算这个次高木板的面积（应该是第i-1和i-2块），再把它俩锯短。直到发觉不需要锯就比第i块矮了，那我继续开开心心往右找更高的。当然为了避免到了最后一直都是递增的，所以可以在最后加一块高度为0的木板。
这个算法的关键点是把那些戳出来的木板早点单独拎出来计算，然后就用不着这个值了。

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int len = heights.length, ans = 0;
        for(int i=0;i<len;i++){
            while(stack.peek()!=-1 && heights[i]<heights[stack.peek()]){
                int right = stack.pop();
                // 此时peek到的值是左边界（不包含），因为已经pop了一次。
                ans = Math.max(heights[right]*(i-1-stack.peek()), ans);
            }
            stack.push(i);
        }
        // 清空栈 1,2,3,2,1,2,3,2,1
        while(stack.peek()!=-1){
            int right = stack.pop();
            ans = Math.max(heights[right]*(len-1-stack.peek()), ans);
        }
        return ans;
    }
}

[H] 剑指 Offer II 040. 矩阵中最大的矩形

剑指 Offer II 040. 矩阵中最大的矩形
和上题一样，每一行都来一次最大矩形，注意有可能是空表。

class Solution {
    public int maximalRectangle(String[] stringMatrix) {
        int height = stringMatrix.length;
        if(height==0) return 0;
        int width = stringMatrix[0].length();
        int[][] matrix = new int[height][width];
        for(int j=0;j<width;j++){
            for(int i=0;i<height;i++){
                matrix[i][j] = stringMatrix[i].charAt(j)=='1' ? 1 : 0;
            }
        }
        for(int j=0;j<width;j++){
            for(int i=1;i<height;i++){
                matrix[i][j] = matrix[i][j]==1 ? matrix[i-1][j]+1 : 0;
            }
        }

        int ans = 0;
        for(int i=0;i<height;i++){
            ans = Math.max(ans, largestRectangleArea(matrix[i]));
        }
        return ans;
    }

    private int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int len = heights.length, ans = 0;
        for(int i=0;i<len;i++){
            while(stack.peek()!=-1 && heights[i]<heights[stack.peek()]){
                int right = stack.pop();
                // 此时peek到的值是左边界（不包含），因为已经pop了一次。
                ans = Math.max(heights[right]*(i-1-stack.peek()), ans);
            }
            stack.push(i);
        }
        // 清空栈 1,2,3,2,1,2,3,2,1
        while(stack.peek()!=-1){
            int right = stack.pop();
            ans = Math.max(heights[right]*(len-1-stack.peek()), ans);
        }
        return ans;
    } 
}

第 14 天 队列

[没写] 剑指 Offer II 041. 滑动窗口的平均值

剑指 Offer II 041. 滑动窗口的平均值

[没写] 剑指 Offer II 042. 最近请求次数

剑指 Offer II 042. 最近请求次数

[M] 剑指 Offer II 043. 往完全二叉树添加节点

剑指 Offer II 043. 往完全二叉树添加节点

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

    Queue<TreeNode> queue = new LinkedList<>();
    TreeNode root;

    public CBTInserter(TreeNode root) {
        this.root = root;
        queue.offer(root);
        TreeNode node = null;
        while(true){
            node = queue.peek();
            if(node.left==null) break;
            queue.offer(node.left);
            if(node.right==null) break;
            queue.offer(node.right);
            queue.poll();
        }
    }
    
    public int insert(int v) {
        TreeNode parent = queue.peek();
        TreeNode newNode = new TreeNode(v);
        if(parent.left==null){
            parent.left = newNode;
            queue.offer(parent.left);
        }else if(parent.right==null){
            parent.right = newNode;
            queue.offer(parent.right);
            queue.poll();
        }
        return parent.val;
    }
    
    public TreeNode get_root() {
        return root;
    }
}

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter obj = new CBTInserter(root);
 * int param_1 = obj.insert(v);
 * TreeNode param_2 = obj.get_root();
 */

第 15 天 队列

[没写][M] 剑指 Offer II 044. 二叉树每层的最大值

剑指 Offer II 044. 二叉树每层的最大值
层次遍历

[M] 剑指 Offer II 045. 二叉树最底层最左边的值

剑指 Offer II 045. 二叉树最底层最左边的值

/**
 * 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 findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode flag = new TreeNode();
        TreeNode node = null, res = root;
        queue.offer(root);
        queue.offer(flag);
        while(queue.size()>1){
            node = queue.poll();
            if(node==flag){
                queue.offer(flag);
                res = queue.peek();
                continue;
            }
            if(node.left!=null) queue.offer(node.left);
            if(node.right!=null) queue.offer(node.right);
        }
        return res.val;
    }
}

[没写] [M] 剑指 Offer II 046. 二叉树的右侧视图

剑指 Offer II 046. 二叉树的右侧视图
层次遍历加判断

第 16 天 树

[M] 剑指 Offer II 047. 二叉树剪枝

剑指 Offer II 047. 二叉树剪枝
dfs

/**
 * 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 pruneTree(TreeNode root) {
        return dfs(root) ? null : root;
    }

    private boolean dfs(TreeNode root) {
        if(root==null) return true;
        boolean leftIsNull=dfs(root.left), rightIsNull=dfs(root.right);
        if(leftIsNull) root.left=null;
        if(rightIsNull) root.right=null;
        return leftIsNull && rightIsNull && root.val==0;
    }
}

[H] 剑指 Offer II 048. 序列化与反序列化二叉树

剑指 Offer II 048. 序列化与反序列化二叉树
写过第 28 天 搜索与回溯算法（困难）

[M] 剑指 Offer II 049. 从根节点到叶节点的路径数字之和

剑指 Offer II 049. 从根节点到叶节点的路径数字之和

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int cur) {
        cur = cur*10+root.val;
        if(root.left==root.right && root.left==null){
            return cur;
        }
        int left = root.left==null ? 0 : dfs(root.left, cur);
        int right = root.right==null ? 0 : dfs(root.right, cur);
        return left + right;
    }
}

第 17 天 树

[不会] [M] 剑指 Offer II 050. 向下的路径节点之和

剑指 Offer II 050. 向下的路径节点之和
对于连续区间的和为target，目前为cur，只需要找到之前从开始的前缀和为cur-target的即可。动态维护一个前缀和列表，不过这里只需要记录前缀和的数目，用map保存。

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> map = new HashMap<>();
        map.put(0L,1);
        return dfs(map, root, targetSum, 0L);
    }

    private int dfs(Map<Long, Integer> map, TreeNode root, int targetSum, Long curSum) {
        if(root==null) return 0;
        int res = 0;
        curSum += root.val;
        // 如果当前和等于目标，也要加1
        // 如果整棵树root等于target，应该有map.get(0)==1
        // 对于[0,0,0]，应该初始化map(0,1)，对于第一个0有一个，第二个有两个，第三个有三个。
        res += map.getOrDefault(curSum-targetSum, 0);

        map.put(curSum, map.getOrDefault(curSum,0)+1);
        res += dfs(map, root.left, targetSum, curSum);
        res += dfs(map, root.right, targetSum, curSum);
        map.put(curSum, map.getOrDefault(curSum,0)-1);
        curSum -= root.val;
        
        return res;
    }
}

[不会][H] 剑指 Offer II 051. 节点之和最大的路径

剑指 Offer II 051. 节点之和最大的路径
可以发现路径中只有一个节点他的左右子树都在路径中，因此对于别的节点，只会取左或右一边，对于这个特殊的节点，用后序遍历确定他能取到的最大值。

class Solution {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxSum;
    }

    private int dfs(TreeNode root) {
        if(root==null) return 0;
        // 遍历同时算出了结果，如果小于0则不要，只要root一个节点即可
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));
        maxSum = Math.max(left+right+root.val, maxSum);
        // 用于计算,这里的root相当于调用者的左或右节点
        return Math.max(right, left)+root.val;
    }
}

剑指 Offer II 052. 展平二叉搜索树

剑指 Offer II 052. 展平二叉搜索树
方法一：中序遍历+队列

class Solution {
    public TreeNode increasingBST(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        midTour(root, queue);
        TreeNode res = queue.poll(), pre = res, cur = null;
        res.left = null;
        while(queue.size()>0){
            cur = queue.poll();
            pre.right = cur;
            pre = cur;
            pre.left = null;
        }
        pre.right = null;
        return res;
    }

    private void midTour(TreeNode root, Queue<TreeNode> queue) {
        if(root==null) return;
        midTour(root.left, queue);
        queue.offer(root);
        midTour(root.right, queue);
    }
}

方法二：中序遍历的过程中改变指向。

class Solution {
    TreeNode pre;

    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummyNode = new TreeNode(-1);
        pre = dummyNode;
        inorder(root);
        return dummyNode.right;
    }

    private void inorder(TreeNode root){
        if(root==null) return;
        inorder(root.left);
        pre.right = root;
        pre = root;
        pre.left = null;
        inorder(root.right);
    }
}

第 18 天 树

[M] 剑指 Offer II 053. 二叉搜索树中的中序后继

剑指 Offer II 053. 二叉搜索树中的中序后继

class Solution {

    boolean found = false;
    TreeNode p, ans;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        this.p = p;
        inorder(root);
        return ans;
    }

    private void inorder(TreeNode root) {
        if(root == null || ans != null) return;
        inorder(root.left);
        if(ans != null) return;
        if(found) {
            ans = root;
            return;
        }
        if(root == p) {
            found = true;
        }
        inorder(root.right);
    }
}

[M] 剑指 Offer II 054. 所有大于等于节点的值之和

剑指 Offer II 054. 所有大于等于节点的值之和
中序遍历变种，先right再left。

class Solution {

    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        inorder(root);
        return root;
    }

    private void inorder(TreeNode root) {
        if(root==null) return;
        inorder(root.right);
        root.val += sum;
        sum = root.val;
        inorder(root.left);
    }
}

[M] 剑指 Offer II 055. 二叉搜索树迭代器

剑指 Offer II 055. 二叉搜索树迭代器
next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存。其中 h 是树的高度。
迭代版的中序遍历，用stack模拟递归栈。

class BSTIterator {

    Deque<TreeNode> stack = new LinkedList<>();

    public BSTIterator(TreeNode root) {
        stack.push(new TreeNode(-1));
        while(root!=null){
            stack.push(root);
            root = root.left;
        }
    }
    
    public int next() {
        TreeNode root = stack.peek();
        if(root.val == -1) return -1;
        stack.pop();
        TreeNode node = root.right;
        while(node != null) {
            stack.push(node);
            node = node.left;
        }
        return root.val;
    }
    
    public boolean hasNext() {
        return stack.size()>1;
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

第 19 天 树

[没写] 剑指 Offer II 056. 二叉搜索树中两个节点之和

剑指 Offer II 056. 二叉搜索树中两个节点之和
中序遍历同时用hashmap保存，如two sum。

[不会] [M] 剑指 Offer II 057. 值和下标之差都在给定的范围内

剑指 Offer II 057. 值和下标之差都在给定的范围内
treeset的实现treemap底层为红黑树。

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> ts = new TreeSet<>();
        for(int i=0; i<n; i++) {
            Long u = nums[i]*1L;
            // 从 ts 中找到小于等于 u 的最大值（小于等于 u 的最接近 u 的数）
            Long l = ts.floor(u); 
            // 从 ts 中找到大于等于 u 的最小值（大于等于 u 的最接近 u 的数）
            Long r = ts.ceiling(u); 
            if(l!=null && u-l<=t) return true;
            if(r!=null && r-u<=t) return true;
            ts.add(u);
            // 将当前数加到 ts 中，并移除下标范围不在 [max(0, i - k), i) 的数（维持滑动窗口大小为 k）
            if(i>=k) ts.remove(nums[i-k]*1L);
        }
        return false;
    }
}

[U] [M] 剑指 Offer II 058. 日程表

剑指 Offer II 058. 日程表
红黑树？

第 20 天 堆

[不会] 剑指 Offer II 059. 数据流的第 K 大数值

剑指 Offer II 059. 数据流的第 K 大数值
大小为k的小顶堆来保存前k大的数。优先队列。

class KthLargest {

    PriorityQueue<Integer> queue;
    int k;
    public KthLargest(int k, int[] nums) {
        queue = new PriorityQueue<>();
        this.k = k;
        for(int num : nums){
            queue.add(num);
        }
        while(queue.size() > k){
            queue.poll();
        }
    }
    
    public int add(int val) {
        queue.add(val);
        if(queue.size() > k){
            queue.poll();
        }
        return queue.peek();
    }
}

[M] 剑指 Offer II 060. 出现频率最高的 k 个数字

剑指 Offer II 060. 出现频率最高的 k 个数字
快排，注意先右还是左。

class Solution {

    Map<Integer, Integer> map;

    public int[] topKFrequent(int[] nums, int k) {
        map = new HashMap<>();
        int len = nums.length;
        for(int i=0; i<len; i++) {
            int num = nums[i];
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        int slen = map.size();
        int[] nodes = new int[slen];
        int index = 0;
        for(int key : map.keySet()){
            // System.out.println(key+" "+map.get(key));
            nodes[index++] = key;
        }
        getPreKByQsort(nodes,0,slen-1,k-1);
        
        int[] ans = new int[k];
        for(int i=0;i<k;i++){
            ans[i] = nodes[i];
        }
        return ans;
    }

    private void getPreKByQsort(int[] nodes, int left, int right, int k) {
        // System.out.println(left+" "+right);
        if(left>=right) return;
        int lp=left, rp=right, temp=0;
        while(lp<rp){
            while(lp<rp && map.get(nodes[rp])<=map.get(nodes[left])) rp--;
            while(lp<rp && map.get(nodes[lp])>=map.get(nodes[left])) lp++;
            temp = nodes[lp];
            nodes[lp] = nodes[rp];
            nodes[rp] = temp;
        }
        nodes[lp] = nodes[left];
        nodes[left] = temp;
        if(lp==k) return;
        if(lp>k) getPreKByQsort(nodes, left, lp-1, k);
        if(lp<k) getPreKByQsort(nodes, lp+1, right, k);
        // getPreKByQsort(nodes, left, lp-1, k);
        // getPreKByQsort(nodes, lp+1, right, k);
    }
}

[没写] [M] 剑指 Offer II 061. 和最小的 k 个数对

剑指 Offer II 061. 和最小的 k 个数对
多路归并

最后

以上就是奋斗季节为你收集整理的剑指offer普通（java）上第1天 整数第 2 天 整数第 3 天 数组第 4 天 数组第 5 天 字符串第 6 天 字符串第 7 天 链表第 8 天 链表第 9 天 链表第 10 天 哈希表第 11 天 哈希表第 12 天 栈第 13 天 栈第 14 天 队列第 15 天 队列第 16 天 树第 17 天 树第 18 天 树第 19 天 树第 20 天 堆的全部内容，希望文章能够帮你解决剑指offer普通（java）上第1天 整数第 2 天 整数第 3 天 数组第 4 天 数组第 5 天 字符串第 6 天 字符串第 7 天 链表第 8 天 链表第 9 天 链表第 10 天 哈希表第 11 天 哈希表第 12 天 栈第 13 天 栈第 14 天 队列第 15 天 队列第 16 天 树第 17 天 树第 18 天 树第 19 天 树第 20 天 堆所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。