class Solution:
    def twoSum(self, nums, target):
        """
        暴力法，两重循环搜索解
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

class Solution(object):
    def twoSum(self, nums, target):
        """
        利用字典实现 Hash表
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 转换为 (value, id) 字典
        dic = dict(map(lambda x: (x[1], x[0]), enumerate(nums)))

        for i, v in enumerate(nums):
            j = dic.get(target - v)
            # 找到 target-v 且不是本身
            if j and i != j:
                return [i, j]

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        result = ListNode(0)
        temp = result
        # 进位标识
        bit = 0
        while l1 or l2:
            # l1 或 l2 缺的部分补0
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            total = val1 + val2 + bit
            bit = total // 10
            temp.next = ListNode(total % 10)
            # l1、l2 指针继续往后移动
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
            # 存储结果的指针也向后移动
            temp = temp.next

        # 末尾还存在进位
        if bit != 0:
            temp.next = ListNode(bit)
        return result.next

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        滑动窗口法
        :type s: str
        :rtype: int
        """
        maxn = 0
        # 保存当前最长的子串
        temp = ''
        for c in s:
            if c not in temp:
                temp += c
            else:
                maxn = max(maxn, len(temp))
                # 找到重复的字符，截断前面部分，末尾继续加
                temp = temp[temp.index(c) + 1:] + c
        # 若 s 只包含一个字符，则 maxn 无法更新
        return max(maxn, len(temp))

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        滑动窗口法 + 哈希字典
        :type s: str
        :rtype: int
        """
        maxn = 0
        # 最长子串的起始位置
        start = 0
        dic = {}
        for i, c in enumerate(s):
            index = dic.get(c)
            # 当前字符在字典中，更新 start
            if index:
                start = max(start, index)
            # 添加到字典中
            dic[c] = i + 1
            # 记录当前最大长度
            maxn = max(maxn, i - start + 1)
        return maxn

class Solution(object):
    def isMatch(self, s, p):
        """
        使用回溯法求解
        :type s: str
        :type p: str
        :rtype: bool
        """
        if not p:
            return not s
        # bool(s) 判断s是否为空
        first_match = bool(s) and p[0] in {s[0], '.'}

        if len(p) >= 2 and p[1] == '*':
            return (self.isMatch(s, p[2:]) or
                    first_match and self.isMatch(s[1:], p))
        else:
            # 如果没有 '*'，则按位匹配即可
            return first_match and self.isMatch(s[1:], p[1:])

class Solution(object):
    def isMatch(self, s, p):
        """
        使用自底向上的动态规划算法求解
        :type s: str
        :type p: str
        :rtype: bool.
        """
        dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]

        dp[-1][-1] = True
        for i in range(len(s), -1, -1):
            for j in range(len(p) - 1, -1, -1):
                first_match = i < len(s) and p[j] in {s[i], '.'}
                if j + 1 < len(p) and p[j + 1] == '*':
                    dp[i][j] = dp[i][j + 2] or first_match and dp[i + 1][j]
                else:
                    dp[i][j] = first_match and dp[i + 1][j + 1]

        return dp[0][0]

class Solution(object):
    def maxArea(self, height):
        """
        暴力法，计算出任何两线段围成的矩形面积
        然后再取出最大的面积
        :type height: List[int]
        :rtype: int
        """
        n = len(height)
        maxa = 0
        for i in range(n):
            for j in range(i + 1, n):
                temp = abs(i - j) * min(height[i], height[j])
                if maxa < temp:
                    maxa = temp
        return maxa

class Solution(object):
    def maxArea(self, height):
        """
        双指针法
        :type height: List[int]
        :rtype: int
        """
        l = 0
        r = len(height) - 1
        result = 0
        while l < r:
            result = max(result, (r - l) * min(height[l], height[r]))
            # 较短线段向中间移动，能够获得更大的面积
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return result

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
         # 元素少于3个，返回空列表
        if len(nums) < 3:
            return []
        nums.sort()
        result = []
        for i in range(len(nums) - 1):
            # num[i] > 0 后不会存在3个数和为0
            if nums[i] <= 0:
                # 去重 nums[i]
                if i > 0 and nums[i] == nums[i - 1]:
                    continue
                l, r = i + 1, len(nums) - 1
                while l < r:
                    if nums[i] + nums[l] + nums[r] < 0:
                        l += 1
                    elif nums[i] + nums[l] + nums[r] > 0:
                        r -= 1
                    else:
                        result.append([nums[i], nums[l], nums[r]])
                        # 去重 num[l] 和 nums[r]
                        while l < r and nums[l] == nums[l + 1]:
                            l += 1
                        while l < r and nums[r] == nums[r - 1]:
                            r -= 1
                        # 两指针向中间移动
                        l += 1
                        r -= 1
        return result

