一、Algorithm

8. 字符串转换整数 (atoi)

https://leetcode-cn.com/problems/string-to-integer-atoi/

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0 。

提示：

本题中的空白字符只包括空格字符 ‘ ‘ 。假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: “42” 输出: 42 示例 2:

输入: “ -42” 输出: -42 解释: 第一个非空白字符为 ‘-‘, 它是一个负号。我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。示例 3:

输入: “4193 with words” 输出: 4193 解释: 转换截止于数字 ‘3’ ，因为它的下一个字符不为数字。示例 4:

输入: “words and 987” 输出: 0 解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。因此无法执行有效的转换。示例 5:

输入: “-91283472332” 输出: -2147483648 解释: 数字 “-91283472332” 超过 32 位有符号整数范围。因此返回 INT_MIN (−231) 。

#
# 
# @param str string字符串 
# @return int整型
#
# 有限状态机
INT_MAX = 2**31 -1
INT_MIN = -2**31
class Automation:
    def __init__(self):
        self.state = "start"
        self.flag = 1
        self.result =0
        self.table = {
            "start": ["start","signed","in_number","end"],
            "signed":["end","end","in_number","end"],
            "in_number":["end","end","in_number","end"],
            "end":["end","end","end","end"]
        }
        
    def get_col(self,c:str):
        if c.isspace():
            return 0
        elif c in ["+", "-"]:
            return 1
        elif c.isdigit():
            return 2
        else:
            return 3
    def get(self,c):
        self.state = self.table[self.state][self.get_col(c)]
        if self.state == "in_number":
            self.result = self.result * 10 + int(c)
            self.result = min(self.result, INT_MAX) if self.flag == 1 else min(self.result, -INT_MIN)
        if self.state == "signed":
            self.flag = 1 if c == "+" else -1
            
class Solution:
    def atoi(self , str ):
        # write code here
        auto = Automation()
        for i in str:
            auto.get(i)
        return auto.flag * auto.result
        

可以用下面的表格来表示这个自动机：

	空字符	加减号	数字	其他
Start	Start	Signed	in_number	end
Signed	End	End	in_number	end
in_number	End	End	in_number	end
end	end	end	end	end

15. 三数之和

https://leetcode-cn.com/problems/3sum/

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
    #     nums.sort()
    #     result = []
    #     l_nums = len(nums)
    #     for first in range(l_nums):
    #         if first>0 and nums[first] == nums[first-1]:
    #             continue
    #         third = l_nums - 1
    #         total = -nums[first]

    #         for second in range(first+1,l_nums):
    #             if second > first+1 and nums[second] == nums[second-1]:
    #                 continue
    #             if nums[second] + nums[third] < total:
    #                 continue

    #             while second < third and nums[second] + nums[third] > total:
    #                 third -= 1

    #             if second == third:
    #                 continue

    #             if nums[second] + nums[third] == total:
    #                 result.append([nums[first], nums[second], nums[third]])
    #     return result


        nums.sort()
        res, k = [], 0
        for k in range(len(nums) - 2):
            if nums[k] > 0: break # 1. because of j > i > k.
            if k > 0 and nums[k] == nums[k - 1]: continue # 2. skip the same `nums[k]`.
            i, j = k + 1, len(nums) - 1
            while i < j: # 3. double pointer
                s = nums[k] + nums[i] + nums[j]
                if s < 0:
                    i += 1
                    while i < j and nums[i] == nums[i - 1]: i += 1
                elif s > 0:
                    j -= 1
                    while i < j and nums[j] == nums[j + 1]: j -= 1
                else:
                    res.append([nums[k], nums[i], nums[j]])
                    i += 1
                    j -= 1
                    while i < j and nums[i] == nums[i - 1]: i += 1
                    while i < j and nums[j] == nums[j + 1]: j -= 1
        return res

22. 括号生成

https://leetcode-cn.com/problems/generate-parentheses/

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例：

输入：n = 3 输出：[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
      # dfs 1
    #     if n == 0:
    #         return []
    #     total_l = []
    #     total_l.append([None])    # 0组括号时记为None
    #     total_l.append(["()"])    # 1组括号只有一种情况
    #     for i in range(2,n+1):    # 开始计算i组括号时的括号组合
    #         l = []        
    #         for j in range(i):    # 开始遍历 p q ，其中p+q=i-1 , j 作为索引
    #             now_list1 = total_l[j]    # p = j 时的括号组合情况
    #             now_list2 = total_l[i-1-j]    # q = (i-1) - j 时的括号组合情况
    #             for k1 in now_list1:  
    #                 for k2 in now_list2:
    #                     if k1 == None:
    #                         k1 = ""
    #                     if k2 == None:
    #                         k2 = ""
    #                     el = "(" + k1 + ")" + k2
    #                     l.append(el)    # 把所有可能的情况添加到 l 中
    #         total_l.append(l)    # l这个list就是i组括号的所有情况，添加到total_l中，继续求解i=i+1的情况
    #     return total_l[n]


    # dfs 2
        res = []
        s = ''
        def dfs(s,left,right,n):
            if left == n and right == n:
                res.append(s)
            if left < right:
                return res
            if left < n:
                dfs(s+'(', left+1, right, n)
            if right < n:
                dfs(s+')', left, right+1, n)
        dfs(s, 0, 0, n)
        return res

39. 组合总和

https://leetcode-cn.com/problems/combination-sum/

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。解集不能包含重复的组合。示例 1：

输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ] 示例 2：

