写在最前
注：由于单版面容不下665道题，因此拆分，之后会单做一个目录。
**答案有误请私信告知，谢谢。
这是由Mono开展的第一个长期项目，会将Leetcode相关习题通过AHKv2实现，每道题会同步贴出相应Python代码。对一些Python程序员而言，可以通过比较，更快迁移到AHK这门语言上。
***引流：请喜欢Python的或是对于人工智能感兴趣的程序员关注我的另一个（大概）每周更新项目《Sinet库》，目前已经迁移了包括Numpy、Pandas和Sklearn在内的大量Python相关函数内容。
更新至第三十题 2022.07.10 Mono
第二十一题 合并两个有序链表
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
合并两个已排序的链表，并将其作为新列表返回。新列表应通过将前两个列表的节点拼接在一起来创建。Python
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
head = dummy = ListNode(-1)
while l1 and l2:
if l1.val < l2.val:
head.next = l1
l1 = l1.next
else:
head.next = l2
l2 = l2.next
head = head.next
if l1:
head.next = l1
if l2:
head.next = l2
return dummy.nextAutoHotkey
; Definition for singly-linked list.
class ListNode
{
__New(x)
{
this.val := x
this.next := ""
}
}
class Solution
{
static mergeTwoLists(l1, l2)
{
head := dummy := ListNode(-1)
while l1 and l2
{
if l1.val < l2.val
{
head.next := l1
l1 := l1.next
}
else
{
head.next := l2
l2 := l2.next
}
head := head.next
}
if l1
head.next := l1
if l2
head.next := l2
return dummy.next
}
}
; Create List_Node
; a := ListNode(1)
; a_head := a
; arr := [2, 4]
; Loop arr.length
; {
; temp := ListNode(arr[A_Index])
; a.next := temp
; a := a.next
; }
; b := ListNode(1)
; b_head := b
; arr := [3, 4]
; Loop arr.length
; {
; temp := ListNode(arr[A_Index])
; b.next := temp
; b := b.next
; }
; Check Solution
; 这里提供了一种直观看链表的办法
; res := Solution.mergeTwoLists(a_head, b_head)
; res_text := ""
; while res
; {
; res_text .= res.val "->"
; res := res.next
; }
; msgBox SubStr(res_text, 1, strlen(res_text) - 2)第二十二题 括号生成（含DFS算法）
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
给定n对括号，编写一个函数来生成格式良好的括号的所有组合。
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]Python
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
def dfs(left, path, res, n):
if len(path) == 2 * n:
if left == 0:
res.append("".join(path))
return
if left < n:
path.append("(")
dfs(left + 1, path, res, n)
path.pop()
if left > 0:
path.append(")")
dfs(left - 1, path, res, n)
path.pop()
res = []
dfs(0, [], res, n)
return resAutoHotkey
class Solution
{
static generateParenthesis(n)
{
dfs(left, path, res, n)
{
if path.length == 2 * n
{
if left == 1
{
tmp := ""
for i in path
tmp .= i
res.push(tmp)
}
return
}
if left <= n
{
path.push("(")
dfs(left + 1, path, res, n)
path.pop()
}
if left > 1
{
path.push(")")
dfs(left - 1, path, res, n)
path.pop()
}
}
res := []
dfs(1, [], res, n)
return res
}
}
; Check Solution
; 为了便于测试我引入比较简单的Print办法，Sinet库中有更强的Print
; print Solution.generateParenthesis(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
}第二十三题 合并K个升序链表
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
合并k个已排序的链表，并将其作为一个已排序的列表返回。分析并描述其复杂性。Python
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
import heapq
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
heap = []
p = dummy = ListNode(-1)
for i in xrange(0, len(lists)):
node = lists[i]
if not node:
continue
heapq.heappush(heap, (node.val, node))
while heap:
value, node = heapq.heappop(heap)
p.next = node
p = p.next
if node.next:
node = node.next
heapq.heappush(heap, (node.val, node))
return dummy.nextAutoHotkey
; Definition for singly-linked list.
class ListNode
{
__New(x)
{
this.val := x
this.next := ""
}
}
; ahk没有xrange函数，这里提供一个简单版本，在Sinet库中有更好的Range函数
xrange(length)
{
arr := []
loop length
arr.push(A_Index-1)
return arr
}
; ahk没有heapq模块，这里写一个简单的替代，Sinet库中暂时无相关内容
class heapq
{
static _siftdown(heap, startpos, pos)
{
newitem := heap[pos]
while pos > startpos
{
parentpos := ((pos - 2) >> 1) + 1
parent := heap[parentpos]
if this.cmp_lt(newitem, parent)
{
heap[pos] := parent
pos := parentpos
continue
}
break
}
heap[pos] := newitem
}
static _siftup(heap, pos)
{
endpos := heap.length + 1
startpos := pos
newitem := heap[pos]
childpos := 2 * pos
while childpos < endpos
{
rightpos := childpos + 1
if rightpos < endpos and not this.cmp_lt(heap[childpos], heap[rightpos])
childpos := rightpos
heap[pos] := heap[childpos]
pos := childpos
childpos := 2 * pos
}
heap[pos] := newitem
this._siftdown(heap, startpos, pos)
}
static cmp_lt(x, y)
{
return x[1] < y[1]
}
static heappop(heap)
{
lastelt := heap.pop()
if heap.length
{
returnitem := heap[1]
heap[1] := lastelt
this._siftup(heap, 1)
}
else
returnitem := lastelt
return returnitem
}
static heappush(heap, arr)
{
heap.push(arr)
this._siftdown(heap, 1, heap.length)
}
}
class Solution
{
static mergeKLists(lists)
{
heap := []
p := dummy := ListNode(-1)
for i in xrange(lists.length)
{
node := lists[i + 1]
if not node
continue
heapq.heappush(heap, [node.val, node])
}
while heap.length
{
tmp := heapq.heappop(heap)
value := tmp[1]
node := tmp[2]
p.next := node
p := p.next
if node.next
{
node := node.next
heapq.heappush(heap, [node.val, node])
}
}
return dummy.next
}
}
; Create List_Node
; a := ListNode(1)
; a_head := a
; arr := [4, 5]
; Loop arr.length
; {
; temp := ListNode(arr[A_Index])
; a.next := temp
; a := a.next
; }
; b := ListNode(1)
; b_head := b
; arr := [3, 4]
; Loop arr.length
; {
; temp := ListNode(arr[A_Index])
; b.next := temp
; b := b.next
; }
; c := ListNode(2)
; c_head := c
; arr := [6]
; Loop arr.length
; {
; temp := ListNode(arr[A_Index])
; c.next := temp
; c := c.next
; }
; Check Solution
; 这里提供了一种直观看链表的办法
; res := Solution.mergeKLists([a_head, b_head, c_head])
; res_text := ""
; while res
; {
; res_text .= res.val "->"
; res := res.next
; }
; msgBox SubStr(res_text, 1, strlen(res_text) - 2)第二十四题 两两交换链表中的节点
Given a linked list, swap every two adjacent nodes and return its head.
给定一个链表，每隔两个相邻节点交换一次，并返回其头部。
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
您的算法应该只使用常量空间。您不能修改列表中的值，只能更改节点本身。Python
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
def reverseList(head, k):
pre = None
cur = head
while cur and k > 0:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
k -= 1
head.next = cur
print(cur.val)
return cur, pre
if not head or not head.next:
return head
ret = head.next
p = head
pre = None
while p:
next, newHead = reverseList(p, 2)
if pre:
pre.next = newHead
pre = p
p = next
return retAutoHotkey
; Definition for singly-linked list.
class ListNode
{
__New(x)
{
this.val := x
this.next := ""
}
}
; 没什么值得注释的，跟之前的链表没啥大的差别
class Solution
{
static swapPairs(head)
{
; 注意这里函数一定要加上static，否则会被反复定义导致结果出现问题
static reverseList(head, k)
{
pre := ""
cur := head
while cur and k > 0
{
tmp := cur.next
cur.next := pre
pre := cur
cur := tmp
k -= 1
}
head.next := cur
return [cur, pre]
}
if not head or not head.next
return head
ret := head.next
p := head
pre := ""
while p
{
tmp := reverseList(p, 2)
next := tmp[1]
newHead := tmp[2]
if pre
pre.next := newHead
pre := p
p := next
}
return ret
}
}
; Create List_Node
; a := ListNode(1)
; a_head := a
; arr := [2, 3, 4]
; Loop arr.length
; {
; temp := ListNode(arr[A_Index])
; a.next := temp
; a := a.next
; }
; Check Solution
; 这里提供了一种直观看链表的办法
; res := Solution.swapPairs(a_head)
; res_text := ""
; while res
; {
; res_text .= res.val "->"
; res := res.next
; }
; msgBox SubStr(res_text, 1, strlen(res_text) - 2)第二十五题 k个一组翻转链表
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
给定一个链表，每次反转链表k的节点，并返回其修改后的列表。
k是一个正整数，小于或等于链表的长度。如果节点数不是k的倍数，那么最后被忽略的节点应该保持不变。
您不能更改节点中的值，只能更改节点本身。
只允许使用恒定内存。
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Python
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
def reverseList(head, k):
pre = None
cur = head
while cur and k > 0:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
k -= 1
head.next = cur
return cur, pre
length = 0
p = head
while p:
length += 1
p = p.next
if length < k:
return head
step = length / k
ret = None
pre = None
p = head
while p and step:
next, newHead = reverseList(p, k)
if ret is None:
ret = newHead
if pre:
pre.next = newHead
pre = p
p = next
step -= 1
return ret
AutoHotkey
; Definition for singly-linked list.
class ListNode
{
__New(x)
{
this.val := x
this.next := ""
}
}
class Solution
{
static reverseKGroup(head, k)
{
static reverseList(head, k)
{
pre := ""
cur := head
while cur and k > 0
{
tmp := cur.next
cur.next := pre
pre := cur
cur := tmp
k -= 1
}
head.next := cur
return [cur, pre]
}
length := 0
p := head
while p
{
length += 1
p := p.next
}
if length < k
return head
step := length / k
ret := ""
pre := ""
p := head
while p and step
{
tmp := reverseList(p, k)
next := tmp[1]
newHead := tmp[2]
if !ret
ret := newHead
if pre
pre.next := newHead
pre := p
p := next
step -= 1
}
return ret
}
}
; 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.reverseKGroup(a_head, 3)
; res_text := ""
; while res
; {
; res_text .= res.val "->"
; res := res.next
; }
; msgBox SubStr(res_text, 1, strlen(res_text) - 2)第二十六题 删除有序数组中的重复项
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
给定一个排序的数组，在适当的位置删除重复项，使每个元素只出现一次并返回新的长度。
不要为另一个数组分配额外的空间，您必须使用恒定内存就地执行此操作
For example,
Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.
Python
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 1:
return len(nums)
slow = 0
for i in xrange(1, len(nums)):
if nums[i] != nums[slow]:
slow += 1
nums[slow] = nums[i]
return slow + 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 removeDuplicates(nums)
{
if nums.length <= 1
return nums.length
slow := 1
for i in xrange(nums.length - 1)
if nums[i + 1] != nums[slow]
{
slow += 1
nums[slow] := nums[i + 1]
}
return slow + 1
}
}
; Check Solution
; msgBox Solution.removeDuplicates([0, 1, 1, 2, 2, 2, 3, 4])第二十七题 移除元素
Given an array and a value, remove all instances of that value in place and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
给定一个数组和一个值，删除该值的所有实例并返回新的长度。
不要为另一个数组分配额外的空间，您必须使用恒定内存就地执行此操作。
元素的顺序可以更改。你在新的长度之外留下什么无关紧要。
Example:
Given input array nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.Python
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
slow = -1
for i in xrange(0, len(nums)):
if nums[i] != val:
slow += 1
nums[slow] = nums[i]
return slow + 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 removeElement(nums, val)
{
slow := 0
for i in xrange(nums.length)
if nums[i + 1] != val
{
slow += 1
nums[slow] := nums[i + 1]
}
return slow
}
}
; Check Solution
; msgBox Solution.removeElement([1, 1, 2, 2, 3, 4, 2], 2)第二十八题 查询指定子字符串
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
执行strStr（）。
返回目标在源字符串中第一次出现的索引，如果目标不是源字符串的一部分，则返回-1。Python
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if len(haystack) == len(needle):
if haystack == needle:
return 0
else:
return -1
for i in xrange(0, len(haystack)):
k = i
j = 0
while j < len(needle) and k < len(haystack) and haystack[k] == needle[j]:
j += 1
k += 1
if j == len(needle):
return i
return -1 if needle else 0AutoHotkey
; 之前提供了一个简单的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版本，等价于ahk的Instr函数
class Solution
{
static strStr(haystack, needle)
{
if strlen(haystack) == strlen(needle)
{
if haystack == needle
return 1
else
return -1
}
; 由于要进行取值，因此转换为array类型
haystack := StrSplit(haystack, "")
needle := StrSplit(needle, "")
for i in xrange(haystack.length)
{
k := i
j := 0
while j < needle.length and k < haystack.length and haystack[k + 1] == needle[j + 1]
{
j += 1
k += 1
}
if j == needle.length
return i + 1
}
return needle ? -1 : 1
}
}
; Check Solution
; msgBox Solution.strStr("abcd", "bc")第二十九题 两数相除
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
不使用乘法、除法和mod运算符对两个整数进行除法。
如果溢出，则返回MAX_INT。Python
class Solution(object):
def divide(self, dividend, divisor):
"""
:type dividend: int
:type divisor: int
:rtype: int
"""
if divisor == 0:
return 0x7fffffff
sign = 1
if dividend * divisor < 0:
sign = -1
ans = 0
cnt = 1
dividend = abs(dividend)
divisor = abs(divisor)
subsum = divisor
while dividend >= divisor:
while (subsum << 1) <= dividend:
cnt <<= 1
subsum <<= 1
ans += cnt
cnt = 1
dividend -= subsum
subsum = divisor
return max(min(sign * ans, 0x7fffffff), -2147483648)AutoHotkey
class Solution
{
static divide(dividend, divisor)
{
if divisor == 0
return 0x7fffffff
sign := 1
if dividend * divisor < 0
sign := -1
ans := 0
cnt := 1
dividend := abs(dividend)
divisor := abs(divisor)
subsum := divisor
while dividend >= divisor
{
while (subsum << 1) <= dividend
{
cnt <<= 1
subsum <<= 1
}
ans += cnt
cnt := 1
dividend -= subsum
subsum := divisor
}
return max(min(sign * ans, 0x7fffffff), -2147483648)
}
}
; Check Solution
; msgBox Solution.divide(5, -3)第三十题 串联所有单词的子串
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
给你一个字符串s和一个单词列表，这些单词都是相同长度的。
在s中查找子串的所有起始索引，该子串是单词中每个单词准确连接一次，并且没有任何中间字符。
For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).Python
from collections import deque
class Solution(object):
def findSubstring(self, s, words):
"""
:type s: str
:type words: List[str]
:rtype: List[int]
"""
if len(words) > len(s):
return []
d = {}
t = {}
ans = []
deq = deque([])
wl = len(words[0])
fullscore = 0
for word in words:
d[word] = d.get(word, 0) + 1
fullscore += 1
for i in xrange(0, len(s)):
head = start = i
t.clear()
score = 0
while start + wl <= len(s) and s[start:start + wl] in d:
cword = s[start:start + wl]
t[cword] = t.get(cword, 0) + 1
if t[cword] <= d[cword]:
score += 1
else:
break
start += wl
if score == fullscore:
ans.append(head)
return ans; 之前提供了一个简单的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
}
}
}
; 此题中deque库未用到，故删去
class Solution
{
static findSubstring(s, words)
{
s := StrSplit(s, "")
if words.length > s.length
return []
d := map()
t := map()
ans := []
wl := strlen(words[1])
fullscore := 0
for word in words
{
d[word] := d.get(word, 0) + 1
fullscore += 1
}
for i in xrange(s.length)
{
head := start := i
t.clear()
score := 0
; 这里之所以要用try是因为最后一次循环时会超索引
; 而python没问题是因为它的这段语句在while循环的判断语句中
try
{
tmp := ""
loop wl
tmp .= s[start + A_Index]
}
while start + wl <= s.length and inarr(tmp, d)
{
cword := tmp
t[cword] := t.get(cword, 0) + 1
if t[cword] <= d[cword]
score += 1
else
break
start += wl
tmp := ""
loop wl
tmp .= s[start + A_Index]
}
if score == fullscore
ans.push(head)
}
return ans
}
}
; Check Solution
; 为了便于测试我引入比较简单的Print办法，Sinet库中有更强的Print
print Solution.findSubstring("barfoothefoobarman", ["foo", "bar"])
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
}
; 这里提供了一个简单的in关键字替换方案，Sinet库中的Sinet.In函数更强大
inarr(str, arr)
{
flag := 0
for i in arr
if str == i
flag := 1
return flag
}
速度不错