Leetcode刷题记录_python给你一个字符串 s 和一个字符串列表 worddict 作为字典。请你判断是否

39. 组合总和

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

思路

递归

代码

class Solution:
    # 还是得用递归的思想
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # 先把数组排序
        candidates.sort()
        def comb(candidates=[],target = 0):
            # if target<candidates[0]:
            #     return []
            # elif target==candidates[0]:
            #     return [[candidates[0]]]
            i = 0
            res = []
            while i<len(candidates) and candidates[i]<=target:
                sub = target-candidates[i]
                ## 这里candidates[i:]是为了去除重复
                res1 = comb(candidates[i:], sub)
                for r in res1:
                    res.append([candidates[i]]+r)
                if len(res1)==0 and candidates[i]==target:
                    res.append([candidates[i]])
                i+=1
            return res 
        return comb(candidates.copy(), target)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

40.组合总和II

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

思路

排序+递归，同39题

代码

class Solution:
    # 还是得用递归的思想
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # 先把数组排序
        candidates.sort()
        def comb(candidates=[],target = 0):
            i = 0
            res = []
            while i<len(candidates) and candidates[i]<=target:
                if i!=0 and candidates[i]==candidates[i-1]:
                    i+=1
                    continue
                sub = target-candidates[i]
                ## 这里candidates[i+1:]是为了去除重复, 且排除使用过的数
                res1 = comb(candidates[i+1:], sub)
                for r in res1:
                    res.append([candidates[i]]+r)
                if len(res1)==0 and candidates[i]==target:
                    res.append([candidates[i]])
                i+=1
            return res 
        return comb(candidates.copy(), target)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

思路

递归，两个数字的全排列好找。n+1个全排列=（n+1）×n的全排列，从n+1数组中随便取出一个数，依次把它放在0，1，2。。n位置上，插入到剩余n个数的全排列中就可以了。

代码

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        cnt = len(nums)
        if cnt==1:
            return [nums]
        elif cnt>1:
            results = []
            # 任意取出一个数
            n0 = nums[0]
            nums_f = self.permute(nums[1:])
            for i in range(cnt):
                for rf in nums_f:
                    # b = rf.copy()
                    # b.insert(i, n0)
                    b = rf[:i]+[n0]+rf[i:]
                    results.append(b)
            return results
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
也即是把具有相同字母的单词组合在一起。

思路

利用哈希表，可以很容易处理。对每个单词排序后的字符串作为key，val是一个列表，把结果添加进去就ok了。

代码

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)
        ## 用sorted函数可以对字符串排序，返回的是列表
        for st in strs:
            key = "".join(sorted(st))
            mp[key].append(st)
        print(mp.values())
        return list(mp.values())
1
2
3
4
5
6
7
8
9

56. 合并区间

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路

先排序再遍历，不排序会超时O(n²)

代码

## 先排序 O(nlog(n))
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        new = sorted(intervals, key=lambda x:x[0])
        big = new[0]
        res = []
        for i in range(1,len(new)):
            if big[1]>=new[i][0]:
                big = [big[0], max(big[1], new[i][1])]
            else:
                res.append(big)
                big = new[i]
        ## 把最后一个区间加进来
        res.append(big)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

思路

中序遍历二叉树，如果是二叉搜索树，遍历结果则应该为递增的

代码

代码中还写了二叉树的先、中、后序、层序四种遍历，结果可以存在res列表中

