每日归档： 2022年1月26日

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

'A' -> 1
'B' -> 2
...
'Z' -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

• "AAJF" ，将消息分组为 (1 1 10 6)
• "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

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

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

思路：动态规划方法

# [91] 解码方法
#动态规划
#dp【i】表示从0-i个数字表示的映射数

# @lc code=start
class Solution:
    def numDecodings(self, s: str) -> int:
        lens=len(s)
        dp=[0 for _ in range(lens)]
        if s[0]!="0":
            dp[0]=1
        else:
            return 0
        if len(s)==1:
            return dp[0]
        else:
            x=1 if s[1]!="0" and dp[0]!=0 else 0
            y=1 if int(s[0:2]) in range(10,27) else 0
            dp[1]=x+y
        for i in range(2,lens):
            x=dp[i-1] if s[i]!="0" and dp[i-1]!=0 else 0
            y=dp[i-2] if int(s[i-1:i+1]) in range(10,27) else 0
            dp[i]=x+y
        return dp[lens-1]

        

# @lc code=end

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

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

示例 1：

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

示例 2：

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

代码：

# @lc app=leetcode.cn id=90 lang=python3
#
# [90] 子集 II
#

# @lc code=start
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def combine(n: int, k: int):
            rev=list()
            res=list()
            import copy
            def f(n,k):
                if k==0:
                    re=copy.deepcopy(rev)
                    res.append(re)
                    return 

                else:
                    for i in range(n,k-1,-1):
                            rev.append(nums[i-1])
                            f(i-1,k-1)
                            rev.pop()
            f(n,k)  
            return res
        re=list()
        nums.sort()
        for i in range(len(nums)+1):
            res=combine(len(nums),i)
            for item in res:
	            if not item in re:
		            re.append(item)
        return re


# @lc code=end

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 有一位不同

代码实现：

# @lc app=leetcode.cn id=89 lang=python3
#
# [89] 格雷编码
#

# @lc code=start
class Solution:
    def grayCode(self, n: int) -> List[int]:
        def subgrayCode(n):
            mid=list()
            if n==1:
                return ["0","1"]
            else:
                res=subgrayCode(n-1)
                lens=len(res)
                for i in range(lens):
                    mid.append("0"+res[i])
                for i in range(lens-1,-1,-1):
                    mid.append("1"+res[i])
                return mid

        x=subgrayCode(n)
        for i in range(len(x)):
            x[i]=int(x[i],2)
        return x
# @lc code=end

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

提示：

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

代码：

# @lc app=leetcode.cn id=86 lang=python3
#
# [86] 分隔链表
#

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        head1=ListNode(0,None)
        cur1=head1
        head2=ListNode(0,None)
        cur2=head2
        head3=head
        while head3!=None:
            #print(head3.val)
            if head3.val<x:
                cur1.next=ListNode(head3.val,None)
                head3=head3.next
                cur1=cur1.next

            else:
                cur2.next=ListNode(head3.val,None)
                head3=head3.next
                cur2=cur2.next
        cur1.next=head2.next
        return head1.next


# @lc code=end

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

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

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

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

# @lc app=leetcode.cn id=88 lang=python3
#
# [88] 合并两个有序数组
#

# @lc code=start
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums3=nums1[0:m]
        k=0
        j=0
        for i in range(m+n):
            if k<n and j<m:
                if nums2[k]<nums3[j]:
                    nums1[i]=nums2[k]
                    k=k+1
                else:
                    nums1[i]=nums3[j]
                    j=j+1
            elif k<n:
                nums1[i]=nums2[k]
                k=k+1
            else:
                nums1[i]=nums3[j]
                j=j+1



# @lc code=end

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

暴力求解：会超时

# [84] 柱状图中最大的矩形
#

# @lc code=start
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxs=0
        for i in range(len(heights)):
            for j in range(i,len(heights)):
                ms=min(heights[i:j+1])
                maxs=max(maxs,ms*(j-i+1))
        return maxs
# @lc code=end

使用栈求解：

• 首先我们枚举某一根柱子 i 作为高 h=heights[i]；
• 随后我们需要进行向左右两边扩展，使得扩展到的柱子的高度均不小于 h。换句话说，我们需要找到左右两侧最近的高度小于 h 的柱子，这样这两根柱子之间（不包括其本身）的所有柱子高度均不小于 h，并且就是 i 能够扩展到的最远范围。

我们用一个具体的例子 [6, 7, 5, 2, 4, 5, 9, 3] 来帮助读者理解单调栈。我们需要求出每一根柱子的左侧且最近的小于其高度的柱子。初始时的栈为空。