输入：candidates = [2,3,5], target = 8, 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]

提示：

1 <= candidates.length <= 30 1 <= candidates[i] <= 200 candidate 中的每个元素都是独一无二的。 1 <= target <= 500

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        temp = []
        def recursion(idx, total):
            if idx >= len(candidates) or total >= target:
                if total == target:
                    result.append(temp[:])
                return
            temp.append(candidates[idx])
            recursion(idx, total + candidates[idx])
            temp.pop()
            recursion(idx+1 , total)
        recursion(0, 0)
        return result

40. 组合总和 II

https://leetcode-cn.com/problems/combination-sum-ii/

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。解集不能包含重复的组合。示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] 示例 2:

输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]

import collections
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        temp = []
        candidates.sort()
        seq = sorted(collections.Counter(candidates).items())
        def recursion(idx, total):
            if idx >= len(seq) or total >= target:
                if total == target:
                    result.append(temp[:])
                return 
            most = min((target-total)//seq[idx][0], seq[idx][1])
            for i in range(1, most+1):
                temp.append(seq[idx][0])
                recursion(idx+1, total + i * seq[idx][0])
            if most:
                temp[:] = temp[:-most]

            recursion(idx+1, total)
        recursion(0,0)
        
        # 二维list去重
        # unique_result = list(list(i) for i in set([tuple(t) for t in result]))
        # return unique_result
        return result

64. 最小路径和

https://leetcode-cn.com/problems/minimum-path-sum/

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。示例 2：

输入：grid = [[1,2,3],[4,5,6]] 输出：12

提示：

m == grid.length n == grid[i].length 1 <= m, n <= 200 0 <= grid[i][j] <= 100

class Solution:
    def minPathSum(self, matrix: List[List[int]]) -> int:
        l_r = len(matrix)
        if l_r == 0:
            return None
        l_c = len(matrix[0])

        dp = [[0 for i in range(l_c)] for j in range(l_r)]
        dp[0][0] = matrix[0][0]
        for i in range(1, l_c):
            dp[0][i] = dp[0][i - 1] + matrix[0][i]
        for i in range(1, l_r):
            dp[i][0] = dp[i - 1][0] + matrix[i][0]

        for i in range(1, l_r):
            for j in range(1, l_c):
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j]
        return dp[-1][-1]

88. 合并两个有序数组

https://leetcode-cn.com/problems/merge-sorted-array/ 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明：

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例：

输入： nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3

输出：[1,2,2,3,5,6]

提示：

