leetcode 个人刷题记录（Python）

朱雀 2022-11-24 14:21 49阅读 0赞

好久没做题了，数据结构和算法是不能丢下的，因此争取每天做一些题，保持思维和手感。

## 第一周 ##

### 8.6 ###

[39. 组合总和][39.]

回溯+剪枝  
这里学到一个小技巧，把数组切片当作参数传进函数，这样就保证了递归下层选取是不比之前小的。其实就是之前C++写法的传指针。

class Solution:
        def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
            candidates.sort()
            ans = []
            def fun(target, candidates, now): 
                # now: list of chose
                if target == 0:
                    ans.append(now)
                    return
                for i, val in enumerate(candidates):
                    if target >= val:
                        fun(target-val, candidates[i:], now+[val])
                    else:
                        return
            fun(target,candidates,[])
            return ans

### 8.7 ###

[100. 相同的树][100.]

注释给了TreeNode的定义，前几天没有看，所以找了半天不会做。注意python中的并是 `and` 不是 `&&`。

# 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
            if p != None and q == None:
                return False
            elif p == None and q != None:
                return False
            elif p is None and q is None:
                return True
            elif p.val != q.val:
                return False
            else:
                return ( self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right) )

### 8.8 ###

去打球了，鸽一天咕咕咕咕。

### 8.9 ###

[93. 复原IP地址][93. _IP]  
第一个问题，类内定义函数没有写`self`,这样会提示错误。  
可以直接用`int()`将string转换为数字，然后要判断前导零。  
进入递归时先判断是否够长度。

class Solution:
        def __init__(self):
            self.ans = []
    
        def isOk(self,s):
            if s[0] == '0' and len(s) > 1:
                return False
            if int(s) <= 255:
                return True
            else:
                return False
        def fun(self, res, ans, cnt):
            # res 剩余串， ans 已组成的答案, cnt 串数
            if cnt > 4:
                return
            if len(res) == 0 and cnt == 4:
                self.ans.append(ans[:-1])
                return
    
            if len(res) >= 1:
                tmp = res[:1]
                if self.isOk(tmp):
                    self.fun(res[1:], ans + tmp + ".", cnt + 1)
    
            if len(res) >= 2:
                tmp = res[:2]
                if self.isOk(tmp):
                    self.fun(res[2:], ans + tmp + ".", cnt + 1)
            if len(res) >= 3:
                tmp = res[:3]
                if self.isOk(tmp):
                    self.fun(res[3:], ans + tmp + ".", cnt + 1)
            return
    
        def restoreIpAddresses(self, s):
            self.fun(s, "", 0)
            return set(self.ans)

### 8.10 ###

[696. 计数二进制子串][696.]  
垃圾题，垃圾代码

class Solution:
        def countBinarySubstrings(self, s: str) -> int:
            li = []
            begin = s[0]
            cnt = 1
            for i, char in enumerate(s[1:]):
                if char == begin:
                    cnt += 1
                else:
                    begin = char
                    li.append(cnt)
                    cnt = 1
                if i == len(s) - 2:
                    li.append(cnt)
            
            ans = 0
            for i, val in enumerate(li):
                if i == len(li) - 1:
                    break
                ans += min(val, li[i+1])
    
            return ans

### 8.11 ###

[130. 被围绕的区域][130.]  
简单的BFS

class Solution:
        def solve(self, board):
            """ Do not return anything, modify board in-place instead. """
            if board == []:
                return 
            xPos = [1, 0, -1, 0]
            yPos = [0, 1, 0, -1]
            n, m = len(board), len(board[0])
            vis, color = [([0] * m) for i in range(n)], [([0] * m) for i in range(n)]
    
            # print(n,m)
            # vis 用于标记是否访问， color 用于标色
            def isOK(x, y):
                if x < 0 or x > n - 1:
                    return False
                if y < 0 or y > m - 1:
                    return False
                if board[x][y] == 'X':
                    return False
                if vis[x][y]:
                    return False
                return True
    
            def bfs(x, y):
                if not isOK(x, y):
                    return
                vis[x][y], color[x][y] = 1, 1
                for xx, yy in zip(xPos, yPos):
                    bfs(x + xx, y + yy)
    
            for x in range(n):
                if board[x][0] == 'O':
                    bfs(x, 0)
                if board[x][m - 1] == 'O':
                    bfs(x, m - 1)
    
            for y in range(m):
                if board[0][y] == 'O':
                    bfs(0, y)
                if board[n - 1][y] == 'O':
                    bfs(n - 1, y)
    
            for x in range(n):
                for y in range(m):
                    if color[x][y] != 1:
                        board[x][y] = 'X'

看别人代码学会了一种写法，遍历元组，这样很方便

for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    tmp_i = i + x
                    tmp_j = j + y

### 8.12 ###

