算法题记录 2

87.扰乱字符串（困难）

使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：
如果字符串的长度为 1 ，算法停止
如果字符串的长度 > 1 ，执行下述步骤：
在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。
给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。

涉及知识点

动态规划

解决思路

先常规流程，按题意对特殊情况进行判断处理，如检验字符串长度是否相等，字符串各字母的个数是否相等，长度为1时检验字符串是否相等。

然后分析该题，试着从题意中找到数学规律来简化完成判断，经分析发现并没有显然的数学规律，于是将重心放在编程模拟上，通过递归产生不同结果来判断目标字符串是否在这些结果中。分析递归过程中意识到可以套用动态规划的模版，dp[i][j][k][h] 表示 T[k..h] 是否由 S[i..j] 变来。由于变换必须长度是一样的，因此这边有个关系 j−i=h−k ，可以把四维数组降成三维。dp[i][j][len] 表示从字符串 S 中 i 开始长度为 len 的字符串是否能变换为从字符串 T 中 j 开始长度为 len 的字符串。
问题简化为三维动态规划，尝试给出动态规划式子：dp[i][j][k]=dp[i][j][w]&&dp[i+w][j+w][k−w]或者dp[i][j+k−w][w]&&dp[i+w][j][k−w]，前者表示没有交换，后者表示进行了交换。动态规划的出口应为dp[0][0][字符串的长]，表示从两个字符串开头也就是两个字符串是否能互相转换，设i从1到字符串的长按动态规划式子对动态规划表进行更新。得到最终答案。

注意：在部分OJ系统中，python处理复杂问题递归容易超时，加入修饰器优化计算过程即可，@functools.lru_cache(None)

class Solution:
    @functools.lru_cache(None)
    def isScramble(self, s1: str, s2: str) -> bool:
        if len(s1) != len(s2):
            return False
        if s1==s2:
            return True
        if sorted(s1)!=sorted(s2):
            return False
        
        for i in range(1,len(s1)):
            if self.isScramble(s1[:i],s2[:i])and self.isScramble(s1[i:],s2[i:]) or \
                 (self.isScramble(s1[:i],s2[-i:])and self.isScramble(s1[i:],s2[:-i])):
                 return True
        return False

88.合并两个有序数组（简单）

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

涉及知识点

指针

解决思路

注意到两个数组均为“非递减数组”，且有时间要求O（m+n），这样我们应该自然把重心放在指针，也就是对数组的直接操作上。因为nums1后面有n个0，方便换位操作，我们直接从后往前排序，避免数字过多交换位置。设置三个指针，p1指向nums1的m-1处，p指向nums1的末尾m+n-1处，p2指向nums2的末尾n-1处。反复比较nums1和nums2有效区域末尾的值谁更大，更大的放在nums1的最后，如果nums2已经全部放入，就结束。nums1移位时p1-1,p-1，nums2放入时,p2-1,p-1。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        p1,p2,p=m-1,n-1,m+n-1
        while p2>=0:
            if p1>=0 and nums1[p1]>nums2[p2]:
                nums1[p]=nums1[p1]
                p1-=1
            else:
                nums1[p]=nums2[p2]
                p2-=1
            p-=1

89.格雷编码（中等）

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

涉及知识点

格雷码

解决思路

没啥好说的，格雷码的生成方式，数电课必考项目，G(n)前面加0，G(n)镜像后前面加1，拼接两部分即可。

class Solution:
    def grayCode(self, n: int) -> List[int]:
        res,head=[0],1
        for i in range(n):
            for j in range(len(res)-1,-1,-1):
                res.append(head+res[j])
            head <<= 1
        return res        

90.子集2（中等）

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的
子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

涉及知识点

dfs

解决思路

首先考虑没重复元素的情况，dfs枚举结果应该是树的形式，遍历数组中每个数（从dfs(0)到dfs(n)），考虑选取（path.append()、dfs(i+1)）或不选取（dfs(i+1)）两种情况，得到所有结果，非常简单。此时出现了重复元素，通过分析可知，树里面同一层，比如第一层为1,2,2，我们在第二个2时已经展开讨论过选取2的情况了，不选取第二个2时我们应当跳过第三个2，不然就出现了重复。所以问题变得很简单，我们在每层设置一个计数器，如果2被跳过了，也应该跳过同层后续所有的2。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n=len(nums)
        ans=[]
        path=[]

        def dfs(i:int)->None:
            if i==n:
                ans.append(path.copy())
                return
            
            x=nums[i]
            path.append(x)
            dfs(i+1)
            path.pop()

            i+=1
            while i<n and nums[i]==x:
                i+=1
            dfs(i)

        dfs(0)
        return ans     

91.解码方法（中等）

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

“1” -> ‘A’

“2” -> ‘B’

…

“25” -> ‘Y’

“26” -> ‘Z’

然而，在 解码 已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（”2” 和 “5” 与 “25”）。

例如，”11106” 可以映射为：

“AAJF” ，将消息分组为 (1, 1, 10, 6)
“KJF” ，将消息分组为 (11, 10, 6)
消息不能分组为 (1, 11, 06) ，因为 “06” 不是一个合法编码（只有 “6” 是合法的）。
注意，可能存在无法解码的字符串。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串，返回 0。

题目数据保证答案肯定是一个 32 位 的整数。

涉及知识点

动态规划

解决思路

该题有一定迷惑性，按很多人思路会尝试dfs不断搜索和判断，实际上该题声明字符长度为100以内，当字符长度过长时，dfs的效率会导致算法严重超时。该题其实是递推的动态规划题。我们很显然能注意到在这种编码方式下，加入一个新的数字，要么它自身能成为码（1～9），要么它与前一个数成为码（10～26），要么两者均可，要么两者都不行。在脑中模拟下该过程，可以发现，动态规划式子如下：f[i]=f[i-1]+f[i-2]，无法自身成码时f[i-1]=0，无法与前一个数成码时f[i-2]=0。继承f[i-1]考虑的是只能在新数字前分隔，此时不对加入前的编码数量产生任何影响，继承f[i-2]考虑的是只能与前一个数组合，在前一个数前进行分隔，后两个数视为一个整体，不影响f[i-2]的编码数量。
同样注意下特殊情况，如字符串开头即为0，可以直接判断，也可以加入哨兵” “，来适配上述公式。

class Solution:
    def numDecodings(self, s: str) -> int:
        n=len(s)
        s=' '+s
        f=[0]*(n+1)
        f[0]=1
        for i in range(1,n+1):
            a=ord(s[i])-ord('0')
            b=(ord(s[i-1])-ord('0'))*10+ord(s[i])-ord('0')
            if 1<=a<=9:
                f[i]=f[i-1]
            if 10<=b<=26:
                f[i]+=f[i-2]
        return f[n]

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。