本文主要是介绍leetcode做题记录 3011(计算二进制中一的个数)3012,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
3011. 判断一个数组是否可以变为有序 [题目的“有序”等价于“升序”]
思考
题目要求两个相邻元素在二进制下数位为1的数目相同才可以交换,那就要判断1相同的一块是否是按顺序排序的。从大到小和从小到大都测试一遍。找到一块中最大的和最小的,放在stack或者vector里面。
流程是先把num中的1的数量统计成vec,之后找出一块中的最大值和最小值,放在两个栈里面,看是否有序。
计算二进制中一的个数
方法一:循环,{是否是奇数,是就ans+1},之后除以2,再循环
while (num){if ((num & 1) == 1)count++;num = num >> 1;
}
方法二:bitset库自带计算1的个数
bitset<9> b(nums[i]);
int tp=b.count();
方法三:位运算
int count = 0;
while (i){i = i & (i - 1);count++;
}
方法四:__builtin_popcount(nums[i])来算1的个数
代码 12ms 击败67.59%
代码中用方法二来计算1的个数
class Solution {
public:bool canSortArray(vector<int>& nums) {stack<int>a;int now=0;int minn=999999999,maxn=0;for (int i=0;i<nums.size();i++){bitset<9> bo(nums[i]);int tp=bo.count();if(i==0 || tp==now){minn=min(minn,nums[i]);maxn=max(maxn,nums[i]);}else{a.push(minn);a.push(maxn);minn=nums[i],maxn=nums[i];}now=tp;}a.push(minn);a.push(maxn);int na=a.top();a.pop();while(!a.empty()){if(a.top()<=na){na=a.top();a.pop();}else return 0;}return 1;}
};
改进代码
用方法四计算1的个数,同时把stack去除
class Solution {
public:bool canSortArray(vector<int>& nums) {int n = nums.size();int i = 0, pre_max = 0;while (i < n) {int mx = nums[i];int ones = __builtin_popcount(nums[i]);while (i < n && __builtin_popcount(nums[i]) == ones) {if (nums[i] < pre_max) {return false;}mx = max(mx, nums[i++]);}pre_max = mx;}return true;}
};
3012. 通过操作使数组长度最小
这篇关于leetcode做题记录 3011(计算二进制中一的个数)3012的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!