leetcode每日一题打卡

2023-12-18 06:35:56


从2023年12月17日开始打卡~持续更新

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;
    }
}

文章来源:https://blog.csdn.net/zzz479/article/details/135052874
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。