写在最前
注：由于单版面容不下665道题，因此拆分，之后会单做一个目录。
**答案有误请私信告知，谢谢。
这是由Mono开展的第一个长期项目，会将Leetcode相关习题通过AHKv2实现，每道题会同步贴出相应Python代码。对一些Python程序员而言，可以通过比较，更快迁移到AHK这门语言上。
***引流：请喜欢Python的或是对于人工智能感兴趣的程序员关注我的另一个（大概）每周更新项目《Sinet库》，目前已经迁移了包括Numpy、Pandas和Sklearn在内的大量Python相关函数内容。
***引流2：目前新出一个长期项目，是关于Sinet库的数据类型的代码示例及解析，有兴趣的可以捧个人场。
***引流3：目前新出一个长期项目，是利用Numahk库进行人工智能机器学习模块的示例教学。
更新至第八十题 2022.07.25 Mono
第七十一题 简化路径
Given an absolute path for a file (Unix-style), simplify it.
给定文件的绝对路径（Unix样式），将其简化。
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"Python
class Solution(object):
def simplifyPath(self, path):
"""
:type path: str
:rtype: str
"""
path = path.split("/")
stack = []
for p in path:
if p in ["", "."]:
continue
if p == "..":
if stack:
stack.pop()
else:
stack.append(p)
return "/" + "/".join(stack)AutoHotkey
class Solution
{
static simplifyPath(path)
{
path := StrSplit(path, "/")
stack := []
for p in path
{
if inarr(p, ["", "."])
continue
if p == ".."
{
if stack
stack.pop()
}
else
stack.push(p)
}
tmp := ""
for i in stack
{
if !tmp
tmp := i
else
tmp .= "/" . i
}
return "/" . tmp
}
}
; Check SOlution
; msgBox Solution.simplifyPath("/a/./b/../../c/")
; 这里提供了一个简单的in关键字替换方案，Sinet库中的Sinet.In函数更强大
inarr(str, arr)
{
flag := 0
for i in arr
if str == i
flag := 1
return flag
}第七十二题 编辑距离
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
给定两个单词word1和word2，找出将word1转换为word2所需的最小步骤数。（每个操作计为一个步骤。）
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
您可以对一个字进行以下3种操作：
a） 插入字符
b） 删除字符
c） 替换字符Python
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
if len(word1) == 0 or len(word2) == 0:
return max(len(word1), len(word2))
dp = [[0] * (len(word2) + 1) for _ in xrange(0, len(word1) + 1)]
dp[0][0] = 0
for i in xrange(0, len(word1) + 1):
for j in xrange(0, len(word2) + 1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
else:
cond1 = dp[i][j - 1] + 1
cond2 = dp[i - 1][j] + 1
cond3 = 0
if word1[i - 1] == word2[j - 1]:
cond3 = dp[i - 1][j - 1]
else:
cond3 = dp[i - 1][j - 1] + 1
dp[i][j] = min(cond1, cond2, cond3)
return dp[-1][-1]AutoHotkey
; 之前提供了一个简单的xrange，这次用一个迭代器对象
; 优化执行代码，Sinet库中迭代方式已全面更换成这个
class xrange
{
__New(length)
{
this.looptimes := length
}
__Enum(num)
{
index := this.looptimes
return Fn
Fn(&a)
{
a := this.looptimes - index
return index-- > 0
}
}
}
class Solution
{
static minDistance(word1, word2)
{
if strlen(word1) == 0 or strlen(word2) == 0
return max(strlen(word1), strlen(word2))
dp := [0]
mutiple(dp, strlen(word2) + 1)
dp := [dp.Clone()]
mutiple(dp, strlen(word1) + 1)
dp[1][1] := 0
word1 := StrSplit(word1, "")
word2 := StrSplit(word2, "")
for i in xrange(word1.Length + 1)
{
for j in xrange(word2.Length + 1)
{
if i == 0
dp[i + 1][j + 1] := j
else if j == 0
dp[i + 1][j + 1] := i
else
{
cond1 := dp[i + 1][j] + 1
cond2 := dp[i][j + 1] + 1
cond3 := 0
if word1[i] == word2[j]
cond3 := dp[i][j]
else
cond3 := dp[i][j] + 1
dp[i + 1][j + 1] := min(cond1, cond2, cond3)
}
}
}
return dp[-1][-1]
}
}
; Check Solution
; msgBox SOlution.minDistance("horse", "ros")
; msgBox SOlution.minDistance("intention", "execution")
; 为了便于操作数组，写了一个数组乘法的简单替代
mutiple(Lst, Number)
{
tmp := Lst.Clone()
Loop Number - 1
For i in tmp
{
Try
Lst.Push(i.Clone())
Catch
Lst.Push(i)
}
}第七十三题 矩阵置零
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
给定一个m x n矩阵，如果一个元素为0，则将其整行和整列设置为0。就地执行。Python
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
colZeroFlag = False
for i in xrange(0, len(matrix)):
if matrix[i][0] == 0:
colZeroFlag = True
for j in xrange(1, len(matrix[0])):
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] = 0
for i in reversed(xrange(0, len(matrix))):
for j in reversed(xrange(1, len(matrix[0]))):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if colZeroFlag:
matrix[i][0] = 0AutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static setZeroes(matrix)
{
colZeroFlag := False
for i in range(0, matrix.Length)
{
if matrix[i + 1][1] == 0
colZeroFlag := True
for j in range(1, matrix[1].Length)
{
if matrix[i + 1][j + 1] == 0
matrix[i + 1][1] := matrix[1][j + 1] := 0
}
}
for i in reversed(range(0, matrix.Length))
{
for j in reversed(range(1, matrix[1].Length))
{
if matrix[i + 1][1] == 0 or matrix[1][j + 1] == 0
matrix[i + 1][j + 1] := 0
}
if colZeroFlag
matrix[i + 1][1] := 0
}
}
}
; ChecK SOlution
; matrix := [[1,1,1],
; [1,0,1],
; [1,1,1]]
; Solution.setZeroes(matrix)
; print matrix
reversed(arr)
{
tmp := []
for i in arr
tmp.insertat(1, i)
return tmp
}
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
}第七十四题 搜索二维矩阵
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
编写一个有效的算法，搜索m x n矩阵中的值。该矩阵具有以下属性：
每行中的整数从左到右排序。
每行的第一个整数大于前一行的最后一个整数。
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.Python
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
m = len(matrix)
n = len(matrix[0])
start, end = 0, m * n - 1
while start + 1 < end:
mid = start + (end - start) / 2
if matrix[mid/n][mid%n] > target:
end = mid
elif matrix[mid/n][mid%n] < target:
start = mid
else:
return True
if matrix[start/n][start%n] == target:
return True
if matrix[end/n][end%n] == target:
return True
return FalseAutoHotkey
class Solution
{
static searchMatrix(matrix, target)
{
if matrix.Length == 0 or matrix[1].Length == 0
return False
m := matrix.Length
n := matrix[1].Length
start := 0
end := m * n - 1
while start + 1 < end
{
mid := start + (end - start) // 2
if matrix[mid // n + 1][mod(mid, n) + 1] > target
end := mid
else if matrix[mid // n + 1][mod(mid, n) + 1] < target
start := mid
else
return True
}
if matrix[start // n + 1][mod(start, n) + 1] == target
return True
if matrix[end // n + 1][mod(end, n) + 1] == target
return True
return False
}
}
; Check Solution
; matrix := [[1, 3, 5, 7],
; [10, 11, 16, 20],
; [23, 30, 34, 50]]
; msgBox SOlution.searchMatrix(matrix, 3)第七十五题 颜色分类
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
给定一个包含n个红色、白色或蓝色对象的数组，对其进行排序
使相同颜色的对象相邻，颜色顺序为红色、白色和蓝色。
在这里，我们将使用整数0、1和2分别表示红色、白色和蓝色。
Note:
You are not suppose to use the library's sort function for this problem.
注：您不应该使用库的排序函数来解决这个问题。Python
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
x = y = z = -1
for i in xrange(0, len(nums)):
if nums[i] == 0:
x += 1
y += 1
z += 1
if z != -1:
nums[z] = 2
if y != -1:
nums[y] = 1
nums[x] = 0
elif nums[i] == 1:
y += 1
z += 1
nums[z] = 2
if x != -1:
nums[x] = 0
if y != -1:
nums[y] = 1
elif nums[i] == 2:
z += 1
if y != -1:
nums[y] = 1
if x != -1:
nums[x] = 0
nums[z] = 2AutoHotkey
; 之前提供了一个简单的xrange，这次用一个迭代器对象
; 优化执行代码，Sinet库中迭代方式已全面更换成这个
class xrange
{
__New(length)
{
this.looptimes := length
}
__Enum(num)
{
index := this.looptimes
return Fn
Fn(&a)
{
a := this.looptimes - index
return index-- > 0
}
}
}
class Solution
{
static sortColors(nums)
{
x := y := z := -1
for i in xrange(nums.Length)
{
if nums[i + 1] == 0
{
x += 1
y += 1
z += 1
if z != -1
nums[z + 1] := 2
if y != -1
nums[y + 1] := 1
nums[x + 1] := 0
}
else if nums[i + 1] == 1
{
y += 1
z += 1
nums[z + 1] := 2
if x != -1
nums[x + 1] := 0
if y != -1
nums[y + 1] := 1
}
else if nums[i + 1] == 2
{
z += 1
if y != -1
nums[y + 1] := 1
if x != -1
nums[x + 1] := 0
nums[z + 1] := 2
}
}
}
}
; Check Solution
; color := [2,0,2,1,1,0]
; Solution.sortColors(color)
; print color
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 string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
给定一个字符串S和一个字符串T，在S中找到最小窗口，该窗口将包含T中的所有字符。
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
Note:
If there is no such window in S that covers all characters in T, return the empty string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
注：
如果S中没有覆盖T中所有字符的窗口，则返回空字符串“”。
如果有多个这样的窗口，则可以保证在S中始终只有一个唯一的最小窗口。
Python
class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
score = 0
wanted = collections.Counter(t)
start, end = len(s), 3 * len(s)
d = {}
deq = collections.deque([])
for i, c in enumerate(s):
if c in wanted:
deq.append(i)
d[c] = d.get(c, 0) + 1
if d[c] <= wanted[c]:
score += 1
while deq and d[s[deq[0]]] > wanted[s[deq[0]]]:
d[s[deq.popleft()]] -= 1
if score == len(t) and deq[-1] - deq[0] < end - start:
start, end = deq[0], deq[-1]
return s[start:end + 1]AutoHotkey
; 这里提供简单的collections替代
; Counter类型在Sinet库中有较为完整替代替代的版本
class collections
{
class Counter Extends Map
{
__New(Object := "Null")
{
if Object == "Null"
Return
if Type(Object) == "Integer" || Type(Object) == "Float" || Type(Object) == "String"
{
Object := String(Object)
Lst_Object := StrSplit(Object, "")
Loop Lst_Object.Length
{
Key := Lst_Object[A_Index]
if Super.Has(Key)
Super[Key]++
else
Super[Key] := 1
}
}
}
}
class Deque Extends Array
{
__New(Object)
{
if Type(Object) == "Array"
Super.Push(Object*)
else
Super.Push(Object)
}
append(Object)
{
Super.Push(Object)
}
popleft()
{
Return Super.RemoveAt(1)
}
}
}
class Solution
{
static minWindow(s, t)
{
score := 0
wanted := collections.Counter(t)
start := strlen(s)
end := 3 * strlen(s)
d := map()
deq := collections.deque([])
; 转换为array类型
s := StrSplit(s, "")
for i, c in s
{
if wanted.has(C)
{
deq.append(i)
d[c] := d.get(c, 0) + 1
if d[c] <= wanted[c]
score += 1
while deq and d[s[deq[1]]] > wanted[s[deq[1]]]
d[s[deq.popleft()]] -= 1
if score == strlen(t) and deq[-1] - deq[1] < end - start
{
start := deq[1]
end := deq[-1]
}
}
}
tmp := ""
loop end - start + 1
; 注意这里是由于deq里存储的数值为正常值，使得需要-1
tmp .= s[A_Index + start - 1]
return tmp
}
}
; Check Solution
; S := "ADOBECODEBANC"
; T := "ABC"
; msgBox Solution.minWindow(S, T)第七十七题 组合
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
给定两个整数n和k，返回1…n中k个数的所有可能组合。
For example,
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]Python
class Solution(object):
def combine(self, n, k):
if k==1:
return [[i] for i in range(1,n+1)]
elif k==n:
return [[i for i in range(1,n+1)]]
else:
rs = []
rs += self.combine(n-1,k)
part = self.combine(n-1,k-1)
for ls in part:
ls.append(n)
rs += part
return rsAutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static combine(n, k)
{
if k==1
{
tmp := []
for i in range(1,n+1)
tmp.push([i])
return tmp
}
else if k==n
{
tmp := []
for i in range(1,n+1)
tmp.push(i)
return [tmp]
}
else
{
rs := this.combine(n-1,k)
part := this.combine(n-1,k-1)
for ls in part
ls.push(n)
for i in part
rs.push(i)
return rs
}
}
}
; Check Solution
; print Solution.combine(4,2)
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 set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
给定一组不同的整数NUM，返回所有可能的子集。
注意：解决方案集不得包含重复子集。
For example,
If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]Python
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
def dfs(nums, index, path, ans):
ans.append(path)
[dfs(nums, i + 1, path + [nums[i]], ans) for i in xrange(index, len(nums))]
ans = []
dfs(nums, 0, [], ans)
return ansAutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static subsets(nums)
{
dfs(nums, index, path, ans)
{
ans.push(path)
tmp := []
for i in range(index, nums.Length)
{
tmp2 := path.Clone()
tmp2.push(nums[i + 1])
tmp.push(dfs(nums, i + 1, tmp2, ans))
}
}
ans := []
dfs(nums, 0, [], ans)
return ans
}
}
; Check Solution
; print Solution.subsets([1,2,3])
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 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
给定一个2D板和一个单词，查找该单词是否存在于网格中。
单词可以由连续相邻单元的字母构成，其中“相邻”单元是指水平或垂直相邻的单元。
同一个字母单元格不能使用多次。
For example,
Given board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.Python
class Solution:
# @param board, a list of lists of 1 length string
# @param word, a string
# @return a boolean
def exist(self, board, word):
# write your code here
if word == "":
return True
if len(board) == 0:
return False
visited = [[0] * len(board[0]) for i in xrange(0, len(board))]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def dfs(i, j, board, visited, word, index):
if word[index] != board[i][j]:
return False
if len(word) - 1 == index:
return True
for direction in directions:
ni, nj = i + direction[0], j + direction[1]
if ni >= 0 and ni < len(board) and nj >= 0 and nj < len(board[0]):
if visited[ni][nj] == 0:
visited[ni][nj] = 1
if dfs(ni, nj, board, visited, word, index + 1):
return True
visited[ni][nj] = 0
return False
for i in xrange(0, len(board)):
for j in xrange(0, len(board[0])):
visited[i][j] = 1
if dfs(i, j, board, visited, word, 0):
return True
visited[i][j] = 0
return FalseAutoHotkey
; 之前提供了一个简单的xrange，这次用一个迭代器对象
; 优化执行代码，Sinet库中迭代方式已全面更换成这个
class xrange
{
__New(length)
{
this.looptimes := length
}
__Enum(num)
{
index := this.looptimes
return Fn
Fn(&a)
{
a := this.looptimes - index
return index-- > 0
}
}
}
class Solution
{
static exist(board, word)
{
if word == ""
return True
if board.Length == 0
return False
visited := [0]
mutiple(visited, board[1].Length)
visited := [visited.Clone()]
mutiple(visited, board.Length)
directions := [[-1, 0], [1, 0], [0, -1], [0, 1]]
word := StrSplit(word, "")
dfs(i, j, board, visited, word, index)
{
if word[index + 1] != board[i + 1][j + 1]
return False
if word.Length - 1 == index
return True
for direction in directions
{
ni := i + direction[1]
nj := j + direction[2]
if ni >= 0 and ni < board.Length and nj >= 0 and nj < board[1].Length
{
if visited[ni + 1][nj + 1] == 0
{
visited[ni + 1][nj + 1] := 1
if dfs(ni, nj, board, visited, word, index + 1)
return True
visited[ni + 1][nj + 1] := 0
}
}
}
return False
}
for i in xrange(board.Length)
{
for j in xrange(board[1].Length)
{
visited[i + 1][j + 1] := 1
if dfs(i, j, board, visited, word, 0)
return True
visited[i + 1][j + 1] := 0
}
}
return False
}
}
; Check Solution
; board :=
; [
; ['A','B','C','E'],
; ['S','F','C','S'],
; ['A','D','E','E']
; ]
; msgBox Solution.exist(board, "ABCCED")
; msgBox Solution.exist(board, "ABCB")
; 为了便于操作数组，写了一个数组乘法的简单替代
mutiple(Lst, Number)
{
tmp := Lst.Clone()
Loop Number - 1
For i in tmp
{
Try
Lst.Push(i.Clone())
Catch
Lst.Push(i)
}
}第八十题 删除有序数组中的重复项 II
Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
跟进“删除重复项”：
如果最多允许重复两次怎么办？
For example,
Given sorted array nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.
你的函数应该返回length=5，nums的前五个元素是1、1、2、2和3。在新的长度之外剩下什么无关紧要。Python
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 2:
return len(nums)
cnt = 0
j = 1
for i in xrange(1, len(nums)):
if nums[i] == nums[i - 1]:
cnt += 1
if cnt < 2:
nums[j] = nums[i]
j += 1
else:
nums[j] = nums[i]
j += 1
cnt = 0
return jAutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static removeDuplicates(nums)
{
if nums.Length <= 2
return nums.Length
cnt := 0
j := 1
for i in range(1, nums.Length)
{
if nums[i + 1] == nums[i]
{
cnt += 1
if cnt < 2
{
nums[j + 1] := nums[i + 1]
j += 1
}
}
else
{
nums[j + 1] := nums[i + 1]
j += 1
cnt := 0
}
}
return j
}
}
; Check Solution
; msgBox Solution.removeDuplicates([1,1,1,2,2,3])
