月度归档： 2022年1月

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

输入：root = [1,null,2,3]
输出：[1,3,2]

# @lc app=leetcode.cn id=94 lang=python3
#
# [94] 二叉树的中序遍历
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        nums=[]
        def inorder(root):
            if root==None:
                return 
            inorder(root.left)
            nums.append(root.val)
            inorder(root.right)
        
        inorder(root)
        return nums
# @lc code=end

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如：”0.1.2.201″ 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、”192.168.1.312″ 和 “192.168@1.1” 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "1111"
输出：["1.1.1.1"]

示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

思路回溯算法

# @lc app=leetcode.cn id=93 lang=python3
#
# [93] 复原 IP 地址
#
#回溯算法：
# void backtracking(参数) {
#     if (终止条件) {
#         存放结果;
#         return;
#     }

#     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
#         处理节点;
#         backtracking(路径，选择列表); // 递归
#         回溯，撤销处理结果
#     }
# }

# @lc code=start
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def backtracking(n,now,k,rev):
            if  k==1:
                if n-now in range(1,4) and str(int(s[now:n]))==s[now:n] and int(s[now:n]) in range(0,256):
                    res.append(rev+s[now:n]) 
                return
            for i in range(1,4):
                if now+i<n and str(int(s[now:now+i]))==s[now:now+i] and int(s[now:now+i]) in range(0,256):
                    now=now+i
                    backtracking(n,now,k-1,rev+s[now-i:now]+".")
                    now=now-i
        # s = "25525511125"
        rev=str()
        res=list()
        backtracking(len(s),0,4,rev)
        return res
# @lc code=end

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

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

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

# [92] 反转链表 II
#反转 left 到 right 部分以后，再拼接起来 

# @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 reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        def reverse_linked_list(head: ListNode):
            # 也可以使用递归反转一个链表
            pre = None
            cur = head
            while cur:
                next = cur.next
                cur.next = pre
                pre = cur
                cur = next

        # 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        dummy_node = ListNode(-1)
        dummy_node.next = head
        pre = dummy_node
        # 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        # 建议写在 for 循环里，语义清晰
        for _ in range(left - 1):
            pre = pre.next

        # 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        right_node = pre
        for _ in range(right - left + 1):
            right_node = right_node.next
        # 第 3 步：切断出一个子链表（截取链表）
        left_node = pre.next
        curr = right_node.next

        # 注意：切断链接
        pre.next = None
        right_node.next = None

        # 第 4 步：同第 206 题，反转链表的子区间
        reverse_linked_list(left_node)
        # 第 5 步：接回到原来的链表中
        pre.next = right_node
        left_node.next = curr
        return  dummy_node.next
        # @lc code=end

一条包含字母 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