实验室暑假考核题目

随便写写解题思路来着

824.山羊拉丁文

给定一个由空格分割单词的句子 S。每个单词只包含大写或小写字母。

我们要将句子转换为 “Goat Latin”(一种类似于 猪拉丁文 - Pig Latin 的虚构语言)。

山羊拉丁文的规则如下:

如果单词以元音开头(a, e, i, o, u),在单词后添加”ma”。
例如,单词”apple”变为”applema”。

如果单词以辅音字母开头(即非元音字母),移除第一个字符并将它放到末尾,之后再添加”ma”。
例如,单词”goat”变为”oatgma”。

根据单词在句子中的索引,在单词最后添加与索引相同数量的字母’a’,索引从1开始。
例如,在第一个单词后添加”a”,在第二个单词后添加”aa”,以此类推。
返回将 S 转换为山羊拉丁文后的句子。

来源:

leetcode 824

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def toGoatLatin(self, S: str) -> str:
vowel = "aeiouAEIOU"

spllit_str = S.split(" ")
for k, s in enumerate(spllit_str):
if s[0] not in vowel:
s = s[1:] + s[0]
s += "ma" + "a" * (k + 1)
spllit_str[k] = s

return ' '.join(spllit_str)

很简单得暴力题目 直接搞定

1
1

1078.Bigram 分词

给出第一个词 first 和第二个词 second,考虑在某些文本 text 中可能以 “first second third” 形式出现的情况,其中 second 紧随 first 出现,third 紧随 second 出现。

对于每种这样的情况,将第三个词 “third” 添加到答案中,并返回答案。

示例 1:

输入:text = “alice is a good girl she is a good student”, first = “a”, second = “good”
输出:[“girl”,”student”]
示例 2:

输入:text = “we will we will rock you”, first = “we”, second = “will”
输出:[“we”,”rock”]

提示:

1 <= text.length <= 1000
text 由一些用空格分隔的单词组成,每个单词都由小写英文字母组成
1 <= first.length, second.length <= 10
first 和 second 由小写英文字母组成

来源:

leetcode 1078

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def findOcurrences(self, text: str, first: str, second: str) -> List[str]:
ans = []

split_str = text.split()
length = len(split_str)

for k, s in enumerate(split_str):
if s == first and k + 1 < length and k + 2 < length:
if split_str[k + 1] == second:
ans.append(split_str[k + 2])

return ans

暴力完事儿,这里顺便优化一下,可以把60ms提到40ms左右

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def findOcurrences(self, text: str, first: str, second: str) -> List[str]:
ans = []

split_str = text.split()
length = len(split_str)

for k, s in enumerate(split_str[:-2]):
if s == first and split_str[k + 1] == second:
ans.append(split_str[k + 2])

return ans

搞定

2
2

120. 三角形最小路径和

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如,给定三角形:

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

说明:

如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

来源:

leetcode 120

dp 说是空间复杂度O(N),但其实这个题目空间复杂度可以到O(1)

先尝试用DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
# DFS
floors = len(triangle)

def dfs(floor, left, right):
# 判断是否最下层也计算过了
if floor == floors:
return 0 # 最低端再往下权重就是0

ans = 0 # 初始为0
if left < floor + 1:
tl = dfs(floor + 1, left, left + 1) + triangle[floor][left]

if right < floor + 1:
tr = dfs(floor + 1, right, right + 1) + triangle[floor][right]

return ans + min(tl, tr)

return dfs(1, 0, 1) + triangle[0][0]

结果果然华丽丽的超时了,打眼一看过了42个,卡在了最后一个,可能改改就能过了吧(可能性比较小,因为用C++试了下也超时,应该是卡的时间),不过也是很极限了,所以改用dp写。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
# dp
floors = len(triangle)
if floors == 0:
return 0
for i in range(floors - 2, -1, -1):
for j in range(i + 1):
triangle[i][j] += min(triangle[i + 1][j + 1], triangle[i + 1][j])

