二叉树节点值和最大的路径 存在负值节点

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

    }

    public int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=Math.max(dfs(root.left),0);//对于子树的最长路径为负值的情况下，直接置为0
        int right=Math.max(dfs(root.right),0);
        res=Math.max(res,left+right+root.val);
        return root.val+Math.max(left,right);
    }
}

将二叉搜索树转为一棵递增的链表

class Solution {
    TreeNode cur;
    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummy=new TreeNode(-1);
        cur=dummy;
                dfs(root);
        return dummy.right;
    }
    public void dfs(TreeNode root){
        if(root==null){
            return;
        }
        dfs(root.left);

        cur.right=root;
        cur=cur.right;
        root.left=null;

        dfs(root.right);
    }
}

反序中序遍历

通过反序中序遍历获得BST递减序列

class Solution {
    int sum=0;
    public TreeNode convertBST(TreeNode root) {
        if(root==null){
            return null;
        }
        //反序中序遍历
        convertBST(root.right);
        sum+=root.val;
        root.val=sum;
        convertBST(root.left);
        return root;
    }
}

BST中序遍历的后继节点

class Solution {
    TreeNode cur=null;
    TreeNode pre=null;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        dfs(root,p);
        return cur;
    }
    public void dfs(TreeNode root,TreeNode p){
        if(root==null){
            return;
        }
        dfs(root.left,p);
        if(pre==p){
            cur=root;
        }
        pre=root;
        dfs(root.right,p);
    }
}

二进制数组中1和0个数相等的最长子数组

hash表

class Solution {
    public int findMaxLength(int[] nums) {
        int n=nums.length;
        Map<Integer,Integer> map=new HashMap<>();
        int count=0;
        map.put(0,-1);
        int res=0;
        for(int i=0;i<n;i++){
            if(nums[i]==1){
                count++;
            }else{
                count--;
            }
            if(map.containsKey(count)){
                res=Math.max(res,i-map.get(count));

            }else{
                map.put(count,i);
            }
        }
        return res;
    }
}

求数组中和为k的连续子数组的个数

通过hash表记录每一个前缀和出现的个数

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> map=new HashMap<>();
        int pre=0;int res=0;
        map.put(0,1);
        for(int i=0;i<nums.length;i++){
            pre+=nums[i];
            if(map.containsKey(pre-k)){
                res+=map.get(pre-k);
            }
            map.put(pre,map.getOrDefault(pre,0)+1);
        }
        return res;
    }
}

数组乘积小于k的连续数组的个数

方式一：溢出

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if(k==0){
            return 0;
        }
      Map<Long,Long> map=new HashMap<>();
        long mul=1;
        long res=0;
        map.put(1L,1L);
        for(int i=0;i<nums.length;i++){
            mul*=nums[i];
            Set<Map.Entry<Long,Long>> entries=map.entrySet();
            for(Map.Entry<Long,Long> entry:entries){
                long key=entry.getKey();
                long value=entry.getValue();
                if(key>mul/k){
                    res+=value;
                }
            }
            map.put(mul,map.getOrDefault(mul,0L)+1);
        }
        return (int)res;
    }
}

方式二 ： 通过滑动窗口
每次将右端点数据累乘之后，调整左窗口的位置

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        long mul=1;
        int res=0;
        int left=0;
        for(int i=0;i<nums.length;i++){
            mul*=nums[i];
            while(left<=i&&mul>=k){
                mul/=nums[left];
                left++;
            }
            res+=i-left+1;
        }
        return res;
    }
}

数组和大于等于target的最小的连续数组长度

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
 int res=Integer.MAX_VALUE;
        int n=nums.length;
        //通过双指针的方式
        int start=0;int end=0;
        int sum=0;
        while(end<n){
            sum+=nums[end];
            while(sum>=target){
                res=Math.min(res,end-start+1);
                sum-=nums[start];
                start++;
            }
            end++;
        }
        return res==Integer.MAX_VALUE? 0:res;
    }
}

字符串中的变位词

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n=s1.length();
        char[] chs=s1.toCharArray();
        Arrays.sort(chs);

        s1=new String(chs);

        for(int i=0;i+n-1<s2.length();i++){
            int j=i+n-1;
            String s=s2.substring(i,j+1);
            char[] ch=s.toCharArray();
            Arrays.sort(ch);
            String ss=new String(ch);
            if(s1.equals(ss)){
                return true;
            }
        }
        return false;
    }
}

