Subsets(78)
Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example, If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
对于子集来说，每个元素只有 2 种状态：在子集中，不在子集中这刚好符合二进制，可以考虑使用 bitmap 的方法。
我们对每个元素一个 bit ：
0：在当前子集中1：不在当前子集中
对于 n 个元素，一共有 2^n 种取法，这和子集数也是一致的。注：与集合中元素的内容无关。
拿 2 个元素 {1,2} 举例：
- 00 ——> [] // 1不取，2不取
- 01 ——> [1] // 取1
- 10 ——> [2] // 取2
- 11 ——> [1,2] // 取1，2
刚好可以取尽所有元素。
这个算法的复杂度是 O(N^2) ，一层循环从 0 到 2^n 种取法，二层循环看每个取法对应的二进制中的 1 的个数，每个 bit 上的 1 就对应数组中的 index 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> resultList = new ArrayList<List<Integer>>();
int len = 1 << nums.length; // 2^n种可能性，n为数组的长度
// 根据每一种可能性，找到数组中与之匹配的元素的下标
// 可能性用二进制表示，正好可以用nums.len个bit，每个bit表示数组中的一个元素的取与不取
for(int i = 0; i < len; i++)
{
List<Integer> tmpList = new ArrayList<Integer>();
for(int j = 0; j < nums.length; j++)
{
// 每一次循环让j位置的bit为1（1左移动j位），看看i是否对应的位置也为1，如果是则符合本次可能性的候选元素
if(((1<<j) & i) != 0)
{
tmpList.add(nums[j]);
}
}
resultList.add(tmpList);
}
return resultList;
}
}
这类题目还有一类比较经典的题目就是：小白鼠吃毒药的问题。更多的讨论请参考知乎。
Reverse Bits(190)
我们只需要把要翻转的数从右向左一位一位的取出来：
- 如果取出来的是1，将结果 res 左移一位并且加上1
- 如果取出来的是0，将结果 res 左移一位，然后将n右移一位即可
参见代码如下：
1
2
3
4
5
6
7
public int reverseBits(int n) {
int res = 0;
for(int i = 0; i < 32; i ++) {
res = (res << 1) + ((n >> i) & 1)
}
return res;
}
Number of 1 Bits(191)
Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11’ has binary representation 00000000000000000000000000001011, so the function should return 3.
实现1
通过对参数进行位移操作，在一层 for 循环中遍历所有二进制位的值并判断&1操作，结果加和。
1
2
3
4
5
6
7
public int hammingWeight(int n) {
int res = 0;
for (int i = 0; i < 32; ++i) {
res += ((n >> i) & 1);
}
return res;
}
实现2
对参数进行移位操作省去了一个变量的空间开销，但是理解起来不如使用一个单独的 mask 变量来处理掩码位置方便。
1
2
3
4
5
6
7
8
9
public int hammingWeight(int n) {
int res = 0;
int mask = 1; // 从最低位开始掩码
for (int i = 0; i < 32; ++i) {
res += (n & mask)
mask << = 1; // 依次向高位移动一位，作为新掩码
}
return res;
}
Single Numbers 1(136)
题目中让我们不使用额外空间来做，本来是一道非常简单的题，但是由于加上了时间复杂度必须是 O(n) ，并且空间复杂度为 O(1) ，使得不能用排序方法，也不能使用 HashSet 数据结构。
1
2
3
4
5
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) res ^= num;
return res;
}
Single Numbers 2(137)
Single Numbers 3(260)
Integer Replacement(397)
这道题给了我们一个整数n，然后让我们通过变换变为1，如果n是偶数，我们变为n/2，如果是奇数，我们可以变为n+1或n-1，让我们求变为1的最少步骤。
递归实现
1
2
3
4
5
6
7
8
9
10
11
int integerReplacement(int n) {
if (n == 1)
return 0; // 此时无需计算
if (n % 2 == 0)
return 1 + integerReplacement(n / 2); // 当前轮计算次数为1，然后与剩下的数字的计算次数加和
else {
long t = n;// 防止n+1溢出，先用long计算
// 分别计算n+1和n-1情况并取最小的计算次数，当前轮计算次数为2
return 2 + min(integerReplacement((t + 1) / 2), integerReplacement((t - 1) / 2));
}
}
因为递归需要分别计算n的变化的两种情况，所以计算量有一部分是浪费的，性能并不好。
迭代实现
- 如果n正好是2的幂次方，则最省心，一直向右移位一位即可，直到n为1
- 如果n不是2的幂次方，则有两种情况
- 如果次低位为0，则向右移动一位后就又变成2的幂次方，所以用n=n-1进行调整
- 如果次低位为1，则不能用n=n-1，因为下一轮计算还是这种情况，会降低效率，所以此时要n=n+1，保证下一轮是2的幂次方
- 特殊情况是当n=3时，如果使用n=n+1，则会变成4，则还需要两轮完成计算，如果用n=n-1，则只需要一轮
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
public int integerReplacement(int n) { int c = 0; long t = n; // 防止n+1溢出 while (t != 1) { if ((n & 1) == 0) { t >>>= 1; } else if (t == 3 || ((t >>> 1) & 1) == 0) { --t; } else { ++t; } ++c; } return c; }
可见，迭代的性能比递归好很多，它不会额外的计算最后不会被选中的计算路径。
Poor Pigs(458)
There are 1000 buckets, one and only one of them contains poison, the rest are filled with water. They all look the same. If a pig drinks that poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket contains the poison within one hour.
Answer this question, and write an algorithm for the follow-up general case.
Follow-up:
If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the “poison” bucket within p minutes? There is exact one bucket with poison.
这道题很经典，在一定的时间范围内，通过多轮测试，在样本一定的条件下，找到最少的测试标本的数目，是一个以时间换空间的例子。要以最少的测试标本在规定时间内达到找到样本中有毒的那一个。
注：更详尽的分析请参考我的另一篇博文关于小动物喝毒药的算法题的分析。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int poorPigs(int buckets, int minutesToDie, int minutesToTest)
{
if (buckets == 1)
return 0;
int base = minutesToTest / minutesToDie + 1;
int r = 1;
for (int i = 1;; i++)
{
r *= base;
if (r >= buckets)
return i;
}
return 0;
}
References
- https://blog.csdn.net/JackZhang_123/article/details/78775716
- https://www.zhihu.com/question/60227816
本文首次发布于 LiuShuo’s Blog, 转载请保留原文链接.