-10^9 <= nums1[i], nums2[i] <= 10^9 nums1.length == m + n nums2.length == n

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.
        """
        nums1_copy = nums1[:m]
        nums1[:] = []
        p1 = p2 = 0
        while p1 < m and p2 < n:
            if nums1_copy[p1] <= nums2[p2]:
                nums1.append(nums1_copy[p1])
                p1 += 1
                continue
            else:
                nums1.append(nums2[p2])
                p2 += 1
                continue

        nums1.extend(nums1_copy[p1:])
        nums1.extend(nums2[p2:])

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1    / \   2   2  / \ / \ 3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1    / \   2   2    \   \    3    3

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

    # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:

        # 1、递归
        # def is_mirror(root1, root2):
        #     if root1 is None and root2 is None:
        #         return True
        #     if root1 is None and root2 is not None:
        #         return False
        #     if root1 is not None and root2 is None:
        #         return False
        #     return root1.val == root2.val  and is_mirror(root1.left, root2.right)  and  is_mirror(root1.right, root2.left)
        
        # return is_mirror(root, root)

        # 2、迭代
        check_list = [root, root]
        while check_list:
            node1 = check_list.pop()
            node2 = check_list.pop()
            if node1 is None and node2 is None:
                continue
            if node1.val != node2.val:
                return False
            
            if node1.left and node2.right:
                check_list.append(node1.left)
                check_list.append(node2.right)

            if node1.right and node2.left:
                check_list.append(node1.right)
                check_list.append(node2.left)

            if node1.left and node2.right is None:
                return False
            elif node1.right and node2.left is None:
                return False
            elif node1.left is None and node2.right:
                return False
            elif node1.right is None and node2.left:
                return False
        return True

        # 3、正反向先序遍历，比较列表
        # if not root:
        #     return True
        # pre_list = []
        # after_list = []
        # def pre_order(root):
        #     pre_list.append(root.val)
        #     if root.left:
        #         pre_order(root.left)
        #     else:
        #         pre_list.append(-1)
        #     if root.right:
        #         pre_order(root.right)
        #     else:
        #         pre_list.append(-1)
            
        # def after_order(root):
        #     after_list.append(root.val)
        #     if root.right:
        #         after_order(root.right)
        #     else:
        #         after_list.append(-1)
        #     if root.left:
        #         after_order(root.left)
        #     else:
        #         after_list.append(-1)
        
        # pre_order(root)
        # after_order(root)
        # if pre_list == after_list:
        #     return True
        # else:
        #     return False

121. 买卖股票的最佳时机

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/ 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。示例 2:

输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #暴力法 O(n^2)
        # max_profit = 0
        # for i in range(len(prices) - 1):
        #     for j in range(i + 1, len(prices)):
        #         if prices[j] > prices[i]:
        #             max_profit = max(max_profit, prices[j] - prices[i])
        # return max_profit
        
        # 差值法 O(n)
        min_price = max(prices)
        max_profit = 0
        for i in prices:
            if i < min_price:
                min_price = i
            elif i - min_price > max_profit:
                max_profit = i - min_price
        return max_profit

122. 买卖股票的最佳时机 II

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/ 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。示例 2:

输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。示例 3:

输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 3 * 10 ^ 4 0 <= prices[i] <= 10 ^ 4

class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        # 假设每天都买入卖出，所有上涨（正值）都是盈利
        result = 0
        if not prices:
            return result
        for n in range(len(prices) - 1):
            if prices[n + 1] - prices[n] > 0:
                result += (prices[n + 1] - prices[n] )
        return result
        
        # 笨方法
        # if len(prices) <= 1:
        #     return 0
        # profit_list = []
        # start = pre = None
        # for price in prices:
        #     if start is None:
        #         start = price
        #         pre = price
        #         continue
        #     if price < pre:
        #         if pre == start:
        #             start = price
        #             pre = price
        #         else:
        #             profit_list.append(pre - start)
        #             start = price
        #             pre = price
        #     else:
        #         pre = price
        # else:
        #     if prices[-1] > start:
        #         profit_list.append(prices[-1] - start)
        # return sum(profit_list)

124. 二叉树中的最大路径和

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1：

输入：[1,2,3]

   1
  / \
 2   3

输出：6 示例 2：

输入：[-10,9,20,null,null,15,7]

-10 /
9 20 /
15 7

输出：42

# 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 __init__(self):
        self.max_sum = float("-inf")  # 最小值
    def maxPathSum(self, root: TreeNode) -> int:
        def gain_max(node):
            if node is None:
                return 0
            l = max(gain_max(node.left), 0) # 左子树贡献值最大值 （不取为0）
            r = max(gain_max(node.right), 0) # 右子树贡献值最大值 （不取为0）
            cur = node.val + l + r
            self.max_sum = max(self.max_sum, cur) # 更新最大值
            return node.val + max(l, r) # 返回当前节点最大贡献值
        gain_max(root)
        return self.max_sum

146. LRU缓存机制

https://leetcode-cn.com/problems/lru-cache/

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例：

输入 [“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4]

解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4

提示：

1 <= capacity <= 3000 0 <= key <= 3000 0 <= value <= 104 最多调用 3 * 104 次 get 和 put

class DLinkedNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        self.pre = None

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = dict()
        self.head = DLinkedNode(0,0)
        self.tail = DLinkedNode(0,0)
        self.head.next = self.tail
        self.tail.pre = self.head
        self.capacity = capacity
        self.size = 0


    def get(self, key: int) -> int:
        if key not in self.cache.keys():
            return -1
        
        node = self.cache[key]
        self.move_to_top(node)
        return node.value


    def put(self, key: int, value: int) -> None:
        if key in self.cache.keys():
            node = self.cache[key]
            node.value = value
            self.move_to_top(node)
        else:
            new_node = DLinkedNode(key,value)
            self.cache[key] = new_node
            self.insert_to_head(new_node)
            self.size += 1

            if self.size > self.capacity:
                pop_node = self.pop_tail()
                self.cache.pop(pop_node.key)
                self.size -= 1
    
    def move_to_top(self, node):
        self.remove_node(node)
        self.insert_to_head(node)

    def remove_node(self,node):
        pre_node = node.pre
        next_node = node.next
        pre_node.next = next_node
        next_node.pre = pre_node

    def insert_to_head(self, node):
        head_next = self.head.next
        self.head.next = node
        node.next = head_next
        node.pre = self.head
        head_next.pre = node

    def pop_tail(self):
        node = self.tail.pre
        self.remove_node(node)
        return node




# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

141. 环形链表

https://leetcode-cn.com/problems/linked-list-cycle/ 给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：

输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：

输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：

输入：head = [1], pos = -1 输出：false 解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104] -105 <= Node.val <= 105 pos 为 -1 或者链表中的一个有效索引。

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

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 队列查询法
        # result = []
        # while head:
        #     if head not in result:
        #         result.append(head)
        #         head = head.next
        #     else:
        #         return True
        # else:
        #     return False

        # 快慢指针：存在循环则必然相遇
        if not head or not head.next:
                return False
            
            slow = head
            fast = head.next

            while slow != fast:
                if not fast or not fast.next:
                    return False
                slow = slow.next
                fast = fast.next.next
            
            return True

142. 环形链表 II

https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/ 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

示例 1：

输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。示例 2：

输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点解释：链表中有一个环，其尾部连接到第一个节点。示例 3：

输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 104] 内 -105 <= Node.val <= 105 pos 的值为 -1 或者链表中的一个有效索引

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

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        result = []
        while head:
            if head not in result:
                result.append(head)
                head = head.next
            else:
                return head
        return None

143. 重排链表

https://leetcode-cn.com/problems/reorder-list/

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3. 示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        
#        1.数组记录，操作数组指向
#         if head is None:
#             return None
#         temp = []
#         start = head
#         while start:
#             temp.append(start)
#             start = start.next
        
#         i,j = 0, len(temp)-1
#         while i<j:
#             temp[i].next = temp[j]
#             i += 1
#             if i>=j:
#                 break
#             temp[j].next = temp[i]
#             j -= 1
#         temp[i].next = None
        
        
        
        
        # 2. 先获取中间节点，再反转后半部分，再拼接两个链表
        def get_mid(head): #双节点取前一个
            slow = fast = head
            while fast.next and fast.next.next:
                fast = fast.next.next
                slow = slow.next
            return slow
        def reverse_link(head):
            if head is None or head.next is None:
                return head
            p = reverse_link(head.next)
            head.next.next = head
            head.next = None
            return p
        def merge_nodes(l1,l2):
            while l1 and l2:
                l1_next = l1.next
                l2_next = l2.next

                l1.next = l2
                l1 = l1_next
                
                l2.next = l1
                l2 = l2_next

        if head is None:
            return head
        start = head
        mid_node = get_mid(head)

        temp = mid_node.next
        mid_node.next = None

        revered_mid_node = reverse_link(temp)
        merge_nodes(start, revered_mid_node)

155. 最小栈

https://leetcode-cn.com/problems/min-stack/ 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。

示例:

输入： [“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”] [[],[-2],[0],[-3],[],[],[],[]]

输出： [null,null,null,null,-3,null,0,-2]

解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); –> 返回 -3. minStack.pop(); minStack.top(); –> 返回 0. minStack.getMin(); –> 返回 -2.

提示：

pop、top 和 getMin 操作总是在非空栈上调用。

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min = None


    def push(self, x: int) -> None:
        self.stack.append(x)
        if self.min is None or x < self.min :
            self.min = x 

    def pop(self) -> None:
        self.stack.pop()
        self.min = min(self.stack) if self.stack else None

    def top(self) -> int:
        return self.stack[-1] if self.stack else None

    def getMin(self) -> int:
        return self.min

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。示例 2：

输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

0 <= nums.length <= 100 0 <= nums[i] <= 400

class Solution:
    def rob(self, nums: List[int]) -> int:
        # dp
        size = len(nums)
        if size == 0:
            return 0
        if size == 1:
            return nums[0]

        max_profits = [0] * size
        max_profits[0] = nums[0]
        max_profits[1] = max(nums[0], nums[1])
        for i in range(2,size):
            max_profits[i] = max(max_profits[i-1], max_profits[i-2] + nums[i])
        return max_profits[size -1 ]

200. 岛屿数量

https://leetcode-cn.com/problems/number-of-islands/

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [ [“1”,”1”,”1”,”1”,”0”], [“1”,”1”,”0”,”1”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”0”,”0”,”0”] ] 输出：1 示例 2：

输入：grid = [ [“1”,”1”,”0”,”0”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”1”,”0”,”0”], [“0”,”0”,”0”,”1”,”1”] ] 输出：3

提示：

m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] 的值为 ‘0’ 或 ‘1’

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        l_r = len(grid)
        if l_r == 0:
            return 0
        l_c = len(grid[0])
        count = 0
        # 深度优先
        # def dfs(grid, r, c):
        #     grid[r][c] = 0
        #     for i,j in [(r-1,c),(r+1,c),(r,c-1),(r,c+1)]:
        #         if 0<=i<len(grid) and 0<=j<len(grid[0]) and grid[i][j] == "1":
        #             dfs(grid, i, j)

        # for r in range(l_r):
        #     for c in range(l_c):
        #         if grid[r][c] == "1":
        #             count += 1
        #             dfs(grid,r,c)
        # return count

        # 广度优先搜索
        temp = []
        for r in range(l_r):
            for c in range(l_c):
                if grid[r][c] == "1":
                    count += 1
                    temp.append((r,c))
                    while temp:
                        row,col = temp.pop()
                        grid[row][col] = 0
                        for i ,j in [(row-1,col),(row+1,col),(row,col-1),(row,col+1)]:
                            if 0<=i<l_r and 0<=j<l_c and grid[i][j] == "1":
                                temp.append((i,j))
                                grid[i][j] == 0
        return count

206. 反转链表

https://leetcode-cn.com/problems/reverse-linked-list/

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # if head is None or head.next is None:
        #     return head
        # p = self.reverseList(head.next)
        # head.next.next = head
        # head.next = None
        # return p

        pre = None
        cur = head
        while cur:
            next_node = cur.next
            cur.next = pre
            pre = cur
            cur = next_node
        return pre

217. 存在重复元素

https://leetcode-cn.com/problems/contains-duplicate/ 给定一个整数数组，判断是否存在重复元素。

如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:

输入: [1,2,3,1] 输出: true 示例 2:

输入: [1,2,3,4] 输出: false 示例 3:

输入: [1,1,1,3,3,4,3,2,4,2] 输出: true

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums)) != len(nums)

226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：

  /   \   2     7  / \   / \ 1   3 6   9 输出：

  /   \   7     2  / \   / \ 9   6 3   1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:

        # 递归（反转左右节点，递归其子节点）
        if not root:
            return None
        
        root.left , root.right  = root.right, root.left

        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

        # 蛮力法： 层级遍历二叉树，记录进列表； 新建一个二叉树根据列表进行还原
        # if root is None:
        #     return None
        # result_list = []
        # start = root
        # temp_list = [start]
        # while temp_list:
        #     node = temp_list.pop(0)
        #     result_list.append(node)
        #     if node is None:
        #         continue
        #     temp_list.append(node.left)
        #     temp_list.append(node.right)
        # new_start = result_list.pop(0)
        # temp_list2=[new_start]

        # while result_list:
        #     temp = temp_list2.pop(0)
        #     node_right = result_list.pop(0)
        #     if node_right:
        #         temp.right = node_right
        #         temp_list2.append(node_right)
        #     else:
        #         temp.right = None

        #     node_left = result_list.pop(0)
        #     if node_left:
        #         temp.left = node_left
        #         temp_list2.append(node_left)
        #     else:
        #         temp.left = None
        # return new_start

231. 2的幂

https://leetcode-cn.com/problems/power-of-two/ 给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例 1:

输入: 1 输出: true 解释: 20 = 1 示例 2:

输入: 16 输出: true 解释: 24 = 16 示例 3:

输入: 218 输出: false

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False
        while n // 2  != 0:
            if n % 2 == 1:
                return False
            n = n// 2
        return True

234. 回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2 输出: false 示例 2:

输入: 1->2->2->1 输出: true 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

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

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # 时间O(n), 空间O(n)
        # result = []
        # while head:
        #     result.append(head.val)
        #     head = head.next
        # return result == result[::-1]

        # 时间O(n),空间O(1)
        # 通过快慢指针获取中间节点，然后反转中间节点之后的链表，再双向指针比对，最后再还原后半部分链表
        if not head:
            return True

        def get_half_node(head):
            fast = slow = head
            while fast.next and fast.next.next:
                fast = fast.next.next
                slow = slow.next
            return slow
        
        def reverse_link(head):
            previous = None
            current = head
            while current:
                next_node = current.next
                current.next = previous
                previous = current
                current = next_node
            return previous


        start = head
        half_node  = get_half_node(head)
        start_of_reversed_link = reverse_link(half_node.next)
        end = start_of_reversed_link

        result = True
        while result and end is not None:
            if start.val != end.val:
                return False
            start = start.next
            end = end.next
        half_node.next = reverse_link(start_of_reversed_link)
        return result

235. 二叉搜索树的最近公共祖先

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/ 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉搜索树中。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        # 二次遍历对比路径
        # def _get_path(root, node):
        #     path = []
        #     while root !=node:
        #         if node.val > root.val:
        #             path.append(root)
        #             root = root.right
        #         elif node.val < root.val:
        #             path.append(root)
        #             root = root.left
        #     path.append(root)

        #     return path

        # start1 = start2 = root
        # path_p = _get_path(start1, p)
        # path_q = _get_path(start2, q)

        # result = None
        # for i in zip(path_p,path_q):
        #     if i[0] == i[1]:
        #         result = i[0]
        #     else:
        #         break
        # return result

        # 递归
        ancestor = root
        if p.val< ancestor.val and q.val < ancestor.val:
            return self.lowestCommonAncestor(ancestor.left,p,q)
        
        if p.val > ancestor.val and q.val > ancestor.val:
            return self.lowestCommonAncestor(ancestor.right,p ,q)
        return ancestor

237. 删除链表中的节点

https://leetcode-cn.com/problems/delete-node-in-a-linked-list/ 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为要被删除的节点。

现有一个链表 – head = [4,5,1,9]，它可以表示为:

示例 1：

输入：head = [4,5,1,9], node = 5 输出：[4,1,9] 解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9. 示例 2：

输入：head = [4,5,1,9], node = 1 输出：[4,5,9] 解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

提示：

链表至少包含两个节点。链表中所有节点的值都是唯一的。给定的节点为非末尾节点并且一定是链表中的一个有效节点。不要从你的函数中返回任何结果。

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

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        # 固定思维限制了我。。。。
        node.val = node.next.val
        node.next = node.next.next

292. Nim 游戏

https://leetcode-cn.com/problems/nim-game/ 你和你的朋友，两个人一起玩 Nim 游戏：

桌子上有一堆石头。你们轮流进行自己的回合，你作为先手。每一回合，轮到的人拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。 j假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

示例 1：

输入：n = 4 输出：false 解释：如果堆中有 4 块石头，那么你永远不会赢得比赛；因为无论你拿走 1 块、2 块还是 3 块石头，最后一块石头总是会被你的朋友拿走。示例 2：

输入：n = 1 输出：true 示例 3：

输入：n = 2 输出：true

提示： 1 <= n <= 231 - 1

class Solution:
    def canWinNim(self, n: int) -> bool:
        # 大家都是聪明人，智商题
        return n % 4 != 0

300. 最长上升子序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

class Solution:
    def lengthOfLIS(self, arr: List[int]) -> int:
        l_arr = len(arr)
        dp = [1] * l_arr
        for i in range(l_arr):
            for j in range(i):
                if arr[j] < arr[i]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)

344. 反转字符串

https://leetcode-cn.com/problems/reverse-string/ 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：[“h”,”e”,”l”,”l”,”o”] 输出：[“o”,”l”,”l”,”e”,”h”] 示例 2：

输入：[“H”,”a”,”n”,”n”,”a”,”h”] 输出：[“h”,”a”,”n”,”n”,”a”,”H”]

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s[:] = s[::-1]

349. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2] 示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4]

说明：

输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

365. 有多少小于当前数字的数字

https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number/

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

示例 1：

输入：nums = [8,1,2,2,3] 输出：[4,0,1,1,3] 解释：对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。对于 nums[1]=1 不存在比它小的数字。对于 nums[2]=2 存在一个比它小的数字：（1）。对于 nums[3]=2 存在一个比它小的数字：（1）。对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。示例 2：

输入：nums = [6,5,4,8] 输出：[2,1,0,3] 示例 3：

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

提示：

2 <= nums.length <= 500 0 <= nums[i] <= 100

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
		"""暴力法"""
        # result = [0] * len(nums)
        # for i in range(len(nums)):
        #     count = 0
        #     for num in nums:
        #         if nums[i] > num:
        #             count += 1
        #     result[i] = count
        # return result
        """计数法"""
        nums_counts = [0] * 101
        for i in nums:
            nums_counts[i] += 1
        temp = 0
        for j in range(len(nums_counts)):
            temp, nums_counts[j] = temp + nums_counts[j], temp
        result = []
        for num in nums:
            result.append(nums_counts[num])
        return result

543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 : 给定二叉树

      1
     / \
    2   3
   / \     
  4   5     返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:

        self.max_diameter = 0
        def get_max_depth(root):
            if root is None:
                return 0
            L = get_max_depth(root.left)
            R = get_max_depth(root.right)
            if (L+R) >self.max_diameter:
                self.max_diameter = L+R
            return max(L , R)+ 1
        get_max_depth(root)
        return self.max_diameter

        # 获取深度 + 前序遍历， 想复杂了
        # if root is None:
        #     return 0
        # depth_list = []

        # def get_max_depth(root):
        #     if root is None:
        #         return -1
        #     if root.left is None and root.right is None:
        #         return 0
        #     return max(get_max_depth(root.left) + 1, get_max_depth(root.right) + 1)

        # def pre_order(root):
        #     depth_list.append(get_max_depth(root.left) + 2 + get_max_depth(root.right))
        #     if root.left:
        #         pre_order(root.left)
        #     if root.right:
        #         pre_order(root.right)

        # pre_order(root)
        # return max(depth_list)

557. 反转字符串中的单词 III

https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/ 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：

输入：”Let’s take LeetCode contest” 输出：”s’teL ekat edoCteeL tsetnoc”

提示：

在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join([sub[::-1] for sub in s.split()])

876. 链表的中间结点

https://leetcode-cn.com/problems/middle-of-the-linked-list/

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL. 示例 2：

输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

给定链表的结点数介于 1 和 100 之间。

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

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

941. 有效的山脉数组

https://leetcode-cn.com/problems/valid-mountain-array/ 给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：

A.length >= 3 在 0 < i < A.length - 1 条件下，存在 i 使得： A[0] < A[1] < … A[i-1] < A[i] A[i] > A[i+1] > … > A[A.length - 1]

示例 1：

输入：[2,1] 输出：false 示例 2：

输入：[3,5,5] 输出：false 示例 3：

输入：[0,3,2,1] 输出：true

提示：

0 <= A.length <= 10000 0 <= A[i] <= 10000

class Solution:
    def validMountainArray(self, A: List[int]) -> bool:


        if len(A)<3:
            return False

        i = 0
        j = len(A)-1
        for _ in range(len(A)-1):
            if A[i] < A[i+1]:
                i += 1
                continue
            if A[j] < A[j-1]:
                j -= 1
                continue
        return i != 0 and j != len(A)-1 and i == j

        # rise = fall = False
        # flag = True
        # pre = A[0]
        # for i in range(1,len(A)):
        #     if flag:
        #         if A[i] < pre:
        #             flag = False
        #             fall = True

        #         elif A[i] == pre:
        #             return False
        #         else:
        #             rise = True

        #     else:
        #         if A[i] >= pre:
        #             return False
        #     pre = A[i]

        # return rise and fall

LCP 01. 猜数字

https://leetcode-cn.com/problems/guess-numbers/ 小A 和小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回小A 猜对了几次？

输入的guess数组为小A 每次的猜测，answer数组为小B 每次的选择。guess和answer的长度都等于3。

示例 1：

输入：guess = [1,2,3], answer = [1,2,3] 输出：3 解释：小A 每次都猜对了。

示例 2：

输入：guess = [2,2,3], answer = [3,2,1] 输出：1 解释：小A 只猜对了第二次。

限制：

guess的长度 = 3 answer的长度 = 3 guess的元素取值为 {1, 2, 3} 之一。 answer的元素取值为 {1, 2, 3} 之一。

class Solution:
    def game(self, guess: List[int], answer: List[int]) -> int:
        count = 0
        for i in range(len(guess)):
            if guess[i] == answer[i]:
                count += 1
        return count

LCP 02. 分式化简

https://leetcode-cn.com/problems/deep-dark-fraction/ 有一个同学在学习分式。他需要将一个连分数化成最简分数，你能帮助他吗？

连分数是形如上图的分式。在本题中，所有系数都是大于等于0的整数。

输入的cont代表连分数的系数（cont[0]代表上图的a0，以此类推）。返回一个长度为2的数组[n, m]，使得连分数的值等于n / m，且n, m最大公约数为1。

示例 1：

输入：cont = [3, 2, 0, 2] 输出：[13, 4] 解释：原连分数等价于3 + (1 / (2 + (1 / (0 + 1 / 2))))。注意[26, 8], [-13, -4]都不是正确答案。示例 2：

输入：cont = [0, 0, 3] 输出：[3, 1] 解释：如果答案是整数，令分母为1即可。限制：

cont[i] >= 0 1 <= cont的长度 <= 10 cont最后一个元素不等于0 答案的n, m的取值都能被32位int整型存下（即不超过2 ^ 31 - 1）。

class Solution:
    def fraction(self, cont: List[int]) -> List[int]:
        n = m = 0
        for i in cont[::-1]:
            if n == 0:
                n,m = i,1
                continue
            n,m = i * n + m ,  n
        """
        a + 1 / b 必定是最简分数，所以不用求GCD了。 
        （前提：a是整数，b是一个最简分数） 因为b是最简分数，所以 1 / b肯定也是一个最简分数，加上一个整数仍然是最简分数：（ab + 1）/ b 
        “”“
        # 数学是万能的
        # for i in range(n//2, 0, -1):
        #     if n % i ==0 and m % i == 0:
        #         return n //i, m// i
        
        return n,m