# 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 ceng(self, root, res=[]):
        queue = [root]
        while len(queue):
            root = queue.pop(0)
            res.append(root.val)
            if root.left:
                queue.append(root.left)
            if root.right:
                queue.append(root.right)

    ## 二叉树中序遍历
    def mid(self, root, res=[]):
        subleft = root.left
        if subleft:
            self.mid(subleft, res)
        res.append(root.val)
        subright = root.right
        if subright:
            self.mid(subright, res)
    ## 二叉树先序遍历
    def before(self, root, res=[]):
        res.append(root.val)
        subleft = root.left
        if subleft:
            self.before(subleft, res)
        subright = root.right
        if subright:
            self.before(subright, res)

    ## 二叉树后序遍历
    def latter(self, root, res=[]):
        subleft = root.left
        if subleft:
            self.latter(subleft, res)
        subright = root.right
        if subright:
            self.latter(subright, res)
        res.append(root.val)
    
    ## 如果为True，则中序遍历的二叉树是递增的
    def midfind(self, root, res=[], flag=True):
        if not flag:
            return flag
        subleft = root.left
        if subleft:
            flag = self.midfind(subleft, res, flag)
        if not len(res):
            res.append(root.val)
        elif root.val>res[-1]:
            res.append(root.val)
        elif root.val<=res[-1]:
            return False
        subright = root.right
        if subright:
            flag = self.midfind(subright, res, flag)
        return flag

    ## 动态设置上下限(low, up)
    def isValidBST(self, root: TreeNode) -> bool:
        # res = []
        # return self.midfind(root, res)
        res = []
        self.ceng(root, res)
        print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成

思路

动态规划，通过s[0:i]，s[0:i-1]，… s[0]是否存在字典中，来判断s[0:i+1]是否在字典中。

代码

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        ## 动态规划
        n = len(s)
        dp=[False]*(n+1)
        dp[0] = True 
        for i in range(len(s)):
            for j in range(i+1):
                if dp[j] and s[j:i+1] in wordDict:
                    dp[i+1] = True
                    break 
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12

146. LRU缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

思路

python中有序字典实现

代码

class LRUCache:

    def __init__(self, capacity: int):
        self.LRU = collections.OrderedDict()
        self.c = capacity

    def get(self, key: int) -> int:
        if key in self.LRU.keys():
            self.LRU.move_to_end(key, last=False)
            return self.LRU[key]
        return -1

    def put(self, key: int, value: int) -> None:
        self.LRU[key] = value
        self.LRU.move_to_end(key, last=False)
        if len(self.LRU.keys())>self.c:
            self.LRU.popitem(-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

200. 岛屿数量

输入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1
也就是找到矩阵中的4-连通区域数量

思路

遍历矩阵，找到"1"时，统计数量加1，按深度优先搜索的方式开始访问其4-邻域节点，如果是"1"则置为"0"。最终的统计数量就是结果。

代码

这里深度优先搜索（dfs）是用队列实现的

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m ,n = len(grid), len(grid[0])
        i,j=0, 0
        queue = []
        num=0
        while i<m:
            j=0
            while j <n:
                if grid[i][j]=='1':
                    num +=1
                    queue.append([i,j])
                    grid[i][j]=0
                while len(queue):
                    # print(queue,'--')
                    ni,nj = queue.pop(0)
                    ## 判断其4-连通区域是否是1
                    if ni-1>=0 and grid[ni-1][nj]=='1':
                        queue.append([ni-1, nj])
                        grid[ni-1][nj] = 0
                    if ni+1<m and grid[ni+1][nj]=='1':
                        queue.append([ni+1, nj])
                        grid[ni+1][nj] = 0
                    if nj-1>=0 and grid[ni][nj-1]=='1':
                        queue.append([ni, nj-1])
                        grid[ni][nj-1] = 0
                    if nj+1<n and grid[ni][nj+1]=='1':
                        queue.append([ni, nj+1])
                        grid[ni][nj+1] = 0
                j+=1
            i+=1
        return num
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

560. 和为k的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
输入：nums = [1,2,3], k = 3
输出：2（1+2=3，3=3）

思路

利用数组的前n项和，sum(nums[i:j+1]) = Sj - Si。每次统计下标到 j 的子数组中所有满足条件的子数组，最后累加起来。
注意，k=0时是一个特殊情况，写代码时要单独处理。

代码

利用哈希表，时间复杂度O(n)。

## 前缀和，哈希表
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        table = collections.defaultdict(int)
        res=0
        sum = 0
        for i in range(len(nums)):
            # 前i项和 0-i
            sum += nums[i]
            ## 判断自身是否等于k，也就是从0，1，2，。。i的和是否是k，可以在前面用table[0]=1代替
            if sum==k:
                res+=1
            ## 判断前面是否出现sum-k，若出现则之后那段加起来就是k
            if table[sum - k]:
                res += table[sum-k]
            table[sum] += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17