位运算

标签：return 运算 nums int Solution public View

1、统计比特数

 1 class Solution {
 2     public int[] countBits(int n) {
 3         int[] ans=new int[n+1];
 4         for(int i=0;i<=n;i++){
 5             int num=i;
 6             int count=0;
 7             while(num>0){
 8                 num=num&(num-1);
 9                 count++;
10             }
11             ans[i]=count;
12         }
13         return ans;
14     }
15 }

View Code

2、颠倒二进制位

 1 public class Solution {
 2     public int reverseBits(int n) {
 3         int ans=0;
 4         int bits=32;
 5         while(bits>0){
 6             ans<<=1;//左移一位
 7             ans+=n&1;//加上n最后一位
 8             n>>=1;//右移一位
 9             bits--;
10         }
11         return ans;
12     }
13 }

View Code

3、判断2进制是否是2的幂

判断1的个数是否为1

1 class Solution {
2     //位运算
3     public boolean isPowerOfTwo(int n) {
4         return n > 0 && (n & (n - 1)) == 0;
5     }
6     
7 }

View Code

4、找缺失的数

1）异或 位运算

1 class Solution {
2     public int missingNumber(int[] nums) {
3         int n = nums.length;
4         int ans = 0;
5         for (int i = 0; i <= n; i++) ans ^= i;
6         for (int i : nums) ans ^= i;
7         return ans;
8     }
9 }

View Code

2）排序，找到i！=num[i]

 1 class Solution {
 2     public int missingNumber(int[] nums) {
 3         int n = nums.length;
 4         Arrays.sort(nums);
 5         for (int i = 0; i < n; i++) {
 6             if (nums[i] != i) return i;
 7         }
 8         return n;
 9     }
10 }

View Code

3）哈希数组

 1 class Solution {
 2     public int missingNumber(int[] nums) {
 3         int n = nums.length;
 4         boolean[] hash = new boolean[n + 1];
 5         for (int i = 0; i < n; i++) hash[nums[i]] = true;
 6         for (int i = 0; i < n; i++) {
 7             if (!hash[i]) return i;
 8         }
 9         return n;
10     }
11 }

View Code

4）作差法，先求出不缺失的等差数列的和，再与得到的实际的和作差

1 class Solution {
2     public int missingNumber(int[] nums) {
3         int n = nums.length;
4         int cur = 0, sum = n * (n + 1) / 2;
5         for (int i : nums) cur += i;
6         return sum - cur;
7     }
8 }

View Code

5、找出两个字符串的不同

异或

 1 class Solution {
 2     public char findTheDifference(String s, String t) {
 3         int ret = 0;
 4         for (int i = 0; i < s.length(); ++i) {
 5             ret ^= s.charAt(i);
 6         }
 7         for (int i = 0; i < t.length(); ++i) {
 8             ret ^= t.charAt(i);
 9         }
10         return (char) ret;
11     }
12 }

View Code

 

 

标签：return,运算,nums,int,Solution,public,View
From： https://www.cnblogs.com/coooookie/p/17491943.html