方法二：通过滑动窗口的方式统计
通过diff记录不同的字符个数，当不同字符个数==0时对应的 true
滑动窗口s2

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n=s1.length();int m=s2.length();
        if(n>m){
            return false;
        }
        int[] cnt=new int[26];
        for(int i=0;i<s1.length();i++){
            cnt[s1.charAt(i)-'a']--;
            cnt[s2.charAt(i)-'a']++;
        }
        int diff=0;
        for(int i=0;i<26;i++){
            if(cnt[i]!=0){
                diff++;
            }
        }
        if(diff==0){
            return true;
        }
        for(int i=n;i<m;i++){
            int x=s2.charAt(i)-'a';int y=s2.charAt(i-n)-'a';
            if(x==y){
                continue;
            }
            if(cnt[x]==0){
                diff++;
            }
            cnt[x]++;
            if(cnt[x]==0){
                diff--;
            }
            if(cnt[y]==0){
                diff++;
            }
            cnt[y]--;
            if(cnt[y]==0){
                diff--;
            }            
            if(diff==0){
                return true;
            }
        }
        return false;
    }
}

删除数组元素 [删除并获得点数]

class Solution {
    static int N=10010;
    public int deleteAndEarn(int[] nums) {
        int[] cnt=new int[N];
        int[][] dp=new int[N][2];
        int res=Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            cnt[nums[i]]++;
        }
        for(int i=1;i<N;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=dp[i-1][0]+i*cnt[i];
            res=Math.max(res,Math.max(dp[i][0],dp[i][1]));
        }
        return res;
    }

}

摘樱桃

dp[i][j][k]表示 两次走的横坐标分别为i,j 横纵坐标之和为 k

class Solution {
    public int cherryPickup(int[][] grid) {
        int n=grid.length;
        int[][][] dp=new int[n+1][n+1][2*n+1];
        for(int i=0;i<n+1;i++){
            for(int j=0;j<n+1;j++){
                Arrays.fill(dp[i][j],-0x3f3f3f);
            }
        }
        if(grid[0][0]!=-1){
            dp[1][1][2]=grid[0][0];            
        }
        for(int k=3;k<=2*n;k++){
            for(int i=Math.max(1,k-n);i<=Math.min(k-1,n);i++){
                for(int j=Math.max(1,k-n);j<=Math.min(k-1,n);j++){
                    if(grid[i-1][k-i-1]==-1||grid[j-1][k-j-1]==-1){
                        continue;
                    }
                    int t=grid[i-1][k-i-1];
                    if(i!=j){
                        t+=grid[j-1][k-j-1];
                    }
                    for(int a=i-1;a<=i;a++){
                        for(int b=j-1;b<=j;b++){
                            dp[i][j][k]=Math.max(dp[i][j][k],dp[a][b][k-1]+t);
                        }
                    }
                }
            }
        }
        return Math.max(0,dp[n][n][2*n]);
    }
}

最接近的时间 将所有的时间排序 最后比较首尾时间即可

class Solution {
    public int findMinDifference(List<String> timePoints) {

        int n=timePoints.size();
        if(n>1440){   //通过鸽巢原理进行剪枝
            return 0;
        }

        //将所有的进行排序
        Collections.sort(timePoints);
        int curmins=getMins(timePoints.get(0));
        int premins=curmins;
        int res=Integer.MAX_VALUE;
        int mins=0;
        for(int i=1;i<timePoints.size();i++){
            mins=getMins(timePoints.get(i));
            res=Math.min(res,mins-premins);
            premins=mins;
        }
        res=Math.min(res,curmins+1440-mins);
        return res;
    }
    public int getMins(String s){
        return ((s.charAt(0)-'0')*10+s.charAt(1)-'0')*60+((s.charAt(3)-'0')*10+s.charAt(4)-'0');
    }
}

每日气温 找到当前气温之后的第一个比当前气温更大的气温的下标

通过单调栈的方式，从右往左进行记录

class Solution {
    public int[] dailyTemperatures(int[] temp) {
        Stack<Integer> stack=new Stack<Integer>();
        int[] res=new int[temp.length];
        int index=temp.length-1;
        for(int i=temp.length-1;i>=0;i--){
            while(!stack.isEmpty()&&temp[i]>=temp[stack.peek()]){
                stack.pop();
            }
            res[index--]=stack.isEmpty()? 0:stack.peek()-i;
            stack.push(i);
        }
        return res;
    }
}

小行星碰撞 通过栈进行模拟

直接将元素入栈的情况：
+ 栈为空
+ 栈顶元素为负值
+ 当前元素为正值
+ 当栈顶元素为正值 当前元素为负值时需要碰撞
+ 比较对应的绝对值

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack=new Stack<Integer>();
        for(int i=0;i<asteroids.length;){
            if(stack.isEmpty()||stack.peek()<0||asteroids[i]>0){
                stack.push(asteroids[i]);
            }else if(stack.peek()<=-asteroids[i]){//将栈顶元素出栈，继续比较
                if(stack.pop()<-asteroids[i]){//如果相等不需要继续比较
                    continue;
                }
            }
            i++;
        }
        int[] res=new int[stack.size()];
        for(int i=res.length-1;i>=0;i--){
            res[i]=stack.pop();
        }
        return res;
    }
}