【算法刷题】Day12_代码007(未授权)

在这里插入图片描述

这是一个二进制数组，里面都是 0 和 1
最多翻转 k 个 0
返回连续 1 的最大个数

这个时候，如果真的一个一个翻转然后判断过于麻烦，我们可以通过判断一个区间内，有没有大于 k 个 0，如果有那就翻转不了，如果没有就可以顺利翻转

这个时候，固定一个起点，然后去枚举终点
用计数器来记住里面 0 的个数（这里用的是zero）
在这里插入图片描述

class Solution {
    public int longestOnes(int[] nums, int k) {
        
        int ret = 0;
        for (int right = 0, left = 0, zero = 0; right &lt; nums.length; right++) {
            if (nums[right] == 0) {
                zero++;
            }
            while (zero &gt; k) {
                if (nums[left++] == 0) {
                    zero--;
                }
            }
            ret = Math.max(ret,right - left + 1);
        }
        return ret;
    }
}

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

显示所有内容

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

个数状态题干

文章 目录

1004. 最大连续1的个数 III

题干：

算法 原理：

1、暴力枚举 + 计数器

2、利用 滑动 窗口

代码：

746. 使用 最小花费爬楼梯

题干：

算法 原理：

解法一：

1.1 状态 表示

1.2 状态转移方程

1.3 初始化

1.4 填表顺序

1.5 返回值

1.6 代码 编写

解法二：

2.1 状态表示

2.2 状态转移方程

2.3 初始化

2.4 填表顺序

2.5 返回值

2.6 代码 编写

总结：

发表回复取消回复

1004. 最大连续1的个数 III

题干：

算法原理：

1、暴力枚举 + 计数器

2、利用滑动窗口

代码：

746. 使用最小花费爬楼梯

题干：

算法原理：

解法一：

1.1 状态表示

1.2 状态转移方程

1.3 初始化

1.4 填表顺序

1.5 返回值

1.6 代码编写

解法二：

2.1 状态表示

2.2 状态转移方程

2.3 初始化

2.4 填表顺序

2.5 返回值

2.6 代码编写

总结：

相关文章

发表回复 取消回复

发表回复取消回复