位运算-剑指offer

字数统计: 1.6k字   |   阅读时长: 8分

位运算实现加法

https://www.nowcoder.com/practice/59ac416b4b944300b617d4f7f111b215?tpId=13&tqId=23249&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  1. 不进位加法 异或实现
  2. 只算进位 与运算然后左移
  3. 两部分相加 
    1
    2
    3
    4
    5
    6
    7
    8
    public int Add(int num1,int num2) {
        while (num2 != 0) {
            int carry = (num1 & num2) << 1;
            num1 ^= num2;
            num2 = carry;
        }
        return num1;
    }

二进制数字中1的个数

https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8?tpId=13&tqId=23273&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

测试发现负数在计算机中是以补码的形式存在的，按位与测试也是补码的形式，不过在打印的时候变成了原码形式

1
2
3
4
5
6
7
8
public int NumberOf1(int n) {
    int result = 0;
    for (int i=0; i<32; i++) {
        // 正数右移动补0，负数补1，所以不能通过while(n != 0)的方式循环每次右移一位
        result += n >> i & 1;
    }
    return result;
}

数值的整数次方

https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00?tpId=13&tqId=23277&ru=%2Fpractice%2F59ac416b4b944300b617d4f7f111b215&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 直接思路
    如果exponent小于0，计算结果为

1 / （base^-exponent)

然后考虑base为0时，结果为0，base是浮点数，不能直接比较是否相等，Math.abs(base) <1e-6比较，科学计数法，e分割底数与指数

exponent为0时，结果为1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public double Power(double base, int exponent) {
    if (Math.abs(base) < 1e-6) {
        return 0.0;
    }
    if (exponent == 0) {
        return 1;
    }
    
    if (exponent < 0) {
        double multi = 1;
        for (int i=0; i<-exponent; i++) {
            multi *= base;
        }
        return 1 / multi;
    } else {
        double multi = 1;
        for (int i=0; i<exponent; i++) {
            multi *= base;
        }
        return multi;
    }
}

优化，预处理负数的乘方
图片

result = 1; result *= base;

base = 0时， result 为0；

exponent=0时，不乘方，结果为1，边界情况仍然满足

1
2
3
4
5
6
7
8
9
10
11
public double Power(double base, int exponent) {
    if (exponent < 0) {
        exponent = -exponent;
        base = 1 / base;
    }
    double result = 1;
    for (int i=0; i<exponent; i++) {
        result *= base;
    }
    return result;
}
  • 位运算
    为了使用位运算而用位运算，导致问题反而复杂了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public double Power(double base, int exponent) {
    if (exponent < 0) {
        exponent = -exponent;
        base = 1 / base;
    }
    // 把exponent拆成 0*2^0 + 1*2^1 + 1*2^2
    // result 为          1 * base^2 * base^4
    double x = base;
    double result = 1.0;
    while (exponent != 0) {
        if ((exponent&1) == 1) {
            result *= x;
        }
        x *= x;
        exponent >>= 1;
    }
    return result;
}
  • 递归
    图片
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public double Power(double base, int exponent) {
    if (exponent < 0) {
        exponent = -exponent;
        base = 1 / base;
    }
    return this.dfs(base, exponent);
}

private double dfs(double base, int exponent) {
    // 递归终止条件
    if (exponent == 0) {
        return 1.0;
    }
    double result = dfs(base, exponent / 2);
    if (exponent % 2 == 0) {
        return result * result;
    } else {
        return result * result * base;
    }
}

优化 减少一层递归,上面的方法exponent，到0时才返回，0的上一层肯定是1， 在1的时候可以直接返回base，判断0是为了判断exponent输入是0的情况，可以单独拎出来处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public double Power(double base, int exponent) {
    if (exponent < 0) {
        exponent = -exponent;
        base = 1 / base;
    }
    if (exponent == 0) {
        return 1.0;
    }
    return this.dfs(base, exponent);
}

