2020-02-16

94.二叉树的中序遍历

image

递归算法：(使用addAll函数，连接子list)


class Solution {

    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> list = new ArrayList<>();

        //Base Case

        if(root==null){

            return list;

        }

        else{

        //遍历左孩子

        list.addAll(inorderTraversal(root.left));

        //根节点

        list.add(root.val);

        //遍历右孩子

        list.addAll(inorderTraversal(root.right));

        return list;

        } 
    }
}

617.合并二叉树

image.png

递归算法：

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        //建立一个新的TreeNode
        TreeNode treeNode = new TreeNode(0);
        if((t1==null)&&(t2==null)){
            return null;
        }else if(t1==null){
             return t2;
        }
        else if(t2==null){
            return t1;
        }else{
             //合并根节点
            treeNode.val =t1.val+t2.val;
            //左子树合并
            treeNode.left = mergeTrees(t1.left,t2.left);
            //右子树合并
            treeNode.right = mergeTrees(t1.right,t2.right);
            return treeNode;
        }
    
    }
}

590.N叉树的后序遍历

image.png

递归算法：

class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> list = new ArrayList<>();
        if (root ==null){
            return list;
        }else{
            for (Node node:root.children){
                list.addAll(postorder(node));
            }
            list.add(root.val);

            return list; 
        }
    
    }
}

559.N叉树的最大深度

image.png

递归算法：

class Solution {
    public int maxDepth(Node root) {
        if(root==null){
            return 0;
        }else{
            int deep=0;
            for (Node node:root.children){
               int current_deep = maxDepth(node);
               if(current_deep>deep){
                   deep=current_deep;
               }
            }
            return deep+1;
        }
    }
}

2020-02-17

100.相同的树

image.png

递归算法：

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null){
            return true;
        }else if(p==null || q==null){
            return false;
        }else if (p.val == q.val){
            if(isSameTree(p.left,q.left)==true && isSameTree(p.right,q.right)==true){
                return true;
            }else{
                return false;
            }
        }else {
            return false;
        }
        
    }
}

101.对称二叉树

image.png

递归算法：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }else return isMirror(root.left,root.right);
        
    }
    public boolean isMirror(TreeNode t1,TreeNode t2){
        if(t1==null && t2==null){
            return true;
        }else if(t1 ==null || t2==null){
            return false;
        }else if(t1.val==t2.val){
            if(isMirror(t1.left,t2.right)==true && isMirror(t1.right,t2.left)==true){
                return true;
            }else {
                return false;
            }
        }else{
            return false;
        }
    }
}

2020-02-18

1302.层数最深叶子点和

image.png

递归算法：

class Solution {
    public int deepestLeavesSum(TreeNode root) {
        if(root==null){
            return 0;
        }else if((root.right==null)&&(root.left==null)){
            return root.val;
        }else if(root.right==null){
            return deepestLeavesSum(root.left);
        }else if(root.left==null){
            return deepestLeavesSum(root.right);
        }
        
        else if(deep(root.left)>deep(root.right)){
            return deepestLeavesSum(root.left);
        }else if(deep(root.right)>deep(root.left)){
           
            return deepestLeavesSum(root.right);
        }else{
            return deepestLeavesSum(root.left)+deepestLeavesSum(root.right);
        }
        
    }
    public int deep(TreeNode root){
        int deep=0;
        if(root==null){
            return 0;
        }else{
            deep = 1+ Math.max(deep(root.left),deep(root.right));
        }
        return deep;
    }
}

2020-02-23

面试题54.二叉搜索树的第k大节点

image.png

递归算法：

class Solution {

    //二叉搜索树 左子树<根<右子树
    //二叉树的中序遍历序列是一个有序的序列
    //java用，size() 获取列表长度
    //list.get() 获取元素
    public int kthLargest(TreeNode root, int k) {
        ArrayList<Integer> list = inorderTraversal(root);
        return list.get(list.size()-k);
    }
    public ArrayList<Integer> inorderTraversal(TreeNode root){
        ArrayList<Integer> list = new ArrayList<>();
        if(root==null){
            return list;
        }else{
            list.addAll(inorderTraversal(root.left)) ;
            list.add(root.val);
            list.addAll(inorderTraversal(root.right));
            return list;
        }
        
    }

}

