- 位1的个数 已解答 简单 相关标签 相关企业 编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中 设置位 的个数(也被称为汉明重量)。
示例 1:
输入:n = 11 输出:3 解释:输入的二进制串 1011 中,共有 3 个设置位。 示例 2:
输入:n = 128 输出:1 解释:输入的二进制串 10000000 中,共有 1 个设置位。 示例 3:
输入:n = 2147483645 输出:30 解释:输入的二进制串 11111111111111111111111111111101
中,共有 30 个设置位。
思路:
看清题目因为无符号,所以我们在右移动时用无符号右移。
这个就是先把数和1做&运算(&符号是遇见0变0,所以我们相当于是计算数的最后一位和1的比较,如果是0那么结果为0,如果是1结果为1) ,然后相加记录个数,遍历完一次之后,需要将数无符号右边移动1位,直至循环结束。
class Solution {
public int hammingWeight(int n) {
int index=0;
for(int i=0;i<=32;i++){
index += n & 1;
n >>>=1;
}
return index;
}
}
- 只出现一次的数字
给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
示例 1 :
输入:nums = [2,2,1] 输出:1 示例 2 :
输入:nums = [4,1,2,1,2] 输出:4 示例 3 :
输入:nums = [1] 输出:1
提示:
1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104 除了某个元素只出现一次以外,其余每个元素均出现两次。
看清题目:我们这里使用异或运算,至于为什么,看下图我的解释。
class Solution {
public int singleNumber(int[] nums) {
int s=nums[0];
for(int i=1;i<nums.length;i++){
s = s ^ nums[i];
}
return s;
}
}
一开始我的想法是map来做,没看清题目要求空间复杂度是只使用常量额外空间。
我下面的代码空间复杂度是O(n)
public class Main {
public static void main(String[] args) {
int [] nums ={1,2,3,1,2};
System.out.println(han(nums));
}
public static int han (int[] nums){
HashMap<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
int count=1;
if(map.containsKey(nums[i])){
count++;
}
map.put(nums[i],count);
}
for(int i=0;i<nums.length;i++){
if(map.get(nums[i])==1){
return nums[i];
}
}
return -1;
}
}