• 我们枚举 6，因为栈为空，所以 6 左侧的柱子是「哨兵」，位置为 -1。随后我们将 6 入栈。
  • 栈：[6(0)]。（这里括号内的数字表示柱子在原数组中的位置）
• 我们枚举 7，由于 6<7，因此不会移除栈顶元素，所以 7 左侧的柱子是 6，位置为 0。随后我们将 7 入栈。
  • 栈：[6(0), 7(1)]
• 我们枚举 5，由于 7≥5，因此移除栈顶元素 7。同样地，6≥5，再移除栈顶元素 6。此时栈为空，所以 5 左侧的柱子是「哨兵」，位置为 −1。随后我们将 5 入栈。
  • 栈：[5(2)]
• 接下来的枚举过程也大同小异。我们枚举 2，移除栈顶元素 5，得到 2 左侧的柱子是「哨兵」，位置为 −1。将 2 入栈。
  • 栈：[2(3)]
• 我们枚举4，5 和 9，都不会移除任何栈顶元素，得到它们左侧的柱子分别是 2，4 和 5，位置分别为 3，4 和 5。将它们入栈。
  • 栈：[2(3), 4(4), 5(5), 9(6)]
• 我们枚举 3，依次移除栈顶元素 9，5 和 4，得到 3 左侧的柱子是 2，位置为 3。将 3 入栈。
  • 栈：[2(3), 3(7)]

这样以来，我们得到它们左侧的柱子编号分别为 [-1, 0, -1, -1, 3, 4, 5, 3]。用相同的方法，我们从右向左进行遍历，也可以得到它们右侧的柱子编号分别为 [2, 2, 3, 8, 7, 7, 7, 8]，这里我们将位置 8 看作「哨兵」。

在得到了左右两侧的柱子之后，我们就可以计算出每根柱子对应的左右边界，并求出答案了。

# @lc code=start
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # maxs=0
        # for i in range(len(heights)):
        #     for j in range(i,len(heights)):
        #         ms=min(heights[i:j+1])
        #         maxs=max(maxs,ms*(j-i+1))
        # return maxs
        n = len(heights)
        left, right = [0] * n, [0] * n

        mono_stack = list()
        for i in range(n):
            while mono_stack and heights[mono_stack[-1]] >= heights[i]:
                mono_stack.pop()
            left[i] = mono_stack[-1] if mono_stack else -1
            mono_stack.append(i)
        
        mono_stack = list()
        for i in range(n - 1, -1, -1):
            while mono_stack and heights[mono_stack[-1]] >= heights[i]:
                mono_stack.pop()
            right[i] = mono_stack[-1] if mono_stack else n
            mono_stack.append(i)
        
        ans = max((right[i] - left[i] - 1) * heights[i] for i in range(n)) if n > 0 else 0
        return ans

Companies

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

# [81] 搜索旋转排序数组 II
#

# @lc code=start
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        if target in nums:
            return True
        else:return False

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

# @lc app=leetcode.cn id=80 lang=python3
#
# [80] 删除有序数组中的重复项 II
#

# @lc code=start
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 2
        for i in range(2, len(nums)):
            if nums[i] != nums[j - 2]:
                nums[j] = nums[i]
                j += 1
        return j

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例 2：

输入：s = "a", t = "a"
输出："a"

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

• 1 <= s.length, t.length <= 105
• s 和 t 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

# @lc app=leetcode.cn id=76 lang=python3
#
# [76] 最小覆盖子串
#
#滑动窗口方法
# @lc code=start
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        dict1=dict()
        for i in t:
            if i in dict1:
                dict1[i]+=1
            else:
                dict1[i]=1
        def isempty(dicts):
            for i in dicts:
                if dicts[i]>0:
                    return False
            return True
        if len(t)==1:
            if t in s:return t
            else: return ""
        j=-1
        i=0
        m=i
        n=j
        lens= 10**5
        while  i<=len(s)-len(t):
            if isempty(dict1):
                if j-i+1<lens:
                    lens=j-i+1
                    m=i
                    n=j
                if s[i] in dict1:
                    dict1[s[i]]= dict1[s[i]]+1
                i=i+1
            elif j<len(s)-1:
                j=j+1
                if s[j] in dict1 :
                    dict1[s[j]]=dict1[s[j]]-1  
            elif j==len(s)-1:
                i=i+1             
                    
        if lens == 10**5:
            return ""
        else: return s[m:n+1]