def help(list1, list2):
    """
    实现两个字符数组的所有排列组合
    """
    result = []
    for s1 in list1:
        for s2 in list2:
            result.append(s1 + s2)
    return result


class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        # 空串判断
        if not digits:
            return []

        dic = {
            '2': ['a', 'b', 'c'],
            '3': ['d', 'e', 'f'],
            '4': ['g', 'h', 'i'],
            '5': ['j', 'k', 'l'],
            '6': ['m', 'n', 'o'],
            '7': ['p', 'q', 'r', 's'],
            '8': ['t', 'u', 'v'],
            '9': ['w', 'x', 'y', 'z']
        }
        result = dic.get(digits[0])
        i = 1
        while i < len(digits):
            result = help(result, dic.get(digits[i]))
            i += 1
        return result

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        两次遍历法
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        total = 1
        curr = head
        while curr.next:
            total += 1
            curr = curr.next

        # 顺数第 m 个节点
        m = total - n + 1
        # 只有一个节点或者要删除的是首节点
        if not head.next or m == 1:
            return head.next
            
        # 找到要删除节点的前一个节点
        curr = head
        while m - 1 > 1:
            curr = curr.next
            m -= 1

        delete = curr.next
        curr.next = delete.next
        return head

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        一次遍历法
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        first = ListNode(0)
        first.next = head
        second = first
        # first指向第 N 个节点
        for i in range(n):
            first = first.next
        # second指向第 L-N 个节点
        while first.next:
            first = first.next
            second = second.next
        # 要删除的是首节点
        if second.next == head:
            return head.next
        # 删除第 L-N+1 个节点
        else:
            second.next = second.next.next
            return head

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        # 空字符串
        if not s:
            return True
        dic = {
            '(': ')',
            '[': ']',
            '{': '}'
        }
        stack = []
        for c in s:
            # 栈不为空
            if stack:
                top = dic.get(stack[-1])
                # 如果是右括号
                if not top:
                    return False
                # 匹配栈顶左括号
                if c.__eq__(top):
                    stack.pop()
                # 不匹配就压栈
                else:
                    stack.append(c)
            else:
                stack.append(c)
        # 栈为空表示所有括号匹配
        return not stack

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        # l1, l2均为非空链表
        result = ListNode(0)
        temp = result
        while l1 and l2:
            if l1.val <= l2.val:
                temp.next = l1
                l1 = l1.next
            else:
                temp.next = l2
                l2 = l2.next
            temp = temp.next
        # l1, l2存在空链表
        temp.next = l1 if l1 else l2
        return result.next

def new_insert(st):
    """
    在有效括号序列中插入一对新的括号
    :param st: 有效括号序列
    :return: 插入后的有效括号序列
    """
    if not st:
        return {'()'}

    result = set()
    for s in st:
        for i in range(len(s)):
            result.add(s[:i+1] + '()' + s[i+1:])
    return result


class Solution(object):
    def generateParenthesis(self, n):
        """
        动态规划方法
        :type n: int
        :rtype: List[str]
        """
        # 保存 i=1 to n 对括号的生成结果
        result = []
        temp = set()
        while n > 0:
            temp = new_insert(temp)
            result.append(list(temp))
            n -= 1
        return result[-1]

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None


def ordered_insert(lists, elem):
    """
    将 elem 有序插入到 lists 中，并返回插入后的有序列表
    """
    if not lists:
        return [elem]

    for i in range(len(lists)):
        # 寻找合适的位置插入
        if lists[i] > elem:
            lists.insert(i, elem)
            break
        # 找不到则插入到末尾
        if i == len(lists) - 1:
            lists.append(elem)
    return lists


