做家政网上推广网站,建网站找哪家好,赣州营销型网站策划,做侵权视频网站2023-09-19每日一题
一、题目编号
2560. 打家劫舍 IV二、题目链接
点击跳转到题目位置
三、题目描述
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统#xff0c;所以小偷 不会窃取…2023-09-19每日一题
一、题目编号
2560. 打家劫舍 IV二、题目链接
点击跳转到题目位置
三、题目描述
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上从左起第 i 间房屋中放有 nums[i] 美元。
另给你一个整数 k 表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。
返回小偷的 最小 窃取能力。 示例 1
示例 2 提示
1 nums.length 1051 nums[i] 1091 k (nums.length 1)/2
四、解题代码
class Solution {
public:int minCapability(vectorint nums, int k) {int lower *min_element(nums.begin(), nums.end());int upper *max_element(nums.begin(), nums.end());while (lower upper) {int middle (lower upper) / 2;int count 0;bool visited false;for (int x : nums) {if (x middle !visited) {count;visited true;} else {visited false;}}if (count k) {upper middle - 1;} else {lower middle 1;}}return lower;}
};五、解题思路
(1) 使用二分查找。
