写在最前
注：由于单版面容不下665道题，因此拆分，之后会单做一个目录。
**答案有误请私信告知，谢谢。
这是由Mono开展的第一个长期项目，会将Leetcode相关习题通过AHKv2实现，每道题会同步贴出相应Python代码。对一些Python程序员而言，可以通过比较，更快迁移到AHK这门语言上。
***引流：请喜欢Python的或是对于人工智能感兴趣的程序员关注我的另一个（大概）每周更新项目《Sinet库》，目前已经迁移了包括Numpy、Pandas和Sklearn在内的大量Python相关函数内容。
***引流2：目前新出一个长期项目，是关于Sinet库的数据类型的代码示例及解析，有兴趣的可以捧个人场。
***引流3：目前新出一个长期项目，是利用Numahk库进行人工智能机器学习模块的示例教学。
更新至第一百题 2022.08.07 Mono
第九十一题 解码方法
A message containing letters from A-Z is being encoded to numbers using the following mapping:
包含A-Z字母的消息正在使用以下映射编码为数字：
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
给定包含数字的编码消息，确定解码方法的总数。
For example,
Given encoded message "12",
it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
例如
给定编码消息“12”，
它可以被解码为“AB”（12）或“L”（12）。
因此解码“12”的方式数为2。Python
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if len(s) == 0:
return 0
dp = [0] * (len(s) + 1)
dp[0] = 1
dp[1] = 0 if s[0] == "0" else 1
for i in xrange(1, len(s)):
pre = int(s[i-1])
cur = int(s[i])
num = pre * 10 + cur
if cur != 0:
dp[i+1] += dp[i]
if pre != 0 and 0 < num <= 26:
dp[i+1] += dp[i - 1]
return dp[-1]AutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static numDecodings(s)
{
s := StrSplit(s, "")
if s.Length == 0
return 0
dp := [0]
mutiple(dp, s.Length + 1)
dp[1] := 1
dp[2] := (s[1] == "0") ? 0 : 1
for i in range(1, s.Length)
{
pre := s[i]
cur := s[i + 1]
num := pre * 10 + cur
if cur != 0
dp[i + 2] += dp[i + 1]
if pre != 0 and 0 < num <= 26
dp[i + 2] += dp[i]
}
return dp[-1]
}
}
; Check Solution
; msgBox Solution.numDecodings("12")
mutiple(Lst, Number)
{
tmp := Lst.Clone()
Loop Number - 1
For i in tmp
{
Try
Lst.Push(i.Clone())
Catch
Lst.Push(i)
}
}第九十二题 反转链表 II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
将链表从位置m反转到位置n。一次到位。
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.Python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
def reverse(root, prep, k):
cur = root
pre = None
next = None
while cur and k > 0:
next = cur.next
cur.next = pre
pre = cur
cur = next
k -= 1
root.next = next
prep.next = pre
return pre
dummy = ListNode(-1)
dummy.next = head
k = 1
p = dummy
start = None
while p:
if k == m:
start = p
if k == n + 1:
reverse(start.next, start, n - m + 1)
return dummy.next
k += 1
p = p.nextAutoHotkey
class ListNode
{
__New(x)
{
this.val := x
this.next := ""
}
}
class Solution
{
static reverseBetween(head, m, n)
{
reverse(root, prep, k)
{
cur := root
pre := ""
next := ""
while cur and k > 0
{
next := cur.next
cur.next := pre
pre := cur
cur := next
k -= 1
}
root.next := next
prep.next := pre
return pre
}
dummy := ListNode(-1)
dummy.next := head
k := 1
p := dummy
start := ""
while p
{
if k == m
start := p
if k == n + 1
{
reverse(start.next, start, n - m + 1)
return dummy.next
}
k += 1
p := p.next
}
}
}
; Create List_Node
a := ListNode(1)
a_head := a
arr := [2,3,4,5]
Loop arr.length
{
temp := ListNode(arr[A_Index])
a.next := temp
a := a.next
}
; Check Solution
; 这里提供了一种直观看链表的办法
; res := Solution.reverseBetween(a_head, 2, 4)
; res_text := ""
; while res
; {
; res_text .= res.val "->"
; res := res.next
; }
; msgBox SubStr(res_text, 1, strlen(res_text) - 2)第九十三题 复原IP地址
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
给定一个只包含数字的字符串，通过返回所有可能的有效IP地址组合来还原它。
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)Python
class Solution(object):
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
ans = []
n = len(s)
def isValid(num):
if len(num) == 1:
return True
if len(num) > 1 and num[0] != "0" and int(num) <= 255:
return True
return False
for i in range(0, min(3, n - 3)):
a = s[:i+1]
if not isValid(a):
break
for j in range(i + 1, min(i + 4, n - 2)):
b = s[i+1:j+1]
if not isValid(b):
break
for k in range(j + 1, min(j + 4, n - 1)):
c = s[j+1:k+1]
d = s[k+1:]
if not isValid(c):
break
if not isValid(d):
continue
ans.append("{}.{}.{}.{}".format(a, b, c, d))
return ansAutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static restoreIpAddresses(s)
{
s := StrSplit(s, "")
ans := []
n := s.Length
isValid(num)
{
if num.Length == 1
return True
if num.Length > 1 and num[1] != "0" and lst2num(num) <= 255
return True
return False
}
for i in range(0, min(3, n - 3))
{
a := []
for k in s
{
if A_Index > i + 2
break
a.push(k)
}
if not isValid(a)
break
for j in range(i + 1, min(i + 4, n - 2))
{
b := []
for l in s
{
if A_Index < i + 3
continue
if A_Index > j + 2
break
b.push(l)
}
if not isValid(b)
break
for k in range(j + 1, min(j + 4, n - 1))
{
c := []
for m in s
{
if A_Index < j + 3
continue
if A_Index > k + 2
break
c.push(m)
}
d := []
for n in s
{
if A_Index < k + 3
continue
d.push(n)
}
if not isValid(c)
break
if not isValid(d)
continue
ans.push(lst2num(a) "." lst2num(b) "." lst2num(c) "." lst2num(d))
}
}
}
return ans
}
}
; Check Solution
; print Solution.restoreIpAddresses("25525511135")
lst2num(lst)
{
nums := 0
for i in lst
{
nums *= 10
nums += i
}
return nums
}
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, return the inorder traversal of its nodes' values.
给定一个二叉树，返回其节点值的按序遍历。
For example:
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
注意：递归解决方案很简单，您可以迭代地进行吗？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 inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res, stack = [], [(1, root)]
while stack:
p = stack.pop()
if not p[1]: continue
stack.extend([(1, p[1].right), (0, p[1]), (1, p[1].left)]) if p[0] != 0 else res.append(p[1].val)
return resAutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class Solution
{
static inorderTraversal(root)
{
res := []
stack := [[1, root]]
while stack.Length
{
p := stack.pop()
if not p[2]
continue
if p[1] != 0
stack.push([1, p[2].right], [0, p[2]], [1, p[2].left])
else
res.push(p[2].val)
}
return res
}
}
; Create TreeNode
a := TreeNode(1)
a_head := a
tmp := TreeNode(2)
a.right := tmp
tmp2 := TreeNode(3)
tmp.left := tmp2
; Check Solution
; print Solution.inorderTraversal(a_head)
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 an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
给定整数n，生成存储值1…n的所有结构唯一的BST（二进制搜索树）。
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
给定n=3，您的程序应该返回所有5个唯一的BST，如下所示。
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3Python
class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
def clone(root, offset):
if root:
newRoot = TreeNode(root.val + offset)
left = clone(root.left, offset)
right = clone(root.right, offset)
newRoot.left = left
newRoot.right = right
return newRoot
if not n:
return []
dp = [[]] * (n + 1)
dp[0] = [None]
for i in range(1, n + 1):
dp[i] = []
for j in range(1, i + 1):
for left in dp[j - 1]:
for right in dp[i - j]:
root = TreeNode(j)
root.left = left
root.right = clone(right, j)
dp[i].append(root)
return dp[-1]AutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static generateTrees(n)
{
clone(root, offset)
{
if root
{
newRoot := TreeNode(root.val + offset)
left := clone(root.left, offset)
right := clone(root.right, offset)
newRoot.left := left
newRoot.right := right
return newRoot
}
}
if not n
return []
dp := [[]]
mutiple(dp, n + 1)
dp[1] := [""]
for i in range(1, n + 1)
{
dp[i + 1] = []
for j in range(1, i + 1)
{
for left in dp[j]
{
for right in dp[i - j + 1]
{
root := TreeNode(j)
root.left := left
root.right := clone(right, j)
dp[i + 1].push(root)
}
}
}
}
return dp[-1]
}
}
; Check Solution
; print Solution.generateTrees(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 if Type(Text) == "TreeNode"
Print_Text .= print_treenode(Text)
else
Print_Text .= Text
Return Print_Text
}
print_treenode(root)
{
res := "None"
if root
{
res := root.val
res .= "->(" print_treenode(root.right) ")"
res := "(" print_treenode(root.left) ")<-" res
}
return res
}第九十六题 不同的二叉搜索树
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
给定整数n，生成存储值1…n的所有结构唯一的BST（二进制搜索树）。
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
给定n=3，您的程序应该返回所有5个唯一的BST，如下所示。
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3Python
class Solution(object):
def _numTrees(self, n):
"""
:type n: int
:rtype: int
"""
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i + 1):
dp[i] += dp[j - 1] * dp[i - j]
return dp[-1]
def numTrees(self, n):
ans = 1
for i in range(1, n + 1):
ans = ans * (n + i) / i
return ans / (n + 1)AutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static _numTrees(n)
{
dp := [0]
mutiple(dp, n + 1)
dp[1] := dp[2] := 1
for i in range(2, n + 1)
{
for j in range(1, i + 1)
dp[i + 1] += dp[j] * dp[i - j + 1]
}
return dp[-1]
}
static numTrees(n)
{
ans := 1
for i in range(1, n + 1)
ans := ans * (n + i) // i
return ans // (n + 1)
}
}
; Check Solution
; msgBox Solution.numTrees(3)
mutiple(Lst, Number)
{
tmp := Lst.Clone()
Loop Number - 1
For i in tmp
{
Try
Lst.Push(i.Clone())
Catch
Lst.Push(i)
}
}第九十七题 交错字符串
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
给定s1、s2、s3，找出s3是否由s1和s2的交错形成。
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.Python
class Solution(object):
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
d = {}
s3 = list(s3)
if len(s1) + len(s2) != len(s3):
return False
def dfs(s1, i, s2, j, d, path, s3):
if (i, j) in d:
return d[(i, j)]
if path == s3:
return True
if i < len(s1):
if s3[i + j] == s1[i]:
path.append(s1[i])
if dfs(s1, i + 1, s2, j, d, path, s3):
return True
path.pop()
d[(i+1, j)] = False
if j < len(s2):
if s3[i + j] == s2[j]:
path.append(s2[j])
if dfs(s1, i, s2, j + 1, d, path, s3):
return True
path.pop()
d[(i, j+1)] = False
return False
return dfs(s1, 0, s2, 0, d, [], s3)AutoHotkey
class Solution
{
static isInterleave(s1, s2, s3)
{
d := map()
s1 := StrSplit(s1, "")
s2 := StrSplit(s2, "")
s3 := StrSplit(s3, "")
if s1.Length + s2.Length != s3.Length
return False
dfs(s1, i, s2, j, d, path, s3)
{
if d.has([i, j])
return d[[i, j]]
if arrcmp(path, s3)
return True
if i < s1.Length
{
if s3[i + j + 1] == s1[i + 1]
{
path.push(s1[i + 1])
if dfs(s1, i + 1, s2, j, d, path, s3)
return True
path.pop()
d[[i+1, j]] := False
}
}
if j < s2.Length
{
if s3[i + j + 1] == s2[j + 1]
{
path.push(s2[j + 1])
if dfs(s1, i, s2, j + 1, d, path, s3)
return True
path.pop()
d[[i, j+1]] := False
}
}
return False
}
return dfs(s1, 0, s2, 0, d, [], s3)
}
}
; Check Solution
; msgBox Solution.isInterleave("aabcc","dbbca","aadbbcbcac")
; msgBox Solution.isInterleave("aabcc","dbbca","aadbbbaccc")
arrcmp(arr1, arr2)
{
if Type(arr1) !== "Array"
Return arr1 == arr2
if arr1.Length != arr2.Length
Return False
for i in arr1
{
if !arrcmp(arr2[A_Index], i)
Return False
}
Return True
}第九十八题 验证二叉搜索树
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
给定一个二叉树，确定它是否是有效的二叉搜索树（BST）。
假设BST定义如下：
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左子树和右子树都必须是二叉搜索树。
Example 1:
2
/ \
1 3
Binary tree [2,1,3], return true.
Example 2:
1
/ \
2 3
Binary tree [1,2,3], return false.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 isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
prev = -float("inf")
stack = [(1, root)]
while stack:
p = stack.pop()
if not p[1]:
continue
if p[0] == 0:
if p[1].val <= prev:
return False
prev = p[1].val
else:
stack.append((1, p[1].right))
stack.append((0, p[1]))
stack.append((1, p[1].left))
return TrueAutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class Solution
{
static isValidBST(root)
{
prev := -float(0x7fffffff)
stack := [[1, root]]
while stack.Length
{
p := stack.pop()
if not p[2]
continue
if p[1] == 0
{
if p[2].val <= prev
return False
prev := p[2].val
}
else
{
stack.push([1, p[2].right])
stack.push([0, p[2]])
stack.push([1, p[2].left])
}
}
return True
}
}
; Create TreeNode
a := TreeNode(2)
a_head := a
tmp := TreeNode(1)
a.left := tmp
tmp2 := TreeNode(3)
a.right := tmp2
b := TreeNode(1)
b_head := b
tmp := TreeNode(2)
b.left := tmp
tmp2 := TreeNode(3)
b.right := tmp2
; Check Solution
; msgBox Solution.isValidBST(a_head)
; msgBox Solution.isValidBST(b_head)第九十九题 恢复二叉搜索树
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
二叉搜索树（BST）的两个元素错误地交换。
恢复树而不更改其结构。
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
注:使用O（n）空间的解决方案非常简单。你能想出一个常数空间解吗？Python
class Solution:
def __init__(self):
self.n1 = None
self.n2 = None
self.pre = None
def findBadNode(self, root):
if root is None : return
self.findBadNode(root.left)
if self.pre is not None:
if root.val < self.pre.val:
if self.n1 is None:
self.n1 = self.pre
self.n2 = root
else:
self.n2 = root
self.pre = root
self.findBadNode(root.right)
def recoverTree(self, root):
self.findBadNode(root)
if self.n1 is not None and self.n2 is not None:
self.n1.val, self.n2.val = self.n2.val, self.n1.valAutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class Solution
{
static n1 := ""
static n2 := ""
static pre := ""
static findBadNode(root)
{
if !root
return
this.findBadNode(root.left)
if this.pre
{
if root.val < this.pre.val
{
if !this.n1
{
this.n1 := this.pre
this.n2 := root
}
else
this.n2 := root
}
}
this.pre := root
this.findBadNode(root.right)
}
static recoverTree(root)
{
this.findBadNode(root)
if this.n1 and this.n2
{
tmp := this.n1.val
this.n1.val := this.n2.val
this.n2.val := tmp
}
}
}
; Create TreeNode
a := TreeNode(3)
a_head := a
tmp := TreeNode(1)
a.left := tmp
tmp2 := TreeNode(4)
a.right := tmp2
tmp3 := TreeNode(2)
tmp2.left := tmp3
Solution.recoverTree(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 two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
给定两个二叉树，编写一个函数来检查它们是否相等。
如果两个二叉树在结构上相同且节点具有相同的值，则认为它们相等。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 isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if not p or not q:
return p == q
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)AutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class Solution
{
static isSameTree(p, q)
{
if not p or not q
return p == q
return p.val == q.val and this.isSameTree(p.left, q.left) and this.isSameTree(p.right, q.right)
}
}
; Create TreeNode
a := TreeNode(3)
a_head := a
tmp := TreeNode(1)
a.left := tmp
tmp2 := TreeNode(4)
a.right := tmp2
tmp3 := TreeNode(2)
tmp2.left := tmp3
b := TreeNode(3)
b_head := b
tmp := TreeNode(1)
b.left := tmp
tmp2 := TreeNode(4)
b.right := tmp2
tmp3 := TreeNode(6)
tmp2.left := tmp3
; msgBox Solution.isSameTree(a_head, b_head)
