写在最前
注：由于单版面容不下665道题，因此拆分，之后会单做一个目录。
**答案有误请私信告知，谢谢。
这是由Mono开展的第一个长期项目，会将Leetcode相关习题通过AHKv2实现，每道题会同步贴出相应Python代码。对一些Python程序员而言，可以通过比较，更快迁移到AHK这门语言上。
***引流：请喜欢Python的或是对于人工智能感兴趣的程序员关注我的另一个（大概）每周更新项目《Sinet库》，目前已经迁移了包括Numpy、Pandas和Sklearn在内的大量Python相关函数内容。
***引流2：目前新出一个长期项目，是关于Sinet库的数据类型的代码示例及解析，有兴趣的可以捧个人场。
更新至第五十题 2022.07.14 Mono
第四十一题 缺失的第一个正数
Given an unsorted integer array, find the first missing positive integer.
给定一个未排序的整数数组，查找第一个缺失的正整数。
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.Python
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
i = 0
while i < len(nums):
if 0 < nums[i] <= len(nums) and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
else:
i += 1
for i in xrange(0, len(nums)):
if nums[i] != i + 1:
return i + 1
return len(nums) + 1AutoHotkey
; 之前提供了一个简单的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 firstMissingPositive(nums)
{
i := 0
while i < nums.length
{
if 0 < nums[i + 1] && nums[i + 1] <= nums.length and nums[nums[i + 1]] != nums[i + 1]
{
tmp := nums[nums[i + 1]]
nums[nums[i + 1]] := nums[i + 1]
nums[i + 1] := tmp
}
else
i += 1
}
for i in xrange(nums.length)
if nums[i + 1] != i + 1
return i + 1
return nums.length + 1
}
}
; Check Solution
; msgBox Solution.firstMissingPositive([3,4,-1,1])第四十二题 接雨水
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
给定n个非负整数表示一个高程图，其中每个条的宽度为1，计算雨后它能够捕获多少水。
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.Python
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
ans = left = 0
right = len(height) - 1
leftWall = rightWall = float("-inf")
while left <= right:
if leftWall <= rightWall:
ans += max(0, leftWall - height[left])
leftWall = max(leftWall, height[left])
left += 1
else:
ans += max(0, rightWall - height[right])
rightWall = max(rightWall, height[right])
right -= 1
return ansAutoHotkey
class Solution
{
static trap(height)
{
ans := left := 0
right := height.length - 1
leftWall := rightWall := -0xffffffff
while left <= right
{
if leftWall <= rightWall
{
ans += max(0, leftWall - height[left + 1])
leftWall := max(leftWall, height[left + 1])
left += 1
}
else
{
ans += max(0, rightWall - height[right + 1])
rightWall := max(rightWall, height[right + 1])
right -= 1
}
}
return ans
}
}
; Check Solution
; msgBox Solution.trap([0,1,0,2,1,0,1,3,2,1,2,1])第四十三题 字符串乘法
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
给定以字符串表示的两个非负整数num1和num2，返回num1和num2的乘积。
Note:
The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
注：
num1和num2的长度均小于110。
num1和num2仅包含数字0-9。
num1和num2均不包含任何前导零。
您不得使用任何内置的BigInteger库或将输入直接转换为整数。Python
class Solution(object):
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
ans = [0] * (len(num1) + len(num2))
for i, n1 in enumerate(reversed(num1)):
for j, n2 in enumerate(reversed(num2)):
ans[i + j] += int(n1) * int(n2)
ans[i + j + 1] += ans[i + j] / 10
ans[i + j] %= 10
while len(ans) > 1 and ans[-1] == 0:
ans.pop()
return "".join(map(str, ans[::-1]))AutoHotkey
; 其实ahk的integer类型和str类型在大多数情况下可以等同
class Solution
{
static multiply(num1, num2)
{
; 还是经典的把字符串转array
num1 := StrSplit(num1, "")
num2 := StrSplit(num2, "")
ans := [0]
mutiple(ans, num1.length + num2.length)
for i, n1 in reversed(num1)
for j, n2 in reversed(num2)
{
ans[i + j - 1] += Integer(n1) * Integer(n2)
ans[i + j] += ans[i + j - 1] // 10
ans[i + j - 1] := mod(ans[i + j - 1], 10)
}
while ans.length > 1 and ans[-1] == 0
ans.pop()
ans := reversed(ans)
tmp := ""
for i in ans
tmp .= i
return tmp
}
}
; Check Solution
; msgBox Solution.multiply("123", "456")
; 为了便于操作数组，写了一个数组乘法的简单替代
mutiple(Lst, Number)
{
tmp := Lst.Clone()
Loop Number - 1
For i in tmp
{
Try
Lst.Push(i.Clone())
Catch
Lst.Push(i)
}
}
reversed(arr)
{
tmp := []
for i in arr
tmp.insertat(1, i)
return tmp
}第四十四题 通配符匹配
Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
实现通配符模式匹配，并支持“？”和“*”。
'?' 匹配任何单个字符。
“*”匹配任何字符序列（包括空序列）。
The matching should cover the entire input string (not partial).
匹配应该覆盖整个输入字符串（而不是部分）。
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") -> false
isMatch("aa","aa") -> true
isMatch("aaa","aa") -> false
isMatch("aa", "*") ->& true
isMatch("aa", "a*") -> true
isMatch("ab", "?*") -> true
isMatch("aab", "c*a*b") -> falsePython
class Solution(Object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
i = j = 0
lenS = len(s)
lenP = len(p)
lastMatchPos = 0
lastStarPos = -1
while i < len(s):
if j < lenP and p[j] in (s[i], "?"):
i += 1
j += 1
elif j < lenP and p[j] == "*":
lastMatchPos = i
lastStarPos = j
j += 1
elif lastStarPos > -1:
i = lastMatchPos + 1
lastMatchPos += 1
j = lastStarPos + 1
else:
return False
while j < lenP and p[j] == "*":
j += 1
return j == lenPAutoHotkey
class Solution
{
static isMatch(s, p)
{
s := StrSplit(s, "")
p := StrSplit(p, "")
i := j := 0
lenS := s.length
lenP := p.length
lastMatchPos := 0
lastStarPos := -1
while i < s.length
{
if j < lenP and (p[j + 1] == s[i + 1] || p[j + 1] == "?")
{
i += 1
j += 1
}
else if j < lenP and p[j + 1] == "*"
{
lastMatchPos := i
lastStarPos := j
j += 1
}
else if lastStarPos > -1
{
i := lastMatchPos + 1
lastMatchPos += 1
j := lastStarPos + 1
}
else
return False
}
while j < lenP and p[j + 1] == "*"
j += 1
return j == lenP
}
}
; Check Solution
; msgBox Solution.isMatch("ab", "?*")第四十五题 跳跃游戏 II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
给定一个非负整数数组，您最初位于该数组的第一个索引处。
数组中的每个元素表示该位置的最大跳跃长度。
你的目标是以最少的跳跃次数达到最后一个索引。
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note:
You can assume that you can always reach the last index.
注：您可以假设始终可以到达最后一个索引。Python
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
pos = 0
ans = 0
bound = len(nums)
while pos < len(nums) - 1:
dis = nums[pos]
farthest = posToFarthest = 0
for i in xrange(pos + 1, min(pos + dis + 1, bound)):
canReach = i + nums[i]
if i == len(nums) - 1:
return ans + 1
if canReach > farthest:
farthest = canReach
posToFarthest = i
ans += 1
pos = posToFarthest
return ansAutoHotkey
; 之前提供了一个简单的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 jump(nums)
{
pos := 0
ans := 0
bound := nums.length
while pos < nums.length - 1
{
dis := nums[pos + 1]
farthest := posToFarthest := 0
for i in xrange(min(pos + dis + 1, bound) - pos - 1)
{
i += pos + 1
canReach := i + nums[i + 1]
if i == nums.length - 1
return ans + 1
if canReach > farthest
{
farthest := canReach
posToFarthest := i
}
}
ans += 1
pos := posToFarthest
}
return ans
}
}
; Check Solution
; msgBox Solution.jump([2,3,1,1,4])第四十六题 全排列
Given a collection of distinct numbers, return all possible permutations.
给定一组不同的数字，返回所有可能的排列。
For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]Python
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
visited = set([])
def dfs(nums, path, res, visited):
if len(path) == len(nums):
res.append(path + [])
return
for i in xrange(0, len(nums)):
# if i > 0 and nums[i - 1] == nums[i]:
# continue
if i not in visited:
visited.add(i)
path.append(nums[i])
dfs(nums, path, res, visited)
path.pop()
visited.discard(i)
dfs(nums, [], res, visited)
return resAutoHotkey
; 之前提供了一个简单的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
}
}
}
; ahk没有集合。这里写个简单版本，Sinet库里有完整版本的。
class set extends array
{
__New(param)
{
for i in param
{
if !inarr(i, this)
this.push(i)
}
}
add(element)
{
if !inarr(element, this)
this.push(element)
}
discard(element)
{
for i in this
{
if i == element
{
this.removeat(A_Index)
break
}
}
}
}
class Solution
{
static permute(nums)
{
res := []
visited := set([])
static dfs(nums, path, res, visited)
{
if path.length == nums.length
{
tmp := path.clone()
tmp.push("")
res.push(tmp)
return
}
for i in xrange(nums.length)
{
if !inarr(i, visited)
{
visited.add(i)
path.push(nums[i + 1])
dfs(nums, path, res, visited)
path.pop()
visited.discard(i)
}
}
}
dfs(nums, [], res, visited)
for i in res
i.pop()
return res
}
}
; Check Solution
; print Solution.permute([1,2,3])
inarr(element, arr)
{
flag := 0
for i in arr
{
if element == i
flag := 1
}
return flag
}
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 a collection of numbers that might contain duplicates, return all possible unique permutations.
给定可能包含重复项的数字集合，返回所有可能的唯一置换。
For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]Python
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
nums.sort()
def dfs(nums, res, path, visited):
if len(path) == len(nums):
res.append(path + [])
return
for i in range(len(nums)):
if i in visited:
continue
if i > 0 and nums[i] == nums[i - 1] and i - 1 not in visited:
continue
visited |= {i}
path.append(nums[i])
dfs(nums, res, path, visited)
path.pop()
visited -= {i}
dfs(nums, res, [], set())
return resAutoHotkey
; 之前提供了一个简单的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
}
}
}
; ahk没有集合。这里写个简单版本，Sinet库里有完整版本的。
class set extends array
{
__New(param)
{
for i in param
{
if !inarr(i, this)
this.push(i)
}
}
add(element)
{
if !inarr(element, this)
this.push(element)
}
discard(element)
{
for i in this
{
if i == element
{
this.removeat(A_Index)
break
}
}
}
}
class Solution
{
static permuteUnique(nums)
{
res := []
; sort的替代
for i in xrange(nums.length)
{
for j in xrange(nums.length - i - 1)
{
j += i + 1
if nums[i + 1] > nums[j + 1]
{
tmp := nums[i + 1]
nums[i + 1] := nums[j + 1]
nums[j + 1] := tmp
}
}
}
static dfs(nums, res, path, visited)
{
if path.length == nums.length
{
tmp := path.clone()
tmp.push("")
res.push(tmp)
return
}
for i in xrange(nums.length)
{
if inarr(i, visited)
continue
if i > 0 and nums[i + 1] == nums[i] and !inarr(i - 1, visited)
continue
visited.add(i)
path.push(nums[i + 1])
dfs(nums, res, path, visited)
path.pop()
visited.discard(i)
}
}
dfs(nums, res, [], set([]))
for i in res
i.pop()
return res
}
}
; Check Solution
; print Solution.permuteUnique([1,1,2])
inarr(element, arr)
{
flag := 0
for i in arr
{
if element == i
flag := 1
}
return flag
}
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
}第四十八题 旋转图像
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
您将获得一个表示图像的n x n 2D矩阵。
将图像旋转90度（顺时针）。
注：
您必须在适当的位置旋转图像，这意味着您必须直接修改输入2D矩阵。
不要分配另一个2D矩阵并进行旋转。
Example 1:
Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Example 2:
Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]Python
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
if len(matrix) == 0:
return
h = len(matrix)
w = len(matrix[0])
for i in xrange(0, h):
for j in xrange(0, w/2):
matrix[i][j], matrix[i][w - j - 1] = matrix[i][w - j - 1], matrix[i][j]
for i in xrange(0, h):
for j in xrange(0, w - 1 - i):
matrix[i][j], matrix[w - 1 - j][h - 1 - i] = matrix[w - 1 - j][h - 1 - i], matrix[i][j]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 rotate(matrix)
{
if matrix.length == 0
return
h := matrix.length
w := matrix[1].length
for i in xrange(h)
{
for j in xrange(w // 2)
{
tmp := matrix[i + 1][j + 1]
matrix[i + 1][j + 1] := matrix[i + 1][w - j]
matrix[i + 1][w - j] := tmp
}
}
for i in xrange(h)
{
for j in xrange(w - 1 - i)
{
tmp := matrix[i + 1][j + 1]
matrix[i + 1][j + 1] := matrix[w - j][h - i]
matrix[w - j][h - i] := tmp
}
}
}
}
; Check Solution
; cuba := [[1,2,3],
; [4,5,6],
; [7,8,9]]
; Solution.rotate(cuba)
; print cuba
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 array of strings, group anagrams together.
给定一个字符串数组，将字谜组合在一起。
For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:
[
["ate", "eat","tea"],
["nat","tan"],
["bat"]
]
Note: All inputs will be in lower-case.
注：所有输入均为小写。Python
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
def hash(count):
p1, p2 = 2903, 29947
ret = 0
for c in count:
ret = ret * p1 + c
p1 *= p2
return ret
d = {}
for str in strs:
count = [0] * 26
for c in str:
count[ord(c) - ord('a')] += 1
key = hash(count)
if key not in d:
d[key] = [str]
else:
d[key].append(str)
return [d[k] for k in d]AutoHotkey
class Solution
{
static groupAnagrams(strs)
{
static hash(count)
{
p1 := 2903
p2 := 29947
ret := 0
for c in count
{
ret := ret * p1 + c
p1 *= p2
}
return ret
}
d := map()
for str in strs
{
str := StrSplit(str, "")
count := [0]
mutiple(count, 26)
for c in str
count[ord(c) - ord('a') + 1] += 1
key := hash(count)
if !d.has(key)
d[key] := [str]
else
d[key].push(str)
}
tmp := []
for k in d
{
tmp2 := []
for i in d[k]
{
tmp3 := ""
loop i.length
tmp3 .= i[A_Index]
tmp2.push(tmp3)
}
tmp.push(tmp2)
}
return tmp
}
}
; Check Solution
; print Solution.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
; 为了便于操作数组，写了一个数组乘法的简单替代
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
}第五十题 幂运算
Implement pow(x, n).
实现幂运算Python
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n < 0:
n = -n
x = 1 / x
ans = 1
while n:
if n & 1:
ans *= x
x *= x
n >>= 1
return ansAutoHotkey
class Solution
{
static myPow(x, n)
{
if n < 0
{
n := -n
x := 1 / x
}
ans := 1
while n
{
if n & 1
ans *= x
x *= x
n >>= 1
}
return ans
}
}
; Check Solution
; msgBox Solution.myPow(20, 5)
