剑指10-1 斐波那契数列

  1. class Solution {
  2.     public int fib(int n) {
  3.         int a = 0,b=1,sum;
  4.         for(int i=0;i<n;i++){
  5.             sum = (a+b)%1000000007;
  6.             a=b;
  7.             b=sum;
  8.         }
  9.         return a;
  10.     }
  11. }

leetcode 42 接雨水

  1. // v1.0 时间复杂度O(N^2)
  2. class Solution {
  3.     public int trap(int[] height) {
  4.         // 按列求，每列能接的雨水与左右两侧最高的柱子有关
  5.         int res = 0;
  6.         int len = height.length;
  7.         for(int i=1;i<len-1;i++){
  8.             int leftMax = 0;
  9.             for(int m=0;m<i;m++){
  10.                 if(height[m]>leftMax){
  11.                     leftMax = height[m];
  12.                 }
  13.             }
  14.             int rightMax = 0;
  15.             for(int n=i+1;n<len;n++){
  16.                 if(height[n]>rightMax){
  17.                     rightMax = height[n];
  18.                 }
  19.             }
  20.             int max = Math.min(leftMax, rightMax);
  21.             if(max>height[i]){
  22.                 res += max-height[i];
  23.             }
  24.         }
  25.         return res;
  27.     }
  28. }
  29. // v2.0 动态规划
  30. class Solution {
  31.     public int trap(int[] height) {
  32.         // 动态规划，将左边最高的和右边最高的先求出来，不放在for循环中
  33.         int res = 0;
  34.         int len = height.length;
  35.         if(len<3){
  36.             return 0;
  37.         }
  38.         int[] left = new int[len];
  39.         int[] right = new int[len];
  40.         for(int i = 1;i<len-1;i++){
  41.             left[i] = Math.max(left[i-1],height[i-1]);
  42.         }
  43.         for(int i=len-2;i>=1;i--){
  44.             right[i] = Math.max(right[i+1],height[i+1]);
  45.         }
  46.         for(int i=1;i<len-1;i++){
  47.             int max = Math.min(left[i],right[i]);
  48.             if(max>height[i]){
  49.                 res+=(max-height[i]);
  50.             }
  51.         }
  52.         return res;
  54.     }
  55. }
  57. // v3.0 双指针
  58. class Solution {
  59.     public int trap(int[] height) {
  60.         // 双指针，用常量存储leftMax和rightMax
  61.         // https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/327718
  62.         int res = 0;
  63.         int len = height.length;
  64.         int left = 0, right = len-1;
  65.         int maxLeft = 0, maxRight = 0;
  66.         while(left<=right){
  67.             if(maxLeft<maxRight){
  68.                 res += Math.max(0, maxLeft-height[left]);
  69.                 maxLeft = Math.max(maxLeft, height[left]);
  70.                 left++;
  71.             }else{
  72.                 res +=Math.max(0, maxRight-height[right]);
  73.                 maxRight = Math.max(maxRight, height[right]);
  74.                 right--;
  75.             }
  76.         }
  77.         return res;
  80.     }
  81. }

leetcode 53 最大子序和

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         // f(n) = max{f(n-1)+nums[n],nums[n]}
  4.         int res = -100000;
  5.         int tmp = -100000;
  6.         for(int num:nums){
  7.             tmp = Math.max(tmp+num,num);
  8.             res = Math.max(res, tmp);
  9.         }
  10.         return res;
  11.     }
  12. }

leetcode 62 不同路径

  1. class Solution {
  2.     public int uniquePaths(int m, int n) {
  3.         int[][] res = new int[m][n];
  4.         for(int i=0;i<m;i++){
  5.             for(int j=0;j<n;j++){
  6.                 if(i==0||j==0){
  7.                     res[i][j]=1;
  8.                 }else{
  9.                     res[i][j] = res[i][j-1]+res[i-1][j];
  10.                 }               
  11.             }
  12.         }
  13.         return res[m-1][n-1];
  14.     }
  15. }

leetcode 72 编辑距离

  1. class Solution {
  2.     public int minDistance(String word1, String word2) {
  3.         int firLen = word1.length();
  4.         int secLen = word2.length();
  5.         int[][] matrix = new int[firLen+1][secLen+1];
  6.         for(int i=0;i<firLen+1;i++){
  7.             matrix[i][0] = i;
  8.         }
  9.         for(int i=0;i<secLen+1;i++){
  10.             matrix[0][i] = i;
  11.         }
  12.         for(int m=1;m<firLen+1;m++){
  13.             for(int n=1;n<secLen+1;n++){
  14.                 if(word1.charAt(m-1)==word2.charAt(n-1)){
  15.                     matrix[m][n] = matrix[m-1][n-1];
  16.                 }else{
  17.                     matrix[m][n] = Math.min(Math.min(matrix[m-1][n],matrix[m-1][n-1]),matrix[m][n-1])+1;
  18.                 }
  19.             }
  20.         }
  21.         return matrix[firLen][secLen];
  22.     }
  23. }

