在leetcode刷200道题，完成学校2020年9月6号到9月20号的小学期任务，特此记录，同时也供大家学习交流。

1.【 表示数值的字符串】

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。

import re
class Solution(object):
    def isNumber(self, s):
        """
        :type s: str
        :rtype: bool
        """    
        matchObj=re.match('^s*[+-]{0,1}((d)+((.)(d)+){0,1}|((.)(d)+)|((d)+(.)))([eE][+-]{0,1}[d]+){0,1}s*$',s)
        if matchObj:
            print ("match --> matchObj.group() : ", matchObj.group())
            return True
        else:
            print ("No match!!")
            return False

 2.【两数之和】

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

第1种最耗时，思路：
拿数组里的第一个数字和后面的数字分别相加，看是否等于target；如果不等于target，那么就继续拿数组里的第二个数字和后面的数字相加；不停的去一个个试...直到等于target，返回这2个数字所在的下标

前置知识：
nums = [11, 2，15，7]，里面的数字对应的下标分别是0,1,2,3
for循环嵌套执行顺序：如果一个for循环里还有一个for循环，如果条件不满足，那么里面的for循环会先执行完，外面的for循环才会执行


class Solution:
	def twoSum(self,nums,target):
		n = len(nums) # 获取nums的长度，是4
		for x in range(n): # 外层循环先取出下标0，对应着数组里的第一个数字
			for y in range(x+1,n): # 内层循环取出下标1，对应着数组里的第二个数字
				if nums[x] + nums[y] == target: # 如果第一个数字+第二个数字=target
					return x,y # 上面的判断是对的话，那么就返回下标
					break # 并停止程序
				else: # 如果上面的条件不满足的话，内层for循环就会继续取出下标2进行判断...如果都不满足，那么外层for循环就会取出下标1...依次类推
					continue 
第2种，用1个for循环
直接用target 减去 取出的数字，看结果有没有在数组里


class Solution:
	def twoSum(self,nums,target):
		n = len(nums)
		for x in range(n):
			a = target - nums[x]
			if a in nums: # 判断a有没有在nums数组里
				y = nums.index(a) # 有的话，那么用index获取到该数字的下标
				if x == y: 
					continue # 同样的数字不能重复用，所以这里如果是一样的数字，那么就不满足条件，跳过
				else: # 否则就返回结果
					return x,y 
					break
			else: 
				continue # 上面的条件都不满足就跳过，进行下一次循环
第3种，用字典提高速度
这个是看了别人的图解答案才知道的（https://leetcode-cn.com/problems/two-sum/solution/tu-jie-ha-xi-biao-by-ml-zimingmeng/），把原先的数组转化成字典，通过字典去查询速度就会快很多。下面的代码我变更了顺序，好理解多了，速度也快了一些。


class Solution:
	def twoSum(self,nums,target):
		d = {}
		n = len(nums)
		for x in range(n):
			d[nums[x]] = x # 把数组里的数字作为key，下标作为value存到d字典中
			if target - nums[x] in d: # 看另外一个数字有没有在字典里
				return d[target-nums[x]],x # 有的话直接就可以返回value了;没有的话会继续循环
经群友指出，上面的写法是错误的。如果先把数组转化成字典的话，target-nums[x]的值很有可能会等于nums[x]，正确的如下：


class Solution:
	def twoSum(self,nums,target):
		d = {}
		n = len(nums)
		for x in range(n):
			if target - nums[x] in d:
				return d[target-nums[x]],x
			else:
				d[nums[x]] = x

 3.【二叉树的层次遍历 II】

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

BFS实现

class Solution(object):
    def levelOrderBottom(self, root):
        if not root:
            return []
        # 创建一个队列，将根节点放入其中    
        queue = [root]
        # 用来存放最终结果
        res = []
        while queue:
            # 每次遍历的数量为队列的长度
            size = len(queue)
            tmp = []
            # 将这一层的元素全部取出，放入到临时数组中，如果节点的左右孩子不为空，继续放入队列
            for _ in xrange(size):
                node = queue.pop(0)
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(tmp)
        # 翻转最终结果并返回
        return res[::-1]

BFS实现-2
第一种方式中，我们将最终结果集定义成数组，等所有元素都放置完后，再翻转一下数组。
我们可以将其结构改成链表，以后每层遍历完将结果放入到链表的第一位，这样就自动完成了翻转的功能了


class Solution(object):
    def levelOrderBottom(self, root):
        if not root:
            return []
        queue = [root]
        # 改用双端队列实现，每次都插入到第一位
        res = collections.deque()
        while queue:
            size = len(queue)
            tmp = []
            for _ in xrange(size):
                node = queue.pop(0)
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            # 每次插入到第一位，这样自带了翻转的功能       
            res.appendleft(tmp)
        return list(res)