[133. 克隆图][133.]  
题意和给定函数结合一开始没读懂，其实就是给你一个节点的引用，让你去把整张图深拷贝一边，然后返回这个节点的引用。  
学到了用字典作为标记数组记录是否访问过，更节省空间。注意用字典判断的话用`in`

""" # Definition for a Node. class Node: def __init__(self, val = 0, neighbors = []): self.val = val self.neighbors = neighbors """
    
    class Solution:
        def __init__(self):
            self.vis = { }
        def cloneGraph(self, node: 'Node') -> 'Node':
    
            if not node:
                return node
    
            if node in self.vis:
                return self.vis[node]
            
            new_node = Node(node.val, [])
            self.vis[node] = new_node
    
            new_node.neighbors = [self.cloneGraph(i) for i in node.neighbors]
            
            return new_node

## 第二周 ##

#### 8.13 ####

[43. 字符串相乘][43.]  
大整数乘法？python? 嗯

class Solution:
        def multiply(self, num1: str, num2: str) -> str:
            return str(int(num1)*int(num2))

#### 8.14 ####

[20. 有效的括号][20.]  
括号匹配，水题

*  list 有pop()
 *  调试的时候注意是不是把类型当作参数传进去啦

import queue
    class Solution:
        def isValid(self, s: str) -> bool:
            def check(c):
                if c == '[' or c == '{' or c == '(':
                    return True
                else:
                    return False
            
            def right(a,b):
                if a == '(' and b == ')':
                    return True
                elif a == '['  and b == ']':
                    return True
                elif a == '{' and b == '}':
                    return True
                else:
                    return False
    
            stack = []
            if len(s) == 0:
                return True
            
            for c in s:
                if len(stack) == 0:
                    if check(c):
                        stack.append(c)
                    else:
                        return False
                    
                elif check(stack[-1]): # 左括号
                    if check(c):
                        stack.append(c)
                    elif right(stack[-1], c):
                        stack.pop()
                    else:
                        return False
                    
                else:
                    return False
    
            if len(stack) == 0:
                return True
            else :
                return False

#### 8.17 ####

[110. 平衡二叉树][110.]  
两天没做题，果然变笨比了，深度可求，然后递归就好  
Python 无穷大`float('inf')`

# Definition for a binary tree node.
    # class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None
    
    class Solution:
        def isBalanced(self, root: TreeNode) -> bool:
            def height(root):
                if root == None:
                    return 0
                else:
                    return max(height(root.left),height(root.right)) + 1
            
            if root == None:
                return True
            return abs(height(root.left)-height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

### 8.18 ###

[109. 有序链表转换二叉搜索树][109.]  
数据结构没学好，暂时做不来。  
资料  
[平衡二叉树][Link 1]

咕咕咕

### 8.27 ###

[491. 递增子序列][491.]  
自己写了一个动态规划+哈希，不知道为什么运行不了，对Python语言结构还是不太熟悉吧。  
然后这个是大佬写的，用`{}`去重，然后里面加元祖，至于为什么加元祖我也不清楚，可能这就是我用list出bug的原因。  
然后我学到了这个词：类似列表推导式，同样集合支持集合推导式(Set comprehension)  
就在列表里面推导的叫做列表推导式，在集合里面的叫做集合推导式。

class Solution:
        def findSubsequences(self, nums):
            if not nums:
                return []
            pres = { (nums[0], )}
            for i in nums[1:]:
                pres.update({ j+(i, ) for j in pres if j[-1] <= i})
                pres.add((i, ))
            return [list(i) for i in pres if len(i) > 1]

第二种写法，dfs+hash，除去重复的，其实就是暴力，这个题分析出时间复杂度其实就是可以直接暴力的

class Solution:
        def findSubsequences(self, nums):
            if not nums:
                return []
            res = []
    
            def dfs(nums, now):
                if len(now) > 1:
                    res.append(now)
                same = set()
                for inx, i in enumerate(nums):
                    if i in same:
                        continue
                    if not now or i >= now[-1]:
                        same.add(i)
                        dfs(nums[inx+1:],now+[i])
                pass
    
            dfs(nums,[])
            return res

[39.]: https://leetcode-cn.com/problems/combination-sum/
[100.]: https://leetcode-cn.com/problems/same-tree/
[93. _IP]: https://leetcode-cn.com/problems/restore-ip-addresses/
[696.]: https://leetcode-cn.com/problems/count-binary-substrings/
[130.]: https://leetcode-cn.com/problems/surrounded-regions/
[133.]: https://leetcode-cn.com/problems/clone-graph/
[43.]: https://leetcode-cn.com/problems/multiply-strings/
[20.]: https://leetcode-cn.com/problems/valid-parentheses/
[110.]: https://leetcode-cn.com/problems/balanced-binary-tree/
[109.]: https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/
[Link 1]: https://www.cnblogs.com/chay/articles/10249732.html
[491.]: https://leetcode-cn.com/problems/increasing-subsequences/