private double dfs(double base, int exponent) {
    if (exponent == 1) {
        return base;
    }
    double result = dfs(base, exponent / 2);
    if (exponent % 2 == 0) {
        return result * result;
    } else {
        return result * result * base;
    }
}

数组中只出现一次的两个数字

https://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8?tpId=13&tqId=1375231&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 利用set
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    public int[] FindNumsAppearOnce (int[] array) {
        // write code here
        List<Integer> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        // 利用集合找出重复项，并保存在list中
        for (int i=0; i<array.length; i++) {
            if (!set.add(array[i])) {
                list.add(array[i]);
            }
        }
        int[] result = new int[2];
        int resultIndex = 0;
        // 遍历array，利用indexOf判断是否在list中，找出不重复的数组
        for (int i=0; i<array.length; i++) {
            int index = list.indexOf(array[i]);
            if (index == -1) {
                result[resultIndex++] = array[i];
            }
        }
        if (result[0] > result[1]) {
            int temp = result[0];
            result[0] = result[1];
            result[1] = temp;
        }
        return result;
    }
  • 利用异或，即模2加 满足题目要求的空间O(1)
    相同数字异或运算结果为0，如果数组中只有1个不重复的数字，那么对整个数组异或运算，得到的最终结果就是这个不重复的数字，我们可以把这个数组拆分成两个子数组，两个不重复的数字，分别位于这两个数组中，并且数组中重复数字都是成对的，这样对每个子数组异或运算，就能得到最后的两个不重复数字

关键在于如何把不重复的数字放到两个子数组中，且保证数组中的重复数字都是成对出现的，我们先把整个数组异或，找到一个为1的二进制位，假设改位为i。异或为1，说明两个不重复数字的i位一个为0，一个为1，我们根据这个标准就能把两个不重复数字区分开，并且相同数字的i位肯定是相同的，就会分到相同的数组中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public int[] FindNumsAppearOnce (int[] array) {
    // write code here
    // 计算整个数组的异或结果
    int xorResult = 0;
    for (int i=0; i<array.length; i++) {
        xorResult ^= array[i];
    }
    // 找到异或结果中为1的位
    int oneIndex=0;
    for (int i=0; i<32; i++) {
        if ((xorResult >> i & 1) == 1) {
            oneIndex = i;
            break;
        }
    }
    // 为了保证O(1)的空间复杂度，使用原数组存放子数组，二进制位为1的挪到数组的左边
    int mark = 0;
    for (int i=0; i<array.length; i++) {
        if ((array[i] >> oneIndex & 1) == 1) {
            this.swap(array, mark++, i);
        }
    }
    // 子数组1异或得到不重复数字1
    int[] result = new int[2];
    for (int i=0; i<mark; i++) {
        result[0] ^= array[i];
    }
    // 子数组2异或得到不重复数字2
    for (int i=mark; i<array.length; i++) {
        result[1] ^= array[i];
    }
    if (result[0] > result[1]) {
        this.swap(result, 0, 1);
    }
    return result;
}

private void swap(int[] array, int src, int des) {
    int temp = array[src];
    array[src] = array[des];
    array[des] = temp;
}

求1+2+3+…+n

https://www.nowcoder.com/practice/7a0da8fc483247ff8800059e12d7caf1?tpId=13&tqId=23248&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

  • 递归
    不能用if，结束递归，if的作用是，当n为1时，不再继续递归，直接返回某个值，可以利用短路与，满足某个条件时不再递归
1
2
3
4
5
public int Sum_Solution(int n) {
    int result=1;
    boolean temp = n>=2 && (result = n + Sum_Solution(n-1)) == 0;
    return result;
}

优化

1
2
3
4
public int Sum_Solution(int n) {
    boolean temp = n>1 && (n += Sum_Solution(n-1)) == 0;
    return n;
}
赏

谢谢你请我喝杯可乐

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

北科大计算机在读<br><br>爱好编程<br><br>热爱技术<br><br>喜欢折腾