面试题55-2.平衡二叉树

image.png

递归算法：

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        if (Math.abs(deep(root.left)-deep(root.right))>1){
            return false;
        }
        if(isBalanced(root.left)&&isBalanced(root.right)){
            return true;
        }else{
            return false;
        }


    }
    //寻找一个树的最大深度
    public int deep(TreeNode root){
        if(root==null){
            return 0;
       }
       return Math.max(deep(root.left),deep(root.right))+1;
    }
}

面试题28.对称的二叉树

image.png

递归算法：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        if((root.left==null)&&(root.right==null)){
            return true;
        }
        if((root.left==null)||(root.right==null)){
            return false;
        }else{
            return isMirrior(root.left,root.right);
        }

    }
    public boolean isMirrior(TreeNode t1,TreeNode t2){
        if((t1==null)&&(t2==null)){
            return true;
        }
        if((t1==null)||(t2==null)){
            return false;
        }
        if (t1.val!=t2.val){
            return false;
        }
        if((isMirrior(t1.left,t2.right))&&(isMirrior(t1.right,t2.left))){
            return true;
        }else{
            return false;
        }
    }
}

2020-03-02

面试题07.重建二叉树

image.png

递归算法：

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
       if(preorder==null || inorder==null){
           return null;
       }
       if (preorder.length==0||inorder.length==0){
           return null;
       }
       if(preorder.length!=inorder.length){
           return null;
       }
       TreeNode root =new TreeNode(preorder[0]);
       for(int i=0;i<inorder.length;i++){
           if(inorder[i]==root.val){
            //Arrays.copyOfRange(name,from,to) [from,to) 左闭右开
                root.left = buildTree(Arrays.copyOfRange(preorder,1,i+1),Arrays.copyOfRange(inorder,0,i));

                root.right =buildTree(Arrays.copyOfRange(preorder,i+1,preorder.length),Arrays.copyOfRange(inorder,i+1,inorder.length));
           }
               
       }
       return root;

    }
}

206.反转列表

image.png

递归算法：

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        else{
            ListNode list_node = new ListNode(head.val);
           // reverseList(head.next).next = list_node;
            ListNode p =reverseList(head.next);
            head.next.next = head;
            head.next=null;
             return p;
        }
     
    }
}

2020-03-04

面试题10 II.青蛙跳台阶

image.png

dp数组：

class Solution {
    public int numWays(int n) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        if(n==0){
            return 1;
        }

        if (n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        for(int i=2;i<n;i++){
            list.add((list.get(i-2)+list.get(i-1))%1000000007);
        }
        
        return list.get(n-1)%1000000007;
        

    }
}

面试题10 I.斐波那契

image.png

dp数组：

class Solution {
    public int fib(int n) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(0);
        list.add(1);
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        for(int i=2;i<=n;i++){
            list.add((list.get(i-1)+list.get(i-2))%1000000007);
        }
        return list.get(n)%1000000007;

    }
}

2020-03-05

面试题300 最长上升子序列

image.png

dp数组：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        //dp数组初始化为1
        Arrays.fill(dp,1);
        //第一个for循环是填满dp数组  
        for(int i=0;i<nums.length;i++){
            //第二个for循环是为了计算dp数组的值
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
           
        }
        //for 循环找到最长上升子序列的长度
        int max=0;
        for(int i=0;i<dp.length;i++){
            max = Math.max(max,dp[i]);
        }
        return max;

    }
}

1103 分糖果2

image.png

dp数组：

class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        //存储糖
        int[] dp = new int[num_people];
        Arrays.fill(dp,0);
        //当前已分糖
        int current_candies =0;
        int i=0;
        while(current_candies<candies){
          
            if((current_candies+i+1)<=candies){
                dp[i%num_people]=dp[i%num_people]+ i+1;
                i=i+1;
            }
            else{
                dp[i%num_people]=dp[i%num_people]+ candies-current_candies;
                return dp;
            }
            
            current_candies = current_candies +i;
           

        }
        return dp;

    }
}

