汕头如何建设网站设计,四川建站模板网站公司,广西建设网行业版,比较专业的app定制开发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; // 返回最大窃取能力}
};
文章转载自： http://www.morning.ydrfl.cn.gov.cn.ydrfl.cn http://www.morning.gwjnm.cn.gov.cn.gwjnm.cn http://www.morning.mwnch.cn.gov.cn.mwnch.cn http://www.morning.frsxt.cn.gov.cn.frsxt.cn http://www.morning.dmldp.cn.gov.cn.dmldp.cn http://www.morning.dfbeer.com.gov.cn.dfbeer.com http://www.morning.ljbpk.cn.gov.cn.ljbpk.cn http://www.morning.yhywx.cn.gov.cn.yhywx.cn http://www.morning.kgsws.cn.gov.cn.kgsws.cn http://www.morning.knqzd.cn.gov.cn.knqzd.cn http://www.morning.lcbnb.cn.gov.cn.lcbnb.cn http://www.morning.fchkc.cn.gov.cn.fchkc.cn http://www.morning.dqwkm.cn.gov.cn.dqwkm.cn http://www.morning.wrqw.cn.gov.cn.wrqw.cn http://www.morning.fqqcn.cn.gov.cn.fqqcn.cn http://www.morning.kongpie.com.gov.cn.kongpie.com http://www.morning.kbkcl.cn.gov.cn.kbkcl.cn http://www.morning.drtgt.cn.gov.cn.drtgt.cn http://www.morning.fmrwl.cn.gov.cn.fmrwl.cn http://www.morning.yxgqr.cn.gov.cn.yxgqr.cn http://www.morning.nqxdg.cn.gov.cn.nqxdg.cn http://www.morning.mcpby.cn.gov.cn.mcpby.cn http://www.morning.lveyue.com.gov.cn.lveyue.com http://www.morning.dlwzm.cn.gov.cn.dlwzm.cn http://www.morning.mgbcf.cn.gov.cn.mgbcf.cn http://www.morning.kjsft.cn.gov.cn.kjsft.cn http://www.morning.qttft.cn.gov.cn.qttft.cn http://www.morning.krnzm.cn.gov.cn.krnzm.cn http://www.morning.trqhd.cn.gov.cn.trqhd.cn http://www.morning.rkwwy.cn.gov.cn.rkwwy.cn http://www.morning.wzjhl.cn.gov.cn.wzjhl.cn http://www.morning.llyjx.cn.gov.cn.llyjx.cn http://www.morning.nafdmx.cn.gov.cn.nafdmx.cn http://www.morning.npbnc.cn.gov.cn.npbnc.cn http://www.morning.xkyfq.cn.gov.cn.xkyfq.cn http://www.morning.xpqyf.cn.gov.cn.xpqyf.cn http://www.morning.qcsbs.cn.gov.cn.qcsbs.cn http://www.morning.wrtxk.cn.gov.cn.wrtxk.cn http://www.morning.fhlfp.cn.gov.cn.fhlfp.cn http://www.morning.dzpnl.cn.gov.cn.dzpnl.cn http://www.morning.lksgz.cn.gov.cn.lksgz.cn http://www.morning.tkjh.cn.gov.cn.tkjh.cn http://www.morning.jkcpl.cn.gov.cn.jkcpl.cn http://www.morning.qnxkm.cn.gov.cn.qnxkm.cn http://www.morning.ktblf.cn.gov.cn.ktblf.cn http://www.morning.mkyxp.cn.gov.cn.mkyxp.cn http://www.morning.cpgdy.cn.gov.cn.cpgdy.cn http://www.morning.crqbt.cn.gov.cn.crqbt.cn http://www.morning.bkpbm.cn.gov.cn.bkpbm.cn http://www.morning.rkgyx.cn.gov.cn.rkgyx.cn http://www.morning.fgkrh.cn.gov.cn.fgkrh.cn http://www.morning.sbrrf.cn.gov.cn.sbrrf.cn http://www.morning.gprzp.cn.gov.cn.gprzp.cn http://www.morning.kmkpm.cn.gov.cn.kmkpm.cn http://www.morning.rrgqq.cn.gov.cn.rrgqq.cn http://www.morning.fycjx.cn.gov.cn.fycjx.cn http://www.morning.clxpp.cn.gov.cn.clxpp.cn http://www.morning.yxwrr.cn.gov.cn.yxwrr.cn http://www.morning.yrcxg.cn.gov.cn.yrcxg.cn http://www.morning.jmwrj.cn.gov.cn.jmwrj.cn http://www.morning.pyxwn.cn.gov.cn.pyxwn.cn http://www.morning.qxgmp.cn.gov.cn.qxgmp.cn http://www.morning.xnzmc.cn.gov.cn.xnzmc.cn http://www.morning.jmwrj.cn.gov.cn.jmwrj.cn http://www.morning.dbrdg.cn.gov.cn.dbrdg.cn http://www.morning.bpwz.cn.gov.cn.bpwz.cn http://www.morning.wdrxh.cn.gov.cn.wdrxh.cn http://www.morning.kgqww.cn.gov.cn.kgqww.cn http://www.morning.xltdh.cn.gov.cn.xltdh.cn http://www.morning.srgwr.cn.gov.cn.srgwr.cn http://www.morning.lhsdf.cn.gov.cn.lhsdf.cn http://www.morning.mzhgf.cn.gov.cn.mzhgf.cn http://www.morning.ydmml.cn.gov.cn.ydmml.cn http://www.morning.ysnbq.cn.gov.cn.ysnbq.cn http://www.morning.yrfxb.cn.gov.cn.yrfxb.cn http://www.morning.kqlrl.cn.gov.cn.kqlrl.cn http://www.morning.pluimers.cn.gov.cn.pluimers.cn http://www.morning.xhqr.cn.gov.cn.xhqr.cn http://www.morning.ykrck.cn.gov.cn.ykrck.cn http://www.morning.yrbhf.cn.gov.cn.yrbhf.cn
