位运算 力扣题目一起练习

位运算基础知识

>、 | 菜鸟教程 (runoob.com)">位运算（&、|、^、~、>>、 | 菜鸟教程 (runoob.com)https://www.runoob.com/w3cnote/bit-operation.html摘选力扣题目136 、137、 260 、645

题目1: 136. 只出现一次的数字https://leetcode-cn.com/problems/single-number/

 代码:

class Solution {
    public int singleNumber(int[] nums) {
        int sn=0;
        //根据异或的性质-自反性 其余元素均出现两次 故全部异或即可
        for(int i=0;i 
结果:
 
 
 
题目2:137. 只出现一次的数字 IIhttps://leetcode-cn.com/problems/single-number-ii/
 
 
代码:
 
class Solution {
    public int singleNumber(int[] nums) {
        int res=0;
        for(int i=0;i<32;i++){
            //从低到高遍历所有位
            int sum=0;
            //遍历数组中所有数
            for(int num:nums){
                //当前位求和 &取某位
                //sum+=(num&(1<>i)&1);
            }
            if(sum%3==1){
                //如果这一位的和模三 有余数 则将余数赋给结果值
                //|令某位置1 因为 对于本题来讲有余数那个单独的数 这位有数 所以就是1了
                res|=(1< 
结果:
 
 
 
 
题目3:260. 只出现一次的数字 IIIhttps://leetcode-cn.com/problems/single-number-iii/
 
 
 
代码:
 
class Solution {
    public int[] singleNumber(int[] nums) {
        int temp=0;
        int flag=0;
        int sn1=0;
        int sn2=0;
        //所有值异或 得到只出现一次的两个数的异或值
        for(int num:nums){
            temp^=num;
        }
        //遍历异或结果 查看两个数具体是哪一位不同
        for(int i=0;i<32;i++){
            //这一位 两数不同了
            if(((temp>>i)&1)==1){
                flag=i;
                break;
            }
        }
        //分两组异或
        for(int num:nums){
            if(((num>>flag)&1)==0){
                sn1^=num;
            }else{
                sn2^=num;
            }
        }
        return new int[]{sn1,sn2};
    }
}
 
结果:
 
 
 
题目4:645. 错误的集合https://leetcode-cn.com/problems/set-mismatch/
 
 
 
代码:
 
class Solution {
    public int[] findErrorNums(int[] nums) {
        int temp=0;
        int flag=1;
        int sn1=0;
        int sn2=0;
        //所有值和1-n一起异或 重复的和丢失的都出现单数次
        //得到重复的和丢失的 两个数的异或值
        for(int i=1;i<=nums.length;i++){
            temp^=nums[i-1];
            temp^=i;
        }
        //遍历异或结果 查看两个数具体是哪一位不同
        while((temp&flag)==0)
            flag<<=1;
        //分两组异或 得到丢失数和重复数
        for(int i=1;i<=nums.length;i++){
            if((nums[i-1]&flag)==0)
                sn1^=nums[i-1];
            else
                sn2^=nums[i-1];  
            if((i&flag)==0)
                sn1^=i;
            else
                sn2^=i;
        }
        //判断哪个数是重复的
        for(int num:nums){
            if(sn1==num)
                return new int[]{sn1,sn2};
        }
        return new int[]{sn2,sn1};
    }
}
 
结果:
 
 
 
 
参考:
 
introduction - 力扣加加 - 努力做西湖区最好的算法题解https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/