leetcode 55 跳跃游戏

  1. class Solution {
  2.     public boolean canJump(int[] nums) {
  3.         // 能跳到的最远位置
  4.         int jumpMax = 0;
  5.         int len = nums.length;
  6.         if(len==1){
  7.             return true;
  8.         }
  9.         for(int i=0;i<nums.length;i++){
  10.             jumpMax = Math.max(jumpMax, i+nums[i]);
  11.             // 能跳到的最远处为当前位置，且当前位置跳跃距离为0时，返回false
  12.             if(jumpMax==i&&nums[i]==0){
  13.                 return false;
  14.             }
  15.             if(jumpMax>=len-1){
  16.                 return true;
  17.             }
  18.         }
  19.         return false;
  20.     }
  21. }

leetcode 198 打家劫舍

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.         int len = nums.length;
  4.         if(len==1){
  5.             return nums[0];
  6.         }
  7.         // 偷窃到第i个房间时，能偷窃到的最高金额只与其前两个房间的金额有关
  8.         int first = nums[0], second = Math.max(nums[0],nums[1]);
  9.         for(int i=2;i<len;i++){
  10.             int tmp = second;
  11.             second = Math.max(second, first+nums[i]);
  12.             first = tmp;
  13.         }
  14.         return second;
  16.     }
  17. }

leetcode 224 最大正方形

  1. class Solution {
  2.     public int maximalSquare(char[][] matrix) {
  3.         int length = matrix[0].length, height = matrix.length;
  4.         int[][] dp = new int[height+1][length+1];
  5.         int maxLen = 0;
  6.         for(int i=0;i<height;i++){
  7.             for(int j=0;j<length;j++){
  8.                 if(matrix[i][j]=='1'){
  9.                     dp[i+1][j+1] = Math.min(Math.min(dp[i][j],dp[i+1][j]),dp[i][j+1])+1;
  10.                     maxLen = Math.max(maxLen, dp[i+1][j+1]);
  11.                 }
  12.             }
  13.         }
  14.         return maxLen*maxLen;
  16.     }
  17. }

leetcode 279 完全平方数

  1. class Solution {
  2.     public int numSquares(int n) {
  3.         int[] dp = new int[n+1];
  4.         int tmp = 1;
  5.         for(int i=1;i<n+1;i++){
  6.             if(i == tmp*tmp){
  7.                 dp[i] = 1;
  8.                 tmp++;
  9.                 continue;
  10.             }
  11.             dp[i] = 4;
  12.             for(int j=tmp-1;j>=1;j--){
  13.                 dp[i] = Math.min(dp[i],dp[j*j]+dp[i-j*j]);
  14.             }
  15.         }
  16.         return dp[n];
  17.     }
  18. }

leetcode 300 最长递增子序列

  1. // v1.0 动态规划 时间复杂度O(N^2)
  2. class Solution {
  3.     public int lengthOfLIS(int[] nums) {
  4.         int len = nums.length;
  5.         if(nums.length<2){
  6.             return 1;
  7.         }
  8.         int res = 1;
  9.         int[] dp = new int[len];
  10.         Arrays.fill(dp,1);
  11.         for(int i=1;i<len;i++){
  12.             for(int j=0;j<i;j++){
  13.                 if(nums[i]>nums[j]){
  14.                     dp[i] = Math.max(dp[i],dp[j]+1);
  16.                 }
  17.             }
  18.             res = Math.max(res, dp[i]);
  19.         }
  20.         return res;
  22.     }
  23. }
  24. // v2.0 二分查找
  25. class Solution {
  26.     public int lengthOfLIS(int[] nums) {
  27.         int res = 0;
  28.         int[] dp = new int[nums.length];
  29.         for(int num:nums){
  30.             int i = 0, j=res;
  31.             while(i<j){
  32.                 int mid = (i+j)>>1;
  33.                 if(dp[mid]<num){
  34.                     i = mid+1;
  35.                 }else{
  36.                     j = mid;
  37.                 }
  38.             }
  39.             dp[j] = num;
  40.             if(j==res) res ++;
  41.         }
  42.         return res;
  44.     }
  45. }

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

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int len = prices.length;
  4.         int[][] dp = new int[3][len];
  5.         // 不手持股票
  6.         dp[0][0] = 0;
  7.         // 手持股票
  8.         dp[1][0] = -prices[0];
  9.         // 冷冻期
  10.         dp[2][0] = 0;
  11.         for(int i=1;i<len;i++){
  12.             // 第i天不手持股票利润最大值(第i-1天不手持股票/第i-1天冷冻期)
  13.             dp[0][i] = Math.max(dp[0][i-1], dp[2][i-1]);
  14.             //  第i天手持股票(第i-1天手持股票/第i-1天不手持股票且为冷冻期)
  15.             dp[1][i] = Math.max(dp[1][i-1], dp[0][i-1]-prices[i]);
  16.             // 第i天为冷冻期
  17.             dp[2][i] = dp[1][i-1]+prices[i];
  18.         }
  19.         return Math.max(dp[0][len-1],dp[2][len-1]);
  20.     }
  21. }

