网站做两个月百度没有录取,做推广哪个平台效果好,狮山做网站,wordpress修改数据库表文章目录 前言一、最大连续1的个数 III 1.1 题目描述 1.2 题目解析 1.2.1 算法原理 1.2.2 代码编写二、将 x 减到 0 的最小操作数 2.1 题目描述 2.2 题目解析 2.2.1 算法原理 2.2.2 代码编写总结 前言
一、最大连… 文章目录 前言一、最大连续1的个数 III 1.1 题目描述 1.2 题目解析 1.2.1 算法原理 1.2.2 代码编写二、将 x 减到 0 的最小操作数 2.1 题目描述 2.2 题目解析 2.2.1 算法原理 2.2.2 代码编写总结 前言
一、最大连续1的个数 III
1.1 题目描述 描述 给定一个二进制数组 nums 和一个整数 k如果可以翻转最多 k 个 0 则返回 数组中连续 1 的最大个数 。 提示 1 nums.length 10^5nums[i] 不是 0 就是 10 k nums.length 示例1 示例2 1.2 题目解析
1.2.1 算法原理无思考 算法思路: 不要去想怎么翻转不要把问题想的很复杂这道题的结果无非就是一段连续的1中间塞了k个0而已 因此我们可以把问题转化成: 求数组中一段最长的连续区间要求这段区间内0的个数不超过k 个。 所以既然是连续区间可以考虑使用「滑动窗口」来解决问题。 解题步骤步骤一 初始化一个大小为2的数组就可以当做哈希表hash了;初始化一些变量 left 0right 0 , ret 0; 步骤二 当right小于数组大小的时候一直进行下列循环: i、让当前元素进入窗口顺便统计到哈希表中;ii、检查的个数是否超标: 如果超标依次让左侧元素滑出窗口顺便更新哈希表的值直到0的个数恢复正常。iii、程序到这里说明窗口内元素是符合要求的更新结果;iv、right处理下一个元素; 步骤三 循环结束后ret存的就是最终结果。 1.2.2 代码编写 二、将 x 减到 0 的最小操作数
2.1 题目描述 描述 给你一个整数数组 nums 和一个整数 x 。每一次操作时你应当移除数组 nums 最左边或最右边的元素然后从 x 中减去该元素的值。请注意需要 修改 数组以供接下来的操作使用。 如果可以将 x 恰好 减到 0 返回 最小操作数 否则返回 -1 。 提示 1 nums.length 10^51 nums[i] 10^41 x 10^9 示例1 示例2 示例3 2.2 题目解析
2.2.1 算法原理无思考 算法思路 题目要求的是数组「左端右端」两段连续的、和为×的最短数组信息量稍微多一些不易理清思路; 我们可以转化成求数组内一段连续的、和为sum(nums) - x的最长数组。 此时就是熟悉的「滑动窗口」问题了。 解题步骤 步骤一 转化问题:求target sum(nums) - ×。如果 target 0问题无解; 步骤二 初始化左右指针l 0,r 0(滑动窗口区间表示为[lr)左右区间是否开闭很重要必须设定与代码一致)记录当前滑动窗口内数组和的变量sum 0记录当前满足条件数组的最大区间长度maxLen -1 ; 步骤三 当r小于等于数组长度时一直循环: 情况i如果sum target右移右指针直至变量和大于等于target或右指针已经移到 头; 情况ii如果sum target右移左指针直至变量和小于等于target或左指针已经移到 头; 情况iii如果经过前两步的左右移动使得sum target维护满足条件数组的最大长度并让下个元素进入窗口; 步骤四 循环结束后如果maxLen的值有意义则计算结果返回;否则返回-1。 2.2.2 代码编写 总结
