写在最前
注：由于单版面容不下665道题，因此拆分，之后会单做一个目录。
**答案有误请私信告知，谢谢。
这是由Mono开展的第一个长期项目，会将Leetcode相关习题通过AHKv2实现，每道题会同步贴出相应Python代码。对一些Python程序员而言，可以通过比较，更快迁移到AHK这门语言上。
***引流：请喜欢Python的或是对于人工智能感兴趣的程序员关注我的另一个（大概）每周更新项目《Sinet库》，目前已经迁移了包括Numpy、Pandas和Sklearn在内的大量Python相关函数内容。
更新至第四十题 2022.07.14 Mono
第三十一题 下一个排列
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
实现下一个排列，将数字重新排列为按字典顺序排列的下一个更大的数字排列。
如果这种排列不可能，则必须将其重新排列为尽可能低的顺序（即，按升序排序）。
更换必须到位，不要分配额外内存
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 -> 1,3,2
3,2,1 -> 1,2,3
1,1,5 -> 1,5,1Python
class Solution(object):
def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
if nums is None or len(nums) <= 1:
return
pos = None
p = len(nums) - 2
# find the first number that is not in correct order
while p >= 0:
if nums[p + 1] > nums[p]:
pos = p
break
p -= 1
if pos is None:
self.reverse(nums, 0, len(nums) - 1)
return
# find the min value in the rest of the array
minPos, minV = pos + 1, nums[pos + 1]
for i in range(pos + 1, len(nums)):
if nums[i] <= minV and nums[i] > nums[pos]:
minV = nums[i]
minPos = i
# swap the two above number and reverse the array from `pos`
nums[pos], nums[minPos] = nums[minPos], nums[pos]
self.reverse(nums, pos + 1, len(nums) - 1)
def reverse(self, nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 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 nextPermutation(nums)
{
if nums == "" or nums.length <= 1
return
pos := ""
p := nums.length - 2
while p >= 0
{
if nums[p + 2] > nums[p + 1]
{
pos := p
break
}
p -= 1
}
if pos == ""
{
this.reverse(nums, 0, nums.length - 1)
return
}
minPos := pos + 1
minV := nums[pos + 2]
for i in xrange(nums.length - pos - 1)
{
i += pos + 1
if nums[i + 1] <= minV and nums[i + 1] > nums[pos + 1]
{
minV := nums[i + 1]
minPos := i
}
}
tmp := nums[pos + 1]
nums[pos + 1] := nums[minPos + 1]
nums[minPos + 1] := tmp
this.reverse(nums, pos + 1, nums.length - 1)
}
static reverse(nums, start, end)
{
while start < end
{
nums[start + 1] := nums[end + 1]
nums[end + 1] := nums[start + 1]
start += 1
end -= 1
}
}
}
; Check Solution
; 为了便于测试我引入比较简单的Print办法，Sinet库中有更强的Print
; nums := [1,2,3,4]
; Solution.nextPermutation(nums)
; print nums
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 a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
给定一个仅包含字符'('和')'的字符串，求最长有效（格式正确）括号子字符串的长度。
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.Python
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
dp = [0 for _ in xrange(0, len(s))]
left = 0
ans = 0
for i in xrange(0, len(s)):
if s[i] == "(":
left += 1
elif left > 0:
left -= 1
dp[i] = dp[i-1] + 2
j = i - dp[i]
if j >= 0:
dp[i] += dp[j]
ans = max(ans, dp[i])
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 longestValidParentheses(s)
{
s := StrSplit(s, "")
dp := []
for _ in xrange(s.length)
dp.push(0)
left := 0
ans := 0
for i in xrange(s.length)
{
if s[i + 1] == "("
left += 1
else if left > 0
{
left -= 1
dp[i + 1] := dp[i] + 2
j := i - dp[i + 1]
if j >= 0
dp[i + 1] += dp[j + 1]
ans := max(ans, dp[i + 1])
}
}
return ans
}
}
; Check Solution
; msgBox Solution.longestValidParentheses(")()())")第三十三题 搜索旋转排序数组
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).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
假设一个按升序排序的数组在您事先未知的某个轴上旋转。
（即，0 1 2 4 5 6 7可能成为4 5 6 7 0 1 2）。
您将获得一个要搜索的目标值。如果在数组中找到，则返回其索引，否则返回-1。
您可以假设阵列中不存在重复项。Python
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums:
return -1
left = 0
right = len(nums) - 1
while left <= right:
mid = (right + left) / 2
if nums[mid] == target:
return mid
if nums[mid] >= nums[left]:
if nums[left] <= target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] <= target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1AutoHotkey
class Solution
{
static search(nums, target)
{
if not nums
return -1
left := 0
right := nums.length - 1
while left <= right
{
mid := (right + left) // 2
if nums[mid + 1] == target
return mid + 1
if nums[mid + 1] >= nums[left + 1]
{
if nums[left + 1] <= target && target <= nums[mid + 1]
right := mid - 1
else
left := mid + 1
}
else
{
if nums[mid + 1] <= target && target <= nums[right + 1]
left := mid + 1
else
right := mid - 1
}
}
return -1
}
}
; Check Solution
; msgBox Solution.search([4,5,6,7,0,1,2],4)第三十四题 在排序数组中查找元素的第一个和最后一个位置
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
给定一个按升序排序的整数数组，查找给定目标值的开始和结束位置。
算法的运行时复杂度必须为O（对数n）。
如果在数组中未找到目标，则返回[-1，-1]。
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].Python
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
l, r = 0, len(nums) - 1
found = 0
start, end = 0, 0
while l < r:
m = l + (r - l) / 2
if target > nums[m]:
l = m + 1
else:
if target == nums[m]:
found += 1
r = m - 1
if nums[l] == target:
found += 1
start = r
if nums[r] != target or r < 0:
start = r + 1
l, r = 0, len(nums) - 1
while l < r:
m = l + (r - l) / 2
if target < nums[m]:
r = m - 1
else:
if target == nums[m]:
found += 1
l = m + 1
end = l
if nums[l] != target:
end = l - 1
if found == 0:
return [-1, -1]
return [start, end]AutoHotkey
class Solution
{
static searchRange(nums, target)
{
l := 0
r := nums.length - 1
found := 0
start := end := 0
while l < r
{
m := l + (r - l) // 2
if target > nums[m + 1]
l := m + 1
else
{
if target == nums[m + 1]
found += 1
r := m - 1
}
}
if nums[l + 1] == target
found += 1
start := r
if nums[r + 1] != target or r < 0
start := r + 1
l := 0
r := nums.length - 1
while l < r
{
m := l + (r - l) // 2
if target < nums[m + 1]
r := m - 1
else
{
if target == nums[m + 1]
found += 1
l := m + 1
}
}
end := l
if nums[l + 1] != target
end := l - 1
if found == 0
return [-1, -1]
return [start, end]
}
}
; Check Solution
; print Solution.searchRange([5, 7, 7, 8, 8, 10], 8)
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 a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
给定排序数组和目标值，如果找到目标，则返回索引。如果不是，则返回按顺序插入的索引。
您可以假设阵列中没有重复项。
Here are few examples.
[1,3,5,6], 5 -> 2
[1,3,5,6], 2 -> 1
[1,3,5,6], 7 -> 4
[1,3,5,6], 0 -> 0Python
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
lo = 0
hi = len(nums)
while lo < hi:
mid = lo + (hi - lo) / 2
if nums[mid] > target:
hi = mid
elif nums[mid] < target:
lo = mid + 1
else:
return mid
return loAutoHotkey
; 注意本题的返回值是根据ahk的InsertAt函数返回
; 与原题目返回值相比均+1
class Solution
{
static searchInsert(nums, target)
{
lo := 0
hi := nums.length
while lo < hi
{
mid := lo + (hi - lo) // 2
if nums[mid + 1] > target
hi := mid
else if nums[mid + 1] < target
lo := mid + 1
else
return mid + 1
}
return lo + 1
}
}
; Check Solution
; msgBox Solution.searchInsert([1,3,5,6],5)第三十六题 有效的数独
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
A partially filled sudoku which is valid.
根据：数独谜题-规则确定数独是否有效。
数独板可以部分填充，其中空单元格填充字符“.”。
有效的部分填充数独。
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
注：有效的数独板（部分填充）不一定是可解的。只需要验证填充的单元格。Python
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
cacheCol = [[0] * 9 for _ in range(0, 10)]
cacheRow = [[0] * 9 for _ in range(0, 10)]
cacheBox = [[0] * 9 for _ in range(0, 10)]
for i in range(0, 9):
for j in range(0, 9):
ib = (i//3)*3 + j//3
if board[i][j] == ".":
continue
num = int(board[i][j]) - 1
if cacheRow[i][num] != 0 or cacheCol[j][num] != 0 or cacheBox[ib][num] != 0:
return False
cacheRow[i][num] = 1
cacheCol[j][num] = 1
cacheBox[ib][num] = 1
return TrueAutoHotkey
; 之前提供了一个简单的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 isValidSudoku(board)
{
; 这里的处理会比较复杂，主要是为了排除同一地址数组导致的共同改变问题。
tmp := [0]
mutiple(tmp, 9)
cacheCol := [tmp.Clone()]
mutiple(cacheCol, 9)
cacheRow := [tmp.Clone()]
mutiple(cacheRow, 9)
cacheBox := [tmp.Clone()]
mutiple(cacheBox, 9)
for i in xrange(9)
{
for j in xrange(9)
{
ib := (i // 3) * 3 + j // 3
if board[i + 1][j + 1] == "."
continue
num := Integer(board[i + 1][j + 1]) - 1
if cacheRow[i + 1][num + 1] != 0 or cacheCol[j + 1][num + 1] != 0 or cacheBox[ib + 1][num + 1] != 0
return False
cacheRow[i + 1][num + 1] := 1
cacheCol[j + 1][num + 1] := 1
cacheBox[ib + 1][num + 1] := 1
}
}
return True
}
}
; Check Solution
; sudu := [['5','3','.','.','7','.','.','.','.'],
; ['6','.','.','1','9','5','.','.','.'],
; ['.','9','8','.','.','.','.','6','.'],
; ['8','.','.','.','6','.','.','.','3'],
; ['4','.','.','8','.','3','.','.','1'],
; ['7','.','.','.','2','.','.','.','6'],
; ['.','6','.','.','.','.','2','8','.'],
; ['.','.','.','4','1','9','.','.','5'],
; ['.','.','.','.','8','.','.','7','9']]
; msgBox Solution.isValidSudoku(sudu)
; 为了便于操作数组，写了一个数组乘法的简单替代
mutiple(Lst, Number)
{
tmp := Lst.Clone()
Loop Number - 1
For i in tmp
{
Try
Lst.Push(i.Clone())
Catch
Lst.Push(i)
}
}第三十七题 解数独
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
编写一个程序，通过填充空单元格来解决数独难题。
空单元格由字符“.”表示。
您可以假设只有一个唯一的解决方案。Python
class Solution(object):
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
cacheBox = [[0] * len(board) for _ in range(len(board))]
cacheRow = [[0] * len(board) for _ in range(len(board))]
cacheCol = [[0] * len(board) for _ in range(len(board))]
def helper(board, i, j, cacheRow, cacheCol, cacheBox):
if board[i][j] == ".":
for k in range(1, 10):
if i < 0 or i >= len(board) or j < 0 or j >= len(board):
continue
ib = (i//3) * 3 + j // 3
if cacheRow[i][k - 1] == 1 or cacheCol[j][k - 1] == 1 or cacheBox[ib][k - 1] == 1:
continue
cacheRow[i][k - 1] = cacheCol[j][k - 1] = cacheBox[ib][k - 1] = 1
board[i][j] = str(k)
if i == j == len(board) - 1:
return True
if i + 1 < len(board):
if helper(board, i + 1, j, cacheRow, cacheCol, cacheBox):
return True
elif j + 1 < len(board):
if helper(board, 0, j + 1, cacheRow, cacheCol, cacheBox):
return True
board[i][j] = "."
cacheRow[i][k - 1] = cacheCol[j][k - 1] = cacheBox[ib][k - 1] = 0
else:
if i == j == len(board) - 1:
return True
if i + 1 < len(board):
if helper(board, i + 1, j, cacheRow, cacheCol, cacheBox):
return True
elif j + 1 < len(board):
if helper(board, 0, j + 1, cacheRow, cacheCol, cacheBox):
return True
return False
for i in range(len(board)):
for j in range(len(board)):
if board[i][j] != ".":
ib = (i//3) * 3 + j // 3
k = int(board[i][j]) - 1
print(k)
cacheRow[i][k] = cacheCol[j][k] = cacheBox[ib][k] = 1
helper(board, 0, 0, cacheRow, cacheCol, cacheBox)
print(board)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 solveSudoku(board)
{
; 这里的处理会比较复杂，主要是为了排除同一地址数组导致的共同改变问题。
tmp := [0]
mutiple(tmp, board.length)
cacheCol := [tmp.Clone()]
mutiple(cacheCol, board.length)
cacheRow := [tmp.Clone()]
mutiple(cacheRow, board.length)
cacheBox := [tmp.Clone()]
mutiple(cacheBox, board.length)
static helper(board, i, j, cacheRow, cacheCol, cacheBox)
{
if board[i + 1][j + 1] == "."
{
for k in xrange(9)
{
k += 1
if i < 0 or i >= board.length or j < 0 or j >= board.length
continue
ib := (i // 3) * 3 + j // 3
if cacheRow[i + 1][k] == 1 || cacheCol[j + 1][k] == 1 || cacheBox[ib + 1][k] == 1
continue
cacheRow[i + 1][k] := cacheCol[j + 1][k] := cacheBox[ib + 1][k] := 1
board[i + 1][j + 1] := String(k)
if i == j == board.length - 1
return True
; 注意，由于ahk的if else语句在设计时有点小问题，因此多重if else需要用语块包裹
if i + 1 < board.length
{
if helper(board, i + 1, j, cacheRow, cacheCol, cacheBox)
return True
}
else if j + 1 < board.length
{
if helper(board, 0, j + 1, cacheRow, cacheCol, cacheBox)
return True
}
board[i + 1][j + 1] := "."
cacheRow[i + 1][k] := cacheCol[j + 1][k] := cacheBox[ib + 1][k] := 0
}
}
else
{
if i == j && i == board.length - 1
return True
; 注意，由于ahk的if else语句在设计时有点小问题，因此多重if else需要用语块包裹
if i + 1 < board.length
{
if helper(board, i + 1, j, cacheRow, cacheCol, cacheBox)
return True
}
else if j + 1 < board.length
{
if helper(board, 0, j + 1, cacheRow, cacheCol, cacheBox)
return True
}
}
return False
}
for i in xrange(board.length)
{
for j in xrange(board.length)
{
if board[i + 1][j + 1] != "."
{
ib := (i // 3) * 3 + j // 3
k := Integer(board[i + 1][j + 1]) - 1
cacheRow[i + 1][k + 1] := cacheCol[j + 1][k + 1] := cacheBox[ib + 1][k + 1] := 1
}
}
}
return helper(board, 0, 0, cacheRow, cacheCol, cacheBox)
}
}
; Check Solution
; sudu := [['5','3','.','.','7','.','.','.','.'],
; ['6','.','.','1','9','5','.','.','.'],
; ['.','9','8','.','.','.','.','6','.'],
; ['8','.','.','.','6','.','.','.','3'],
; ['4','.','.','8','.','3','.','.','1'],
; ['7','.','.','.','2','.','.','.','6'],
; ['.','6','.','.','.','.','2','8','.'],
; ['.','.','.','4','1','9','.','.','5'],
; ['.','.','.','.','8','.','.','7','9']]
; if Solution.solveSudoku(sudu)
; print sudu
; 为了便于操作数组，写了一个数组乘法的简单替代
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
}第三十八题 外观数组
The count-and-say sequence is the sequence of integers with the first five terms as following:
外观序列是具有以下前五项的整数序列：
1. 1
2. 11
3. 21
4. 1211
5. 111221
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth term of the count-and-say sequence.
Note: Each term of the sequence of integers will be represented as a string.
给定整数n，生成序列的第n项，然后表示外观序列。
注：整数序列的每个项将表示为一个字符串。
Example 1:
Input: 1
Output: "1"
Example 2:
Input: 4
Output: "1211"Python
class Solution(object):
def countAndSay(self, n):
"""
:type n: int
:rtype: str
"""
ans = "1"
n -= 1
while n > 0:
res = ""
pre = ans[0]
count = 1
for i in range(1, len(ans)):
if pre == ans[i]:
count += 1
else:
res += str(count) + pre
pre = ans[i]
count = 1
res += str(count) + pre
ans = res
n -= 1
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 countAndSay(n)
{
ans := "1"
ans := StrSplit(ans, "")
n -= 1
while n > 0
{
res := ""
pre := ans[1]
count := 1
for i in xrange(ans.length - 1)
{
i += 1
if pre == ans[i + 1]
count += 1
else
{
res .= string(count) . pre
pre := ans[i + 1]
count := 1
}
}
res .= string(count) . pre
ans := StrSplit(res, "")
n -= 1
}
tmp := ""
for i in ans
tmp .= i
return tmp
}
}
; Check Solution
; msgBox Solution.countAndSay(4)第三十九题 组合总和（含回溯算法）
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
给定一组候选数（C）（无重复）和目标数（T），在C中找到所有唯一组合，其中候选数和为T。
可以从C中选择相同的重复次数，次数不限。
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
注：
所有数字（包括目标）都将是正整数。
解决方案集不得包含重复的组合。
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]Python
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
def dfs(candidates, start, target, path, res):
if target == 0:
return res.append(path + [])
for i in range(start, len(candidates)):
if target - candidates[i] >= 0:
path.append(candidates[i])
dfs(candidates, i, target - candidates[i], path, res)
path.pop()
res = []
dfs(candidates, 0, target, [], res)
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
}
}
}
class Solution
{
static combinationSum(candidates, target)
{
static dfs(candidates, start, target, path, res)
{
if target == 0
{
tmp := path.Clone()
tmp.push("")
return res.push(tmp)
}
for i in xrange(candidates.length - start)
{
i += start
if target - candidates[i + 1] >= 0
{
path.push(candidates[i + 1])
dfs(candidates, i, target - candidates[i + 1], path, res)
path.pop()
}
}
}
res := []
dfs(candidates, 0, target, [], res)
; 这一步是为了排除多余元素
for i in res
i.pop()
return res
}
}
; Check Solution
; print Solution.combinationSum([2, 3, 6, 7], 9)
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 candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
给定候选数（C）和目标数（T）的集合，找出C中所有唯一的组合，其中候选数和为T。
C中的每个数字在组合中只能使用一次。
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
注：
所有数字（包括目标）都将是正整数。
解决方案集不得包含重复的组合。
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]Python
class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
def dfs(nums, target, start, visited, path, res):
if target == 0:
res.append(path + [])
return
for i in xrange(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
if target - nums[i] < 0:
return 0
if i not in visited:
visited.add(i)
path.append(nums[i])
dfs(nums, target - nums[i], i + 1, visited, path, res)
path.pop()
visited.discard(i)
candidates.sort()
res = []
visited = set([])
dfs(candidates, target, 0, visited, [], res)
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 combinationSum2(candidates, target)
{
static dfs(nums, target, start, visited, path, res)
{
if target == 0
{
tmp := path.Clone()
tmp.push("")
res.push(tmp)
return
}
for i in xrange(nums.length)
{
i += start
if i > start and nums[i + 1] == nums[i]
continue
if target - nums[i + 1] < 0
return 0
if !inarr(i, visited)
{
visited.add(i)
path.push(nums[i + 1])
dfs(nums, target - nums[i + 1], i + 1, visited, path, res)
path.pop()
visited.discard(i)
}
}
}
for i in xrange(candidates.length)
{
for j in xrange(candidates.length - i - 1)
{
j += i + 1
if candidates[i + 1] > candidates[j + 1]
{
tmp := candidates[i + 1]
candidates[i + 1] := candidates[j + 1]
candidates[j + 1] := tmp
}
}
}
res := []
visited := set([])
dfs(candidates, target, 0, visited, [], res)
; 这一步是为了排除多余元素
for i in res
i.pop()
return res
}
}
; Check Solution
; print Solution.combinationSum2([10, 1, 2, 7, 6, 1, 5], 8)
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
}
