leetcode每日一题打卡

746.使用最小花费爬楼梯

2023/12/17

代码

• 解法一

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

• 解法二（优化空间）

class Solution {
   
    public int minCostClimbingStairs(int[] cost) {
   
        int dp1 = 0;
        int dp2 = 0;
        for(int i = 2;i <= cost.length;i++){
   
            int dpi = Math.min(cost[i-1]+dp2,cost[i-2]+dp1);
            dp1 = dp2;
            dp2 = dpi;
        }
        return dp2;
    }
}

分析

• 确定dp数组的含义

  • 到达第i个台阶需要花费的价格为dp[i]

• 确定递推公式

  • 上一个台阶，dp[i] = dp[i-1]+cost[i-1]
  • 上两个台阶，dp[i] = dp[i-2]+cost[i-2]

• 初始化dp

  • 根据题意 第一步不需要花钱所以，dp[0] = 0,dp[1]=0

• 解法二

  • 递推公式本来就是根据cost数组得来的，只需要记录一下前两位的值并且更新就行了。

162.寻找峰值

2023/12/18

代码

• 直接找最大值

class Solution {
   
    public int findPeakElement(int[] nums) {
   
        int maxIndex = 0;
        for(int i = 1;i<nums.length;i++){
   
            if(nums[i] > nums[maxIndex]){
   
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}

• 模拟

class Solution {
   
    public int findPeakElement(int[] nums) {
   
        int n = nums.length;
        for(int i = 0;i < n;i++){
   
            boolean ok = true;
            if(i - 1 >= 0){
   
                if(nums[i-1] >= nums[i]) ok = false;
            }
            if(i + 1 < n){
   
                if(nums[i+1] >= nums[i]) ok = false;
            }
            if(ok) return i;
        }
        return -1;
    }
}

• 二分

class Solution {
   
    public int findPeakElement(int[] nums) {
   
        int l = 0;
        int r = nums.length - 1;
        while(l < r){
   
            int mid = (l+r)/2;
            if(nums[mid] < nums[mid+1]) l = mid + 1;
            else r = mid;
        }
        return r;
    }
}

1901.寻找峰值Ⅱ

2023/12/19

代码

• 暴力

class Solution {
   
    public int[] findPeakGrid(int[][] mat) {
   
        int p = 0,q = 0;
        for(int i = 0;i < mat.length;i++){
   
            for(int j = 0;j < mat[0].length;j++){
   
                if(mat[i][j] > mat[p][q]){
   
                    p = i;
                    q = j;
                }
            }
        }
        return new int[]{
   p,q};
    }
}

• 二分

class Solution {
   
    public int[] findPeakGrid(int[][] mat) {
   
        int m = mat.length,n = mat[0].length;
        int t = 0,b = m - 1;
        int max = 0,k = 0;
        while(t < b){
   
            int mid = (t+b)/2;
            for(int i = 0;i < n;i++){
   
                if(mat[mid][i] > max){
   
                    max = mat[mid][i];
                    k = i;
                }
            }
            if(mat[mid][k] < mat[mid+1][k]) t = mid+1;
            else b = mid;
        }
        for(int j = 0;j < n;j++){
   
            if(mat[b][j] > mat[b][k]){
   
                max = mat[b][j];
                k = j;
            }
        }
        return new int[]{
   b,k};
    }
}

分析

• 二分
  • 上一个峰值问题，我们二分的是数，这次我们二分的是层
  • 定义最上层t和最底层b，就如同上一个峰值问题的左右边界
  • 因为找的峰值必定是每层的最大值，所以定义一个max和k记录值和下标
  • 进入循环，先找到mid层的最大值
  • 再和mid下一层进行比较，改换边界。二分为什么这么写，可看宫水三叶大佬的证明
  • 找到最终的层数mid，遍历找最大值即可。