大家好,又见面了,我是全栈君。
题目:
Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011
, so the function should return 3.
Credits: Special thanks to @ts for adding this problem and creating all test cases.
解法一:
此题关键是怎样推断一个数字的第i为是否为0 即: x& (1<<i)
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
for(int i = 0; i < 32; i++){
if((n & (1<<i)) != 0)count++;
}
return count;
}
};
解法二:此解关键在于明确n&(n-1)会n最后一位1消除,这样循环下去就能够求出n的位数中为1的个数
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while(n > 0){
n &= n-1;
count ++;
}
return count;
}
};
二: Bitwise AND of Numbers Range
题目:
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.
分析:此题提供两种解法:1:当m到n之前假设跨过了1,2,4,8等2^i次方的数字时(即推断m与n是否具有同样的最高位),则会为0,否则顺序将m到n相与。
解法二:利用上题中的思路。n&(n-1)会消除n中最后一个1,如1100000100当与n-1按位与时便会消除最后一个1,赋值给n(这样就减免了非常多不必要按位与的过程)
解法一:
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int bitm = 0, bitn = 0;
for(int i =0; i < 31; i++){
if(m & (1<<i))bitm = i;
if(n & (1<<i))bitn = i;
}
if(bitm == bitn){
int sum = m;
for(int i = m; i < n; i++) // 为了防止 2147483647+1 超过范围
sum = (sum & i);
sum = (sum & n);
return sum;
}
else return 0;
}
};
解法二:
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
while(n > m){
n &= n-1;
}
return n;
}
};
三: Happy Number
题目:
Write an algorithm to determine if a number is “happy”.
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example: 19 is a happy number
分析:此题关键是用一个set或者map来存储该数字是否已经出现过————hash_map+math
class Solution {
public:
bool isHappy(int n) {
while(n != 1){
if(hset.count(n)) return false; // 通过hashtable 推断是否出现过
hset.insert(n);
int sum = 0;
while(n != 0){ // 求元素的各个位置平方和
int mod = n%10;
n = n/10;
sum += mod * mod;
}
n = sum;
}
return true;
}
private:
set<int> hset;
};
题目:
Given an array of integers, every element appears twice except for one. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
分析:此题关键在于用到异或
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for(int i = 0; i < nums.size(); i++)
ans ^= nums[i];
return ans;
}
};
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/115212.html原文链接:https://javaforall.cn