专栏首页Bingo的深度学习杂货店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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode【227、468、848、1081】

    这道题是实现一个基本计算器,即给一个只包括 +、-、*、/、数字和空格的字符串,计算结果。

    echobingo
  • Q5 Longest Palindromic Substring

    Given a string s, find the longest palindromic substring in s. You may assume th...

    echobingo
  • Leetcode【526、667、932】

    这道题是一道构造题,即构造一个长度为 N 的自然序列,满足整除关系: i % nums[i] = 0 或 nums[i] % i = 0(i 为第 i 个位置)...

    echobingo
  • 4️⃣ 核酸(蛋白)序列特征分析(5):序列motif的查找和可视化工具

    模体Motif,指DNA或蛋白质序列中局部的保守区域,或者是一组序列中共有的一小段序列模式。这些motif很可能具有分子功能,结构性质或家族成员相关的任何序列模...

    Y大宽
  • Python3--csv读写问题

    说明一下我是以‘|’为分隔符的,打开文件后发现自己写入的文件被以字节为单位分开了,而我们想要的是这样的效果

    明天依旧可好
  • 【LeetCode - 018】四数之和

    Given an array S of n integers, are there elements a, b, c, and d in S such that...

    周三不加班
  • 彭碧发:腾讯云文字识别OCR技术构建和应用

    2019年9月7日,云+社区(腾讯云官方开发者社区)主办的技术沙龙——AI技术原理与实践,在上海成功举行。现场的5位腾讯云技术专家,在现场与开发者们面对面交流,...

    云加社区技术沙龙
  • [别被脱库系列]1 数据库的初恋

    此时小蓝还没有提交这个事务,小林去访问了这个表(小林去年买了个表,哈哈哈嗝),于是

    我是程序员小贱
  • 2019二级C题库及解析(7)

    此题为if...else...语句的嵌套,第二if...else...作为第一个if...else...语句else部分的复合语句。

    用户6755376
  • 算法篇:数的转换

    这类算法的核心,在于负数的处理,也就是用到补码的转换,num = ((-num)^0xffffffff)+1。

    灰子学技术

扫码关注云+社区

领取腾讯云代金券