面试题42 连续子数组的最大和

image.png

dp数组：

class Solution {
    public int maxSubArray(int[] nums) {
        //dp[i] 存储以nums[i]结尾时子数组和的最大值
        int[] dp = new int[nums.length];
        Arrays.fill(dp,0);
        dp[0]=nums[0];
        int max= dp[0];
        for(int i=1;i<nums.length;i++){
            dp[i] =Math.max(nums[i],dp[i-1]+nums[i]);
            max = Math.max(dp[i],max);
        }
        return max;

    }
}

面试题47 礼物的最大值

image.png

dp数组：

class Solution {
    public int maxValue(int[][] grid) {
        //定义一个二维的dp数组，dp[i][j] 表示走到棋盘上i，j位置的最大价值
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0]=grid[0][0];
        for(int i=1;i<grid[0].length;i++){
            dp[0][i] = grid[0][i]+dp[0][i-1];
        }
        for(int i =1;i<grid.length;i++){
            dp[i][0] = grid[i][0]+dp[i-1][0];
        }
        for(int i=1;i<grid.length;i++){
            for(int j=1;j<grid[0].length;j++){
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[grid.length-1][grid[0].length-1];

    }
}

面试题63 股票的最大利润

image.png

class Solution {
    public int maxProfit(int[] prices) {
        int max=0;
        for(int i=0;i<prices.length;i++){
            for(int j=i;j<prices.length;j++){
                if((prices[j]-prices[i])>0){
                    max = Math.max(max,prices[j]-prices[i]);
                }
               
            }
        }
        return max;

    }
}

2020-03-06

面试题887 鸡蛋掉落

image.png

备忘录：

class Solution {
    HashMap<ArrayList<Integer>,Integer> map = new HashMap();
    public int superEggDrop(int K, int N) {

        if(K==1){
            return N;
        }
        if(N==0){
            return 0;
        }
        int min = N;
        ArrayList<Integer> list = new ArrayList<>();
        list.add(K);
        list.add(N);
        if (map.containsKey(list)){
            return map.get(list);
        }

        for(int i=1;i<=N;i++){
            min =Math.min(min,Math.max(superEggDrop(K-1,i-1),superEggDrop(K,N-i))+1);
        }
        map.put(list,min);
        return min;
    }
}

516 最长回文子序列

image.png

dp数组：

class Solution {
    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length()];
     
        //初始化自己的回文子序列是1
        for(int i=0;i<s.length();i++){
            dp[i][i]=1;
        }
        for(int i=1;i<s.length();i++){
            dp[i][i-1]=0;
        }
        for(int i=s.length()-2;i>=0;i--){
            for(int j=i+1;j<s.length();j++){
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j]=dp[i+1][j-1]+2;
                }
                else{
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }

        }
        return dp[0][s.length()-1];

    }
}

877 石子游戏

image.png

dp数组：

class Solution {
    public boolean stoneGame(int[] piles) {
        //定义dp数组存储 dp[i][j][0] 第i堆和第j堆之间选择石子的话第一个可以得到的最大利润
        int[][][] dp = new int[piles.length][piles.length][2];
        //初始化dp数组为0
        for(int i=0;i<piles.length;i++){
            for(int j=i;j<piles.length;j++){
                for(int k=0;k<2;k++){
                    dp[i][j][k]=0;
                }
            }
        }
        for(int i=0;i<piles.length;i++){
            dp[i][i][0]=piles[i];
            dp[i][i][1] = 0;
        }
        for(int l=1;l<piles.length;l++){
            for(int i=0;i<piles.length-l;i++){
                int j=i+l;
                //选择左边时候石子数目和选择右边时候石子数目
                int left = piles[i]+dp[i+1][j][1];
                int right =piles[j]+dp[i][j-1][1];
                if(left>right){
                    dp[i][j][0]=left;
                    dp[i][j][1]=dp[i+1][j][0];
                }else{
                    dp[i][j][0]=right;
                    dp[i][j][1]=dp[i][j-1][0];
                }
                

            }

        }
        if(dp[0][piles.length-1][0]>dp[0][piles.length-1][1]){
            return true;
        }
        return false;
            
    }
}

