7.14号刷题

第一题 260. Single Number III

题目描述

给定一个整数数组，其中除两个数字只出现一次外，其余数字均出现两次。找出这两个只出现一次的数字。

例如：

给定 nums = [1, 2, 1, 3, 2, 5]，返回 [3, 5]

注意：

结果的顺序不重要。因此在上例中，[5, 3]也是正确的。

你的算法应该满足线性时间复杂度。你可以只使用常数空间复杂度完成题目吗？

算法

首先计算nums数组中所有数字的异或，记为xor

令lowbit = xor & -xor，lowbit的含义为xor从低位向高位，第一个非0位所对应的数字

例如假设xor = 6（二进制：0110），则-xor为（二进制：1010，-6的补码，two's complement）

则lowbit = 2（二进制：0010）

根据异或运算的性质，“同0异1”

记只出现一次的两个数字分别为a与b

可知a & lowbit与b & lowbit的结果一定不同

通过这种方式，即可将a与b拆分开来

public class singleNumber260 {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int num : nums) xor ^= num;

        xor &= ~(xor - 1);
        int[] res = {0, 0};

        for (int num : nums) {
            if ((num & xor) == 0) {
                res[0] ^= num;
            } else {
                res[1] ^= num;
            }
        }
        return res;
    }
}
```	

### 第二题 [191. Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/#/description)

#### 题目描述
编写函数接收一个无符号整数，返回其二进制形式中包含的1的个数（也叫做汉明权重）

例如，32位整数'11'的二进制表示为：00000000000000000000000000001011，因此函数应当返回3

#### 算法

	n & (n - 1)能够让最低位的1变为0
	n & ~(n - 1)能够找出最低位的1 

```java
public class hammingWeight {
    public int hammingWeight(int n) {
        int sum = 0;
        while (n != 0) {
            sum++;
            n &= (n - 1);
        }
        return sum;
    }
}

第三题 190. Reverse Bits

题目描述

按位反转一个给定的32位无符号整数。

例如，输入整数43261596（二进制形式为：00000010100101000001111010011100），返回964176192（转换为二进制为00111001011110000010100101000000）

算法

对每一位移动后查看是否为1，并将结果相加

注意： >> 和 >>>的区别，>> 是在左边，根据正负号添0或1，>>>只会添0

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int mock = 1, res = 0;
        for (int i = 0; i < 32; i++) {
            res <<= 1;
            res |= n & mock;
            n >>= 1;
        }
        return res;
    }
}

第四题 7. Reverse Integer

题目描述

将一个数字进行反转

算法

注意对溢出的处理

public class reverse7 {
    public int reverse(int x) {
        long res = 0;
        while (x != 0) {
            res = res * 10 + x % 10;
            x /= 10;
            if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) {
                return 0;
            }
        }
        return (int) res;
    }
}

第五题 8. String to Integer (atoi)

题目描述

将一个String转化成Integer

算法

public class Solution {
    public int myAtoi(String str) {
        if (str.length() == 0) return 0;
        
        int index = 0, sign = 1;
        char[] chars = str.toCharArray();

        while (chars[index] == ' ') index++;
        if (chars[index] == '-' || chars[index] == '+') {
            sign = 1 - 2 * (chars[index++] == '-' ? 1 : 0);
        }

        long num = 0;
        while (index < chars.length && chars[index] >= '0' && chars[index] <= '9') {
            num = num * 10 + chars[index++] - '0';
            if (num * sign > Integer.MAX_VALUE) return Integer.MAX_VALUE;
            if (num * sign < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        }
        return sign * (int) num;
    }
}

第六题 338. Counting Bits

题目描述

给定一个非负整数num。对于每一个满足0 ≤ i ≤ num的数字i，计算其数字的二进制表示中1的个数，并以数组形式返回。

测试用例如题目描述。

算法

利用位运算，将当前数左移一位，然后查看要加的最后一位是否为1

public class countBits338 {
    public int[] countBits(int num) {
        int[] res = new int[num + 1];
        for (int i = 1; i < num + 1; i++) {
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }
}

第七题 477. Total Hamming Distance

题目描述

两个整数的汉明距离是指其二进制不相等的位的个数。

计算给定的整数数组两两之间的汉明距离之和。

注意：

元素大小在[0, 10^9]之间。
数组长度不超过10^4。

算法

对于每个位，统计所有数的0或1的状态，之后通过sum * (sum - 1)一次性算出两两之间对于这个位差多少个1

public class totalHammingDistance477 {
    public int totalHammingDistance(int[] nums) {
        int total = 0;
        for (int i = 0; i < 32; i++) {
            int bitOneSum = 0;
            for (int num : nums) {
                if (((num >> i) & 1)== 1) bitOneSum++;
            }
            total += bitOneSum * (nums.length - bitOneSum);
        }
        return total;
    }
}

第八题 421. Maximum XOR of Two Numbers in an Array

题目描述

给定一列数字，a[0], a[1], a[2], … , a[N-1]，其中0 <= a[i] < 2^32。计算a[i] XOR a[j]的最大值。

你可以给出O(n)时间复杂度的解法吗？

算法

利用HashSet辅助计算

对于[9, 5, 7]这三个数字进行举例
9 -> 1001
5 -> 0101
7 -> 0111
首先我们从第bit的31位开始进行检查，如果存在有两个数，第31位不相同。那么现在的他们即使后面所有bit位都相同，也有亦或的最大值 1 << 31。
因此对于9来说，第三位为1，对于5或7来说，第三位为0。那么这批数里，最大值最起码为8。我们对每一位进行检查，利用一个亦或的性质 a ^ b = c => a ^ c = b， c为我们假设的最大值。每次循环查看其是否存在

public class findMaximumXOR421 {
    public static int findMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        for (int i = 31; i >= 0; i--) {
            mask |= (1 << i);
            Set<Integer> set = new HashSet<>();
            for (int num : nums)
                set.add(num & mask);

            int candidate = max | (1 << i);
            for (int prefix : set) {
                if (set.contains(prefix ^ candidate)) {
                    max = candidate;
                    break;
                }
            }
        }
        return max;
    }
}

第九题 320. Generalized Abbreviation

题目描述

将一个字符串进行缩减

算法

对于每一个位置，我们可以选择缩减或者保留，并因此写出递归程序

public class generateAbbreviations320 {
    public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<>();
        if (word.isEmpty()) return res;
        backtrack(res, "", 0, 0, word);
        return res;
    }

    public void backtrack(List<String> res, String cur, int pos, int count, String word) {
        if (pos == word.length()) {
            if (count > 0) cur += count;
            res.add(cur);
            return;
        }
        backtrack(res, cur, pos + 1, count + 1, word); //omit the position now
        backtrack(res, cur + (count == 0 ? "" : count) + word.charAt(pos), pos + 1, 0, word); //Ab it
    }
}