写在最前
注:由于单版面容不下665道题,因此拆分,之后会单做一个目录。
**答案有误请私信告知,谢谢。
这是由Mono开展的第一个长期项目,会将Leetcode相关习题通过AHKv2实现,每道题会同步贴出相应Python代码。对一些Python程序员而言,可以通过比较,更快迁移到AHK这门语言上。
***引流:请喜欢Python的或是对于人工智能感兴趣的程序员关注我的另一个(大概)每周更新项目《Sinet库》,目前已经迁移了包括Numpy、Pandas和Sklearn在内的大量Python相关函数内容。
***引流2:目前新出一个长期项目,是关于Sinet库的数据类型的代码示例及解析,有兴趣的可以捧个人场。
***引流3:目前新出一个长期项目,是利用Numahk库进行人工智能机器学习模块的示例教学。
更新至第九十题 2022.08.07 Mono
第八十一题 搜索旋转排序数组 II
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
“在旋转排序数组中搜索”的后续操作:
如果允许重复呢?
这会影响运行时复杂性吗?如何以及为什么?
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
假设一个按升序排序的数组在您事先未知的某个轴上旋转。
(即,0 1 2 4 5 6 7可能成为4 5 6 7 0 1 2)。
编写函数以确定给定目标是否在数组中。
阵列可能包含重复项。
Python
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if nums[mid] == target:
return True
if nums[start] < nums[mid]:
if nums[start] <= target <= nums[mid]:
end = mid
else:
start = mid
elif nums[start] > nums[mid]:
if nums[mid] <= target <= nums[end]:
start = mid
else:
end = mid
else:
start += 1
if nums[start] == target:
return True
if nums[end] == target:
return True
return False
AutoHotkey
class Solution
{
Static search(nums, target)
{
start := 0
end := nums.Length - 1
while start + 1 < end
{
mid := start + (end - start) // 2
if nums[mid + 1] == target
return True
if nums[start + 1] < nums[mid + 1]
{
if nums[start + 1] <= target and target <= nums[mid + 1]
end := mid
else
start := mid
}
else if nums[start + 1] > nums[mid + 1]
{
if nums[mid + 1] <= target and target <= nums[end + 1]
start := mid
else
end := mid
}
else
start += 1
}
if nums[start + 1] == target
return True
if nums[end + 1] == target
return True
return False
}
}
; Check Solution
; msgBox Solution.search([2,5,6,0,0,1,2], 0)
; msgBox Solution.search([2,5,6,0,0,1,2], 3)
第八十二题 删除排序链表中的重复元素 II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
给定一个已排序的链表,删除所有具有重复编号的节点,只留下与原始列表不同的编号。
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
Python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummy = ListNode(-1)
dummy.next = head
p = dummy
while p.next:
if p.next.next and p.next.val == p.next.next.val:
z = p.next
while z and z.next and z.val == z.next.val:
z = z.next
p.next = z.next
else:
p = p.next
return dummy.next
AutoHotkey
class ListNode
{
__New(x)
{
this.val := x
this.next := ""
}
}
class Solution
{
static deleteDuplicates(head)
{
dummy := ListNode(-1)
dummy.next := head
p := dummy
while p.next
{
if p.next.next and p.next.val == p.next.next.val
{
z := p.next
while z and z.next and z.val == z.next.val
z := z.next
p.next := z.next
}
else
p := p.next
}
return dummy.next
}
}
; Create List_Node
a := ListNode(1)
a_head := a
arr := [2,3,3,4,4,5]
Loop arr.length
{
temp := ListNode(arr[A_Index])
a.next := temp
a := a.next
}
; Check Solution
; 这里提供了一种直观看链表的办法
; res := Solution.deleteDuplicates(a_head)
; res_text := ""
; while res
; {
; res_text .= res.val "->"
; res := res.next
; }
; msgBox SubStr(res_text, 1, strlen(res_text) - 2)
第八十三题 删除排序链表中的重复元素
Given a sorted linked list, delete all duplicates such that each element appear only once.
给定一个已排序的链表,删除所有重复项,使每个元素只出现一次。
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
Python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummy = ListNode(None)
dummy.next = head
p = dummy
while p and p.next:
if p.val == p.next.val:
p.next = p.next.next
else:
p = p.next
return dummy.next
AutoHotkey
class ListNode
{
__New(x)
{
this.val := x
this.next := ""
}
}
class Solution
{
static deleteDuplicates(head)
{
dummy := ListNode("")
dummy.next := head
p := dummy
while p and p.next
{
if p.val == p.next.val
p.next := p.next.next
else
p := p.next
}
return dummy.next
}
}
; Check Solution
; Create List_Node
a := ListNode(1)
a_head := a
arr := [1,2,3,3]
Loop arr.length
{
temp := ListNode(arr[A_Index])
a.next := temp
a := a.next
}
; Check Solution
; 这里提供了一种直观看链表的办法
; res := Solution.deleteDuplicates(a_head)
; res_text := ""
; while res
; {
; res_text .= res.val "->"
; res := res.next
; }
; msgBox SubStr(res_text, 1, strlen(res_text) - 2)
第八十四题 柱状图中最大的矩形
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
给定n个表示直方图条高的非负整数,其中每个条的宽度为1,求出直方图中最大矩形的面积。
For example,
Given heights = [2,1,5,6,2,3],
return 10.
Python
class Solution(object):
def largestRectangleArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
if not height:
return 0
height.append(-1)
stack = []
ans = 0
for i in xrange(0, len(height)):
while stack and height[i] < height[stack[-1]]:
h = height[stack.pop()]
w = i - stack[-1] - 1 if stack else i
ans = max(ans, h * w)
stack.append(i)
height.pop()
return ans
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 largestRectangleArea(height)
{
if not height.Length
return 0
height.push(-1)
stack := []
ans := 0
for i in xrange(height.Length)
{
while stack.Length and height[i + 1] < height[stack[-1] + 1]
{
h := height[stack.pop() + 1]
w := stack.Length ? (i - stack[-1] - 1) : i
ans := max(ans, h * w)
}
stack.push(i)
}
height.pop()
return ans
}
}
; Check Solution
; msgBox Solution.largestRectangleArea([2,1,5,6,2,3])
第八十五题 最大矩形
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
给定一个填充了0和1的2D二进制矩阵,找到只包含1的最大矩形并返回其面积。
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.
Python
class Solution(object):
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
def histogram(height):
if not height:
return 0
height.append(-1)
stack = []
ans = 0
for i in xrange(0, len(height)):
while stack and height[i] < height[stack[-1]]:
h = height[stack.pop()]
w = i - stack[-1] - 1 if stack else i
ans = max(ans, h * w)
stack.append(i)
return ans
ans = 0
dp = [[0] * len(matrix[0]) for _ in xrange(0, len(matrix))]
for i in reversed(xrange(0, len(matrix))):
if i == len(matrix) - 1:
dp[i] = [int(h) for h in matrix[i]]
else:
for j in xrange(0, len(matrix[0])):
if matrix[i][j] != "0":
dp[i][j] = dp[i + 1][j] + 1
ans = max(ans, histogram(dp[i]))
return ans
AutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static maximalRectangle(matrix)
{
histogram(height)
{
if not height.Length
return 0
height.push(-1)
stack := []
ans := 0
for i in range(0, height.Length)
{
while stack.Length and height[i + 1] < height[stack[-1] + 1]
{
h := height[stack.pop() + 1]
w := stack.Length ? (i - stack[-1] - 1) : i
ans := max(ans, h * w)
}
stack.push(i)
}
height.pop()
return ans
}
ans := 0
dp := [0]
mutiple(dp, matrix[1].Length)
dp := [dp.Clone()]
mutiple(dp, matrix.Length)
for i in reversed(range(0, matrix.Length))
{
if i == matrix.Length - 1
{
tmp := []
for h in matrix[i + 1]
tmp.push(Integer(h))
dp[i + 1] := tmp
}
else
{
for j in range(0, matrix[1].Length)
{
if matrix[i + 1][j + 1] !== "0"
dp[i + 1][j + 1] := dp[i + 2][j + 1] + 1
}
}
; 这个地方我也不知道什么问题,得改成这样写
tmp := ans
ans := max(tmp, histogram(dp[i + 1]))
}
return ans
}
}
; Check Solution
; matrix :=
; [
; [1, 0, 1, 0, 0],
; [1, 0, 1, 1, 1],
; [1, 1, 1, 1, 1],
; [1, 0, 0, 1, 0]
; ]
; msgBox Solution.maximalRectangle(matrix)
; 为了便于操作数组,写了一个数组乘法的简单替代
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
}
第八十六题 分隔链表
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
给定一个链表和一个值x,对其进行分区,使小于x的所有节点位于大于或等于x的节点之前。
您应该保留两个分区中节点的原始相对顺序。
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
Python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
if head is None:
return None
dummy = ListNode(-1)
dummy.next = head
sHead = sDummy = ListNode(-1)
p = dummy
while p and p.next:
if p.next.val < x:
sDummy.next = p.next
p.next = p.next.next
sDummy = sDummy.next
else:
p = p.next
# if you change p.next then make sure you wouldn't change p in next run
sDummy.next = dummy.next
return sHead.next
AutoHotkey
class ListNode
{
__New(x)
{
this.val := x
this.next := ""
}
}
class Solution
{
static partition(head, x)
{
if !head
return ""
dummy := ListNode(-1)
dummy.next := head
sHead := sDummy := ListNode(-1)
p := dummy
while p and p.next
{
if p.next.val < x
{
sDummy.next := p.next
p.next := p.next.next
sDummy := sDummy.next
}
else
p := p.next
}
sDummy.next := dummy.next
return sHead.next
}
}
; Create List_Node
a := ListNode(1)
a_head := a
arr := [4,3,2,5,2]
Loop arr.length
{
temp := ListNode(arr[A_Index])
a.next := temp
a := a.next
}
; Check Solution
; 这里提供了一种直观看链表的办法
; res := Solution.partition(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 string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
给定一个字符串s1,我们可以通过递归地将其划分为两个非空子字符串,将其表示为二叉树。
Below is one possible representation of s1 = "great":
下面是s1=“great”的一种可能表示:
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
为了对字符串进行加扰,我们可以选择任何非叶节点并交换其两个子节点。
例如,如果我们选择节点“gr”并交换其两个子节点,它将生成一个加扰字符串“rgeat”。
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
我们说“rgeat”是一组“great”的拼音。
类似地,如果我们继续交换节点的子节点“eat”和“at”,它将生成一个加扰字符串“rgtae”。
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
We say that "rgtae" is a scrambled string of "great".
我们说“rgtae”是一个“great”的混乱字符串。
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
给定长度相同的两个字符串s1和s2,确定s2是否为s1的加扰字符串。
Python
class Solution(object):
def isScramble(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
n = len(s1)
m = len(s2)
if sorted(s1) != sorted(s2):
return False
if n < 4 or s1 == s2:
return True
for i in range(1, n):
if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
return True
if self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]):
return True
return False
AutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static isScramble(s1, s2)
{
n := strlen(s1)
m := strlen(s2)
; 注意这里的修改,Python的sorted函数是会影响对象本身。
s1 := sorted(s1)
s2 := sorted(s2)
if s1 != s2
return False
if n < 4 or s1 == s2
return True
for i in range(1, n)
{
if this.isScramble(substr(s1, 1, i), substr(s2, 1, i)) and this.isScramble(substr(s1, i + 1), substr(s2, i + 1))
return True
if this.isScramble(substr(s1, 1, i), substr(s2, -i)) and this.isScramble(substr(s1, i + 1), substr(s2, 1, strlen(s2) - i))
return True
}
return False
}
}
; Check Solution
; msgBox Solution.isScramble("great", "rgtae")
sorted(Str)
{
Str := StrSplit(Str, "")
loop Str.Length
{
index := A_Index
loop Str.Length - index
{
if Ord(Str[index]) > Ord(Str[index + A_Index])
{
temp := Str[index]
Str[index] := Str[index + A_Index]
Str[index + A_Index] := temp
}
}
}
Res := ""
For i in Str
Res .= i
Return Res
}
第八十八题 合并两个有序数组
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
给定两个排序整数数组nums1和nums2,将nums2合并为nums1作为一个排序数组。
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.
注:您可以假设nums1有足够的空间(大小大于或等于m+n)来容纳nums2中的其他元素。
nums1和nums2初始化的元素数分别为m和n。
Python
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
end = m + n - 1
m -= 1
n -= 1
while end >= 0 and m >= 0 and n >= 0:
if nums1[m] > nums2[n]:
nums1[end] = nums1[m]
m -= 1
else:
nums1[end] = nums2[n]
n -= 1
end -= 1
while n >= 0:
nums1[end] = nums2[n]
end -= 1
n -= 1
AutoHotkey
class Solution
{
static merge(nums1, m, nums2, n)
{
end := m + n - 1
m -= 1
n -= 1
while end >= 0 and m >= 0 and n >= 0
{
if nums1[m + 1] > nums2[n + 1]
{
nums1[end + 1] := nums1[m + 1]
m -= 1
}
else
{
nums1[end + 1] := nums2[n + 1]
n -= 1
}
end -= 1
}
while n >= 0
{
nums1[end + 1] := nums2[n + 1]
end -= 1
n -= 1
}
}
}
; Check Solution
; nums1 := [1,2,3,0,0,0], m := 3, nums2 := [2,5,6], n := 3
; Solution.merge(nums1, m, nums2, n)
; print nums1
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 gray code is a binary numeral system where two successive values differ in only one bit.
格雷码是一种二进制数字系统,其中两个连续值仅在一位上不同。
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
给定一个非负整数n表示代码中的总位数,打印格雷码序列。格雷码序列必须以0开头。
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
例如,给定n=2,返回[0,1,3,2]。其格雷码序列是:
00 - 0
01 - 1
11 - 3
10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
注:对于给定的n,格雷码序列不是唯一定义的。
例如,根据上述定义,[0,2,3,1]也是有效的格雷码序列。
Python
class Solution(object):
def grayCode(self, n):
"""
:type n: int
:rtype: List[int]
"""
if n < 1:
return [0]
ans = [0] * (2 ** n)
ans[1] = 1
mask = 0x01
i = 1
while i < n:
mask <<= 1
for j in range(0, 2**i):
root = (2**i)
ans[root + j] = ans[root - j - 1] | mask
i += 1
return ans
AutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static grayCode(n)
{
if n < 1
return [0]
ans := [0]
mutiple(ans, 2 ** n)
ans[2] := 1
mask := 0x01
i := 1
while i < n
{
mask <<= 1
for j in range(0, 2**i)
{
root := (2 ** i)
ans[root + j + 1] := ans[root - j] | mask
}
i += 1
}
return ans
}
}
; Check Solution
; print Solution.grayCode(2)
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
}
第九十题 子集 II
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
给定可能包含重复项的整数集合,nums返回所有可能的子集。
注意:解决方案集不得包含重复子集。
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
Python
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
def dfs(start, nums, path, res, visited):
res.append(path + [])
for i in xrange(start, len(nums)):
if start != i and nums[i] == nums[i - 1]:
continue
if i not in visited:
visited[i] = 1
path.append(nums[i])
dfs(i + 1, nums, path, res, visited)
path.pop()
del visited[i]
nums.sort()
res = []
visited = {}
dfs(0, nums, [], res, visited)
return res
AutoHotkey
range(start, stop)
{
tmp := []
loop stop - start
tmp.push(start + A_Index - 1)
return tmp
}
class Solution
{
static subsetsWithDup(nums)
{
dfs(start, nums, path, res, visited)
{
tmp := path.Clone()
res.push(tmp)
for i in range(start, nums.Length)
{
if start != i and nums[i + 1] == nums[i]
continue
if !visited.has(i + 1)
{
visited[i + 1] := 1
path.push(nums[i + 1])
dfs(i + 1, nums, path, res, visited)
path.pop()
visited.Delete(i + 1)
}
}
}
For i in range(0, nums.Length)
{
For j in range(i, nums.Length)
{
if nums[i + 1] > nums[j + 1]
{
tmp := nums[i + 1]
nums[i + 1] := nums[j + 1]
nums[j + 1] := tmp
}
}
}
res := []
visited := map()
dfs(0, nums, [], res, visited)
return res
}
}
; Check Solution
; print Solution.subsetsWithDup([1,2,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
}