122 买卖股票的最佳时机

image.png

dp数组：

class Solution {
    public int maxProfit(int[] prices) {
        int i_0 = 0;
        int i_1 = Integer.MIN_VALUE;
        for(int i=0;i<prices.length;i++){
            i_0 = Math.max(i_0,i_1+prices[i]);
            i_1 = Math.max(i_0-prices[i],i_1);
        }
        return i_0;

    }
}

309 最佳买卖股票时机含冷冻期

image.png

dp数组：

class Solution {
    public int maxProfit(int[] prices) {

        int i_0 = 0;
        int i_1 = Integer.MIN_VALUE;
        int i_2_0 = 0;

        for(int i=0;i<prices.length;i++){
            int temp=i_0;
            i_0 = Math.max(i_0,i_1+prices[i]);
            i_1 = Math.max(i_1,i_2_0-prices[i]);
            i_2_0 = temp;
        }
        return i_0;
    }
}

714 买股票最佳时机含手续费

image.png

dp数组：

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int dp_i_0 = 0;
        int dp_i_1 = Integer.MIN_VALUE;
        for(int i=0;i<prices.length;i++){
            int temp =dp_i_0;
            dp_i_0 = Math.max(dp_i_0,dp_i_1+prices[i]);
            dp_i_1 = Math.max(dp_i_1,temp-prices[i]-fee);
        }
        return dp_i_0;

    }
}

714 买股票最佳时机 III

image.png

dp数组：

class Solution {
    public int maxProfit(int[] prices) {
   

        int dp_i10 = 0, dp_i11 = Integer.MIN_VALUE;
        int dp_i20 = 0, dp_i21 = Integer.MIN_VALUE;


        for(int i=0;i<prices.length;i++){
            dp_i20 = Math.max(dp_i20, dp_i21 + prices[i]);
            dp_i21 = Math.max(dp_i21, dp_i10 - prices[i]);
            dp_i10 = Math.max(dp_i10, dp_i11 + prices[i]);
            dp_i11 = Math.max(dp_i11,-prices[i]);

        }
        return dp_i20;

    }
}

714 买股票最佳时机 iV

image.png

dp数组：

class Solution {
class Solution {
    public int maxProfit(int k, int[] prices) {
         if(k>prices.length/2){
           return maxProfit1(prices);
        }
        //dp数组
        int[][][] dp = new int[prices.length][k+1][2];
        if (prices.length==0){
            return 0;
        }
       

        for(int i=0;i<prices.length;i++){
            for(int j=0;j<=k;j++){
                //处理base case
                if(i==0){
                    dp[i][j][0]=0;
                    dp[i][j][1] = -prices[i];
                    continue;
                }
                else if(j==0){
                    dp[i][j][0] = 0;
                    dp[i][j][1] = Integer.MIN_VALUE;
                    continue;

                }

                dp[i][j][0] =Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
                dp[i][j][1] = Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);


            }   
        }
        return dp[prices.length-1][k][0];

    }
    public int maxProfit1(int[] prices){
                int i_0 = 0;
        int i_1 = Integer.MIN_VALUE;
        for(int i=0;i<prices.length;i++){
            i_0 = Math.max(i_0,i_1+prices[i]);
            i_1 = Math.max(i_0-prices[i],i_1);
        }
        return i_0;

    }



}

198 打家劫舍

image.png

dp数组：

class Solution {
    public int rob(int[] nums) {
        //dp[i] 从第i家开始获得的值
        int[] dp =new int[nums.length];
        if(nums.length==0){
            return 0;
        }
        for(int i=nums.length-1;i>=0;i--){
            if(i>=nums.length-2){
                dp[i]=Math.max(nums[i],nums[nums.length-1]);
                continue;

            }
            dp[i] = Math.max(nums[i]+dp[i+2],dp[i+1]);

        }
        return dp[0];

    }
}

