Leetcode【46、47、89、357、659】
Leetcode【46、47、89、357、659】
问题描述：【DFS】46. Permutations
解题思路：
这道题是给一个不同整数的集合，返回集合所有的全排列。
模板题，使用回溯法解决。
Python3 实现：
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def search(d, path):
for i in range(N):
if not b[i]:
path.append(nums[i])
b[i] = True
if d == N: # 保存结果
ans.append(path[:]) # 防止传引用调用
else:
search(d+1, path)
path.pop() # 回溯一步
b[i] = False # 回溯一步
N = len(nums)
b = [False] * len(nums) # 标记数字是否可用
ans = []
search(1, [])
return ans问题描述：【DFS】47. Permutations II
解题思路：
这道题是给一个不同整数的集合，可能包含重复的数字，返回集合所有的全排列。
同上面的 Leetcode 46，使用 DFS 回溯法。需要用集合 set 保存结果，然后再加入到集合前判断之前是否出现过。最后，将集合转化为列表输出即可。
Python3 实现：
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def search(k, path):
for i in range(N):
if not b[i]:
path.append(nums[i])
b[i] = True
if k == N and tuple(path) not in ans: # 没有在集合中出现过
ans.add((tuple(path)))
else:
search(k+1, path)
b[i] = False
path.pop()
ans = set()
N = len(nums)
b = [False] * N
search(1, [])
return list(ans)问题描述：【Math、Bit】89. Gray Code
解题思路：
这道题是给一个非负整数n，表示二进制数的位数，求一个格雷码序列（格雷码序列中，相邻两个二进制数只有一位不同）。
方法1（找规律）：
这道题实际上可以采用构造法，长度为 n 的序列可以由长度为 n-1 的序列构造得到。
例如 n = 3，我们已经直到 n = 2 时的结果为 [0,1,3,2]，即 [00,01,11,10]，那么我们只需要在 [00,01,11,10] 前面加 0 和 1 就可以得到 8 个数。可以发现，序列 1：[000,001,011,010]、序列 2：[100,101,111,110] 分别满足格雷码条件，但是如果只是简单的将两个序列拼接起来就不满足（010->100）。但是，序列 2 的最后一个数 110 是可以和序列 1 的最后一个数拼接到一起满足格雷码条件的。因此，我们得到求解规律：
对于 n = k，先将 n = k-1 的序列反转；然后每一项加上 2^(k-1) 构造序列 2；最后，将序列 2 拼接到 n = k-1 的序列的后面，即可得到答案。
Python3 实现：
class Solution:
def grayCode(self, n: int) -> List[int]:
ans = [0]
base = 1
for i in range(n):
ans += [(a + base) for a in ans[::-1]] # 反转序列进行拼接
base *= 2
return ans方法2（位操作）：
对于 n，共有 1 << n 个二进制数（[1, 2^n]），对于每个数，进行 i ^ (i >> 1) （自己与自己右移一位的数字进行异或操作）即可得到格雷码序列。
为什么可以这样做？参考如下：
Python3 实现：
class Solution:
def grayCode(self, n: int) -> List[int]:
return [k ^ (k >> 1) for k in range(1 << n)]问题描述：【Math】357. Count Numbers with Unique Digits
解题思路：
这道题是给一个非负整数n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10^n。
这是一道数学题，很容易发现规律：
- 如果 n = 1，ans = 10；
- 如果 n = 2，考虑两位数都不相同，有 9 * 9 = 81 种情况（第一个数字不能以 0 开头，第二个数字可以有 0），再加上 n = 1 时的情况即可得到 ans = 91；
- 如果 n = 3，考虑三位数都不相同，有 9 * 9 * 8 = 648 种情况（第一个数字不能以 0 开头），再加上 n = 2 时的情况即可得到 ans = 739；
以此类推即可。
因此，我们从 i = 1 开始，每次累加结果，一直计算到 i = n 即可得到答案。注意：当 n > 10 时，与 n = 10 的结果相同。
Python3 实现：
class Solution:
def countNumbersWithUniqueDigits(self, n: int) -> int:
def factorial(cnt): # 从9阶乘cnt次
res = 1
factor = 9
for i in range(cnt):
res *= factor
factor -= 1
return res
pre = i = 1
while i <= n and i <= 10: # i要<=10
pre += 9 * factorial(i-1) # i位不同的数字与前面结果累加
i += 1
return pre问题描述：【Greedy+Heap】659. Split Array into Consecutive Subsequences
解题思路：
这道题是给一个递增序列，将其划分成若干个子序列，判断每个子序列是否长度大于 3 且连续。
这就是所谓的扑克牌算法，必须全部弄成“顺子”。一个“顺子”至少3张连续的牌。方法是使用堆（优先队列），优先把当前的牌放入到更短的“顺子”里（贪心）。
这里要说明一下所使用的数据结构：以 nums = [1,2,3,3,4,4,5,6] 为例，我们只需要记录划分的每个段的最后一个 num 以及以 num 结尾的子序列的长度，因此我们可以使用 Python 中的默认字典数组，即 collections.defalutdict(list)，key 是以 num 为结尾的 num，value 是一个列表（默认为空），记录以 num 为结尾的子序列的长度列表。如我们遍历到第二个 3 时，字典中的 key = 3 应该保存的是 { 3: [1,3] }（一个子序列是 [1,2,3]，长度为 3；另一个子序列是 [3]，长度为 1）。接下来，当我们遇到第一个 4 时，我们应该先满足更短的“顺子”，即要把 4 放入到 [3] 中变成 [3,4]，同时 { 3: [1,3] } 要变成 { 3: [3], 4: [2] }。我们发现，因为我们要取出更短的“顺子”，因此字典中的 list 应该是一个堆（优先队列），这样每次就能弹出短“顺子”，同时压入新的以 num 为结尾的 key 和长度。
因此，具体做法是：
- 首先判断以（num-1）为结尾的序列是否存在；
- 如果不存在，创建以 num 为结尾的 key，并且长度为1，压入堆中；
- 如果存在，从堆中弹出最小长度，创建以 num 为结尾的键 key，并设置长度为 len + 1，压入堆中；
- 最后，检查字典数组中各个不为空的 list 中的值（子序列的长度），如果有一个长度小于 3，那么就返回 False，否则返回 True。
还是以 nums = [1,2,3,3,4,4,5,6] 为例，字典数组中的变化情况是：
initial {}
1 {0: [], 1: [1]}
2 {0: [], 1: [], 2: [2]}
3 {0: [], 1: [], 2: [], 3: [3]}
3 {0: [], 1: [], 2: [], 3: [1, 3]}
4 {0: [], 1: [], 2: [], 3: [3], 4: [2]}
4 {0: [], 1: [], 2: [], 3: [], 4: [2, 4]}
5 {0: [], 1: [], 2: [], 3: [], 4: [4], 5: [3]}
5 {0: [], 1: [], 2: [], 3: [], 4: [], 5: [3, 5]}
6 {0: [], 1: [], 2: [], 3: [], 4: [], 5: [5], 6: [4]}例如，其中 4 {0: [], 1: [], 2: [], 3: [], 4: [2, 4]} 表示有两个以 4 结尾的子序列，一个长度为 2，即 [3, 4]，一个长度为 4，即 [1,2,3,4]。
这样做，时间复杂度为 O(n*logk)，k 代表最多有 k 个以 num 为结尾的子序列；空间复杂度为 O(n)。
Python3 实现：
class Solution:
def isPossible(self, nums: List[int]) -> bool:
dic_heap = collections.defaultdict(list) # 每个key的默认值是一个空列表
for num in nums:
if len(dic_heap[num-1]) == 0: # 没有以num-1为结尾的key
heapq.heappush(dic_heap[num], 1) # 以num为结尾的初始长度为1
else: # 弹出以num-1为结尾的key, 将以num为结尾的key压入, 并更新长度
lens = heapq.heappop(dic_heap[num-1])
heapq.heappush(dic_heap[num], lens + 1)
for key in dic_heap.keys():
for lens in dic_heap[key]:
if lens < 3: # 如果列表中有小于3的长度
return False
return True