写在最前
注：由于单版面容不下665道题，因此拆分，之后会单做一个目录。
**答案有误请私信告知，谢谢。
这是由Mono开展的第一个长期项目，会将Leetcode相关习题通过AHKv2实现，每道题会同步贴出相应Python代码。对一些Python程序员而言，可以通过比较，更快迁移到AHK这门语言上。
***引流：请喜欢Python的或是对于人工智能感兴趣的程序员关注我的另一个（大概）每周更新项目《Sinet库》，目前已经迁移了包括Numpy、Pandas和Sklearn在内的大量Python相关函数内容。
***引流2：目前新出一个长期项目，是关于Sinet库的数据类型的代码示例及解析，有兴趣的可以捧个人场。
更新至第六十题 2022.07.15 Mono
第五十一题 N皇后
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
n皇后难题是将n个皇后放置在一个n×n棋盘上，使得没有两个皇后相互攻击的问题。
给定整数n，返回n皇后难题的所有不同解。
每个解决方案都包含一个不同的n皇后布局板配置，其中“Q”和“.”两者分别表示女王和空白。
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]Python
class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
ans = []
def dfs(path, n, ans):
if len(path) == n:
ans.append(drawChess(path))
return
for i in range(n):
if i not in path and isValidQueen(path, i):
path.append(i)
dfs(path, n, ans)
path.pop()
def isValidQueen(path, k):
for i in range(len(path)):
if abs(k - path[i]) == abs(len(path) - i):
return False
return True
def drawChess(path):
ret = []
chess = [["."] * len(path) for _ in range(len(path))]
for i in range(0, len(path)):
chess[i][path[i]] = "Q"
for chs in chess:
ret.append("".join(chs))
return ret
dfs([], n, ans)
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 solveNQueens(n)
{
ans := []
static dfs(path, n, ans)
{
if path.length == n
{
ans.push(drawChess(path))
return
}
for i in xrange(n)
{
if !inarr(i, path) and isValidQueen(path, i)
{
path.push(i)
dfs(path, n, ans)
path.pop()
}
}
}
static isValidQueen(path, k)
{
for i in xrange(path.length)
if abs(k - path[i + 1]) == abs(path.length - i)
return False
return True
}
static drawChess(path)
{
ret := []
tmp := ["."]
mutiple(tmp, path.length)
chess := [tmp.Clone()]
mutiple(chess, path.length)
for i in xrange(path.length)
chess[i + 1][path[i + 1] + 1] := "Q"
for chs in chess
{
tmp := ""
for i in chs
tmp .= i
ret.push(tmp)
}
return ret
}
dfs([], n, ans)
return ans
}
}
; Check Solution
; print Solution.solveNQueens(4)
; 为了便于操作数组，写了一个数组乘法的简单替代
mutiple(Lst, Number)
{
tmp := Lst.Clone()
Loop Number - 1
For i in tmp
{
Try
Lst.Push(i.Clone())
Catch
Lst.Push(i)
}
}
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
}第五十二题 N皇后 II （含DFS算法）
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
跟N皇后问题相关。
现在，返回不同解决方案的总数，而不是输出配置方案。Python
class Solution(object):
def totalNQueens(self, n):
"""
:type n: int
:rtype: int
"""
def dfs(path, n):
if len(path) == n:
return 1
res = 0
for i in range(n):
if i not in path and isValidQueen(path, i):
path.append(i)
res += dfs(path, n)
path.pop()
return res
def isValidQueen(path, k):
for i in range(len(path)):
if abs(k - path[i]) == abs(len(path) - i):
return False
return True
return dfs([], n)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 totalNQueens(n)
{
static dfs(path, n)
{
if path.length == n
return 1
res := 0
for i in xrange(n)
{
if !inarr(i, path) and isValidQueen(path, i)
{
path.push(i)
res += dfs(path, n)
path.pop()
}
}
return res
}
static isValidQueen(path, k)
{
for i in xrange(path.length)
{
if abs(k - path[i + 1]) == abs(path.length - i)
return False
}
return True
}
return dfs([], n)
}
}
; Check Solution
msgBox Solution.totalNQueens(4)
inarr(element, arr)
{
flag := 0
for i in arr
{
if element == i
flag := 1
}
return flag
}第五十三题 最大子序和
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
在一个数组（至少包含一个数字）中查找和最大的连续子数组。
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
如果您已经找到了O(n)解，请尝试使用分而治之的方法编写另一个解，这更微妙。Python
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
preSum = maxSum = nums[0]
for i in xrange(1, len(nums)):
preSum = max(preSum + nums[i], nums[i])
maxSum = max(maxSum, preSum)
return maxSumAutoHotkey
; 之前提供了一个简单的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 maxSubArray(nums)
{
if nums.length == 0
return 0
preSum := maxSum := nums[1]
for i in xrange(nums.length - 1)
{
i += 1
preSum := max(preSum + nums[i + 1], nums[i + 1])
maxSum := max(maxSum, preSum)
}
return maxSum
}
}
; Check Solution
; msgBox Solution.maxSubArray([-2,1,-3,4,-1,2,1,-5,4])第五十四题 螺旋矩阵
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
给定一个由m x n个元素（m行，n列）组成的矩阵，按螺旋顺序返回矩阵的所有元素。
For example,
Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].Python
class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if len(matrix) == 0 or len(matrix[0]) == 0:
return []
ans = []
left, up, down, right = 0, 0, len(matrix) - 1, len(matrix[0]) - 1
while left <= right and up <= down:
for i in range(left, right + 1):
ans += matrix[up][i],
up += 1
for i in range(up, down + 1):
ans += matrix[i][right],
right -= 1
for i in reversed(range(left, right + 1)):
ans += matrix[down][i],
down -= 1
for i in reversed(range(up, down + 1)):
ans += matrix[i][left],
left += 1
return ans[:(len(matrix) * len(matrix[0]))]AutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static spiralOrder(matrix)
{
if matrix.length == 0 or matrix[1].length == 0
return []
ans := []
left := up := 0
down := matrix.length - 1
right := matrix[1].length - 1
while left <= right and up <= down
{
for i in range(left, right + 1)
ans.push(matrix[up + 1][i + 1])
up += 1
for i in range(up, down + 1)
ans.push(matrix[i + 1][right + 1])
right -= 1
for i in reversed(range(left, right + 1))
ans.push(matrix[down + 1][i + 1])
down -= 1
for i in reversed(range(up, down + 1))
ans.push(matrix[i + 1][left + 1])
left += 1
}
tmp := []
for i in range(0, matrix.length * matrix[1].length)
tmp.push(ans[i + 1])
return tmp
}
}
; Check Solution
; matrix := [[ 1, 2, 3 ],
; [ 4, 5, 6 ],
; [ 7, 8, 9 ]]
; print Solution.spiralOrder(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
}第五十五题 跳跃游戏
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.
Determine if you are able to reach the last index.
给定一个非负整数数组，您最初位于该数组的第一个索引处。
数组中的每个元素表示该位置的最大跳跃长度。
确定您是否能够达到最后一个索引。
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.Python
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
pos = 0
bound = len(nums)
while pos < len(nums) - 1:
dis = nums[pos]
if dis == 0:
return False
farthest = posToFarthest = 0
for i in xrange(pos + 1, min(pos + dis + 1, bound)):
canReach = i + nums[i]
if i == len(nums) - 1:
return True
if canReach > farthest:
farthest = canReach
posToFarthest = i
pos = posToFarthest
return True if pos >= len(nums) - 1 else 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 canJump(nums)
{
pos := 0
bound := nums.length
while pos < nums.length - 1
{
dis := nums[pos + 1]
if dis == 0
return False
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 True
if canReach > farthest
{
farthest := canReach
posToFarthest := i
}
}
pos := posToFarthest
}
return pos >= nums.length - 1
}
}
; Check Solution
; msgBox Solution.canJump([2,3,1,1,4])
; msgBox Solution.canJump([3,2,1,0,4])第五十六题 合并区间
Given a collection of intervals, merge all overlapping intervals.
给定一组区间，合并所有重叠区间。
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].Python
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
ans = []
for intv in sorted(intervals, key=lambda x:x.start):
if ans and ans[-1].end >= intv.start:
ans[-1].end = max(ans[-1].end, intv.end)
else:
ans.append(intv)
return ansAutoHotkey
class Interval
{
__New(s := 0, e := 0)
{
this.start := s
this.end := e
}
}
class Solution
{
static merge(intervals)
{
ans := []
; 替换sorted
loop intervals.length
{
index := A_Index
loop intervals.length - index
{
if intervals[index].start > intervals[A_Index + index].start
{
tmp := intervals[index]
intervals[index] := intervals[A_Index]
intervals[A_Index] := tmp
}
}
}
for intv in intervals
{
if ans.length and ans[-1].end >= intv.start
ans[-1].end := max(ans[-1].end, intv.end)
else
ans.push(intv)
}
return ans
}
}
; Check Solution
; intervals := []
; arr := [[1,3],[2,6],[8,10],[15,18]]
; for i in arr
; intervals.push(Interval(i*))
; print Solution.merge(intervals)
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) == "Interval"
{
Print_Text .= "["
Print_Text .= Text.start ","
Print_Text .= Text.end
Print_Text .= "]"
}
else
Print_Text .= Text
Return Print_Text
}第五十七题 插入区间
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
给定一组不重叠的区间，在区间中插入一个新区间（必要时合并）。
您可以假设间隔最初是根据其开始时间排序的。
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].Python
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution(object):
def insert(self, intervals, newInterval):
"""
:type intervals: List[Interval]
:type newInterval: Interval
:rtype: List[Interval]
"""
s, e = newInterval.start, newInterval.end
left = filter(lambda x:x.end < newInterval.start, intervals)
right = filter(lambda x:x.start > newInterval.end, intervals)
if left + right != intervals:
s = min(intervals[len(left)].start, s)
e = max(intervals[~len(right)].end, e)
return left + [Interval(s, e)] + rightAutoHotkey
class Interval
{
__New(s := 0, e := 0)
{
this.start := s
this.end := e
}
}
class Solution
{
static insert(intervals, newInterval)
{
s := newInterval.start
e := newInterval.end
; 替代filter函数
left := []
right := []
for i in intervals
{
if i.end < newInterval.start
left.push(i)
if i.start > newInterval.end
right.push(i)
}
tmp := []
for i in left
tmp.push(i)
for j in right
tmp.push(j)
flag := 1
for k in intervals
{
if !inarr(k, tmp)
{
flag := 0
break
}
}
if !flag
{
s := min(intervals[left.length + 1].start, s)
e := max(intervals[intervals.length - right.length].end, e)
}
tmp := left.Clone()
tmp.push(Interval(s, e))
tmp.push(right.Clone())
return tmp
}
}
; Check Solution
; intervals := []
; arr := [[1,2],[3,5],[6,7],[8,10],[12,16]]
; for i in arr
; intervals.push(Interval(i*))
; print Solution.insert(intervals, Interval(4,9))
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 if Type(Text) == "Interval"
{
Print_Text .= "["
Print_Text .= Text.start ","
Print_Text .= Text.end
Print_Text .= "]"
}
else
Print_Text .= Text
Return Print_Text
}第五十八题 最后一个单词的长度
Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
假设字符串s由大写/小写字母和空格字符“”组成，则返回字符串中最后一个单词的长度。
如果最后一个单词不存在，则返回0。
注：单词定义为仅由非空格字符组成的字符序列。
For example,
Given s = "Hello World",
return 5.Python
class Solution(object):
def lengthOfLastWord(self, s):
"""
:type s: str
:rtype: int
"""
if len(s) == 0:
return 0
s = s.split()
if len(s) > 0:
return len(s[-1])
return 0AutoHotkey
class Solution
{
static lengthOfLastWord(s)
{
if strlen(s) == 0
return 0
s := StrSplit(s, " ")
if s.length > 0
return strlen(s[-1])
return 0
}
}
; Check Solution
; msgBox Solution.lengthOfLastWord("Hello World")第五十九题 螺旋矩阵 II
Given an integer n, generate a square matrix filled with elements from 1 to n in spiral order.
给定一个整数n，生成一个平方矩阵，该矩阵按螺旋顺序填充从1到n的元素。
For example,
Given n = 3,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]Python
class Solution(object):
def generateMatrix(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
ans = [[0] * n for _ in range(n)]
left, right, up, down = 0, n - 1, 0, n - 1
k = 1
while left <= right and up <= down:
for i in range(left, right + 1):
ans[up][i] = k
k += 1
up += 1
for i in range(up, down + 1):
ans[i][right] = k
k += 1
right -= 1
for i in reversed(range(left, right + 1)):
ans[down][i] = k
k += 1
down -= 1
for i in reversed(range(up, down + 1)):
ans[i][left] = k
k += 1
left += 1
return ansAutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static generateMatrix(n)
{
ans := [0]
mutiple(ans, n)
ans := [ans.Clone()]
mutiple(ans, n)
left := up := 0
right := down := n - 1
k := 1
while left <= right and up <= down
{
for i in range(left, right + 1)
{
ans[up + 1][i + 1] := k
k += 1
}
up += 1
for i in range(up, down + 1)
{
ans[i + 1][right + 1] := k
k += 1
}
right -= 1
for i in reversed(range(left, right + 1))
{
ans[down + 1][i + 1] := k
k += 1
}
down -= 1
for i in reversed(range(up, down + 1))
{
ans[i + 1][left + 1] := k
k += 1
}
left += 1
}
return ans
}
}
; Check Solution
; print Solution.generateMatrix(3)
; 为了便于操作数组，写了一个数组乘法的简单替代
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
}
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
}第六十题 排列序列
The set [1,2,3,...,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
集合[1,2,3,...,n]总共包含n！唯一排列。
通过按顺序列出并标记所有排列，
我们得到以下序列（即，对于n=3）：
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
给定n和k，返回第k个置换序列。
注：给定的n将在1和9之间（包括1和9）。Python
class Solution(object):
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
visited = [0 for i in range(n)]
fact = [math.factorial(n - i - 1) for i in range(n)]
ans = ""
k -= 1
for i in range(n):
t = k / fact[i]
for j in range(n):
if not visited[j]:
if t == 0:
ans += str(j + 1)
visited[j] = 1
break
t -= 1
k %= fact[i]
return ansAutoHotkey
; 这里简单写一个本题要用到的math库，Sinet库中有更为完善的Sinet.math类
class math
{
static factorial(num)
{
res := 1
loop Integer(num)
res *= A_Index
return res
}
}
; 之前提供了一个简单的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 getPermutation(n, k)
{
visited := [0]
mutiple(visited, n)
fact := []
loop n
fact.push(math.factorial(n - A_Index))
ans := ""
k -= 1
for i in xrange(n)
{
t := k // fact[i + 1]
for j in xrange(n)
{
if not visited[j + 1]
{
if t == 0
{
ans .= string(j + 1)
visited[j + 1] := 1
break
}
t -= 1
}
}
k := mod(k, fact[i + 1])
}
return ans
}
}
; Check Solution
; msgBox Solution.getPermutation(4, 17)
; 为了便于操作数组，写了一个数组乘法的简单替代
mutiple(Lst, Number)
{
tmp := Lst.Clone()
Loop Number - 1
For i in tmp
{
Try
Lst.Push(i.Clone())
Catch
Lst.Push(i)
}
}