213 打家劫舍II

image.png

dp数组：

class Solution {
    public int rob(int[] nums) {
          if(nums.length==0){
            return 0;
        }
        if(nums.length==1){
            return nums[0];
        }
        int[] dp1 =new int[nums.length-1];
        int[] dp2 = new int[nums.length-1];
      

        for(int i=nums.length-2;i>=0;i--){
            if(i>=nums.length-3){
                dp1[i] = Math.max(nums[i],nums[nums.length-2]);
                dp2[i] = Math.max(nums[i+1],nums[nums.length-1]);
                continue;
            }
            dp1[i] = Math.max(nums[i]+dp1[i+2],dp1[i+1]);
            dp2[i] = Math.max(nums[i+1]+dp2[i+2],dp2[i+1]);



        }
        return Math.max(dp1[0],dp2[0]);

    }
}

213 打家劫舍III

image.png

递归：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return root.val;
        }
        if(root.left==null){
            return Math.max(root.val+rob(root.right.right)+rob(root.right.left),rob(root.left)+rob(root.right));
        }
        if(root.right==null){
            return Math.max(root.val+rob(root.left.left)+rob(root.left.right),rob(root.left)+rob(root.right));
        }
            return Math.max(root.val+rob(root.left.left)+rob(root.right.right)+rob(root.left.right)+rob(root.right.left),rob(root.left)+rob(root.right));
     

    }
}

2020-03-21

746 使用最小花费爬楼梯

image.png

dp数组：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length];
        dp[0] = cost[0];
        if(cost.length>=2){
            dp[1] = cost[1];
        }
        for(int i=2;i<cost.length;i++){
            if(i!=cost.length-1){
                dp[i] = Math.min(cost[i]+dp[i-1],cost[i]+dp[i-2]);
            }
            else{
                dp[i] = Math.min(dp[i-1],cost[i]+dp[i-2]);
            }
        }
        return dp[cost.length-1];

    }
}

面试题 17.16 按摩师

image.png

dp数组：

class Solution {
    public int massage(int[] nums) {
        int[] dp =new int[nums.length];
        if(nums.length==0){
            return 0;
        }
        dp[nums.length-1]=nums[nums.length-1];
        if(nums.length>=2){
            dp[nums.length-2]=Math.max(nums[nums.length-2],dp[nums.length-1]);
            for(int i=nums.length-3;i>=0;i--){
    
                dp[i] = Math.max(nums[i]+dp[i+2],dp[i+1]);
                

            }
        }
        return dp[0];
        
    }
}

64 最小路径和

image.png

dp数组：

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n= grid[0].length;
        int[][] path = new int[m][n];
        if(m==0||n==0){
            return 0;
        }
        path[0][0] = grid[0][0];
        for(int i=1;i<m;i++){
            path[i][0]=path[i-1][0]+grid[i][0];
        }
        for(int i=1;i<n;i++){
            path[0][i] = path[0][i-1]+grid[0][i];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                path[i][j]=Math.min(path[i-1][j],path[i][j-1])+grid[i][j];
            }
        }
        return path[m-1][n-1];


    }
}

2020-04-02

46 全排列

image.png

回溯算法：

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        //定义一个列表 记录路径
        LinkedList<Integer> trace = new LinkedList<>();
        //定义一个列表，记录选择
        LinkedList<Integer> choice = new LinkedList<>();
        for(int i=0;i<nums.length;i++){
            choice.add(nums[i]);
        }
        backtrack(trace,choice);


        return res;
    }
    public void backtrack(LinkedList<Integer> trace_list,LinkedList<Integer> choice_list ){
        if(choice_list.size()==0){
            res.add(new LinkedList(trace_list));
            return ;
        }


        for(int i=0;i<choice_list.size();i++){
            //做选择
            LinkedList choice = new LinkedList<Integer>(choice_list);
            trace_list.add(choice_list.get(i));
            System.out.println(choice.remove(i));
        
            //进入下一层
            backtrack(trace_list,choice);
            //撤销选择
            trace_list.removeLast();
        }
    } 
}

