【数据结构与算法】LeetCode：day13

1. 颠倒二进制位

解法一：调用 api

使用 Integer 现成的 api 翻转二进制位

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        return Integer.reverse(n);
    }
}

不推荐这种做法，但是我们可以深究一步，看看 Integer.reverse() 方法究竟是怎样实现的

// Integer 源码
public static int reverse(int i) {
    // HD, Figure 7-1
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i << 24) | ((i & 0xff00) << 8) |
    ((i >>> 8) & 0xff00) | (i >>> 24);
    return i;
}

看起来花里胡哨，经过简单了解，该方法是使用了分治思想，反转左右16位，然后反转每个16位中的左右8位，依次类推，最后反转2位，反转后合并即可，同时可以利用位运算在原地反转。

暂时不做深究……

• 时间复杂度：O (1)
• 空间复杂度：O (1)

解法二：取模求和

与反转十进制整数使用取模除十累加的方法类似，

十进制：ans = ans * 10 + n % 10;

​ n = n / 10;
二进制：ans = ans * 2 + n % 2;

​ n = n / 2;
但是，仅仅使用这种写法，会有一些问题，比如都要考虑是否整型溢出，Java的整数溢出后的二进制数会表示成负数（补码形式），Java中负数除以2会向零取整

然后还要考虑前导零，因为十进制是不考虑前面是否还有零的，比如100反转后就是1，不用写成001，而二进制要考虑前导零的问题。

所以综上所述，要使用位运算来避免溢出问题，同时循环32次。

因为一共只有32位，所以时间复杂度和空间复杂度都是O(1)。

作者：lartecy
链接：https://leetcode-cn.com/problems/reverse-bits/solution/zhi-qi-ran-zhi-qi-suo-yi-ran-wei-yun-suan-jie-fa-x/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            // res << 1：左移一位，相当于十进制中的 *10
            // n & 1：取最后一位，相当于十进制中的 %10
            res = (res << 1) | (n & 1);
            // n 右移一位，相当于十进制中 /10
            n >>= 1;
        }
        return res;
    }
}

• 时间复杂度：O (1)
• 空间复杂度：O (1)

2. 位1的个数

我的思路

受 颠倒二进制位 启发，使用 n & 1 取出最后一位，若为1则 count++，然后将n右移，如此循环32次。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & 1) == 1) count++;
            n >>= 1;
        }
        return count;
    }
}

其他思路：位操作的小技巧

我们可以把前面的算法进行优化。我们不再检查数字的每一个位，而是不断把数字最后一个 1 反转，并把答案加一。当数字变成 0 的时候偶，我们就知道它没有 1 的位了，此时返回答案。

这里关键的想法是对于任意数字 n ，将 n 和 n−1 做与运算，会把最后一个 1 的位变成 0 。为什么？考虑 n 和 n−1 的二进制表示。

在二进制表示中，数字 n 中最低位的 1 总是对应 n−1 中的 0 。因此，将 n 和 n−1 与运算总是能把 n 中最低位的 1 变成 0 ，并保持其他位不变。

使用这个小技巧，代码变得非常简单。

作者：LeetCode
链接：https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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

/*
作者：LeetCode
链接：https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

3. 打家劫舍

解题思路

首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。

如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 k (k>2) 间房屋，有两个选项：

偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 kk 间房屋的金额之和。

不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。

在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。

用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：

dp[i]=max(dp[i−2]+nums[i],dp[i−1])

边界条件为：

dp[0] = nums[0] 只有一间房屋，则偷窃该房屋

dp[1] = max(nums[0], nums[1]) 只有两间房屋，选择其中金额较高的房屋进行偷窃

只有一间房屋，则偷窃该房屋
只有两间房屋，选择其中金额较高的房屋进行偷窃

最终的答案即为 dp[n−1]，其中 n 是数组的长度。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
}

/*
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

上述方法使用了数组存储结果。考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}

/*
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/