LeetCode50天刷题计划第二季（Day 2 — 格雷编码（12.30-13.00）子集 II（13.00-14.00）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

坚持！坚持！坚持！！

一、题目

格雷编码

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
第一个整数是 0
一个整数在序列中出现 不超过一次
每对 相邻 整数的二进制表示 恰好一位不同 ，且
第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

示例 1

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。

• 00 和 01 有一位不同
• 01 和 11 有一位不同
• 11 和 10 有一位不同
• 10 和 00 有一位不同
  [0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
• 00 和 10 有一位不同
• 10 和 11 有一位不同
• 11 和 01 有一位不同
• 01 和 00 有一位不同

示例 2

输入：n = 1
输出：[0,1]

提示

1 <= n <= 16

二、思路

主要是了解了格雷编码的定义后用找规律的方法就可以写出来啦
可以用递推解决，n+1的列表元素数目是n的二倍，其前一半是n的每个元素前面加‘0’，正序排列；后一半是n的每个元素前面加‘1’，倒序排列
注意二进制字符串转换为十进制的函数为：int(str,2)

三、代码

class Solution:
    def grayCode(self, n: int) -> List[int]:
        relist=['0','1'] #初始值，n最小也是1
        for i in range(2,n+1):
            #temp=['1'+x for x in relist[::-1]] #后半段
            relist=['0'+x for x in relist] + ['1'+x for x in relist[::-1]][:] #全部
        relist=[int(x,2) for x in relist] #int(x,2)将二进制的x转换为十进制
        return relist

四、题目

子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2

输入：nums = [0]
输出：[[],[0]]

提示

1 <= nums.length <= 10
-10 <= nums[i] <= 10

五、思路

也可以用递推来实现，首先将nums排序使相同的数字都相邻，其次一个一个向其中添加元素，扩充relist。
需要注意的是,需要保留上一次新增到relist中的部分（temp），如果某元素和上一个元素相同，那么仅在这些新增元素中添加即可

六、代码

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort() #排序
        relist=[[],[nums[0]]] #数组中至少有一个数
        temp=[[nums[0]]] #上一次新增的
        for i in range(1,len(nums)):
            if (nums[i] == nums [i-1]): #相同元素
                temp=[x+[nums[i]] for x in temp] #新增   
            else:
                temp=[x+[nums[i]] for x in relist] #全部
            relist.extend(temp[:]) #扩展结果数组
        relist.sort() #规范化，可以不要
        return relist