78 子集

image.png

回溯算法：

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        //保存路径
        LinkedList<Integer> trace = new LinkedList<>();
  
        backtrack(nums,0,trace);
        return res;


    }
    public void backtrack(int[] nums,int start,LinkedList<Integer> trace){
        res.add(new LinkedList(trace));
        for(int i =start;i<nums.length;i++){
            
            trace.add(nums[i]);
            backtrack(nums,i+1,trace);
            trace.removeLast();
        }

    }
}

77 组合

image.png

回溯算法：

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        //定义路径
        LinkedList<Integer> trace = new LinkedList<>();
        int[] nums = new int[n];
        for(int i=0;i<n;i++){
            nums[i] = i+1;
        }
        traceback(nums,0,trace,k);
        return res;


    }

    public void traceback(int[] nums,int start , LinkedList<Integer> trace,int k){
        if(trace.size()==k){
            res.add(new LinkedList(trace));
            return ;
        }

        for(int i=start;i<nums.length;i++){
            trace.add(nums[i]);
            traceback(nums,i+1,trace,k);
            trace.removeLast();
            
        }
    }
}

2020-04-04f

面试题08 07 无重复字符串的排列

image.png

回溯算法：

class Solution {
    LinkedList<String> res = new LinkedList<>();
    public String[] permutation(String S) {

        String trace = new String();
        backtrace(S,trace);
        String[] arr = new String[res.size()];
        res.toArray(arr);
        return arr;

    }
    public void backtrace(String str,String trace){
        if(trace.length()== str.length()){
            res.add(trace);
            return;
        }
        for(int i=0;i<str.length();i++){
            if (trace.contains(Character.toString(str.charAt(i)))){
                continue;
            }
              trace = trace + str.charAt(i);
                backtrace(str,trace);
                trace = trace.substring(0,trace.length()-1);
        }
       
              
         
    }
}

2020-04-05

338 比特位计数

image.png

dp数组：

class Solution {
    public int[] countBits(int num) {
        int[] dp =new int[num+1];
        dp[0]=0;
        for(int i=1;i<num+1;i++){
            //奇数一定比偶数多1，偶数1的个数一定和他除以2的个数相同
            if(i%2==0){
                dp[i] = dp[i/2];

            }else{
                dp[i]=dp[i-1]+1;
            }
           
        }
        return dp;

    }
}

221 最大正方形

image.png

dp数组：

class Solution {

    public int maximalSquare(char[][] matrix) {
        if(matrix==null||matrix.length<1||matrix[0].length<1){
            return 0;
        }
        int m = matrix.length;

        int n = matrix[0].length;
        int[][] dp =new int[m][n];
        int max=0;
        //Arrays.fill(dp,0);
        for(int i=0;i<m;i++){
            dp[i][0] = matrix[i][0]-'0';
               max = Math.max(dp[i][0],max);  
        }
        for(int j=0;j<n;j++){
            dp[0][j] = matrix[0][j]-'0';
               max = Math.max(dp[0][j],max);  
        }

  
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){

                if(matrix[i][j]-'0'==1){
                    dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;

                }
                else{
                    dp[i][j]=0;
                }

            max = Math.max(dp[i][j],max);    
           
            }
        }
        return max*max;

    }
}

1277 统计全为1的正方形子矩阵

image.png

dp数组：

class Solution {
    public int countSquares(int[][] matrix) {
        if(matrix==null || matrix.length<0||matrix[0].length<0){
            return 0;
        }

        int m= matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int ans=0;
        for(int i=0;i<m;i++){
            dp[i][0] = matrix[i][0];
            ans =ans + matrix[i][0];
        }
        for(int j=0;j<n;j++){
            dp[0][j] = matrix[0][j];
            ans =ans + matrix[0][j];
        }
        if(matrix[0][0]==1){
            ans = ans -1;
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(matrix[i][j]==1){
                    dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;
                    ans = ans + dp[i][j];
                }
                else{
                    dp[i][j]=0;
                    
                }
            }
        }

