每日归档： 2022年1月21日

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

思路：先转置，在每行倒序

# @lc code=start
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        mid=0
        n=len(matrix)
        for i  in range(n):
            for j in range(i):
                mid = matrix[i][j]
                matrix[i][j] = matrix[j][i]
                matrix[j][i] =  mid 
        for i  in range(n):
            for j in range(n//2):
                mid=matrix[i][j]
                matrix[i][j]=matrix[i][n-j-1]
                matrix[i][n-j-1] = mid
# @lc code=end

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

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

示例 2：

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

提示：

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

递归求解：

# [46] 全排列
#

# @lc code=start
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        import copy
        def subpermute(nums,index):
            if index==0:
               return [[nums[0]]]
            else:
                rev=subpermute(nums,index-1)
                res=list()
                for i in range(len(rev)):
                    #print(rev[i])
                    for j in range(len(rev[i])+1):
                        if j==len(rev[i]) or rev[i][j]!=nums[index]:
                            mid=copy.deepcopy(rev[i])
                        #print(mid)
                            mid.insert(j,nums[index])
                            if mid not in res:
                               res.append(mid)
                        
                return res
        index=len(nums)-1
        return subpermute(nums,index)

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

暴力求解：

# [46] 全排列
#

# @lc code=start
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        import copy
        def subpermute(nums,index):
            if index==0:
               return [[nums[0]]]
            else:
                rev=subpermute(nums,index-1)
                res=list()
                for i in range(len(rev)):
                    #print(rev[i])
                    for j in range(len(rev[i])+1):
    
                        mid=copy.deepcopy(rev[i])
                        #print(mid)
                        mid.insert(j,nums[index])
                        res.append(mid)
                        
                return res
        index=len(nums)-1
        return subpermute(nums,index)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn ）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

# [50] Pow(x, n)
#

# @lc code=start
class Solution:
    def myPow(self, x: float, n: int) -> float:
        return pow(x, n)

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

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

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

法一：暴力求解

# @lc code=start
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        lens=len(nums) 
        maxs=nums[0]
        for i in range(lens):
            for j in range(0,i+1):
                maxs=max(maxs,sum(nums[j:i+1]))
        return maxs

超时了

法二：动态规划

我们用 f(i) 代表以第 i 个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：

因此我们只需要求出每个位置的f(i)，然后返回 f 数组中的最大值即可。那么我们如何求 f(i) 呢？我们可以考虑nums[i] 单独成为一段还是加入 f(i−1) 对应的那一段，这取决于 nums[i] 和 f(i−1)+nums[i] 的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        lens=len(nums)
        maxs=nums[0]
        n=0
        for i in range(lens):
            n=max(n+nums[i],nums[i])
            maxs=max(maxs,n)
        return maxs

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000

思路：贪心算法：

如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。

例如，对于数组 [2,3,1,2,4,2,3]，初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。从下标 1 出发，最远可到达下标 4。下标 1 可到达的位置中，下标 4 的值是 4 ，从下标 4 出发可以达到更远的位置，因此第二步到达下标 4。

代码：

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        maxPos, end, step = 0, 0, 0
        for i in range(n - 1):
            if maxPos >= i:
                maxPos = max(maxPos, i + nums[i])
                if i == end:
                    end = maxPos
                    step += 1
        return step

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

这么说有点抽象，来举一个例子：例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？指定每次拿最大的，最终结果就是拿走最大数额的钱。每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。

刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。

例如刚刚举的拿钞票的例子，就是模拟一下每次拿做大的，最后就能拿到最多的钱，这还要数学证明的话，其实就不在算法面试的范围内了，可以看看专业的数学书籍！

所以这也是为什么很多同学通过（accept）了贪心的题目，但都不知道自己用了贪心算法，因为贪心有时候就是常识性的推导，所以会认为本应该就这么做！

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

其实这个分的有点细了，真正做题的时候很难分出这么详细的解题步骤，可能就是因为贪心的题目往往还和其他方面的知识混在一起。

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

示例 3:

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4:

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5:

输入:
s = "acdcb"
p = "a*c?b"
输出: false

思路：回溯算法（N叉树）

# @lc code=start
class Solution:
    def isMatch(self,s: str, p: str) -> bool:
        if s=="" and p=="":
            return True
        if p=="":
            return False
        len1=len(s)
        n1=0
        m1=""
        len2=len(p)
        for i in range(1,len2):
            if p[i]=="*" and p[i-1]=="*":
                continue
            else : 
                m1=m1+p[i-1]
                n1=1+n1
        p=m1+p[-1]
        len2=len(p)
        def submacth(i,j):
            if i==len1 and j==len2:
                return True
            if j==len2:
                return False
            if i==len1 and (p[j:]!="*"*len(p[j:])):
                #print(False)
                return False
            if p[j]!="*" :
                if p[j]=="?"or p[j]==s[i]:
                    i=i+1
                    j=j+1
                    return submacth(i,j)

                else:
                    #print(False)
                    return False
            if p[j]=="*" and j==len2-1:
                    #print("3333")
                    l=len1
                    h=len2
                    return submacth(l,h)
                        
            if p[j]=="*" and j<len2-1:
                for m in range(i,len1):
                    if s[m]==p[j+1] or p[j+1]=="?":
                        #print(m,j+1,"hh")
                        l=m+1
                        h=j+2
                        if submacth(l,h):
                            return True
                return False

        return submacth(0,0)

需改进：

动态规划步骤：

• 确定dp[i][j]状态含义
• 确定 状态转移方程
• 确定dp初始值

参考官方题解：动态规划问题dp[i][j]表示s的前i个字符和 p的前j个字符是否匹配。在进行状态转移时，我们可以考虑模式 p 的第 j 个字符 pj​，与之对应的是字符串 s 中的第 i 个字符si​：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for i in range(1, n + 1):
            if p[i - 1] == '*':
                dp[0][i] = True
            else:
                break
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    dp[i][j] = dp[i][j - 1] | dp[i - 1][j]
                elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                
        return dp[m][n]