打家劫舍II

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.         int len = nums.length;
  4.         if(len==1) return nums[0];
  5.         //分为两段，分别是0-n-1和1-n
  6.         int a=0;
  7.         int b=nums[0];
  8.         int sum=0;
  9.         for(int i=1;i<len-1;i++){
  10.             sum = Math.max(b,a+nums[i]);
  11.             a=b;
  12.             b=sum;
  13.         }
  14.         int resOne = b;
  15.         a=0;
  16.         b=nums[1];
  17.         sum=0;
  18.         for(int i=2;i<len;i++){
  19.             sum = Math.max(b,a+nums[i]);
  20.             a=b;
  21.             b=sum;
  22.         }
  23.         int resTwo = b;
  24.         return Math.max(resOne,resTwo);
  25.     }
  26. }

leetcode 337 打家劫舍III

  1. class Solution {
  2.     public int rob(TreeNode root) {
  3.         int[] arr = robInternal(root);
  4.         return Math.max(arr[0],arr[1]);
  7.     }
  8.     public int[] robInternal(TreeNode root){
  9.         if(root==null) return new int[2];
  10.         int[] res = new int[2];//res[0]表示偷，res[1]表示不偷
  11.         int[] left = robInternal(root.left);
  12.         int[] right = robInternal(root.right);
  13.         res[0] = left[1]+right[1]+root.val;
  14.         res[1] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);
  15.         return res;
  16.     }
  17. }

leetcode 121 买卖股票的最佳时机

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         // 动态规划 第i天利润最大值等于第i-1天利润和(第i天价格-前i-1天最低价格)中的最大值
  4.         int res = 0;
  5.         int minPrice = prices[0];
  6.         for(int i=1;i<prices.length;i++){
  7.             res = Math.max(res, prices[i]-minPrice);
  8.             minPrice = Math.min(minPrice,prices[i]);
  9.         }
  10.         return res;
  11.     }
  12. }

leetcode122 买卖股票的最佳时机

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int len = prices.length;
  4.         if(len<2){
  5.             return 0;
  6.         }
  7.         int[][] dp = new int[len][2];
  8.         //0表示持有现金，1表示持有股票
  9.         dp[0][0] = 0;
  10.         dp[0][1] = -prices[0];
  11.         for(int i=1;i<len;i++){
  12.             dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
  13.             dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
  14.         }
  15.         return dp[len-1][0];
  16.     }
  17. }

leetcode 416 分割等和子集

  1. //0-1背包问题
  2. class Solution {
  3.     public boolean canPartition(int[] nums) {
  4.         int len = nums.length;
  5.         int sum = 0;
  6.         for(int num:nums){
  7.             sum+=num;
  8.         }
  9.         if((sum&1)==1){
  10.             return false;
  11.         }
  12.         int target = sum>>1;
  13.         boolean[] dp = new boolean[target+1]; //状态压缩为一维数组
  14.         dp[0] = true;
  15.         for(int i=1;i<len;i++){
  16.             //倒序更新
  17.             for(int j=target;j>=nums[i];j--){
  18.                 if(dp[target]==true){
  19.                     return true;
  20.                 }
  21.                 dp[j] = dp[j]||dp[j-nums[i]];
  22.             }
  23.         }
  24.         return dp[target];
  25.     }
  26. }

