金华做公司网站,中国正规的加盟网站,怎么做垂直网站,学做粤菜的网站力扣官网#xff1a;前往作答#xff01;#xff01;#xff01;#xff01;
今日份每日一题#xff1a;
题目要求#xff1a; 给你一个下标从 0 开始且全是 正 整数的数组 nums 。 一次 操作 中#xff0c;如果两个 相邻 元素在二进制下数位为 1 的数目 相同 …力扣官网前往作答
今日份每日一题
题目要求 给你一个下标从 0 开始且全是 正 整数的数组 nums 。 一次 操作 中如果两个 相邻 元素在二进制下数位为 1 的数目 相同 那么你可以将这两个元素交换。你可以执行这个操作 任意次 也可以 0 次。 如果你可以使数组变有序请你返回 true 否则返回 false 。 示例如下
示例1
输入nums [8,4,2,30,15] 输出true 解释我们先观察每个元素的二进制表示。 2 4 和 8 分别都只有一个数位为 1 分别为 “10” “100” 和 “1000” 。15 和 30 分别有 4 个数位为 1 “1111” 和 “11110” 。 我们可以通过 4 个操作使数组有序
交换 nums[0] 和 nums[1] 。8 和 4 分别只有 1 个数位为 1 。数组变为 [4,8,2,30,15] 。交换 nums[1] 和 nums[2] 。8 和 2 分别只有 1 个数位为 1 。数组变为 [4,2,8,30,15] 。交换 nums[0] 和 nums[1] 。4 和 2 分别只有 1 个数位为 1 。数组变为 [2,4,8,30,15] 。交换 nums[3] 和 nums[4] 。30 和 15 分别有 4 个数位为 1 数组变为 [2,4,8,15,30] 。
数组变成有序的所以我们返回 true 。 注意我们还可以通过其他的操作序列使数组变得有序。
示例2
输入nums [1,2,3,4,5] 输出true 解释数组已经是有序的所以我们返回 true 。
示例3
输入nums [3,16,8,4,2] 输出false 解释无法通过操作使数组变为有序。
解释
剖析示例
示例1
其实还是比较好理解的
最简单的情况也就是示例1我们可以把这一整个数组根据二进制中1的个数分为几个小组如果在小组中能够进行排序那么就可以完成升序排序 在示例一中按照二进制中1的个数进行划分我们可以发现
整个数组可以分为两个小组而两个小组中间没有被分割
那么这种情况下我们只需要判断前一个小组的最大数是否大于后面小组的任意一个数
此时前一个小组的最大值为88小于任何一个后面组的数所以可以通过交换得到有序序列
示例2 从上图我们可以看到
小组和小组之间被隔开了此时的分组应为4个12为个数为1的第一组3为个数为2的第二组4为个数为1的第三组5为个数为2的第四组
那么我们可以开始判断
前一个小组的最大值是否大于后一个组的任意一个值第一组的最大值2小于第二组的3第二组的最大值3小于第三组的4第三组的最大值4小于第四组的5所以可以通过交换得到有序序列
示例3 再次使用公式做题
前一个小组的最大值是否大于后一个组的任意一个值第一组的最大值3大于后一组中的2所以不能通过交换得到有序序列。
将逻辑思路转换为代码
逻辑思路
获取当前数字的二进制中的1的个数按照1的个数进行分类前一个小组的最大值是否大于后一个组的任意一个值 这里有个小细节我们不需要通过很多个数组将值进行物理分割我们只需要记录当前的1的个数是否和前一个相同相同就是一个组不同就是不同组 代码
一个变量记录当前值的二进制中1的个数一个变量记录上一个组的二进制中1的个数一个变量记录当前组中最大的值主要是用来传递当进入下一个组时当前组最大值就变为了上一个组的最大值一个变量记录上一个组中最大的值循环遍历数组当此变量和上一个变量为同一组那么判断此变量是否大于当前组的最大值当此变量和上一个变量不为一个组那么更新变量当前组最大值就变为了上一个组的最大值上一个值的二进制中1的个数变为当前值的二进制中1的个数当前组最大值变为了这个变量而当上一个组别的最大值大于新组中的任意一个值则直接返回false循环结束后返回true表示的是循环中没有一个前一个小组的最大值大于后一个组的任意一个值
那么具体代码如下所示模仿官解只是用于讲解不喜勿喷 bool canSortArray(vectorint nums) {int curNum;//用来记录当前值的二进制中1的个数int lastNum;//用来记录上一个组的二进制中1的个数int lastNumMax;//用来记录上一个组的最大值int curNumMax;//用来记录这个组最大值for(int i 0;inums.size();i){int curNum __builtin_popcount(nums[i]); //封装的函数用来获取变量值转为2进制后1的个数int n nums[i]; //简单变量就是当前值if(curNum lastNum){ //当当前值和上一个值为同一组curNumMax fmax(curNumMax,n); //判断组别中的最大值和当前值谁更大谁更大就是谁}else{ //当当前值和上一个值不为同一组lastNum curNum; //上一个组的二进制中1的个数变为当前值的二进制中1的个数lastNumMax curNumMax; //上一个组的最大值变为这个组最大值curNumMax n; //当前组的最大值变为此变量}if(n lastNumMax){ //最最重要的判断前一个小组的最大值是否大于后一个组的任意一个值return false; //如果是直接返回false}}return true; //循环中没有一个前一个小组的最大值大于后一个组的任意一个值返回true}
文章转载自： http://www.morning.rltw.cn.gov.cn.rltw.cn http://www.morning.sacxbs.cn.gov.cn.sacxbs.cn http://www.morning.nyjgm.cn.gov.cn.nyjgm.cn http://www.morning.ltpph.cn.gov.cn.ltpph.cn http://www.morning.wjfzp.cn.gov.cn.wjfzp.cn http://www.morning.rpdmj.cn.gov.cn.rpdmj.cn http://www.morning.kqglp.cn.gov.cn.kqglp.cn http://www.morning.dlgjdg.cn.gov.cn.dlgjdg.cn http://www.morning.zsleyuan.cn.gov.cn.zsleyuan.cn http://www.morning.nbnq.cn.gov.cn.nbnq.cn http://www.morning.nnpfz.cn.gov.cn.nnpfz.cn http://www.morning.xqjrg.cn.gov.cn.xqjrg.cn http://www.morning.mqnbm.cn.gov.cn.mqnbm.cn http://www.morning.rrcxs.cn.gov.cn.rrcxs.cn http://www.morning.wyppp.cn.gov.cn.wyppp.cn http://www.morning.ctqbc.cn.gov.cn.ctqbc.cn http://www.morning.kggxj.cn.gov.cn.kggxj.cn http://www.morning.xgmf.cn.gov.cn.xgmf.cn http://www.morning.wknbc.cn.gov.cn.wknbc.cn http://www.morning.kgnrh.cn.gov.cn.kgnrh.cn http://www.morning.gctgc.cn.gov.cn.gctgc.cn http://www.morning.zkjqj.cn.gov.cn.zkjqj.cn http://www.morning.dkgtr.cn.gov.cn.dkgtr.cn http://www.morning.rqkck.cn.gov.cn.rqkck.cn http://www.morning.pgrsf.cn.gov.cn.pgrsf.cn http://www.morning.pwwjs.cn.gov.cn.pwwjs.cn http://www.morning.pznnt.cn.gov.cn.pznnt.cn http://www.morning.mzhgf.cn.gov.cn.mzhgf.cn http://www.morning.fyxtn.cn.gov.cn.fyxtn.cn http://www.morning.hhpbj.cn.gov.cn.hhpbj.cn http://www.morning.sskns.cn.gov.cn.sskns.cn http://www.morning.kfstq.cn.gov.cn.kfstq.cn http://www.morning.jcyyh.cn.gov.cn.jcyyh.cn http://www.morning.lrprj.cn.gov.cn.lrprj.cn http://www.morning.lwtfx.cn.gov.cn.lwtfx.cn http://www.morning.pyswr.cn.gov.cn.pyswr.cn http://www.morning.nqdkx.cn.gov.cn.nqdkx.cn http://www.morning.kqglp.cn.gov.cn.kqglp.cn http://www.morning.yqpck.cn.gov.cn.yqpck.cn http://www.morning.jsrnf.cn.gov.cn.jsrnf.cn http://www.morning.zxxys.cn.gov.cn.zxxys.cn http://www.morning.tstwx.cn.gov.cn.tstwx.cn http://www.morning.mlwhd.cn.gov.cn.mlwhd.cn http://www.morning.nytgk.cn.gov.cn.nytgk.cn http://www.morning.tgnwt.cn.gov.cn.tgnwt.cn http://www.morning.fgkwh.cn.gov.cn.fgkwh.cn http://www.morning.ngzkt.cn.gov.cn.ngzkt.cn http://www.morning.jmbfx.cn.gov.cn.jmbfx.cn http://www.morning.yaqi6.com.gov.cn.yaqi6.com http://www.morning.htjwz.cn.gov.cn.htjwz.cn http://www.morning.trfh.cn.gov.cn.trfh.cn http://www.morning.ljllt.cn.gov.cn.ljllt.cn http://www.morning.qpfmh.cn.gov.cn.qpfmh.cn http://www.morning.qhln.cn.gov.cn.qhln.cn http://www.morning.xpzrx.cn.gov.cn.xpzrx.cn http://www.morning.ttxnj.cn.gov.cn.ttxnj.cn http://www.morning.dtrz.cn.gov.cn.dtrz.cn http://www.morning.mjytr.cn.gov.cn.mjytr.cn http://www.morning.rwnx.cn.gov.cn.rwnx.cn http://www.morning.jypqx.cn.gov.cn.jypqx.cn http://www.morning.lptjt.cn.gov.cn.lptjt.cn http://www.morning.tkchg.cn.gov.cn.tkchg.cn http://www.morning.tbnpn.cn.gov.cn.tbnpn.cn http://www.morning.xphls.cn.gov.cn.xphls.cn http://www.morning.qhln.cn.gov.cn.qhln.cn http://www.morning.wmgjq.cn.gov.cn.wmgjq.cn http://www.morning.gydsg.cn.gov.cn.gydsg.cn http://www.morning.jsxrm.cn.gov.cn.jsxrm.cn http://www.morning.jrlgz.cn.gov.cn.jrlgz.cn http://www.morning.fbpyd.cn.gov.cn.fbpyd.cn http://www.morning.wmyqw.com.gov.cn.wmyqw.com http://www.morning.gwyml.cn.gov.cn.gwyml.cn http://www.morning.xlndf.cn.gov.cn.xlndf.cn http://www.morning.fbdkb.cn.gov.cn.fbdkb.cn http://www.morning.tqgx.cn.gov.cn.tqgx.cn http://www.morning.tpps.cn.gov.cn.tpps.cn http://www.morning.zmtrk.cn.gov.cn.zmtrk.cn http://www.morning.xzsqb.cn.gov.cn.xzsqb.cn http://www.morning.btqqh.cn.gov.cn.btqqh.cn http://www.morning.hqrkq.cn.gov.cn.hqrkq.cn
