写在最前
注：由于单版面容不下665道题，因此拆分，之后会单做一个目录。
**答案有误请私信告知，谢谢。
这是由Mono开展的第一个长期项目，会将Leetcode相关习题通过AHKv2实现，每道题会同步贴出相应Python代码。对一些Python程序员而言，可以通过比较，更快迁移到AHK这门语言上。
***引流：请喜欢Python的或是对于人工智能感兴趣的程序员关注我的另一个（大概）每周更新项目《Sinet库》，目前已经迁移了包括Numpy、Pandas和Sklearn在内的大量Python相关函数内容。
***引流2：目前新出一个长期项目，是关于Sinet库的数据类型的代码示例及解析，有兴趣的可以捧个人场。
更新至第七十题 2022.07.16 Mono
第六十一题 旋转链表
Given a list, rotate the list to the right by k places, where k is non-negative.
给定一个列表，将列表向右旋转k个位置，其中k为非负。
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.Python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if not head:
return head
l = 1
p = head
while p.next:
l += 1
p = p.next
k = k % l
if k == 0:
return head
k = l - k % l - 1
pp = head
print k
while k > 0:
pp = pp.next
k -= 1
newHead = pp.next
pp.next = None
p.next = head
return newHeadAutoHotkey
; Definition for singly-linked list.
class ListNode
{
__New(x)
{
this.val := x
this.next := ""
}
}
class Solution
{
static rotateRight(head, k)
{
if not head
return head
l := 1
p := head
while p.next
{
l += 1
p := p.next
}
k := mod(k, l)
if k == 0
return head
k := l - mod(k, l) - 1
pp := head
while k > 0
{
pp := pp.next
k -= 1
}
newHead := pp.next
pp.next := ""
p.next := head
return newHead
}
}
; 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.rotateRight(a_head, 2)
; res_text := ""
; while res
; {
; res_text .= res.val "->"
; res := res.next
; }
; msgBox SubStr(res_text, 1, strlen(res_text) - 2)第六十二题 不同路径
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
机器人位于m x n网格的左上角。
机器人只能在任何时间点向下或向右移动。机器人正试图到达网格的右下角。
有多少种可能的唯一路径？
Note: m and n will be at most 100.
注：m和n最多为100。Python
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [1] * n
for i in xrange(1, m):
pre = 1
for j in xrange(1, n):
dp[j] = dp[j] + pre
pre = dp[j]
return dp[-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 uniquePaths(m, n)
{
dp := [1]
mutiple(dp, n)
for i in xrange(m - 1)
{
i += 1
pre := 1
for j in xrange(n - 1)
{
j += 1
dp[j + 1] := dp[j + 1] + pre
pre := dp[j + 1]
}
}
return dp[-1]
}
}
; Check Solution
; msgBox Solution.uniquePaths(7, 3)
; 为了便于操作数组，写了一个数组乘法的简单替代
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 "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
现在考虑是否在网格中添加了一些障碍。有多少条独特的路径？
障碍物和空白空间在网格中分别标记为1和0。
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.
Note: m and n will be at most 100.
注：m和n最多为100。Python
class Solution(object):
def uniquePathsWithObstacles(self, grid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
if not grid:
return 0
if grid[0][0] == 1:
return 0
dp = [[0] * len(grid[0]) for _ in xrange(0 ,len(grid))]
dp[0][0] = 1 if grid[0][0] == 0 else 0
for i in xrange(1, len(grid)):
if grid[i][0] == 0:
dp[i][0] = 1
else:
break
for j in xrange(1, len(grid[0])):
if grid[0][j] == 0:
dp[0][j] = 1
else:
break
for i in xrange(1, len(grid)):
for j in xrange(1, len(grid[0])):
if grid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
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 uniquePathsWithObstacles(grid)
{
if not grid.length
return 0
if grid[1][1] == 1
return 0
dp := [0]
mutiple(dp, grid[1].length)
dp := [dp.Clone()]
mutiple(dp, grid.length)
dp[1][1] := (grid[1][1] == 0) ? 1 : 0
for i in xrange(grid.length - 1)
{
i += 1
if grid[i + 1][1] == 0
dp[i + 1][1] := 1
else
break
}
for j in xrange(grid[1].length - 1)
{
j += 1
if grid[1][j + 1] == 0
dp[1][j + 1] := 1
else
break
}
for i in xrange(grid.length - 1)
{
i += 1
for j in xrange(grid[1].length - 1)
{
j += 1
if grid[i + 1][j + 1] == 1
dp[i + 1][j + 1] := 0
else
dp[i + 1][j + 1] := dp[i][j + 1] + dp[i + 1][j]
}
}
return dp[-1][-1]
}
}
; Check Solution
; cuba := [[0,0,0],
; [0,1,0],
; [0,0,0]]
; msgBox Solution.uniquePathsWithObstacles(cuba)
; 为了便于操作数组，写了一个数组乘法的简单替代
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 grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
给定一个由非负数填充的m x n网格，找到一条从左上角到右下角的路径
该路径使其路径上所有数字的总和最小化。
Note: You can only move either down or right at any point in time.
注意：您只能在任何时间点向下或向右移动。Python
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if len(grid) == 0:
return 0
dp = [0 for _ in xrange(0, len(grid[0]))]
dp[0] = grid[0][0]
for j in xrange(1, len(grid[0])):
dp[j] = dp[j - 1] + grid[0][j]
for i in xrange(1, len(grid)):
pre = dp[0] + grid[i][0]
for j in xrange(1, len(grid[0])):
dp[j] = min(dp[j], pre) + grid[i][j]
pre = dp[j]
dp[0] += grid[i][0]
return dp[-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 minPathSum(grid)
{
if grid.length == 0
return 0
dp := [0]
mutiple(dp, grid[1].length)
dp[1] := grid[1][1]
for j in xrange(grid[1].length - 1)
{
j += 1
dp[j + 1] := dp[j] + grid[1][j + 1]
}
for i in xrange(grid.length - 1)
{
i += 1
pre := dp[1] + grid[i + 1][1]
for j in xrange(grid[1].length - 1)
{
j += 1
dp[j + 1] := min(dp[j + 1], pre) + grid[i + 1][j + 1]
pre := dp[j + 1]
}
dp[1] += grid[i + 1][1]
}
return dp[-1]
}
}
; Check Solution
; msgBox Solution.minPathSum([[1,3,1],[1,5,1],[4,2,1]])
; 为了便于操作数组，写了一个数组乘法的简单替代
mutiple(Lst, Number)
{
tmp := Lst.Clone()
Loop Number - 1
For i in tmp
{
Try
Lst.Push(i.Clone())
Catch
Lst.Push(i)
}
}第六十五题 有效数字
Validate if a given string is numeric.
验证给定字符串是否为数字。
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.
注：问题陈述的目的是含糊不清。在实现一个需求之前，您应该提前收集所有需求。Python
class States(object):
def __init__(self):
self.init = 0
self.decimal = 1
self.decpoint = 2
self.afterdp = 3
self.e = 4
self.aftere = 5
self.sign = 6
self.nullpoint = 7
self.esign = 8
self.afteresign = 9
class Solution(object):
def isNumber(self, s):
"""
:type s: str
:rtype: bool
"""
s = s.strip()
states = States()
state = states.init
decimals = "01234567890"
for c in s:
if state == states.init:
if c == ".":
state = states.nullpoint
elif c in decimals:
state = states.decimal
elif c in ["+", "-"]:
state = states.sign
else:
return False
elif state == states.sign:
if c in decimals:
state = states.decimal
elif c == ".":
state = states.nullpoint
else:
return False
elif state == states.esign:
if c not in decimals:
return False
state = states.afteresign
elif state == states.afteresign:
if c not in decimals:
return False
elif state == states.nullpoint:
if c not in decimals:
return False
state = states.decpoint
elif state == states.decimal:
if c in decimals:
continue
elif c == "e":
state = states.e
elif c == ".":
state = states.decpoint
else:
return False
elif state == states.decpoint:
if c in decimals:
state = states.afterdp
elif c == "e":
state = states.e
else:
return False
elif state == states.afterdp:
if c in decimals:
continue
elif c == "e":
state = states.e
else:
return False
elif state == states.e:
if c in decimals:
state = states.aftere
elif c in ["+", "-"]:
state = states.esign
else:
return False
elif state == states.aftere:
if c not in decimals:
return False
else:
return False
return state not in [states.init, states.e, states.nullpoint, states.sign, states.esign]AutoHotkey
class Statesy
{
__New()
{
this.init := 0
this.decimal := 1
this.decpoint := 2
this.afterdp := 3
this.e := 4
this.aftere := 5
this.sign := 6
this.nullpoint := 7
this.esign := 8
this.afteresign := 9
}
}
class Solution
{
static isNumber(s)
{
s := Trim(s)
; 注这里是因为ahk变量不区分大小写，因此得改名。
states := Statesy()
state := states.init
decimals := "01234567890"
decimals := StrSplit(decimals, "")
for c in StrSplit(s, "")
{
if state == states.init
{
if c == "."
state := states.nullpoint
else if inarr(c, decimals)
state := states.decimal
else if inarr(c, ["+", "-"])
state := states.sign
else
return False
}
else if state == states.sign
{
if inarr(c, decimals)
state := states.decimal
else if c == "."
state := states.nullpoint
else
return False
}
else if state == states.esign
{
if !inarr(c, decimals)
return False
state := states.afteresign
}
else if state == states.afteresign
{
if !inarr(c, decimals)
return False
}
else if state == states.nullpoint
{
if !inarr(c, decimals)
return False
state := states.decpoint
}
else if state == states.decimal
{
if inarr(c, decimals)
continue
else if c == "e"
state := states.e
else if c == "."
state := states.decpoint
else
return False
}
else if state == states.decpoint
{
if inarr(c, decimals)
state := states.afterdp
else if c == "e"
state := states.e
else
return False
}
else if state == states.afterdp
{
if inarr(c, decimals)
continue
else if c == "e"
state := states.e
else
return False
}
else if state == states.e
{
if inarr(c, decimals)
state := states.aftere
else if inarr(c, ["+", "-"])
state := states.esign
else
return False
}
else if state == states.aftere
{
if !inarr(c, decimals)
return False
}
else
return False
}
return !inarr(state, [states.init, states.e, states.nullpoint, states.sign, states.esign])
}
}
; Check Solution
; msgBox Solution.isNumber("2e10")
inarr(element, arr)
{
flag := 0
for i in arr
{
if element == i
flag := 1
}
return flag
}第六十六题 加一
Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.
You may assume the integer do not contain any leading zero, except the number 0 itself.
The digits are stored such that the most significant digit is at the head of the list.
给定一个非负整数，表示为一个非空的数字数组，加上一个整数。
您可以假设整数不包含任何前导零，数字0本身除外。
存储数字时，最重要的数字位于列表的开头。Python
class Solution(object):
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
carry = 1
for i in reversed(xrange(0, len(digits))):
digit = (digits[i] + carry) % 10
carry = 1 if digit < digits[i] else 0
digits[i] = digit
if carry == 1:
return [1] + digits
return digitsAutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static plusOne(digits)
{
carry := 1
for i in reversed(range(0, digits.length))
{
digit := mod(digits[i + 1] + carry, 10)
carry := digit < digits[i + 1] ? 1 : 0
digits[i + 1] := digit
}
if carry == 1
{
tmp := [1]
tmp.push(digits*)
return tmp
}
return digits
}
}
; Check Solution
; print Solution.plusOne([1,2,3])
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 two binary strings, return their sum (also a binary string).
给定两个二进制字符串，返回其总和（也是一个二进制字符串）。
For example,
a = "11"
b = "1"
Return "100".Python
class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
diff = abs(len(a) - len(b))
if len(a) > len(b):
b = "0" * diff + b
else:
a = "0" * diff + a
ret = ""
carry = 0
ai, bi = len(a) - 1, len(b) - 1
al, bl = len(a), len(b)
while ai >= 0 and bi >= 0:
ac, bc = a[ai], b[bi]
if ac == "1" and bc == "1":
if carry == 1:
ret += "1"
else:
ret += "0"
carry = 1
elif ac == "0" and bc == "0":
if carry == 1:
ret += "1"
else:
ret += "0"
carry = 0
else:
if carry == 1:
ret += "0"
else:
ret += "1"
ai -= 1
bi -= 1
if carry == 1:
ret += "1"
return ret[::-1]AutoHotkey
class Solution
{
static addBinary(a, b)
{
diff := abs(strlen(a) - strlen(b))
if strlen(a) > strlen(b)
{
loop diff
b := "0" . b
}
else
{
loop diff
a := "0" . a
}
ret := ""
carry := 0
ai := strlen(a) - 1
bi := strlen(b) - 1
al := strlen(a)
bl := strlen(b)
while ai >= 0 and bi >= 0
{
ac := StrSplit(a, "")[ai + 1]
bc := StrSplit(b, "")[bi + 1]
if ac == "1" and bc == "1"
{
if carry == 1
ret .= "1"
else
ret .= "0"
carry := 1
}
else if ac == "0" and bc == "0"
{
if carry == 1
ret .= "1"
else
ret .= "0"
carry := 0
}
else
{
if carry == 1
ret .= "0"
else
ret .= "1"
}
ai -= 1
bi -= 1
}
if carry == 1
ret .= "1"
tmp := ""
for i in StrSplit(ret, "")
tmp := i . tmp
return tmp
}
}
; Check Solution
; msgBox Solution.addBinary("11", "1")第六十八题 文本左右对齐
Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
给定一个单词数组和长度L，格式化文本，使每行正好有L个字符，并且完全（左和右）对齐。
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.
你应该用贪婪的方式来包装你的话；也就是说，在每行中尽可能多地填充单词。
如有必要，请填充额外的空格“”，使每行正好包含L个字符。
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
单词之间的额外空格应尽可能均匀分布。如果一行中的空格数不在单词之间平均分配，
则左侧的空槽将分配比右侧槽更多的空格。
For the last line of text, it should be left justified and no extra space is inserted between words.
对于文本的最后一行，它应该左对齐，并且在单词之间不插入额外的空格。
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:
[
"This is an",
"example of text",
"justification. "
]
Note: Each word is guaranteed not to exceed L in length.
注：保证每个单词的长度不超过L。Python
class Solution(object):
def fullJustify(self, words, maxWidth):
"""
:type words: List[str]
:type maxWidth: int
:rtype: List[str]
"""
ans = []
line = []
lens = map(len, words)
idx = 0
curLen = 0
while idx < len(words):
if curLen == 0:
curLen = lens[idx]
else:
curLen += lens[idx] + 1
line.append(words[idx])
idx += 1
if curLen > maxWidth:
curLen = 0
line.pop()
idx -= 1
if len(line) == 1:
ans.append(line[0] + " " * (maxWidth - len(line[0])))
line = []
continue
spaces = maxWidth - sum(map(len,line))
avgSpace = spaces / (len(line) - 1)
extraSpace = spaces % (len(line) - 1)
res = ""
for i in xrange(0, len(line)):
res += line[i]
if i < len(line) - 1:
res += " " * (avgSpace + (extraSpace > 0))
extraSpace -= 1
ans.append(res)
line = []
elif idx == len(words):
res = ""
for i in xrange(0, len(line)):
res += line[i]
if i < len(line) - 1:
res += " "
res += " " * (maxWidth - len(res))
ans.append(res)
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 fullJustify(words, maxWidth)
{
ans := []
line := []
lens := []
for i in words
lens.push(strlen(i))
idx := 0
curLen := 0
while idx < words.length
{
if curLen == 0
curLen := lens[idx + 1]
else
curLen += lens[idx + 1] + 1
line.push(words[idx + 1])
idx += 1
if curLen > maxWidth
{
curLen := 0
line.pop()
idx -= 1
if line.length == 1
{
tmp := ""
loop maxWidth - strlen(line[1])
tmp .= " "
ans.push(line[1] . tmp)
line := []
continue
}
sum := 0
for i in line
sum += strlen(i)
spaces := maxWidth - sum
avgSpace := spaces // (line.length - 1)
extraSpace := mod(spaces, (line.length - 1))
res := ""
for i in xrange(line.length)
{
res .= line[i + 1]
if i < line.length - 1
{
loop avgSpace + (extraSpace > 0)
res .= " "
extraSpace -= 1
}
}
ans.push(res)
line := []
}
else if idx == words.length
{
res := ""
for i in xrange(line.length)
{
res .= line[i + 1]
if i < line.length - 1
res .= " "
}
reslen := strlen(res)
loop maxWidth - reslen
res .= " "
ans.push(res)
}
}
return ans
}
}
; Check Solution
print Solution.fullJustify(["This", "is", "an", "example", "of", "text", "justification."], 16)
Print(Text)
{
msgBox ToString(Text)
}
ToString(Text)
{
Print_Text := ""
if Type(Text) == "Array"
{
Print_Text .= "[`n"
For i in Text
Print_Text .= ToString(i) ",`n"
Print_Text := SubStr(Print_Text, 1, StrLen(Print_Text) - 2)
Print_Text .= "`n]"
}
else
Print_Text .= Text
Return Print_Text
}第六十九题 二分算法
Implement int sqrt(int x).
Compute and return the square root of x.
计算并返回x的平方根。Python
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
lo = 0
hi = x
while lo <= hi:
mid = (hi + lo) // 2
v = mid * mid
if v < x:
lo = mid + 1
elif v > x:
hi = mid - 1
else:
return mid
return hiAutoHotkey
class Solution
{
static mySqrt(x)
{
lo := 0
hi := x
while lo <= hi
{
mid := (hi + lo) // 2
v := mid * mid
if v < x
lo := mid + 1
else if v > x
hi := mid - 1
else
return mid
}
return hi
}
}
; Check Solution
; msgBox Solution.mySqrt(4)第七十题 爬楼梯问题
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
你正在爬楼梯。到达顶端需要n步。
每次你可以爬1步或2步。你能用多少种不同的方式爬到山顶？
Note: Given n will be a positive integer.
注：给定n为正整数。Python
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 1:
return 1
pre, ppre = 1, 1
for i in xrange(2, n + 1):
tmp = pre
pre = ppre + pre
ppre = tmp
return preAutoHotkey
; 之前提供了一个简单的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 climbStairs(n)
{
if n <= 1
return 1
pre := ppre := 1
for i in xrange(n - 1)
{
tmp := pre
pre := ppre + pre
ppre := tmp
}
return pre
}
}
; Check Solution
; msgBox Solution.climbStairs(10)