leetcode 474

  1. class Solution {
  2.     public int findMaxForm(String[] strs, int m, int n) {
  3.         int len = strs.length;
  4.         int[][] dp = new int[m+1][n+1];
  5.         for(int i=1;i<=len;i++){
  6.             int[] countZeroandOne = count(strs[i-1]);
  7.             for(int p=m;p>=countZeroandOne[0];p--){
  8.                 for(int q=n;q>=countZeroandOne[1];q--){
  9.                     dp[p][q] = Math.max(dp[p][q],dp[p-countZeroandOne[0]][q-countZeroandOne[1]]+1);
  10.                 }
  11.             }
  13.         }
  14.         return dp[m][n];
  15.     }
  16.     public int[] count(String str){
  17.         int[] countZeroandOne = new int[2];
  18.         for(int i=0;i<str.length();i++){
  19.             countZeroandOne[str.charAt(i)-'0']++;
  20.         }
  21.         return countZeroandOne;
  22.     }
  23. }

leetcode 152 乘积最大子数组

  1. //imax维护当前子数组最大值，imin维护当前子数组最小值
  2. //遇到负数时，imax和imin互换
  3. class Solution {
  4.     public int maxProduct(int[] nums) {
  5.         int res = Integer.MIN_VALUE;
  6.         int imax=1;
  7.         int imin=1;
  8.         for(int num:nums){
  9.             if(num<0){
  10.                 int temp= imax;
  11.                 imax = imin;
  12.                 imin = temp;
  13.             }
  14.             imax = Math.max(imax*num,num);
  15.             imin = Math.min(imin*num,num);
  16.             res = Math.max(imax,res);
  17.         }
  18.         return res;
  19.     }
  20. }

leetcode 96 不同的二叉搜索树

  1. class Solution {
  2.     public int numTrees(int n) {
  3.         //设值为n时拥有的种数为G(n)，当根节点为1时，左节点为null，右节点有n-1种可能性，
  4.         //当根节点为2时，左节点有n-2种可能性...
  5.         int[] dp = new int[n+1];
  6.         dp[0] = 1;
  7.         dp[1] = 1;
  8.         for(int i=2;i<n+1;i++){
  9.             for(int j=0;j<i;j++){
  10.                 dp[i] += dp[j] * dp[i-1-j];
  11.             }
  12.         }
  13.         return dp[n];
  15.     }
  16. }

以下为背包问题类型：

leetcode 518 零钱兑换II

  1. class Solution {
  2.     public int change(int amount, int[] coins) {
  3.         //完全背包问题
  4.         if(amount==0){
  5.             return 1;
  6.         }
  7.         int[] count = new int[amount+1];
  8.         int len = coins.length;
  9.         for(int i=0;i<len;i++){
  10.             for(int j=coins[i];j<=amount;j++){
  11.                 if(j==coins[i]){
  12.                     count[j]=count[j]+1;
  13.                     continue;
  14.                 }
  15.                 count[j] = count[j]+count[j-coins[i]];
  16.             }
  17.         }
  18.         return count[amount];
  19.     }
  20. }

leetcode 377 组合总数IV

  1. class Solution {
  2.     public int combinationSum4(int[] nums, int target) {
  3.         //完全背包问题
  4.         //dp[m] = dp[m-nums[0]]+dp[m-nums[1]]+...
  6.         int[] dp = new int[target+1];
  7.         dp[0] = 1;//m=nums[i]
  8.         for(int i=1;i<=target;i++){
  9.             for(int num:nums){
  10.                 if(i>=num){
  11.                     dp[i] += dp[i-num];
  12.                 }
  14.             }
  15.         }
  16.         return dp[target];
  17.     }
  18. }

leetcode 494 目标和

  1. class Solution {
  2.     public int findTargetSumWays(int[] nums, int target) {
  3.         // sum(M)-sum(N) = target
  4.         // sum(M)-sum(N)+sum(M)+sum(N) = target+sum
  5.         // ==> sum(M) = (target+sum)/2
  6.         int sum = 0;
  7.         for(int num:nums){
  8.             sum+=num;
  9.         }
  10.         if(((target+sum)&1)==1) return 0;
  11.         int newTarget = (target+sum)>>1;
  12.         if(newTarget<0) return 0;
  13.         int[] dp = new int[newTarget+1];
  14.         dp[0] = 1;
  15.         for(int i=0;i<nums.length;i++){
  16.             for(int j=newTarget;j>=nums[i];j--){
  17.                 dp[j] = dp[j]+dp[j-nums[i]];
  18.             }
  19.         }
  20.         return dp[newTarget];
  21.     }
  22. }