DFS实现

class Solution(object):
    def levelOrderBottom(self, root):
        if not root:
            return []
        # 用来存放最终结果    
        res = []
        def dfs(root,index):
            if not root:
                return
            # 如果index大于res大小，说明这一层没有对应的集合，需要新创建    
            if index>len(res):
                res.append([])
            # 将当前层的元素直接放到对应层的末尾即可    
            res[index-1].append(root.val)
            # 继续遍历左右节点，同时将层高+1
            dfs(root.left,index+1)
            dfs(root.right,index+1)
        dfs(root,1)
        return res[::-1]

4.【两数相加】

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

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

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 创建一个结点值为 None 的头结点, dummy 和 p 指向头结点, dummy 用来最后返回, p 用来遍历
        dummy = p = ListNode(None)          
        s = 0               # 初始化进位 s 为 0
        while l1 or l2 or s:
            # 如果 l1 或 l2 存在, 则取l1的值 + l2的值 + s(s初始为0, 如果下面有进位1, 下次加上)
            s += (l1.val if l1 else 0) + (l2.val if l2 else 0)  
            p.next = ListNode(s % 10)       # p.next 指向新链表, 用来创建一个新的链表
            p = p.next                      # p 向后遍历
            s //= 10                        # 有进位情况则取模, eg. s = 18, 18 // 10 = 1
            l1 = l1.next if l1 else None    # 如果l1存在, 则向后遍历, 否则为 None
            l2 = l2.next if l2 else None    # 如果l2存在, 则向后遍历, 否则为 None
        return dummy.next   # 返回 dummy 的下一个节点, 因为 dummy 指向的是空的头结点, 下一个节点才是新建链表的后序节点

5.【无重复字符的最长子串】

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度

思路：
这道题主要用到思路是：滑动窗口

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度：O(n)O(n)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        left = 0
        lookup = set()
        n = len(s)
        max_len = 0
        cur_len = 0
        for i in range(n):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:max_len = cur_len
            lookup.add(s[i])
        return max_len

6.【前k个高频元素】

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

先利用哈希表，再对字典排序。

class Solution:
    def topKFrequent(self, nums, k):
        Hash = {}
        for i in nums:
            Hash[i] = Hash.get(i, 0) + 1
        keyvalues = sorted(Hash.items(), key = lambda x: (x[1], x[0]), reverse=True)
        return [keyvalues[j][0] for j in range(k)]

7.【组合】

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

回溯算法 剪枝
class Solution:
    def combine(self, n, k):

        all_combination=[]

        def backtracking(remain_selection,unfinished_count,prefix):
            if unfinished_count==0:
                all_combination.append(prefix[:])
            tmp_length=len(remain_selection)
            for i in range(tmp_length):
                #此处代码优化可以显著提高运行的效率
                if unfinished_count<=tmp_length-i+1:
                    backtracking(remain_selection[i+1:],unfinished_count-1,prefix+[remain_selection[i]])
                else:
                    break
        
        if n<k or n<=0 or k<=0:
            return []
        backtracking([i for i in range(1,n+1)],k,[])
        return all_combination

8.【组合总和】

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

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

说明：

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

回溯算法
from typing import List


class Solution:
    def combinationSum(self, candidates, target):

        def dfs(candidates, begin, size, path, res, target):
            if target < 0:
                return
            if target == 0:
                res.append(path)
                return

            for index in range(begin, size):
                dfs(candidates, index, size, path + [candidates[index]], res, target - candidates[index])

        size = len(candidates)
        if size == 0:
            return []
        path = []
        res = []
        dfs(candidates, 0, size, path, res, target)
        return res


剪枝提速
from typing import List


class Solution:
    def combinationSum(self, candidates, target):

        def dfs(candidates, begin, size, path, res, target):
            if target == 0:
                res.append(path)
                return

            for index in range(begin, size):
                residue = target - candidates[index]
                if residue < 0:
                    break

                dfs(candidates, index, size, path + [candidates[index]], res, residue)

        size = len(candidates)
        if size == 0:
            return []
        candidates.sort()
        path = []
        res = []
        dfs(candidates, 0, size, path, res, target)
        return res

9.【寻找两个正序数组的中位数】

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

解题思路
1.length=m+n 如果是奇数中间值的下标就是 length//2,偶数就是 mid=length/2, 也就是mid-1和mid的下标所对应的值/2
2.i,j 分别对应两个数组对应的下标，将小的值插入到new_Arry
3.当new_Arry的长度等于mid的时候就停止循环。


