厦门做网站维护的公司,网站架构基本知识,wordpress健身模版,可以做微课ppt模板 网站有哪些内容2560. 打家劫舍 IV 沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。 由于相邻的房屋装有相互连通的防盗系统#xff0c;所以小偷 不会窃取相邻的房屋 。 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。…
2560. 打家劫舍 IV 沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。 由于相邻的房屋装有相互连通的防盗系统所以小偷 不会窃取相邻的房屋 。 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。 给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上从左起第 i 间房屋中放有 nums[i] 美元。 另给你一个整数 k 表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。 返回小偷的 最小 窃取能力。 示例 1 输入nums [2,3,5,9], k 2
输出5
解释
小偷窃取至少 2 间房屋共有 3 种方式
- 窃取下标 0 和 2 处的房屋窃取能力为 max(nums[0], nums[2]) 5 。
- 窃取下标 0 和 3 处的房屋窃取能力为 max(nums[0], nums[3]) 9 。
- 窃取下标 1 和 3 处的房屋窃取能力为 max(nums[1], nums[3]) 9 。
因此返回 min(5, 9, 9) 5 。示例 2 输入nums [2,7,9,3,1], k 2
输出2
解释共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) 2 。 思路 这个解法使用了二分查找的思想来确定最小窃取能力的范围。 首先通过min_element和max_element函数找到数组nums中的最小值和最大值分别存储在min和max中。 然后在while循环中进行二分查找。每次选取最小值和最大值的中间值num作为当前的窃取能力。 接下来遍历数组nums判断是否可以窃取其中的房屋。使用num1标记上一个房屋是否被窃取const1记录窃取的数量。 如果当前房屋的现金金额小于num并且上一个房屋没有被窃取则将const1增加1并将num1设置为true表示该房屋被窃取。 如果当前房屋的现金金额大于等于num则将num1设置为false表示该房屋未被窃取。 完成数组遍历后比较const1与目标窃取的房屋数量k。如果const1小于k则说明窃取能力太低需要增加窃取能力更新minnum1否则说明窃取能力过高需要减小窃取能力更新maxnum-1。 当min大于max时循环结束结果即为最大窃取能力max。 代码
class Solution {
public:int minCapability(vectorint nums, int k) {// 找到数组中的最小值和最大值int min *min_element(nums.begin(), nums.end());int max *max_element(nums.begin(), nums.end());// 二分查找while (min max) {int num (min max) / 2; // 当前窃取能力bool num1 false; // 上一个房屋是否被窃取int const1 0; // 窃取的数量for (int i 0; i nums.size(); i) {if (nums[i] num !num1) {const1;num1 true;} else {num1 false;}}if (const1 k) {min num 1; // 窃取能力过低增加窃取能力} else {max num - 1; // 窃取能力过高减小窃取能力}}return max; // 返回最大窃取能力}
};
