大家好,又见面了,我是全栈君。
题目:
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
- 12 + 92 = 82
- 82 + 22 = 68
- 62 + 82 = 100
- 12 + 02 + 02 = 1
分析:此题关键是用一个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; } };
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115212.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...