栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【LeetCode】位运算篇

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【LeetCode】位运算篇

文章目录
  • 逻辑运算符
    • 与
    • 或
    • 异或
  • 撸码时间
    • 1、191. 位1的个数
    • 2、461. 汉明距离
    • 3、136. 只出现一次的数字

传送门难度
191. 位1的个数简单
461. 汉明距离简单
136. 只出现一次的数字简单
逻辑运算符 与

在java中,与运算符为&,其运算规则如下。

0 & 00 & 11 & 01 & 1
0001

即全1为1,否则为0

或

在java中,与运算符为|,其运算规则如下。

0 或 00 或 11 或 01 或 1
0111

即有1为1,否则为0

异或

在java中,异或运算符为^,其运算规则如下。

0 ^ 00 ^ 11 ^ 01 ^ 1
0110

即相同为0,不同为1。

撸码时间 1、191. 位1的个数

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

示例:

输入:11
输出:3
解释:输入的11的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。
输入:128
输出:1
解释:输入的128的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

解法:与运算
思路:由于int型是32位,每次将n与1进行与运算,结果为1则count++,然后将n右移1位继续。

public int hammingWeight(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        if ((n & 1) == 1) {
            count++;
        }
        n = n >> 1;
    }
    return count;
}
2、461. 汉明距离

题目描述:
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y,计算并返回它们之间的汉明距离。

解法1:与
思路:分别x和y的二进制位,不同则count++

public int hammingDistance(int x, int y) {
   int count = 0;
   for (int i = 0; i < 32; i++) {
       if ((x&1)!=(y&1)){
           count++;
       }
       x = x>>1;
       y = y>>1;
   }
   return count;
}

解法2:异或
思路:由于汉明距离对应二进制位不同的数目,而异或正好是不同为1,将x和y异或之后,就变相等于191.位1的个数这一题。

public int hammingDistance(int x, int y) {
    int count = 0;
    int z = x^y;
    for (int i = 0; i < 32; i++) {
        if ((z&1)==1){
            count++;
       }
        z = z>>1;
    }
    return count;
}
3、136. 只出现一次的数字

题目描述:
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

解法
本来有挺多方法去解的,数组、map等等,但是看到说明后,突然懵了…

思路:
这是一个非常巧妙的解法,利用异或的思想,两个相同的数异或为0,0异或任何一个数等于它本身,并且异或满足交换律。即a^b^a = a^a^b = b。而本题正好每个元素都出现两次,只有一个元素出现了一次,那么遍历数组,异或最终结果就是只出现一次的那个数。

public int singleNumber(int[] nums) {
    int num = nums[0];
    for (int i = 1; i < nums.length; i++) {
        num = num^nums[i];
    }
    return num;
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/940830.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号