leetcode（16，17，18，20，22）

今日总结：做题效果不是很好，出现各种状况。感觉不是很难的题，就是陷入思维误区。还有两道题（18，22），暂且搁置。有点窝火，再努力吧。

---

16. 最接近的三数之和（C）

分析：跟之前的题很相识，一个求和，这个是求近似。直观想法还是老套路，排序，然后遍历，比较。

方法一：排序遍历比较，注意下，近似使用abs求绝对值。

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        if len(nums)<3:
            return None
        
        gol_ans = nums[0]+nums[1]+nums[2]
        for i in range(len(nums)-2):
            j = i+1
            k = len(nums)-1
            while j<k:
                cur_ans = nums[i]+nums[j]+nums[k]
                if cur_ans == target:
                    return cur_ans
                if abs(cur_ans-target) < abs(gol_ans-target):
                    gol_ans=cur_ans
                if cur_ans > target:
                    k-=1
                else:
                    j+=1
        return gol_ans

方法二：优化运算时间，想法就是优先考虑两端情况，最大最小。然后其余情况正常，最后将结果。绝对值排序。选出最优。

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        closest = []
        length = len(nums)
        for i, num in enumerate(nums[0:-2]):
            l,r = i+1, length-1
            if num+nums[r]+nums[r-1] < target:
                closest.append(num+nums[r]+nums[r-1])
            elif num+nums[l]+nums[l+1] > target:
                closest.append(num+nums[l]+nums[l+1])
            else:
                while l<r:
                    closest.append(num+nums[r]+nums[l])
                    if num+nums[l]+nums[r] > target:
                        r -= 1
                    elif num+nums[l]+nums[r] < target:
                        l += 1
                    else:
                        return target
        closest.sort(key=lambda x:abs(x-target))
        return closest[0]

17. 电话号码的字母组合（C）

分析：每个数字列出对应字母，先读一个数字放入列表。再依次拼接。

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: 
            return []
        table = {'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 = ['']
        for digit in digits:
            str_list = []
            for char in table[digit]:
                str_list += [x + char for x in result]
            result = str_list
        return result

优化后（A）。yield生成器返回结果。学习到了。还有函数构造这个也很巧妙。

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        
        dict = {'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']
                }
        def helper(digits, comb = ''):
            if len(digits) > 0:
                for i in dict[digits[0]]:
                    yield from helper(digits[1:], comb + i)
                else:
                    yield comb
        return list(helper(digits)) if digits != '' else []

18. 四数之和（C）（暂）

分析：emmm~四数之和来了，首先考虑顺着三数之和的思路，4个指针，固定两个数。两个数往中间逼近。考虑可能存在多种情况，需要加一条判断。双嵌套复杂度太高了，直接借鉴优化代码。

（A）可以通过递归解决n个数之和。

• 考虑将n数之和降低为一个数加上n-1数之和
• 分化为二数之和
• target = target - nums[i]来调用nSum（）方法。递归
• 注意列表的拼接。

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        def nSum(nums, target, n, result, results):
            if len(nums) < n or n < 2 or n * nums[0] > target or n * nums[-1] < target:
                return []
            if n == 2:
                begin, end = 0, len(nums)-1
                while begin < end:
                    sums = nums[begin] + nums[end]
                    if sums < target:
                        begin += 1
                    elif sums > target:
                        end -= 1
                    else:
                        plet  = [nums[begin], nums[end]]
                        results.append(result + plet)
                        while begin < end and nums[begin] == plet[0]: begin += 1
                        while begin < end and nums[end] == plet[1]: end -= 1
            else:
                for i in range(len(nums) - n + 1):
                    if (i > 0 and nums[i] == nums[i-1]) or (nums[i] + (n-1)*nums[len(nums)-1]<target):
                        continue
                    if n * nums[i] > target:
                        break
                    if n * nums[i] == target and i + n - 1 < len(nums) and nums[i+n-1] == nums[i]:
                        plet = [nums[i]] * n
                        results.append(result + plet)
                        break
                    nSum(nums[i + 1:], target - nums[i], n - 1, result + [nums[i]], results)
        results = []
        nums.sort()
        nSum(nums, target, 4, [], results)
        return results

20. 有效的括号（D）

分析：字符串问题，很好实现。

第一种，利用replace直接替换。不需要考虑其他位置。

class Solution:
    def isValid(self, s: str) -> bool:
        n = len(s)
        if n == 0:
            return True
        if n % 2 != 0:
            return False
        while '()' in s or '[]' in s or '{}' in s:
            s = s.replace('()',"").replace('[]',"").replace('{}',"")
        return s == ""

第二种，利用堆栈的方式，匹配之后用pop删除。

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for char in s:
            if char in ['(','{','[']:
                stack.append(char)
            elif not stack:
                return False
            elif (char == ')') and (stack[len(stack)-1]=='('):
                stack.pop()
                
            elif (char == ']') and (stack[len(stack)-1]=='['):
                stack.pop()
                
            elif (char == '}') and (stack[len(stack)-1]=='{'):
                stack.pop()
            else:
                return False
        return len(stack) == 0

22. 括号生成（B）（暂）

分析：跟20题逻辑相逆。

方法1：暴力法，生成所有括号序列，再判断是否有效。数目够就匹配（）是否是对应的。如果，出现）在前，直接返回结果。正好相等时，判断返回True。然后添加。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate(A = []):
            if len(A) == 2*n:
                if valid(A):
                    ans.append("".join(A))
            else:
                A.append('(')
                generate(A)
                A.pop()
                A.append(')')
                generate(A)
                A.pop()
        def valid(A):
            bal = 0
            for C in A:
                if C == '(': bal += 1
                else: bal -= 1
                if bal < 0: return False
            return bal == 0
        ans = []
        generate()
        return ans

方法二？（A）：递归生成有效序列。方法二为什么就递归了。知识漏洞！

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def backtrack(S = '',left = 0, right = 0):
            if len(S) == 2 * n:
                ans.append(S)
                return
            if left < n:
                backtrack(S+'(', left+1, right)
            if right < left:
                backtrack(S+')', left, right+1)     #取出一个值后，为什么再次递归。
        ans = []
        backtrack()
        return ans