AHK Leetcode系列 21-30

写在最前

注：由于单版面容不下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.next

AutoHotkey
; 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 res

AutoHotkey
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.next

AutoHotkey
; 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 ret

AutoHotkey
; 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 + 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 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 + 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 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 0

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
        }
    }
}
; 这道题我转化为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
}