class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        res = 0.0
        new_array = []
        m = len(nums1)
        n = len(nums2)
        length = m + n
        mid = 0
        if length & 1:
            mid = int(length//2)
        else:
            mid = int(length/2)
        i,j = 0,0
        while len(new_array) -1 < mid:
            if i < m and j < n :
                if nums1[i] < nums2[j]:
                    new_array.append(nums1[i])
                    i+=1
                    continue
                if nums1[i] >= nums2[j]:
                    new_array.append(nums2[j])
                    j+=1
                    continue
            if i == m and j < n:
                while j < n and len(new_array) -1 < mid:
                    new_array.append(nums2[j])
                    j+=1
            if i < m and j == n:
                while i < m and len(new_array) -1 < mid:
                    new_array.append(nums1[i])
                    i+=1
        if length & 1:
            res = new_array[mid]
        else:
            res = (new_array[mid-1] + new_array[mid])/2.0
        return res

10.【最长回文子串】

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

动态规划

对于一个子串而言，如果它是回文串，并且长度大于 22，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 textrm{``ababa''}“ababa”，如果我们已经知道 textrm{``bab''}“bab” 是回文串，那么 textrm{``ababa''}“ababa” 一定是回文串，这是因为它的首尾两个字母都是 textrm{``a''}“a”。

class Solution:
    def longestPalindrome(self, s):
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = ""
        # 枚举子串的长度 l+1
        for l in range(n):
            # 枚举子串的起始位置 i，这样可以通过 j=i+l 得到子串的结束位置
            for i in range(n):
                j = i + l
                if j >= len(s):
                    break
                if l == 0:
                    dp[i][j] = True
                elif l == 1:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
                if dp[i][j] and l + 1 > len(ans):
                    ans = s[i:j+1]
        return ans

11.【z字形变换】

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

class Solution:
    def convert(self, s, numRows):
        if numRows < 2: return s
        res = ["" for _ in range(numRows)]
        i, flag = 0, -1
        for c in s:
            res[i] += c
            if i == 0 or i == numRows - 1: flag = -flag
            i += flag
        return "".join(res)

12.【整数反转】

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

注意: 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2**31,  2**31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if -10 < x < 10:
            return x
        str_x = str(x)
        if str_x[0] != "-":
            str_x = str_x[::-1]
            x = int(str_x)
        else:
            str_x = str_x[:0:-1]
            x = int(str_x)
            x = -x
        return x if -2147483648 < x < 2147483647 else 0

优化解
我们可以一次构建反转整数的一位数字。在这样做的时候，我们可以预先检查向原整数附加另一位数字是否会导致溢出。
反转整数的方法可以与反转字符串进行类比。

我们想重复 “弹出” x 的最后一位数字，并将它 “推入” 到 res 的后面。最后，res 将与 x 相反。

def reverse_better(
        self, 
        x: int) -> int:
       
        
        y, res = abs(x), 0
        # 则其数值范围为 [−2^31,  2^31 − 1]
        boundry = (1<<31) -1 if x>0 else 1<<31
        while y != 0:
            res = res*10 +y%10
            if res > boundry :
                return 0
            y //=10
        return res if x >0 else -res

13.【字符串转换整数（atoi）】

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

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

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

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

提示：

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

import re
class Solution:
    def myAtoi(self, str: str) -> int:
        INT_MAX = 2147483647    
        INT_MIN = -2147483648
        str = str.lstrip()      #清除左边多余的空格
        num_re = re.compile(r'^[+-]?d+')   #设置正则规则
        num = num_re.findall(str)   #查找匹配的内容
        num = int(*num) #由于返回的是个列表，解包并且转换成整数
        return max(min(num,INT_MAX),INT_MIN)    #返回值

^：匹配字符串开头
[+-]：代表一个+字符或-字符
?：前面一个字符可有可无
d：一个数字
+：前面一个字符的一个或多个
D：一个非数字字符
*：前面一个字符的0个或多个


简洁版本：
class Solution:
    def myAtoi(self, s: str) -> int:
        return max(min(int(*re.findall('^[+-]?d+', s.lstrip())), 2**31 - 1), -2**31)

14.【回文数】

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

class Solution(object):
    def isPalindrome(self, x):
        return str(x)==str(x)[::-1]	

15.【正则表达式匹配】

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

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

思路
1.先判断s和p的第一个字符是否匹配
2.处理p[1]为*号的情况：匹配0个或多个字符
3.处理.号的情况：匹配一个字符

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p: return not s  # 结束条件

        first_match = (len(s) > 0) and p[0] in {s[0], '.'}
        # 先处理 `*`
        if len(p) >=2 and p[1] == '*':
            # 匹配0个 | 多个
            return self.isMatch(s, p[2:]) or (first_match and self.isMatch(s[1:], p))
        
        # 处理 `.` ，匹配一个
        return first_match and self.isMatch(s[1:], p[1:])

16.【盛最多水的容器】

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

双指针
class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        ans = 0
        while l < r:
            area = min(height[l], height[r]) * (r - l)
            ans = max(ans, area)
            if height[l] <= height[r]:
                l += 1
            else:
                r -= 1
        return ans

17.【整数转罗马数字】

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

贪心算法
class Solution:
    def intToRoman(self, num):
        # 把阿拉伯数字与罗马数字可能出现的所有情况和对应关系，放在两个数组中
        # 并且按照阿拉伯数字的大小降序排列，这是贪心选择思想
        nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        romans = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]

        index = 0
        res = ''
        while index < 13:
            # 注意：这里是等于号，表示尽量使用大的"面值"
            while num >= nums[index]:
                res += romans[index]
                num -= nums[index]
            index += 1
        return res

