社交网站建设教程,icp,网站视频模块配置参数,建立个人博客网站3011. 判断一个数组是否可以变为有序 [题目的“有序”等价于“升序”]
思考
题目要求两个相邻元素在二进制下数位为1的数目相同才可以交换#xff0c;那就要判断1相同的一块是否是按顺序排序的。从大到小和从小到大都测试一遍。找到一块中最大的和最小的#xff0c;放在sta…3011. 判断一个数组是否可以变为有序 [题目的“有序”等价于“升序”]
思考
题目要求两个相邻元素在二进制下数位为1的数目相同才可以交换那就要判断1相同的一块是否是按顺序排序的。从大到小和从小到大都测试一遍。找到一块中最大的和最小的放在stack或者vector里面。
流程是先把num中的1的数量统计成vec之后找出一块中的最大值和最小值放在两个栈里面看是否有序。
计算二进制中一的个数
方法一循环{是否是奇数是就ans1}之后除以2再循环
while (num){if ((num 1) 1)count;num num 1;
}
方法二bitset库自带计算1的个数 bitset9 b(nums[i]); int tpb.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(vectorint nums) {stackinta;int now0;int minn999999999,maxn0;for (int i0;inums.size();i){bitset9 bo(nums[i]);int tpbo.count();if(i0 || tpnow){minnmin(minn,nums[i]);maxnmax(maxn,nums[i]);}else{a.push(minn);a.push(maxn);minnnums[i],maxnnums[i];}nowtp;}a.push(minn);a.push(maxn);int naa.top();a.pop();while(!a.empty()){if(a.top()na){naa.top();a.pop();}else return 0;}return 1;}
};
改进代码
用方法四计算1的个数同时把stack去除
class Solution {
public:bool canSortArray(vectorint 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. 通过操作使数组长度最小