class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        result = []
        # 遍历每个链表中的元素，将其插入到 result 列表中
        for lt in lists:
            while lt:
                result = ordered_insert(result, lt.val)
                lt = lt.next
        head = ListNode(0)
        temp = head
        # 将有序的列表转换为有序的链表
        for r in result:
            temp.next = ListNode(r)
            temp = temp.next
        return head.next

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        i = len(nums) - 2
        # 找到 num[i+1] > nums[i] 的位置
        while i >= 0 and nums[i + 1] <= nums[i]:
            i -= 1

        if i >= 0:
            j = len(nums) - 1
            # 寻找比 nums[i] 略大的数 nums[j]，并交换位置
            while j >= 0 and nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        # 反转 nums[i] 后面的所有数字，以获取它们的最小排列
        l, r = i + 1, len(nums) - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        # 我们只关心维数大于 1 的矩阵
        if n > 1:
            # 设置元素是否被处理过的标识
            flag = [[False] * n for _ in range(n)]
            for i in range(n):
                for j in range(i + 1, n):
                    if not flag[i][j]:
                        """
                        [5, 1, 9, 11],
                        [2, 4, 8, 10],
                        [13, 3, 6, 7],
                        [15, 14, 12, 16]
                        # 旋转的思路，以i=0、j=1为例：
                        m[0][1] -> m[1][n-1-0], 1 -> 10
                        m[1][n-1-0] -> m[n-1-0][n-1-1], 10 -> 12
                        m[n-1-0][n-1-1] -> m[n-1-1][0], 12 -> 13
                        m[n-1-1][0] -> m[0][1], 13 -> 1
                        """
                        curr = matrix[i][j]
                        matrix[i][j] = matrix[n - 1 - j][i]
                        matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
                        matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
                        matrix[j][n - 1 - i] = curr
                        flag[i][j] = True
                        flag[j][n - 1 - i] = True
                        flag[n - 1 - j][i] = True
                        flag[n - 1 - i][n - 1 - j] = True

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        dic = {}
        for i, s in enumerate(strs):
            # 每个字符串按照字母序排序
            ordered = ''.join((lambda x: (x.sort(), x))(list(s))[1])
            # 将字母序作为 key，实际值作为 value 存到字典
            if ordered not in dic:
                dic[ordered] = [strs[i]]
            else:
                dic[ordered].append(strs[i])
        # 将每个字母序的实际值取出返回
        return list(dic.values())

class Solution(object):
    def maxSubArray(self, nums):
        """
        动态规划方法
        :type nums: List[int]
        :rtype: int
        """
        # 保存当前和，最大和
        curr_sum, result = nums[0], nums[0]
        for num in nums:
            # 对结果有增益价值，则继续加和
            if curr_sum > 0:
                curr_sum += num
            # 无增益价值，则更换为当前数字
            else:
                curr_sum = num
            # 更新当前获得的最大和
            result = max(result, curr_sum)
        return result

class Solution(object):
    def maxSubArray(self, nums):
        """
        分治法
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 1:
            return nums[0]
        # 左半边的最大子序和
        maxleft = self.maxSubArray(nums[:n // 2])
        # 右半边的最大子序和
        maxright = self.maxSubArray(nums[n // 2:])
        # 中间的最大子序和
        m = n // 2
        templ, tempr = 0, 0
        mid_maxl, mid_maxr = nums[m - 1], nums[m]
        for i in range(m):
            templ += nums[m - 1 - i]
            mid_maxl = max(mid_maxl, templ)
            tempr += nums[m + i]
            mid_maxr = max(mid_maxr, tempr)
        # n 为奇数的时候，上面的循环会漏掉最后一个元素
        if n % 2 != 0:
            tempr += nums[n - 1]
            mid_maxr = max(mid_maxr, tempr)
        maxmid = mid_maxl + mid_maxr
        # 返回全局的最大子序和
        return max(maxleft, maxmid, maxright)

class Solution(object):
    def canJump(self, nums):
        """
        动态规划算法
        :type nums: List[int]
        :rtype: bool
        """
        n = len(nums)
        # 标记是否是跳到终点的好位置，0-不是，1-是
        flag = [0] * n
        flag[n - 1] = 1
        # 从右往左寻找能跳到终点的所有点
        for i in range(n - 2, -1, -1):
            further_jump = min(i + nums[i], n - 1)
            for j in range(i + 1, further_jump + 1):
                if flag[j] == 1:
                    flag[i] = 1
                    break
        # 最终看起点是否也能跳到
        return flag[0] == 1

class Solution(object):
    def canJump(self, nums):
        """
        贪心算法
        :type nums: List[int]
        :rtype: bool
        """
        good_pos = len(nums) - 1
        # 从右向左迭代，对每个位置检查是否存在一步跳跃可以到达最后一个位置
        for i in range(len(nums) - 1, -1, -1):
            if i + nums[i] >= good_pos:
                good_pos = i
        return good_pos == 0