二、Review

三、Tip

四、Share

为什么Python 3.6以后字典有序并且效率更高？

在Python 3.5（含）以前，字典是不能保证顺序的，键值对A先插入字典，键值对B后插入字典，但是当你打印字典的Keys列表时，你会发现B可能在A的前面。

但是从Python 3.6开始，字典是变成有顺序的了。你先插入键值对A，后插入键值对B，那么当你打印Keys列表的时候，你就会发现B在A的后面。

不仅如此，从Python 3.6开始，下面的三种遍历操作，效率要高于Python 3.5之前：

for` `key ``in` `字典`
for` `value ``in` `字典.values()`
for` `key, value ``in` `字典.items()

从Python 3.6开始，字典占用内存空间的大小，视字典里面键值对的个数，只有原来的30%~95%。

Python 3.6到底对字典做了什么优化呢？为了说明这个问题，我们需要先来说一说，在Python 3.5（含）之前，字典的底层原理。

当我们初始化一个空字典的时候，CPython的底层会初始化一个二维数组，这个数组有8行，3列，如下面的示意图所示：

my_dict ``=` `{}` `'''``此时的内存示意图``
[[---, ---, ---],`
`[---, ---, ---],`
`[---, ---, ---],`
`[---, ---, ---],`
`[---, ---, ---],`
`[---, ---, ---],`
`[---, ---, ---],`
`[---, ---, ---]]`'''