return triangle[0][0]

这里可以不用开新的dp数组(无论是二维还是一维),因为是从下往上的,只需要最终结果,所以可以直接利用原三角形数组当作dp数组,所以空间就变成了O(1)了。

不过这个才只打败了50%的人,甚至空间只打败了5%

3
3

下面这个是最快用时的答案:

1
2
3
4
5
6
7
8
9
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
if not triangle:
return
res = triangle[-1]
for i in range(len(triangle) - 2, -1, -1):
for j in range(len(triangle[i])):
res[j] = min(res[j], res[j + 1]) + triangle[i][j]
return res[0]

从中,可以看到:

  1. 其实定义过多变量会减缓速度并且增加空间用量,编译器会给优化的。
  2. 尽量用一维list索引,速度会快很多
  3. 尽量使用相同的list进行索引,编译器会优化

872. 叶子相似的树

请考虑一颗二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

举个例子,如上图所示,给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两颗二叉树的叶值序列是相同,那么我们就认为它们是 叶相似 的。

如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的,则返回 true;否则返回 false 。

提示:

给定的两颗树可能会有 1 到 100 个结点。

来源:

leetcode 872

treepic
treepic

直接前序遍历加判断,暴力就完事儿

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

class Solution:
def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
# 前序遍历
def tree_leaf_sim_calcu(root: TreeNode):
stack, ans = [], [] # 用list
while len(stack) or root:
if root:
if root.left is root.right is None:
ans.append(root.val)
stack.append(root)
root = root.left
else:
root = stack.pop().right
return ans

return tree_leaf_sim_calcu(root1) == tree_leaf_sim_calcu(root2)

但其实这样只击败了44%的用户,看了一下用时快的回答,发现基本上都是用的递归,递归占用资源太大,所以就不改了,思想都是一样的。

4
4

为什么递归用时会短呢,这是因为python里的while循环是用纯python编写的,所以效率远不及简单函数堆栈的效率,所以会出现非递归比递归用时长的现象,如果用别的语言(没错就是C++)是不会出现这种问题的!

863. 二叉树中所有距离为 K 的结点

给定一个二叉树(具有根结点 root), 一个目标结点 target ,和一个整数值 K 。

返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

示例 1:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

输出:[7,4,1]

解释:
所求结点为与目标结点(值为 5)距离为 2 的结点,
值分别为 7,4,以及 1

注意,输入的 “root” 和 “target” 实际上是树上的结点。
上面的输入仅仅是对这些对象进行了序列化描述。

提示:

给定的树是非空的,且最多有 K 个结点。
树上的每个结点都具有唯一的值 0 <= node.val <= 500 。
目标结点 target 是树上的结点。
0 <= K <= 1000.

来源:

leetcode 863

dfs加父节点转成图问题再利用bfs寻找target为中心的节点。这里代码参考了标准答案,想看的去题解看第一个就ok了。

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
class Solution:
def distanceK(self, root, target, K):
"""
:type root: TreeNode
:type target: TreeNode
:type K: int
:rtype: List[int]
"""
from collections import deque

# 判断是否是本身
if not K:
return [target.val]

# dfs标记父节点
def dfs(node: TreeNode, father_node: TreeNode):
if node:
node.father = father_node
dfs(node.left, node)
dfs(node.right, node)

dfs(root, None)

# 这一步过后其实就变成了图问题,每个都有三个节点的图
# 下面对于target进行bfs
def bfs():
search = {target}
queue = deque([(target, 0)]) # 存0 即原点
while queue:
if queue[0][1] == K:
return [node.val for node, N in queue]
node, N = queue.popleft()
for n in (node.left, node.right, node.father):
if n and n not in search:
queue.append((n, N + 1))
search.add(n)
return []

return bfs()

看了一下速度最快的回答,也是dfs建图+bfs搜索,除了一些骚操作,应该大部分都是优化这个思路的代码实现。

5
5