18.【罗马数字转整数】

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

class Solution:
    def romanToInt(self, s):
        d = {'I':1, 'IV':3, 'V':5, 'IX':8, 'X':10, 'XL':30, 'L':50, 'XC':80, 'C':100, 'CD':300, 'D':500, 'CM':800, 'M':1000}
        return sum(d.get(s[max(i-1, 0):i+1], d[n]) for i, n in enumerate(s))

19.【最长公共前缀】

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

取一个单词 s，和后面单词比较，看 s 与每个单词相同的最长前缀是多少！遍历所有单词。

class Solution:
    def longestCommonPrefix(self, s):
        if not s:
            return ""
        res = s[0]
        i = 1
        while i < len(s):
            while s[i].find(res) != 0:
                res = res[0:len(res)-1]
            i += 1
        return res

20.【三数之和】

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

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

排序+双指针
解题思路：
暴力法搜索为 O(N^3) 时间复杂度，可通过双指针动态消去无效解来优化效率。
双指针法铺垫： 先将给定 nums 排序，复杂度为 O(NlogN)O(NlogN)。
双指针法思路： 固定 33 个指针中最左（最小）数字的指针 k，双指针 i，j 分设在数组索引 (k, len(nums))(k,len(nums)) 两端，通过双指针交替向中间移动，记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 i,j 组合：
1.当 nums[k] > 0 时直接break跳出：因为 nums[j] >= nums[i] >= nums[k] > 0，即 33 个数字都大于 00 ，在此固定指针 k 之后不可能再找到结果了。
2.当 k > 0且nums[k] == nums[k - 1]时即跳过此元素nums[k]：因为已经将 nums[k - 1] 的所有组合加入到结果中，本次双指针搜索只会得到重复组合。
3.i，j 分设在数组索引 (k, len(nums))(k,len(nums)) 两端，当i < j时循环计算s = nums[k] + nums[i] + nums[j]，并按照以下规则执行双指针移动：
    当s < 0时，i += 1并跳过所有重复的nums[i]；
    当s > 0时，j -= 1并跳过所有重复的nums[j]；
    当s == 0时，记录组合[k, i, j]至res，执行i += 1和j -= 1并跳过所有重复的nums[i]和        nums[j]，防止记录到重复组合。

class Solution:
    def threeSum(self, nums: [int]) -> [[int]]:
        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

21.【把二叉搜索树转换为累加树】

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

思路:
“中序遍历”

思路一：递归

思路二：迭代

代码:
思路一：


class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        cur = 0

        def dfs(root):
            nonlocal cur
            if not root: return 
            dfs(root.right)
            cur += root.val
            root.val = cur
            dfs(root.left)

        dfs(root)
        return root
思路二：


class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        cur, stack, p = 0, [], root
        while p or stack:
            while p:
                stack.append(p)
                p = p.right
            p = stack.pop()
            cur += p.val
            p.val = cur
            p = p.left
        return root

最后

以上就是务实机器猫为你收集整理的Python 200道leetcode编程题在leetcode刷200道题，完成学校2020年9月6号到9月20号的小学期任务，特此记录，同时也供大家学习交流。1.【 表示数值的字符串】 2.【两数之和】 3.【二叉树的层次遍历 II】4.【两数相加】5.【无重复字符的最长子串】6.【前k个高频元素】7.【组合】8.【组合总和】9.【寻找两个正序数组的中位数】10.【最长回文子串】11.【z字形变换】12.【整数反转】13.【字符串转换整数（atoi）】14.【回文数】15.【正则表达式匹配】1的全部内容，希望文章能够帮你解决Python 200道leetcode编程题在leetcode刷200道题，完成学校2020年9月6号到9月20号的小学期任务，特此记录，同时也供大家学习交流。1.【 表示数值的字符串】 2.【两数之和】 3.【二叉树的层次遍历 II】4.【两数相加】5.【无重复字符的最长子串】6.【前k个高频元素】7.【组合】8.【组合总和】9.【寻找两个正序数组的中位数】10.【最长回文子串】11.【z字形变换】12.【整数反转】13.【字符串转换整数（atoi）】14.【回文数】15.【正则表达式匹配】1所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。