Leetcode题解（5）- 2018 力扣 Leetcode CN 高频题汇总 part 1 字符串
《2018 力扣高频算法面试题汇总》专题 Part 1: 前言+字符串
# 一、开始之前
# 1、只出现一次的数字
Leetcode 136 题，详见 题解（4） (opens new window)
# 2、求众数
Leetcode 169 题，详见 题解（4） (opens new window)
# 3、搜索二维矩阵 II
Leetcode 240 题，剑指Offer第一题，可以说是我刷题的起点了 hhhhh，详见 剑指Offer (opens new window)
# 4、合并两个有序数组
Leetcode 88题，详见 题解（3） (opens new window)
# 5、鸡蛋掉落
Leetcode 887题，之前没做过。
# 问题
你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
2
3
4
5
6
7
# 思路及代码
思路详解可参考 鸡蛋掉落详解 (opens new window)
Leetcode hard难度还是很hard的，这个题的暴力解法，可以采用递归的方式。假如在n层扔了一个鸡蛋，会有两种结果：碎和不碎。如果碎掉，说明F应该小于n,之下，如果没碎，说明F应该大于等于n。通过这种切分，其实相当于分成了两个楼，每个楼再分别扔鸡蛋去判断。所以可以递归来做。需注意的是，要找的是无论F值如何的查找次数，所以递归时要对两个子楼的结果取max。
class Solution {
public int superEggDrop(int K, int N) {
return Solution.recursive(K, N);
}
public static int recursive(int K, int N) {
if (N == 0 || N == 1 || K == 1) {
return N;
}
int minimun = N;
for (int i = 1; i <= N; i++) {
int tMin = Math.max(Solution.recursive(K - 1, i - 1), Solution.recursive(K, N - i));
minimun = Math.min(minimun, 1 + tMin);
}
return minimun;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
这种做法的暴力就在于类似斐波那契数列时从上到下的递归计算方法，会有很多重复计算。
换种思路的动态规划解法。可以求 ** k 个鸡蛋在 m 步之内最多可以测出多少层 **。我们令 dp[k][m]表示k个鸡蛋在m步内可以测出的最多的层数。
dp[k][m] 的含义是k个鸡蛋 移动m次最多能够确定多少楼层
这个角度思考
dp[k][m] 最多能够确定的楼层数为L
那么我选定第一个扔的楼层之后，我要么碎，要么不碎
这就是把L分成3段
左边是碎的那段 长度是dp[k][m - 1]
右边是没碎的那段 长度是dp[k-1][m - 1] 因为已经碎了一个了
中间是我选定扔的楼层 是1
所以递推公式是
dp[k][m] = dp[k - 1][m - 1] + dp[k][m - 1] + 1
2
3
4
5
6
7
8
9
10
仔细想下上面的逻辑，然后可以编写代码。
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
m = 0
dp = [[0] * (K+1)] # 为了下标的简洁易读，从1开始编码。下标为0的列忽略掉。
while dp[m][K] < N:
m += 1
dp.append([0] * (K+1))
for k in range(1, K+1):
dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1
return m
2
3
4
5
6
7
8
9
10
# 二、主题要点
常见算法及数据结构：
--- 算法 - Algorithms ---
排序算法：快速排序、归并排序、计数排序
搜索算法：回溯、递归、剪枝技巧
图论：最短路、最小生成树、网络流建模
动态规划：背包问题、最长子序列、计数问题
基础技巧：分治、倍增、二分、贪心
--- 数据结构 - Data Structures ---
数组与链表：单 / 双向链表、跳舞链
栈与队列
树与图：最近公共祖先、并查集
哈希表
堆：大 / 小根堆、可并堆
字符串：字典树、后缀树
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 三、字符串
# 验证回文串
Leetcode 125题，详见 题解（4） (opens new window)
# 分割回文串
Leetcode 131题。
# 问题
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
2
3
4
5
6
# 思路
遇到求所有的组合、可能、排列等解集的题目，考虑DFS+回溯。以aab为例，从左到右遍历字符串，先取a，是回文则余下部分继续调用回文，不是则跳过，取aa，取aab...
# 代码
class Solution:
def __init__(self):
self.result = []
self.current = []
def partition(self, s: str) -> List[List[str]]:
self.dfs(s, 0)
return self.result
def dfs(self, s, start):
if start == len(s):
self.result.append(self.current[::]) # 注意一下这里，append时要做深拷贝，不然只放进去一个引用，后面修改了current后之前append进result的也会变了
return
for i in range(start, len(s)):
if self.is_huiwen(s[start:i+1]):
self.current.append(s[start:i+1])
self.dfs(s, i+1)
self.current.pop(-1)
def is_huiwen(self, s):
return s[::1] == s[::-1]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 单词拆分
Leetcode 第139题。
# 问题
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明： 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
2
3
4
# 思路
动态规划的题目。动态规划的思路：确定可以保存的信息 -> 递推式子，以及如何在递推中使用保存的信息 -> 确定起始条件。
这个题，dp[i]的含义代表从头至i的字符串可以被拆分。外层循环从头至尾循环各个位置，对于位置i，从头至i长度的字符串可以被拆分的条件是i之前存在一个位置j，使得dp[j]=True，且 s[j:i+1]在字典中。外层循环到最后，i等于最后一个位置，如果此处可被拆分的话就说明串可以被拆分。
# 代码
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False] * (len(s) + 1) # 下标从1开始
dp[0] = True # 0置为True，用于判断第一个字符时使之符合条件
for i in range(1, len(s) + 1):
for k in range(0, i):
if dp[k] and s[k:i] in wordDict:
dp[i] = True
return dp[-1]
2
3
4
5
6
7
8
9
# 单词拆分 2
Leetcode 第 140 题。
# 问题
题目要求同上，这次返回的是所有可能的组合情况，而不是仅仅返回True False。
输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。
2
3
4
5
6
7
8
9
10
# 代码
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
if not self.canBreak(s, wordDict): # 调用判断的原因是有个case会导致递归超时
return []
res = []
self.dfs(s, wordDict, res, '')
return res
def dfs(self, s, wordDict, res, tmp):
# tmp 用于记录当前已切分好了的内容，随着切分不断变长，s是余下的部分，随着切分不断变短
if not s:
res.append(tmp.strip())
for word in wordDict:
if s.startswith(word):
self.dfs(s[len(word):], wordDict, res, tmp+word+' ')
def canBreak(self, s, wordDict):
dp = [False] * (len(s) + 1) # 下标从1开始
dp[0] = True # 0置为True，用于判断第一个字符时使之符合条件
for i in range(1, len(s) + 1):
for k in range(0, i):
if dp[k] and s[k:i] in wordDict:
dp[i] = True
return dp[-1]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 实现 Trie 前缀树
Leetcode 第 208 题
# 问题
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
2
3
4
5
6
7
说明: 你可以假设所有的输入都是由小写字母 a-z 构成的。 保证所有输入均为非空字符串。
# 思路
想清楚如何构造每个节点，如何做插入和搜索操作就行。因为这个题只提供了插入、搜索，所以还是相对简单点的吧。
以 leet 字符串为例，存储时应该是这样的：
其中，isEnd用来标记该节点是否为结束。这个标记是必须的，例如先插入 apple，此时search app的话应该是false。如果再插入app，再search app就应该是true了。
# 代码
class Node(object):
def __init__(self):
self.data = {}
self.isEnd = False
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = Node()
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
cursor = self.root
for c in word:
if c not in cursor.data.keys():
cursor.data[c] = Node()
cursor = cursor.data[c]
cursor.isEnd = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
cursor = self.root
for c in word:
if c not in cursor.data.keys():
return False
cursor = cursor.data[c]
return cursor.isEnd
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
cursor = self.root
for c in prefix:
if c not in cursor.data.keys():
return False
cursor = cursor.data[c]
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
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
# 单词搜索
Leetcode 第79、212题。
# 问题
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
2
3
4
5
6
7
8
9
10
# 思路
回溯法。
# 代码
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
# find a start
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == word[0]:
ret = self.check([], board, word, i, j)
if ret:
return True
return False
def check(self, mem, board, word, i, j):
if i < 0 or i == len(board) or j < 0 or j == len(board[0]) or (i, j) in mem:
# 越界 或者重复访问节点
return False
if board[i][j] != word[0]:
# 不相等
return False
if len(word) == 1:
# 找到末尾了
return True
# 上下左右找
mem.append((i, j))
if self.check(mem, board, word[1:], i-1, j) or self.check(mem, board, word[1:], i, j-1) or self.check(mem, board, word[1:], i+1, j) or self.check(mem, board, word[1:], i, j+1):
return True
mem.pop() # 一定要注意这句，如果该节点无法走下一步了，那么该节点也走不通，需要将它从mem中弹出去
return False
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
# 问题
以上是单词搜索I 的内容，到了单词搜索II 这道题，单词不止一个了，而是要找出一个list中出现在board中的所有单词。
# 思路
这个题理论上可以直接调用前面的判断，对list中的单词逐个判断即可。但有一些非常特殊的test case，比如说数据量很大，而且具有相同的很长的前缀，该前缀不能匹配到。但在执行时仍然逐个去判断，导致超时了。
解决的方法可以是借助 Trie 树。首先对word list构建一棵Trie树。之前的I 中，我们在递归时是对单词从前到后逐个字母进行下去，而现在可以改成对 Trie树 按照深度优先搜索进行遍历。
# 思路
class Node(object):
def __init__(self):
self.data = {}
self.isEnd = False
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = Node()
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
cursor = self.root
for c in word:
if c not in cursor.data.keys():
cursor.data[c] = Node()
cursor = cursor.data[c]
cursor.isEnd = True
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
ret = set()
# build trie tree
tree = Trie()
for word in words:
tree.insert(word)
# 递归对树进行判断
self.exist(board, tree.root, ret)
return list(ret)
def exist(self, board: List[List[str]], tree: Node, ret: set) -> bool:
# find a start
for k in tree.data.keys():
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == k:
self.dfs([], board, tree.data[k], i, j, [k, ], ret)
def dfs(self, mem, board, tree, i, j, path, ret):
if i < 0 or i == len(board) or j < 0 or j == len(board[0]) or (i, j) in mem:
# 越界 或者重复访问节点
return
if board[i][j] != path[-1]:
# 不相等
return
if tree.isEnd:
# 找到末尾了
ret.add(''.join(path))
# 上下左右找
for k in tree.data.keys():
mem.append((i, j))
path.append(k)
self.dfs(mem, board, tree.data[k], i-1, j, path, ret)
self.dfs(mem, board, tree.data[k], i, j-1, path, ret)
self.dfs(mem, board, tree.data[k], i+1, j, path, ret)
self.dfs(mem, board, tree.data[k], i, j+1, path, ret)
path.pop()
mem.pop()
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
# 有效的字母异位词
Leetcode 242 题
# 问题
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词（含有的字母相同只是位置不同）。可以假设全部为小写字母。
示例 输入: s = "anagram", t = "nagaram" 输出: true
# 思路
其实可用的做法很多，甚至python里面 sorted(s) == sorted(t) 直接返回，一句话就解决了。
主要思路就是先扫一遍s，每个字母出现则其计数++，再扫一遍t，每个字母出现则其计数--，最后所有计数都为0则说明ok。
# 代码
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
mem = [0] * 26
for c in s:
mem[ord(c) - ord('a')] += 1
for c in t:
mem[ord(c) - ord('a')] -= 1
for n in mem:
if n != 0:
return False
return True
2
3
4
5
6
7
8
9
10
11
# 字符串中的第一个唯一字符
Leetcode 第387题。
# 问题
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
案例: s = "leetcode" 返回 0.
s = "loveleetcode", 返回 2.
可以假定该字符串只包含小写字母。
# 思路
鉴于限定为只包含小写字母，拿一个长为26的数组，先遍历一遍字符串，记下每个字符出现的次数；再遍历一遍字符串，同时去查询次数，遇到次数为1的字符，则直接返回此时下标即可。
# 代码
class Solution:
def firstUniqChar(self, s: str) -> int:
info = [0] * 26
for c in s:
info[ord(c)-ord('a')] += 1
for i in range(len(s)):
if info[ord(s[i])-ord('a')] == 1:
return i
return -1
2
3
4
5
6
7
8
9
# 反转字符串
leetcode 344题。
# 题目
输入char数组，原地修改数组，使用o（1）额外空间，返回反转后的串
# 代码
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
c = len(s)
for i in range(c//2):
s[i], s[c-1-i] = s[c-1-i], s[i]
2
3
4
5
6
7
8