写在最前
注：由于单版面容不下665道题，因此拆分，之后会单做一个目录。
**答案有误请私信告知，谢谢。
这是由Mono开展的第一个长期项目，会将Leetcode相关习题通过AHKv2实现，每道题会同步贴出相应Python代码。对一些Python程序员而言，可以通过比较，更快迁移到AHK这门语言上。
更新至第一百二十题 2022.08.25 Mono
第一百一十一题 二叉树的最小深度
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
给定一棵二叉树，求其最小深度。
最小深度是沿着从根节点到最近叶节点的最短路径的节点数。; Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
left = self.minDepth(root.left)
right = self.minDepth(root.right)
if not left and not right:
return 1
elif not left:
return right + 1
elif not right:
return left + 1
else:
return min(left, right) + 1; AutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class Solution
{
static minDepth(root)
{
if not root
return 0
left := this.minDepth(root.left)
right := this.minDepth(root.right)
if not left and not right
return 1
else if not left
return right + 1
else if not right
return left + 1
else
return min(left, right) + 1
}
}
; Create TreeNode
a := TreeNode(3)
a_head := a
tmp := TreeNode(9)
a.left := tmp
tmp2 := TreeNode(20)
a.right := tmp2
tmp3 := TreeNode(15)
tmp2.left := tmp3
tmp4 := TreeNode(7)
tmp2.right := tmp4
; Check Solution
; msgBox Solution.minDepth(a_head)第一百一十二题 路径总和
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
给定一个二叉树和一个和，确定该树是否有根到叶的路径，以便沿路径的所有值相加等于给定和。
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.; Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution(object):
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if root:
queue = deque([(root, root.val)])
while queue:
p, s = queue.popleft()
left, right = p.left, p.right
if left:
queue.append((p.left, s + p.left.val))
if right:
queue.append((p.right, s + p.right.val))
if not left and not right and s == sum:
return True
return False
return False; AutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class deque
{
__New(arr)
{
this.arr := arr
}
append(item)
{
this.arr.push(item)
}
popleft()
{
Return this.arr.RemoveAt(1)
}
}
class Solution
{
static hasPathSum(root, sum)
{
if root
{
queue := deque([[root, root.val]])
while queue.arr.Length
{
tmp := queue.popleft()
p := tmp[1]
s := tmp[2]
left := p.left
right := p.right
if left
queue.append([p.left, s + p.left.val])
if right
queue.append([p.right, s + p.right.val])
if not left and not right and s == sum
return True
}
return False
}
return False
}
}
; Create TreeNode
a := TreeNode(5)
a_head := a
tmp := TreeNode(4)
a.left := tmp
tmp2 := TreeNode(8)
a.right := tmp2
tmp3 := TreeNode(11)
tmp.left := tmp3
tmp4 := TreeNode(13)
tmp2.left := tmp4
tmp5 := TreeNode(4)
tmp2.right := tmp5
tmp6 := TreeNode(7)
tmp3.left := tmp6
tmp7 := TreeNode(2)
tmp3.right := tmp7
tmp8 := TreeNode(1)
tmp5.right := tmp8
; Check Solution
; msgBox Solution.hasPathSum(a_head, 22)第一百一十三题 路径总和 II : DFS回溯
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
给定一个二叉树和一个和，找到所有根到叶的路径，其中每个路径的和等于给定的和。
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]; Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
def dfs(root, s, path, res):
if root:
path.append(root.val)
s -= root.val
left = dfs(root.left, s, path, res)
right = dfs(root.right, s, path, res)
if not left and not right and s == 0:
res.append(path + [])
path.pop()
return True
res = []
dfs(root, sum, [], res)
return res; AutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class Solution
{
static pathSum(root, sum)
{
dfs(root, s, path, res)
{
if root
{
path.push(root.val)
s -= root.val
left := dfs(root.left, s, path, res)
right := dfs(root.right, s, path, res)
if not left and not right and s == 0
res.push(path.Clone())
path.pop()
return True
}
}
res := []
dfs(root, sum, [], res)
return res
}
}
; Create TreeNode
a := TreeNode(5)
a_head := a
tmp := TreeNode(4)
a.left := tmp
tmp2 := TreeNode(8)
a.right := tmp2
tmp3 := TreeNode(11)
tmp.left := tmp3
tmp4 := TreeNode(13)
tmp2.left := tmp4
tmp5 := TreeNode(4)
tmp2.right := tmp5
tmp6 := TreeNode(7)
tmp3.left := tmp6
tmp7 := TreeNode(2)
tmp3.right := tmp7
tmp8 := TreeNode(5)
tmp5.left := tmp8
tmp9 := TreeNode(1)
tmp5.right := tmp9
; Check Solution
; print Solution.pathSum(a_head, 22)
Print(Text)
{
msgBox ToString(Text)
}
ToString(Text)
{
Print_Text := ""
if Type(Text) == "Array"
{
Print_Text .= "["
For i in Text
Print_Text .= ToString(i) ","
Print_Text := SubStr(Print_Text, 1, StrLen(Print_Text) - 1)
Print_Text .= "]"
}
else
Print_Text .= Text
Return Print_Text
}第一百一十四题 二叉树展开为链表
Given a binary tree, flatten it to a linked list in-place.
给定一个二叉树，将其展平为一个链接列表。
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6; Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
def dfs(root):
if not root:
return root
left = dfs(root.left)
right = dfs(root.right)
if not left and not right:
return root
if right is None:
root.right = root.left
root.left = None
return left
if not left:
return right
tmp = root.right
root.right = root.left
root.left = None
left.right = tmp
return right
dfs(root); AutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class Solution
{
static flatten(root)
{
dfs(root)
{
if not root
return root
left := dfs(root.left)
right := dfs(root.right)
if not left and not right
return root
if !right
{
root.right := root.left
root.left := ""
return left
}
if not left
return right
tmp := root.right
root.right := root.left
root.left := ""
left.right := tmp
return right
}
dfs(root)
}
}
; Create TreeNode
a := TreeNode(1)
a_head := a
tmp := TreeNode(2)
a.left := tmp
tmp2 := TreeNode(5)
a.right := tmp2
tmp3 := TreeNode(3)
tmp.left := tmp3
tmp4 := TreeNode(4)
tmp.right := tmp4
tmp5 := TreeNode(6)
tmp2.right := tmp5
Solution.flatten(a_head)
; Check Solution
; msgBox print_treenode(a_head)
print_treenode(root)
{
res := "None"
if root
{
res := root.val
res .= "->(" print_treenode(root.right) ")"
res := "(" print_treenode(root.left) ")<-" res
}
return res
}第一百一十五题 不同的子序列
Given a string S and a string T, count the number of distinct subsequences of S which equals T.
给定一个字符串S和一个字符串T，计算S的不同子序列的数量，这些子序列等于T。
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
字符串的子序列是一个新字符串，它是通过删除一些字符（可以是无字符）而从原始字符串中形成的，而不干扰其余字符的相对位置。（即，“ACE”是“ABCDE”的子序列，而“AEC”不是）。
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.; Python
class Solution(object):
# space O(n^2)
def _numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
dp = [[0] * (len(t) + 1) for _ in xrange(0, len(s) + 1)]
for i in xrange(0, len(s) + 1):
dp[i][0] = 1
for i in xrange(1, len(s) + 1):
for j in xrange(1, len(t) + 1):
dp[i][j] += dp[i - 1][j]
if t[j - 1] == s[i - 1]:
dp[i][j] += dp[i - 1][j - 1]
return dp[-1][-1]
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
dp = [0] * (len(t) + 1)
for i in xrange(1, len(s) + 1):
pre = 1
for j in xrange(1, len(t) + 1):
tmp = dp[j]
if t[j - 1] == s[i - 1]:
dp[j] += pre
pre = tmp
return dp[-1]; AutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static _numDistinct(s, t)
{
s := StrSplit(s, "")
t := StrSplit(t, "")
dp := [0]
mutiple(dp, t.Length + 1)
dp := [dp]
mutiple(dp, s.Length + 1)
loop s.Length + 1
dp[A_Index][1] := 1
for i in range(1, s.Length + 1)
{
for j in range(1, t.Length + 1)
{
dp[i + 1][j + 1] += dp[i][j + 1]
if t[j] == s[i]
dp[i + 1][j + 1] += dp[i][j]
}
}
return dp[-1][-1]
}
static numDistinct(s, t)
{
s := StrSplit(s, "")
t := StrSplit(t, "")
dp := [0]
mutiple(dp, t.Length + 1)
for i in range(1, s.Length + 1)
{
pre := 1
for j in range(1, t.Length + 1)
{
tmp := dp[j + 1]
if t[j] == s[i]
dp[j + 1] += pre
pre := tmp
}
}
return dp[-1]
}
}
; Check Solution
; msgBox Solution._numDistinct("rabbbit", "rabbit")
; msgBox Solution.numDistinct("rabbbit", "rabbit")
mutiple(Lst, Number)
{
tmp := Lst.Clone()
Loop Number - 1
For i in tmp
{
Try
Lst.Push(i.Clone())
Catch
Lst.Push(i)
}
}第一百一十六题 填充每个节点的下一个右侧节点指针
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
填充每个下一个指针以指向其下一个右节点。如果没有下一个右节点，则下一个指针应设置为空。
最初，所有下一个指针都设置为空。
注：您只能使用恒定的额外空间。
你可以假设它是一个完美的二叉树（即，所有的叶子都在同一层次上，每个父树都有两个子树）。
For example,
Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL; Python
# Definition for binary tree with next pointer.
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
if root and root.left and root.right:
root.left.next = root.right
root.right.next = root.next and root.next.left
return self.connect(root.left) or self.connect(root.right); AutoHotkey
class TreeLinkNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
this.next := ""
}
}
class Solution
{
connect(root)
{
if root and root.left and root.right
{
root.left.next := root.right
root.right.next := root.next and root.next.left
return this.connect(root.left) or this.connect(root.right)
}
}
}
; 本题意义参考：https://blog.csdn.net/llzqxl/article/details/117249156第一百一十七题 填充每个节点的下一个右侧节点指针 II
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
You may only use constant extra space.
跟进“在每个节点中填充下一个右指针”问题。
如果给定的树可以是任何二叉树呢？您以前的解决方案仍然有效吗？
注：您只能使用恒定的额外空间。
For example,
Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL; Python
# Definition for binary tree with next pointer.
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
p = root
pre = None
head = None
while p:
if p.left:
if pre:
pre.next = p.left
pre = p.left
if p.right:
if pre:
pre.next = p.right
pre = p.right
if not head:
head = p.left or p.right
if p.next:
p = p.next
else:
p = head
head = None
pre = None; AutoHotkey
class TreeLinkNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
this.next := ""
}
}
class Solution
{
static connect(root)
{
p := root
pre := ""
head := ""
while p
{
if p.left
{
if pre
pre.next := p.left
pre := p.left
}
if p.right
{
if pre
pre.next := p.right
pre := p.right
}
if not head
head := p.left or p.right
if p.next
p := p.next
else
{
p := head
head := ""
pre := ""
}
}
}
}
; 本题意义参考：https://blog.csdn.net/baidu_37588698/article/details/108849592第一百一十八题 杨辉三角
Given numRows, generate the first numRows of Pascal's triangle.
给定numRows，生成Pascal三角形的第一个numRows。
For example, given numRows = 5,
Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]; Python
class Solution(object):
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
ans = [[1] * n for n in xrange(1, numRows + 1)]
for i in range(1, numRows + 1):
for j in range(0, i - 2):
ans[i - 1][1 + j] = ans[i - 2][j] + ans[i - 2][j + 1]
return ans; AutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static generate(numRows)
{
ans := []
for n in range(1, numRows + 1)
{
tmp := [1]
mutiple(tmp, n)
ans.push(tmp)
}
for i in range(1, numRows + 1)
{
for j in range(0, i - 2)
ans[i][2 + j] := ans[i - 1][j + 1] + ans[i - 1][j + 2]
}
return ans
}
}
; Check Solution
; print Solution.generate(5)
mutiple(Lst, Number)
{
tmp := Lst.Clone()
Loop Number - 1
For i in tmp
{
Try
Lst.Push(i.Clone())
Catch
Lst.Push(i)
}
}
Print(Text)
{
msgBox ToString(Text)
}
ToString(Text)
{
Print_Text := ""
if Type(Text) == "Array"
{
Print_Text .= "["
For i in Text
Print_Text .= ToString(i) ","
Print_Text := SubStr(Print_Text, 1, StrLen(Print_Text) - 1)
Print_Text .= "]"
}
else
Print_Text .= Text
Return Print_Text
}第一百一十九题 杨辉三角 II
Given an index k, return the kth row of the Pascal's triangle.
给定索引k，返回帕斯卡三角形的第k行。
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?
注：你能优化你的算法只使用O（k）个额外空间吗？; Python
class Solution(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
fact = [1] * (rowIndex + 1)
ans = [1] * (rowIndex + 1)
for i in range(1, rowIndex + 1):
fact[i] = fact[i - 1] * i
for i in range(1, rowIndex):
ans[i] = fact[-1] / (fact[i] * fact[rowIndex - i])
return ans; AutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static getRow(rowIndex)
{
fact := [1]
mutiple(fact, rowIndex + 1)
ans := [1]
mutiple(ans, rowIndex + 1)
for i in range(1, rowIndex + 1)
fact[i + 1] := fact[i] * i
for i in range(1, rowIndex)
ans[i + 1] := fact[-1] // (fact[i + 1] * fact[rowIndex - i + 1])
return ans
}
}
; Check Solution
; print Solution.getRow(3)
mutiple(Lst, Number)
{
tmp := Lst.Clone()
Loop Number - 1
For i in tmp
{
Try
Lst.Push(i.Clone())
Catch
Lst.Push(i)
}
}
Print(Text)
{
msgBox ToString(Text)
}
ToString(Text)
{
Print_Text := ""
if Type(Text) == "Array"
{
Print_Text .= "["
For i in Text
Print_Text .= ToString(i) ","
Print_Text := SubStr(Print_Text, 1, StrLen(Print_Text) - 1)
Print_Text .= "]"
}
else
Print_Text .= Text
Return Print_Text
}第一百二十题 三角形最小路径和
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
给定一个三角形，求从上到下的最小路径和。每一步您都可以移动到下一行的相邻数字。
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
从上到下的最小路径和为11（即2+3+5+1=11）。
注：如果您仅能使用O（n）个额外空间来执行此操作，则会获得额外的积分，其中n是三角形中的行总数。; Python
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
dp = [0] * len(triangle)
dp[0] = triangle[0][0]
for i in range(1, len(triangle)):
pre = dp[0]
for j in range(len(triangle[i])):
tmp = dp[j]
if j == 0:
dp[j] = pre
elif j == len(triangle[i]) - 1:
dp[j] = pre
else:
dp[j] = min(dp[j], pre)
dp[j] += triangle[i][j]
pre = tmp
return min(dp); AutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static minimumTotal(triangle)
{
dp := [0]
mutiple(dp, triangle.Length)
dp[1] := triangle[1][1]
for i in range(1, triangle.Length)
{
pre := dp[1]
for j in range(0, triangle[i + 1].Length)
{
tmp := dp[j + 1]
if j == 0
dp[j + 1] := pre
else if j == triangle[i + 1].Length - 1
dp[j + 1] := pre
else
dp[j + 1] := min(dp[j + 1], pre)
dp[j + 1] += triangle[i + 1][j + 1]
pre := tmp
}
}
return min(dp*)
}
}
; Check Solution
triangle :=
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
; msgBox Solution.minimumTotal(triangle)
mutiple(Lst, Number)
{
tmp := Lst.Clone()
Loop Number - 1
For i in tmp
{
Try
Lst.Push(i.Clone())
Catch
Lst.Push(i)
}
}
