标签: 位运算

LeetCode刷题【剑指 Offer 15】二进制中1的个数

编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为 汉明重量).)。

 

提示:

  • 请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
  • 在 Java 中,编译器使用 二进制补码 记法来表示有符号整数。因此,在上面的 示例 3 中,输入表示有符号整数 -3

 

示例 1:

输入:n = 11 (控制台输入 00000000000000000000000000001011)
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

示例 2:

输入:n = 128 (控制台输入 00000000000000000000000010000000)
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

示例 3:

输入:n = 4294967293 (控制台输入 11111111111111111111111111111101,部分语言中 n = -3)
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。

 

提示:

  • 输入必须是长度为 32二进制串

 

注意:本题与主站 191 题相同:https://leetcode-cn.com/problems/number-of-1-bits/

Related Topics
  • 位运算

  • 👍 255
  • 👎 0
  • 位运算
    简单
    1&1 = 1
    1&0 = 0
    0&0 = 0

    public class Solution {
        // you need to treat n as an unsigned value
        public int hammingWeight(int n) {
            int ans = 0;
            int p = 0;
            while (++p <= 32){
                ans += n & 1;
                n >>= 1;
            }
            return ans;
        }
    }

    LeetCode刷题【1310】子数组异或查询

    有一个正整数数组 arr,现给你一个对应的查询数组 queries,其中 queries[i] = [Li, Ri]

    对于每个查询 i,请你计算从 Li 到 Ri 的 XOR 值(即 arr[Li] xor arr[Li+1] xor ... xor arr[Ri])作为本次查询的结果。

    并返回一个包含给定查询 queries 所有结果的数组。

     

    示例 1:

    输入:arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
    输出:[2,7,14,8] 
    解释:
    数组中元素的二进制表示形式是:
    1 = 0001 
    3 = 0011 
    4 = 0100 
    8 = 1000 
    查询的 XOR 值为:
    [0,1] = 1 xor 3 = 2 
    [1,2] = 3 xor 4 = 7 
    [0,3] = 1 xor 3 xor 4 xor 8 = 14 
    [3,3] = 8
    

    示例 2:

    输入:arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
    输出:[8,0,4,4]
    

     

    提示:

    • 1 <= arr.length <= 3 * 10^4
    • 1 <= arr[i] <= 10^9
    • 1 <= queries.length <= 3 * 10^4
    • queries[i].length == 2
    • 0 <= queries[i][0] <= queries[i][1] < arr.length
    Related Topics
    • 位运算
    • 数组
    • 前缀和

  • 👍 146
  • 👎 0
  • 树状数组
    基本是模板套用,不过思路要转变下

    原本的前缀和套用为异或操作,本质没有改变

    class Solution {
        public int[] xorQueries(int[] arr, int[][] queries) {
            FenwickTree fenwickTree = new FenwickTree(arr.length);
            for (int i = 0; i < arr.length; i++) {
                fenwickTree.add(i+1, arr[i]);
            }
            int[] ans = new int[queries.length];
            for (int i = 0; i < queries.length; i++) {
                ans[i] = fenwickTree.query(queries[i][0]) ^ fenwickTree.query(queries[i][1]+1);
            }
            return ans;
        }
    
        class FenwickTree{
            int[] arr;
    
            public FenwickTree(int n){
                arr = new int[n+1];
            }
    
            public int lowBit(int i){
                return i & ( -i );
            }
    
            public void add(int idx, int num){
                while (idx < arr.length){
                    arr[idx] ^= num;
                    idx += lowBit(idx);
                }
            }
    
            public int query(int idx){
                int res = 0;
                while (idx > 0 ){
                    res ^= arr[idx];
                    idx -= lowBit(idx);
                }
                return res;
            }
        }
    }

    LeetCode刷题【89】格雷编码

    n 位格雷码序列 是一个由 2n 个整数组成的序列,其中:
    • 每个整数都在范围 [0, 2n - 1] 内(含 02n - 1
    • 第一个整数是 0
    • 一个整数在序列中出现 不超过一次
    • 每对 相邻 整数的二进制表示 恰好一位不同 ,且
    • 第一个最后一个 整数的二进制表示 恰好一位不同

    给你一个整数 n ,返回任一有效的 n 位格雷码序列

     

    示例 1:

    输入:n = 2
    输出:[0,1,3,2]
    解释:
    [0,1,3,2] 的二进制表示是 [00,01,11,10] 。
    - 00 和 01 有一位不同
    - 01 和 11 有一位不同
    - 11 和 10 有一位不同
    - 10 和 00 有一位不同
    [0,2,3,1] 也是一个有效的格雷码序列,其二进制表示是 [00,10,11,01] 。
    - 00 和 10 有一位不同
    - 10 和 11 有一位不同
    - 11 和 01 有一位不同
    - 01 和 00 有一位不同
    

    示例 2:

    输入:n = 1
    输出:[0,1]
    

     

    提示:

    • 1 <= n <= 16
    Related Topics
  • 位运算
  • 数学
  • 回溯

  • 👍 509
  • 👎 0
  • 找规律想方法,找到对称关系

    试着先从头开始写几行数据看下吧

       0
       0    1
      00   01   11   10
     000  001  011  010  110  111  101  100
    0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
    1. 只有0的时候,不明显,继续往下看,只有第二行也一样
    2. 第三行,我们先把数字都扩充到2位,之前的变成00, 01,那么剩下的只有11, 10 了此时只有 00 01 11 10这个顺序了,其他的组合情况暂不考虑
    3. 第三行依旧扩充到3位000 001 011 010 ,下一个数字要和010只有一位不同的话只能选择110了,再下一位依旧只能111,这样 101 100
    4. 开始总结规律,可以看到后半部分都是1xx这样的数据了,且如果户管最高位的话,和前面的内容是对称的,即,下标i和下标n - i对应,且下标i的值加1xx(二进制数)等于下标n - i 的值,那么我们基本就总结出规律了
    5. 看第四行,原本前8位数字整体原封不动的保留,同时对应后面对称位置的值为当前位置的值加1000(二进制数)

    稍微总结下

    这个怎么来理解关系呢?我们来缕下 假设数组长度为 2n,(n不等于0,指实际位置从1开始,不是指从0开始的下标)

    1. 从对称的最中间两位开始看,也就是第 nn+1位,这两个数字后面部分是完全一样的,只有头部第一位一个是1 一个是0的区别,相差一位
    2. 再看n-1 和n+2这两个对称位置,拿上面的第四行数据中间部分来说明
      0101 0100 1100 1101
      对应数字为0101和 1101, 因为0101和后面一位0100相差一位,所以同样对称部分的11001101如果忽略头部的1的话和这边其实是一致的也是相差一位,而又因为这两者头部都是加的1是相同的,所以这两者是必然相差一位的即n+1n+2相差的一位是和n-1n相差的一位是一样的
    3. 再往后更多的对称部分和这一步也一样可以推断出是相差一位的

    代码

    class Solution {
        public List<Integer> grayCode(int n) {
            int i = 0;
            int[] list1 = new int[1];
            int[] list2 = new int[2];
            while (++i <=n){
                list2 = new int[1<<i];
                int lastIdx = list1.length * 2 - 1;
                int plus = 1 << (i-1);
                for (int idx = 0; idx < list1.length; idx++) {
                    list2[idx] = list1[idx];
                    list2[lastIdx - idx] =  list1[idx] | plus ;
                }
                list1 = list2;
            }
            List<Integer> r = new ArrayList<>();
            for (int i1 : list2) {
                r.add(i1);
            }
            return r;
        }
    }

    LeetCode刷题【318】最大单词长度乘积

    给你一个字符串数组 words ,找出并返回 length(words[i]) * length(words[j]) 的最大值,并且这两个单词不含有公共字母。如果不存在这样的两个单词,返回 0

     

    示例 1:

    输入:words = ["abcw","baz","foo","bar","xtfn","abcdef"]
    输出:16 
    解释这两个单词为 "abcw", "xtfn"

    示例 2:

    输入:words = ["a","ab","abc","d","cd","bcd","abcd"]
    输出:4 
    解释这两个单词为 "ab", "cd"

    示例 3:

    输入:words = ["a","aa","aaa","aaaa"]
    输出:0 
    解释不存在这样的两个单词。
    

     

    提示:

    • 2 <= words.length <= 1000
    • 1 <= words[i].length <= 1000
    • words[i] 仅包含小写字母
    Related Topics
  • 位运算
  • 数组
  • 字符串

  • 👍 364
  • 👎 0
  • 位运算->哈希,位运算->重复判断

    抄大佬作业,这个我是真想不来

    class Solution {
        public int maxProduct(String[] words) {
            int max = 0;
            int[] arr = new int[words.length];
            for (int i = 0; i < words.length; i++) {
                int h = 0;
                for (int c = 0; c < words[i].length(); c++) {
                    h |= 1 << (words[i].charAt(c) - 'a');
                }
                arr[i] = h;
            }
            for (int i = 0; i < words.length; i++) {
                for (int j = i+1; j < words.length; j++) {
                    if ((arr[i] & arr[j]) != 0){
                        continue;
                    }
                    max = Math.max(max,words[i].length() * words[j].length());
                }
            }
            return max;
        }
    }

    LeetCode刷题【剑指 Offer 56 – II】数组中数字出现的次数 II

    在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。

     

    示例 1:

    输入:nums = [3,4,3,3]
    输出:4
    

    示例 2:

    输入:nums = [9,1,7,9,7,9,7]
    输出:1

     

    限制:

    • 1 <= nums.length <= 10000
    • 1 <= nums[i] < 2^31

     

    Related Topics
  • 位运算
  • 数组

  • 👍 342
  • 👎 0
  • 凑合,记录下没啥参考意义

    class Solution {
        public int singleNumber(int[] nums) {
            int[] arrCount = new int[32];
            for (int num : nums) {
                int idx = 32;
                while (--idx>=0 && num > 0){
                    arrCount[idx] += num%2;
                    num >>= 1;
                }
            }
            int res = 0;
            for (int count : arrCount) {
                res <<= 1;
                res += count%3;
            }
            return res;
        }
    }

    LeetCode刷题【268】丢失的数字

    给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

     

    示例 1:

    输入:nums = [3,0,1]
    输出:2
    解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2 是丢失的数字,因为它没有出现在 nums 中。

    示例 2:

    输入:nums = [0,1]
    输出:2
    解释:n = 2,因为有 2 个数字,所以所有的数字都在范围 [0,2] 内。2 是丢失的数字,因为它没有出现在 nums 中。

    示例 3:

    输入:nums = [9,6,4,2,3,5,7,0,1]
    输出:8
    解释:n = 9,因为有 9 个数字,所以所有的数字都在范围 [0,9] 内。8 是丢失的数字,因为它没有出现在 nums 中。

    示例 4:

    输入:nums = [0]
    输出:1
    解释:n = 1,因为有 1 个数字,所以所有的数字都在范围 [0,1] 内。1 是丢失的数字,因为它没有出现在 nums 中。

     

    提示:

    • n == nums.length
    • 1 <= n <= 104
    • 0 <= nums[i] <= n
    • nums 中的所有数字都 独一无二

     

    进阶:你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

    Related Topics
  • 位运算
  • 数组
  • 哈希表
  • 数学
  • 排序

  • 👍 579
  • 👎 0
  • 异或、求和 & 【看起来没人用的其实也能用的 原地交换 !!】

    都知道的异或、求和先贴下、其他还有哈希表,重构数组遍历等等,没啥好说的了,大家都看很多遍了

    异或
    class Solution {
        public int missingNumber(int[] nums) {
            int num = 0;
            for (int i = 0; i < nums.length; i++) {
                num ^= nums[i];
                num ^= i;
            }
            num ^= nums.length;
            return num;
        }
    }
    
    求和
    class Solution {
    
        public int missingNumber(int[] nums) {
            int num = 0;
            for (int i = 0; i < nums.length; i++) {
                num -= nums[i];
                num += i;
            }
            num += nums.length;
            return num;
        }
    
    }
    

    丢失数字之类的还有一种会用到原地交换的解法

    这里我们其实也可以尝试下。大促晚值班摸鱼,来玩点花样

    原地交换

    跟官方题解写一样缺少乐趣,毕竟是简单题,能玩的花样一遍都比较多,

    拿官方例题来分析下,第一行对应为数组下标,第二行数原始数组,

    1. 如果nums[i] == nums.length原地交换会越界,那么我就声明一个变量用来保存存放在这个位置的数字,这样我们就可以顺利使用原地交换了,毕竟要求时间O(n),空间O(1)
    • 其实你也可以声明一个长度为nums.length+1的数组来处理,这样可以省事,不过空间就不是O(1)
    1. 原来第n位上的数字不存在,那就在代码里用-1表示,图里用x表示
    2. 从0下标开始交换,把0交换给n,此时记录丢失数字为0 ,missing = 0;
    3. 后面从下标1开始交换,一直交换这些比较简单省略,直到到下标1上的值为x了,记录当前丢失数字missing = 1;
    4. 后面继续交换,直到最后下标8上的值为x,记录missing = 8;
    5. 结束

    同时,看下剑指offer03的数组中的重复数字这题,试着用原地交换的方法来理解下,或许对你能有帮助
    【原地交换】图解,看个明白

    原地交换代码
    class Solution {
    
        public int missingNumber(int[] nums) {
            //丢失的
            int misssing = nums.length;
            //额外占用的第nums.length下标位
            int n = -1;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i]==nums.length){
                    n = nums[i];
                    nums[i] = -1;
                }
                while (nums[i] != -1 && nums[i] != i ){
                    swap(nums,i,nums[i]);
                    if (nums[i]==nums.length){
                        n = nums[i];
                        nums[i] = -1;
                    }
                }
                if (nums[i]==-1){
                    misssing = i;
                }
            }
            return misssing;
        }
        
        public void swap(int[] nums, int x, int y){
            int tmp = nums[x];
            nums[x] = nums[y];
            nums[y] = tmp;
        }
    
    }

    LeetCode刷题【476】数字的补数

    对整数的二进制表示取反(0110)后,再转换为十进制表示,可以得到这个整数的补数。

    • 例如,整数 5 的二进制表示是 "101" ,取反后得到 "010" ,再转回十进制表示得到补数 2

    给你一个整数 num ,输出它的补数。

     

    示例 1:

    输入:num = 5
    输出:2
    解释:5 的二进制表示为 101(没有前导零位),其补数为 010。所以你需要输出 2 。
    

    示例 2:

    输入:num = 1
    输出:0
    解释:1 的二进制表示为 1(没有前导零位),其补数为 0。所以你需要输出 0 。
    

     

    提示:

    • 1 <= num < 231

     

    注意:本题与 1009 https://leetcode-cn.com/problems/complement-of-base-10-integer/ 相同

    Related Topics
  • 位运算

  • 👍 294
  • 👎 0
  • 简单做下,不用位运算 & 用位运算

    首先在不用位运算的情况下,我们理清下逻辑

    1. 要取反的话,用当前数字余2,结果为1则取0,结果为0则取1,得到的数字留在当前位置
    2. 然后接下来,对应二进制数往前找一位,我们用除法的除以2来实现,用`num = num /2`
    3. 再次对num值余2,结果为1则取0,结果为0则取1,得到的结果要放在之前(1)中的二进制数前面,那么简单的相应作法把当前数字乘以2再加上(1)的结果,得到一个新的结果
    4. 再次`num = num /2`
    5. 再次对num值余2,结果为1则取0,结果为0则取1,这次得到的结果需要放在(3)的结果前面,那么对应的这次的结果需要乘以2的平方
    6. 依此继续循环
    class Solution {
        public int findComplement(int num) {
            int res = 0;
            int i = 1;
            while ( num > 0){
                res +=  (num%2==0?1:0) * i;
                i *= 2;
                num /= 2;
            }
            return res;
        }
    }

    更进一步

    根据位运算相关规则,我们把上面的代码重新写一遍

    乘以i个2就可以直接改写成左移i次,同时把后面要执行的`i+1`的操作也一并带上的话就变成了`<< i++`

    余2判断奇偶性变成`num&1`,结果再取相反的那么就是`num&1^1`,注意不要使用`~`,这会把原来的1变成`11111111111111111111111111111110`,而0变成`11111111111111111111111111111111`

    而对应的`num = num /2`改为`num = num >> 1`

    class Solution {
    
        /**
         * 与&:0&0=0 0&1=0 1&0=0 1&1=1
         * 或|:0|0=0 0|1=1 1|0=1 1|1=1
         * 异或^:0^0=0 0^1=1 1^0=1 1^1=0
         * 取反~:~1=0 ~0=1
         * 左移<<:左边的二进制位丢弃,右边补0
         * 右移>>:正数左补0,负数左补1,右边丢弃
         * 无符号左移<<<:左边的二进制位丢弃,右边补0
         * 无符号右移>>>:忽略符号位,空位都以0补齐
         * @param num
         * @return
         */
        public int findComplement(int num) {
            int res = 0;
            int i = 0;
            while ( num > 0){
                res += (num&1^1) << i++;
                num = num >> 1;
            }
            return res;
        }
        
    }

    结束收工