写在前面

开个贴记录一下 刷题的过程，目前参照 leetcode101，目标101题，由于太久没写java了，也会涉及到一些java的基础用法，希望能和大家共勉吧～

已刷链接：

• 贪心算法：https://www.nowcoder.com/discuss/1051877
• 双指针：https://www.nowcoder.com/discuss/1057237
• 二分查找：https://www.nowcoder.com/discuss/1059986
• 排序：https://www.nowcoder.com/discuss/1063581
• 搜索：https://www.nowcoder.com/discuss/1069407
• 动态规划：https://www.nowcoder.com/discuss/1071676
• 分治法：https://www.nowcoder.com/discuss/1091335
• 链表：https://www.nowcoder.com/discuss/post/419235544456052736
• 树：https://www.nowcoder.com/discuss/post/424955068647997440

位运算原理

• ^ 异或 0^0 = 0,1^0 = 1,0^1 = 1, 1^1 = 0（同为0，异为1）
• | 按位或
• & 按位与
• ~ 按位取反
• >> 右移一位，表示/2
• << 左移一位，表示*2



No.1 Hamming Distance

链接：https://leetcode.com/problems/hamming-distance/



解题思路：

class Solution {
    public int hammingDistance(int x, int y) {
        int res = x^y;
        int ans = 0;
        while (res != 0) {
            ans += res & 1;
            res = res >> 1;
        }
        return ans;
    }
}

No.2 Maximum Product of Word Lengths

题目：https://leetcode.com/problems/maximum-product-of-word-lengths/

解题思路：

把一个string转为一个用位表示字母是否出现的数字，则string的array变成了int的array。

注意：string 转为 int 使用的是 mask |= 1 << ((char*)c-'a')，即将1 左移(c-'a'）表示位数

这个array遍历两两位与，0的即为没有重复数字

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

No.3 Counting Bits

题目链接：https://leetcode.com/problems/counting-bits/

解题思路：

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            ans[i] = (i & 1) == 1 ? ans[i - 1] + 1 : ans[i>>1];
        }
        return ans;
    }
}

No.4 Single Number

题目链接：https://leetcode.com/problems/single-number/

解题思路：

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int num : nums) {
            ans ^= num;
        }
        return ans;
    }
}