现在，我们往字典里面添加一个数据：

my_dict[``'name'``] ``=` `'kingname'` `'''``此时的内存示意图
``[[---, ---, ---],`
`[---, ---, ---],`
`[---, ---, ---],`
`[---, ---, ---],`
`[---, ---, ---],`
`[1278649844881305901, 指向name的指针, 指向kingname的指针],`
`[---, ---, ---],`
`[---, ---, ---]]``'''

这里解释一下，为什么添加了一个键值对以后，内存变成了这个样子：

首先我们调用Python 的hash函数，计算name这个字符串在当前运行时的hash值：

>>> ``hash``(``'name'``)
1278649844881305901

特别注意，我这里强调了『当前运行时』，这是因为，Python自带的这个hash函数，和我们传统上认为的Hash函数是不一样的。Python自带的这个hash函数计算出来的值，只能保证在每一个运行时的时候不变，但是当你关闭Python再重新打开，那么它的值就可能会改变，如下图所示：

假设在某一个运行时里面，hash('name')的值为1278649844881305901。现在我们要把这个数对8取余数：

>>> ``1278649844881305901` `%` `8`
`5

余数为5，那么就把它放在刚刚初始化的二维数组中，下标为5的这一行。由于name和kingname是两个字符串，所以底层C语言会使用两个字符串变量存放这两个值，然后得到他们对应的指针。于是，我们这个二维数组下标为5的这一行，第一个值为name的hash值，第二个值为name这个字符串所在的内存的地址（指针就是内存地址），第三个值为kingname这个字符串所在的内存的地址。

