leetcode算法2

76 最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring/

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

双指针，r每次移动一个位

如果check满足要求，移动l，循环check，直到不满足要求。

public class LC76 {
    public String minWindow(String s, String t) {
        int[] b =  new int[54];
        for (char c : t.toCharArray()){
            b[toIndex(c)]++;
        }
        int[] win =  new int[54];
        int l=0,r=0,minLen=Integer.MAX_VALUE;
        String res="";
        while (r<s.length()){
            int index =toIndex(s.charAt(r));
            if (b[index]>0){
                win[index]++;
            }
            while (check(win,b)){
                System.out.println(l+","+r+"|"+s.substring(l,r+1));
                if (r-l<minLen){
                    res=s.substring(l,r+1);
                    minLen=r-l;
                }
                int  i=toIndex(s.charAt(l));
                if (b[i]>0){
                    win[i]--;
                }
                l++;
            }
            r++;
        }

        return res;

    }

    private boolean check(int[] win, int[] b) {

        for (int i=0;i<win.length;i++){
            if (b[i]>win[i]){
                return false;
            }
        }
        System.out.println(Arrays.toString(b));
        System.out.println(Arrays.toString(win));
        return true;
    }

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

239滑动窗口最大值

https://leetcode.cn/problems/sliding-window-maximum

滑动窗口的位置                最大值
---------------               -----
[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，移除左边最小序列号

满足要求长度k，输出。

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length<2){
        return nums;
    }
    if (k>=nums.length){
        return new int[]{Arrays.stream(nums).max().getAsInt()};
    }


    int len=nums.length,j=0;
    int[] a = new int[len-k+1];
    ArrayDeque<Integer> deque = new ArrayDeque<>();//值从大到小，序列号从小到大
    for (int i=0;i<len;i++){
        while (deque.size()>0 && nums[deque.getLast()]<=nums[i]){
            deque.removeLast();
        }
        deque.offerLast(i);
        if (deque.getFirst()<=i-k){
            deque.removeFirst();
        }

        if (i-k+1>=0){
            a[j++]=nums[deque.getFirst()];
        }


    }
    return a;
}

124二叉树中的最大路径和

https://leetcode.cn/problems/binary-tree-maximum-path-sum

public class LC124 {
    private int res=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        cal(root);
        return res;
    }
    
    private int cal(TreeNode root) {
        if (root==null){
            return 0;
        }
        int left=cal(root.left);
        int right = cal(root.right);
        int sum=Math.max(Math.max(left,right)+root.val,root.val);//比较本身，和左右两边
        res=Math.max(Math.max(res,sum), root.val+left+right);//比较（左+右+本身）
        return sum;

    }
    
}

647回文子串

	j0	1	2	3	4
i0	1	0	0	0	1
1		1	0	1	0
2			1	0	0
3				1	0
4					1

abcba

01234

2个问题：

1为什么不用左下角？左下角是i>j,不方便理解，相当于（j->i）

2.为什么i不从上到下？比如要判断abcba（i,j）是回文，bcb(i+1,j-1）必然是回文，而(i+1,j-1）在下方。

• abcba
• 如果字符相等，相邻1个元素以内，必然是回文
• 如果字符相等，比如第一个a和最后一个a，就判断bcb是否为回文。

public class LC647 {
    public int countSubstrings(String s) {
        int len=s.length();
        boolean[][] dp = new boolean[len][len];
        int count=0;
        for (int i=len-1;i>=0;i--){
            for (int j=i;j<len;j++){
                if (j-i<2 && s.charAt(i)==s.charAt(j)){
                    dp[i][j]=true;
                    count++;
                }else if (s.charAt(i)==s.charAt(j) && dp[i+1][j-1]){
                    dp[i][j]=true;
                    count++;

                }
            }
        }

        return count;

    }
}

96不同的二叉搜索树

https://leetcode.cn/problems/unique-binary-search-trees

n个节点
G(n)=f(1)+f(2)+…+f(n)[f(i)代表i为根节点的个数]
f(i)=G(i-1)*G(n-i)
G(i)=G(j-1)*G(i-j)…….+

public  int numTrees(int n) {
    int[] dp = new int[Math.max(n+1,5)];
    dp[0]=1;
    dp[1]=1;
    dp[2]=2;
    dp[3]=5;
    if (dp[n]>0){
        return dp[n];
    }
    for (int i=4;i<=n;i++){
        int count=0;
        for (int j=1;j<=i;j++){
           count+=dp[j-1]*dp[i-j];
        }
        dp[i]=count;
    }
    return dp[n];
}