        return ans;


    }
}

2020-04-07

37 解数独

image.png

回溯算法：

class Solution {
    public void solveSudoku(char[][] board) {
        if(backtrack(board,0,0)){
            return ;
        }

    }
    public boolean backtrack(char[][] board, int i, int j) {
    int m = 9, n = 9;
    if (j == n) {
        // 穷举到最后一列的话就换到下一行重新开始。
        return backtrack(board, i + 1, 0);
    }
    if (i == m) {
        // 找到一个可行解，触发 base case
        return true;
    }

    if (board[i][j] != '.') {
        // 如果有预设数字，不用我们穷举
        return backtrack(board, i, j + 1);
    } 

    for (char ch = '1'; ch <= '9'; ch++) {
        // 如果遇到不合法的数字，就跳过
        if (!isValid(board, i, j, ch))
            continue;

        board[i][j] = ch;
        // 如果找到一个可行解，立即结束
        if (backtrack(board, i, j + 1)) {
            return true;
        }
        board[i][j] = '.';
    }
    // 穷举完 1~9，依然没有找到可行解，此路不通
    return false;
}

    // 判断 board[i][j] 是否可以填入 n
    public boolean isValid(char[][] board, int r, int c, char n) {
        for (int i = 0; i < 9; i++) {
            // 判断行是否存在重复
            if (board[r][i] == n) return false;
            // 判断列是否存在重复
            if (board[i][c] == n) return false;
            // 判断 3 x 3 方框是否存在重复
            if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)
                return false;
        }
        return true;
}
}

647 回文子串

image.png

dp 数组：

class Solution {
    public int countSubstrings(String s) {
        int[][] dp = new int[s.length()][s.length()];
        int res=0;
        //初始化自己的回文子序列是1
        for(int i=0;i<s.length();i++){
            dp[i][i]=1;
            res = res +1;
        }
        for(int i=1;i<s.length();i++){
            dp[i][i-1]=1;
        }
        for(int i=s.length()-2;i>=0;i--){
            for(int j=i+1;j<s.length();j++){
                if(dp[i+1][j-1]==1){
                    if(s.charAt(i)==s.charAt(j)){
                        dp[i][j]=1;
                        res = res+1;
                    }
                    else{
                        dp[i][j]=0;
                    }
                }else{
                    dp[i][j]=0;
                }
                
            }

        }
        return res;

    }
}

记录我的leetcode刷题

2020-02-16

94.二叉树的中序遍历

617.合并二叉树

590.N叉树的后序遍历

559.N叉树的最大深度

2020-02-17

100.相同的树

101.对称二叉树

2020-02-18

1302.层数最深叶子点和

2020-02-23

面试题54.二叉搜索树的第k大节点

面试题55-2.平衡二叉树

面试题28.对称的二叉树

2020-03-02

面试题07.重建二叉树

206.反转列表

2020-03-04

面试题10 II.青蛙跳台阶

面试题10 I.斐波那契

2020-03-05

面试题300 最长上升子序列

1103 分糖果2

面试题42 连续子数组的最大和

面试题47 礼物的最大值

面试题63 股票的最大利润

2020-03-06

面试题887 鸡蛋掉落

516 最长回文子序列

877 石子游戏

122 买卖股票的最佳时机

309 最佳买卖股票时机含冷冻期

714 买股票最佳时机 含手续费

714 买股票最佳时机 III

714 买股票最佳时机 iV

198 打家劫舍

213 打家劫舍II

213 打家劫舍III

2020-03-21

746 使用最小花费爬楼梯

面试题 17.16 按摩师

64 最小路径和

2020-04-02

46 全排列

78 子集

77 组合

2020-04-04f

**面试题08 07 无重复字符串的排列 **

2020-04-05

338 比特位计数

221 最大正方形

1277 统计全为1的正方形子矩阵

2020-04-07

**37 解数独 **

**647 回文子串 **

推荐阅读更多精彩内容

714 买股票最佳时机含手续费

面试题08 07 无重复字符串的排列

37 解数独

647 回文子串