现在，我们再来插入两个键值对：

my_dict[``'age'``] ``=` `26`
my_dict[``'salary'``] ``=` `999999` 
此时的内存示意图
``[[-4234469173262486640, 指向salary的指针, 指向999999的指针],
``[1545085610920597121, 执行age的指针, 指向26的指针],
``[---, ---, ---],
``[---, ---, ---],
``[---, ---, ---],
``[1278649844881305901, 指向name的指针, 指向kingname的指针],
``[---, ---, ---],
``[---, ---, ---]]``'''

那么字典怎么读取数据呢？首先假设我们要读取age对应的值。

此时，Python先计算在当前运行时下面，age对应的Hash值是多少：

>>> ``hash``(``'age'``)``
1545085610920597121

现在这个hash值对8取余数：

>>> ``1545085610920597121` `%` `8``
1

余数为1，那么二维数组里面，下标为1的这一行就是需要的键值对。直接返回这一行第三个指针对应的内存中的值，就是age对应的值26。

当你要循环遍历字典的Key的时候，Python底层会遍历这个二维数组，如果当前行有数据，那么就返回Key指针对应的内存里面的值。如果当前行没有数据，那么就跳过。所以总是会遍历整个二位数组的每一行。

每一行有三列，每一列占用8byte的内存空间，所以每一行会占用24byte的内存空间。

由于Hash值取余数以后，余数可大可小，所以字典的Key并不是按照插入的顺序存放的。

注意，这里我省略了与本文没有太大关系的两个点：

开放寻址，当两个不同的Key，经过Hash以后，再对8取余数，可能余数会相同。此时Python为了不覆盖之前已有的值，就会使用开放寻址技术重新寻找一个新的位置存放这个新的键值对。
当字典的键值对数量超过当前数组长度的2/3时，数组会进行扩容，8行变成16行，16行变成32行。长度变了以后，原来的余数位置也会发生变化，此时就需要移动原来位置的数据，导致插入效率变低。

在Python 3.6以后，字典的底层数据结构发生了变化，现在当你初始化一个空的字典以后，它在底层是这样的：

my_dict ``=` `{}` 
`'''``此时的内存示意图``
indices = [None, None, None, None, None, None, None, None]` 
entries = []``'''

当你初始化一个字典以后，Python单独生成了一个长度为8的一维数组。然后又生成了一个空的二维数组。

现在，我们往字典里面添加一个键值对：

my_dict[``'name'``] ``=` `'kingname'
` `'''``此时的内存示意图``
indices = [None, 0, None, None, None, None, None, None]` `
entries = [[-5954193068542476671, 指向name的指针, 执行kingname的指针]]``'''

为什么内存会变成这个样子呢？我们来一步一步地看：

在当前运行时，name这个字符串的hash值为-5954193068542476671，这个值对8取余数是1：

>>> ``hash``(``'name'``)``-``
5954193068542476671``
>>> ``hash``(``'name'``) ``%` `8``
1

所以，我们把indices这个一维数组里面，下标为1的位置修改为0。

这里的0是什么意思呢？0是二位数组entries的索引。现在entries里面只有一行，就是我们刚刚添加的这个键值对的三个数据：name的hash值、指向name的指针和指向kinganme的指针。所以indices里面填写的数字0，就是刚刚我们插入的这个键值对的数据在二位数组里面的行索引。

好，现在我们再来插入两条数据：

my_dict[``'address'``] ``=` `'xxx'``
my_dict[``'salary'``] ``=` `999999` `'''``
此时的内存示意图``
indices = [1, 0, None, None, None, None, 2, None]` `
entries = [[-5954193068542476671, 指向name的指针, 执行kingname的指针],``     ``
[9043074951938101872, 指向address的指针，指向xxx的指针],``     ``
[7324055671294268046, 指向salary的指针, 指向999999的指针]``     ``]``'''

现在如果我要读取数据怎么办呢？假如我要读取salary的值，那么首先计算salary的hash值，以及这个值对8的余数：

>>> ``hash``(``'salary'``)``
7324055671294268046``
>>> ``hash``(``'salary'``) ``%` `8``
6

那么我就去读indices下标为6的这个值。这个值为2.

然后再去读entries里面，下标为2的这一行的数据，也就是salary对应的数据了。

新的这种方式，当我要插入新的数据的时候，始终只是往entries的后面添加数据，这样就能保证插入的顺序。当我们要遍历字典的Keys和Values的时候，直接遍历entries即可，里面每一行都是有用的数据，不存在跳过的情况，减少了遍历的个数。

老的方式，当二维数组有8行的时候，即使有效数据只有3行，但它占用的内存空间还是 8 * 24 = 192 byte。但使用新的方式，如果只有三行有效数据，那么entries也就只有3行，占用的空间为3 * 24 =72 byte，而indices由于只是一个一维的数组，只占用8 byte，所以一共占用 80 byte。内存占用只有原来的41%。

参考：[Python-Dev] More compact dictionaries with faster iteration

Via https://www.cnblogs.com/songyifan427/p/11198719.html

ARTS-015

一、Algorithm

8. 字符串转换整数 (atoi)

15. 三数之和

22. 括号生成

39. 组合总和

40. 组合总和 II

64. 最小路径和

88. 合并两个有序数组

101. 对称二叉树

121. 买卖股票的最佳时机

122. 买卖股票的最佳时机 II

124. 二叉树中的最大路径和

146. LRU缓存机制

141. 环形链表

142. 环形链表 II

143. 重排链表

155. 最小栈

198. 打家劫舍

200. 岛屿数量

206. 反转链表

217. 存在重复元素

226. 翻转二叉树

231. 2的幂

234. 回文链表

235. 二叉搜索树的最近公共祖先

237. 删除链表中的节点

292. Nim 游戏

300. 最长上升子序列

344. 反转字符串

349. 两个数组的交集

365. 有多少小于当前数字的数字

543. 二叉树的直径

557. 反转字符串中的单词 III

876. 链表的中间结点

941. 有效的山脉数组

LCP 01. 猜数字

LCP 02. 分式化简

二、Review

三、Tip

四、Share

为什么Python 3.6以后字典有序并且效率更高？

Similar Posts