AHK Leetcode系列 1-20

写在最前

这是由Mono开展的第一个长期项目，会将Leetcode相关习题通过AHKv2实现，每道题会同步贴出相应Python代码。对一些Python程序员而言，可以通过比较，更快迁移到AHK这门语言上。

***引流：请喜欢Python的或是对于人工智能感兴趣的程序员关注我的另一个（大概）每周更新项目《Sinet库》，目前已经迁移了包括Numpy、Pandas和Sklearn在内的大量Python相关函数内容。

更新至第二十题 2022.07.08 Mono

第一题 两数之和

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
给定一个整数数组，返回两个数字的索引，使它们相加到一个特定的目标。
您可以假设每个输入将恰好有一个解决方案，并且您可能不会两次使用同一个元素。

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Python
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = {}
        for i, num in enumerate(nums):
            if target - num in d:
                return [d[target - num], i]
            d[num] = i
        # no special case handling becasue it's assumed that it has only one solution

AutoHotKey
; ahk的类对象不支持参数
class Solution
{
    ; 注意函数前要加上static属性表示为公有函数，如缺少则为类的自有属性
    static twoSum(nums, target)
    {
        ; 在ahk中{}表示Object类型的对象，且ahk中赋值符为:=，=表示不区分大小写比较，==表示区分大小写比较
        d := Map()
        ; ahk中array类型索引从1开始，同时支持双参数枚举，且ahk中没有枚举器办法
        for i, num in nums
        {
            ; 由于ahk关键字in只能在for这样的枚举语句中使用，因此这里使用has替换
            if d.has(target - num)
                Return [d[target - num], i]
            
            d[num] := i
        }
    }
}
; Check Solution
; res := Solution.twoSum([2, 7, 11, 15], 9)
; 注意AutoHotkey的索引是从1开始的。
; msgBox res[1]
; msgBox res[2]

第二题 两数相加

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
给您两个非空链表，表示两个非负整数。数字按相反顺序存储，每个节点包含一个数字。将这两个数字相加，并将其作为链接列表返回。
您可以假设这两个数字不包含任何前导零，除了数字0本身。

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Python
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    # maybe standard version
    def _addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        p = dummy = ListNode(-1)
        carry = 0
        while l1 and l2:
            p.next = ListNode(l1.val + l2.val + carry)
            carry = p.next.val / 10
            p.next.val %= 10
            p = p.next
            l1 = l1.next
            l2 = l2.next
        
        res = l1 or l2
        while res:
            p.next = ListNode(res.val + carry)
            carry = p.next.val / 10
            p.next.val %= 10
            p = p.next
            res = res.next
        if carry:
            p.next = ListNode(1)
        return dummy.next
    
    # shorter version
    def addTwoNumbers(self, l1, l2):
        p = dummy = ListNode(-1)
        carry = 0
        while l1 or l2 or carry:
            val = (l1 and l1.val or 0) + (l2 and l2.val or 0) + carry
            carry = val / 10
            p.next = ListNode(val % 10)
            l1 = l1 and l1.next
            l2 = l2 and l2.next
            p = p.next
        return dummy.next

AutoHotkey
; Definition for singly-linked list.
class ListNode
{
    ; ahk的类初始化办法为__New()
    __New(x)
    {
        this.val := x
        this.next := ""
    }
}    

class Solution
{
    ; maybe standard version
    static _addTwoNumbers(l1, l2)
    {
        p := dummy := ListNode(-1)
        carry := 0
        while l1 and l2
        {
            p.next := ListNode(l1.val + l2.val + carry)
            ; 注意ahk中的精度较低，因此//在整数除法中更常用
            carry := p.next.val // 10
            ; 由于ahk的%运算符有特殊含义，因此求余数使用运算函数mod
            p.next.val := mod(p.next.val, 10)
            p := p.next
            l1 := l1.next
            l2 := l2.next
        }
        
        res := l1 or l2
        while res
        {
            p.next := ListNode(res.val + carry)
            carry := p.next.val // 10
            p.next.val := mod(p.next.val, 10)
            p := p.next
            res := res.next
        }
        if carry
            p.next := ListNode(1)
        return dummy.next
    }
    
    ; shorter version
    static addTwoNumbers(l1, l2)
    {
        p := dummy := ListNode(-1)
        carry := 0
        while l1 or l2 or carry
        {
            val := (l1 and l1.val or 0) + (l2 and l2.val or 0) + carry
            carry := val // 10
            p.next := ListNode(mod(val, 10))
            l1 := l1 and l1.next
            l2 := l2 and l2.next
            p := p.next
        }
        return dummy.next
    }
}
; Create List_Node
; a := ListNode(2)
; a_head := a
; arr := [4, 3]
; Loop 2
; {
    ; temp := ListNode(arr[A_Index])
    ; a.next := temp
    ; a := a.next
; }

; b := ListNode(5)
; b_head := b
; arr := [6, 4]
; Loop 2
; {
    ; temp := ListNode(arr[A_Index])
    ; b.next := temp
    ; b := b.next
; }

; Check Solution
; res := Solution._addTwoNumbers(a_head, b_head)
; while res
; {
    ; msgBox res.val
    ; res := res.next
; }

第三题 最长不重复子串

Given a string, find the length of the longest substring without repeating characters.
给定一个字符串，求最长子字符串的长度，不包含重复字符。

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Python
class Solution(object):
    def _lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        d = collections.defaultdict(int)
        l = ans = 0
        for i, c in enumerate(s):
            while l > 0 and d[c] > 0:
                d[s[i-l]] -= 1
                l -= 1
            d[c] += 1
            l += 1
            ans = max(ans, l)
        return ans
        
        
    def lengthOfLongestSubstring(self, s):
        d = {}
        start = 0
        ans = 0
        for i, c in enumerate(s):
            if c in d:
                start = max(start, d[c] + 1)
            d[c] = i
            ans = max(ans, i - start + 1)
        return ans

AutoHotkey
class Solution
{
    static _lengthOfLongestSubstring(s)
    {
        ; 由于ahk的string类型不可枚举，需要将它处理成array对象
        s := StrSplit(s, "")
        ; 由于ahk没有collections函数，因此这里需要这样改写
        d := map()
        loop s.length
            d[s[A_Index]] := 0
        l := ans := 0
        for i, c in s
        {
            while l > 0 and d[c] > 0
            {
                d[s[i-l]] -= 1
                l -= 1
            }
            d[c] += 1
            l += 1
            ans := max(ans, l)
        }
        return ans
    }
        
        
    static lengthOfLongestSubstring(s)
    {
        s := StrSplit(s, "")
        d := map()
        ; 注意开始索引为1，这里若为0，后续start与i运算时结果会与python产生偏差
        start := 1
        ans := 0
        for i, c in s
        {
            if d.has(c)
                start := max(start, d[c] + 1)
            d[c] := i
            ans := max(ans, i - start + 1)
        }
        return ans
    }
}
; Check Solution
; msgBox Solution._lengthOfLongestSubstring("abcabcbb")
; msgBox Solution._lengthOfLongestSubstring("bbbbb")
; msgBox Solution._lengthOfLongestSubstring("pwwkew")

第四题 寻找两个有序数组的中位数

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
有两个大小分别为m和n的排序数组nums1和nums2。
求两个排序数组的中值。总体运行时复杂度应为O(log (m+n))。

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Python
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        a, b = sorted((nums1, nums2), key=len)
        m, n = len(a), len(b)
        after = (m + n - 1) // 2
        lo, hi = 0, m
        while lo < hi:
            i = (lo + hi) // 2
            if after - i - 1 < 0 or a[i] >= b[after - i - 1]:
                hi = i
            else:
                lo = i + 1
        i = lo
        print(sorted(a[i:i + 2] + b[after - i:after - i + 2]))
        nextfew = sorted(a[i:i + 2] + b[after - i:after - i + 2])
        return (nextfew[0] + nextfew[1 - (m + n) % 2]) / 2.0

AutoHotkey
class Solution
{
    static findMedianSortedArrays(nums1, nums2)
    {
        ; ahk没有元组类型，自带sort函数只支持数值比较
        ; 这里使用三目表达式拆解sorted函数
        a := (nums1.length < nums2.length) ? nums1 : nums2
        b := (nums1.length < nums2.length) ? nums2 : nums1
        ; ahk没有len函数，array类型使用length属性替代
        ; ahk没有多不同值赋值办法，所以将下式拆分
        m := a.length, n := b.length
        after := (m + n + 1) // 2
        lo := 1, hi := m + 1
        while lo < hi
        {
            i := (lo + hi) // 2
            ; 注意ahk列表索引从1起，包含右端点
            if after-i < 1 or a[i] >= b[after-i]
                hi := i
            else
                lo := i + 1
        }
        i := lo
        ; ahk没有列表切分的办法，在Sinet库中，我引入了List类型支持切分
        ; 这里只能采用循环法解决
        nextfew := array()
        ; 注意计算元素偏移量时考虑是否已经偏移
        index_a := i
        index_b := after - i + 1
        ; 注意python的列表索引超范围切分返回值为超范围前数组，因此需要用try办法来避免
        loop 2
            Try
                nextfew.push(a[index_a++])
        loop 2
            Try
                nextfew.push(b[index_b++])
        ; 这里还需要对列表排序，这里使用全排序循环，复杂度为n**2
        for i in nextfew
        {
            index := A_Index
            for j in nextfew
            {
                if index < A_Index && i > j
                {
                    temp := nextfew[index]
                    nextfew[index] := nextfew[A_Index]
                    nextfew[A_Index] := temp
                }
            }
        }
        return (nextfew[1] + nextfew[2 - mod((m+n+2),2)]) / 2.0
    }
}
; Check Solution
; nums1 := [1, 2, 3]
; nums2 := [4, 5, 6, 7, 8]
; msgBox Solution.findMedianSortedArrays(nums1, nums2)

第五题 最长回文子串(动态规划)

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
给定一个字符串s，在s中找到最长的回文子串。您可以假设s的最大长度为1000。

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

Python
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        left = right = 0
        n = len(s)
        for i in range(n - 1):
            if 2 * (n - i) + 1 < right - left + 1:
                break
            l = r = i
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            if r - l - 2 > right - left:
                left = l + 1
                right = r - 1
            l = i
            r = i + 1
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            if r - l - 2 > right - left:
                left = l + 1
                right = r - 1
        return s[left:right + 1]

AutoHotkey
; ahk没有range函数，这里提供一个简单版本，在Sinet库中有更好的Range函数
range(length)
{
    arr := []
    loop length
        arr.push(A_Index-1)
    return arr
}

class Solution
{
    static longestPalindrome(s)
    {
        s := StrSplit(s, "")
        left := right := 0
        n := s.length
        for i in range(n - 1)
        {
            if 2 * (n - i) + 1 < right - left + 1
                break
            l := r := i + 1
            ; 注意这里简单的移植办法为将判断相等的索引+1
            while l >= 0 and r < n and s[l + 1] == s[r + 1]
            {
                l -= 1
                r += 1
            }
            if r - l - 2 > right - left
            {
                left := l + 1
                right := r - 1
            }
            l := i
            r := i + 1
            ; 注意这里简单的移植办法为将判断相等的索引+1
            while l >= 0 and r < n and s[l + 1] == s[r + 1]
            {
                l -= 1
                r += 1
            }
            if r - l - 2 > right - left
            {
                left := l + 1
                right := r - 1
            }
        }
        ; 字符串切分的ahk写法
        tmp := ""
        loop right + 1 - left
            tmp .= s[left + A_Index]
        return tmp
    }
}
; Check Solution
; s := "ababa"
; msgBox Solution.longestPalindrome(s)

第六题 Z字形变换

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
字符串“PAYPALISHIRING”以锯齿形模式写入给定数量的行，如下所示：（您可能希望以固定字体显示此模式以提高可读性）

P   A   H   N
A P L S I I G
Y   I   R


And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:
编写将获取字符串的代码，并在给定行数的情况下进行此转换：

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Python
class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows <= 1:
            return s
        n = len(s)
        ans = []
        step = 2 * numRows - 2
        for i in range(numRows):
            one = i
            two = -i
            while one < n or two < n:
                if 0 <= two < n and one != two and i != numRows - 1:
                    ans.append(s[two])
                if one < n:
                    ans.append(s[one])
                one += step
                two += step
        return "".join(ans)

AutoHotkey
; ahk没有range函数，这里提供一个简单版本，在Sinet库中有更好的Range函数
range(length)
{
    arr := []
    loop length
        arr.push(A_Index-1)
    return arr
}

class Solution
{
    static convert(s, numRows)
    {
        if numRows <= 1
            return s
        s := StrSplit(s, "")
        n := s.length
        ans := []
        step := 2 * numRows - 2
        for i in range(numRows)
        {
            one := i
            two := -i
            while one < n or two < n
            {
                ; 注意ahk不支持连续比较符
                ; 这里还是简单的进行索引偏移
                if 0 <= two and two < n and one != two and i != numRows - 1
                    ans.push(s[two + 1])
                if one < n
                    ans.push(s[one + 1])
                one += step
                two += step
            }
        }
        ; Join办法的替代，Sinet库中有Sinet.String.Join()函数替代
        tmp := ""
        loop ans.length
            tmp .= ans[A_Index]
        return tmp
    }
}
; Check Solution
; msgBox Solution.convert("LEETCODEISHIRING",4)

第七题 整数反转

Reverse digits of an integer.
整数的反位。

Example1: x =  123, return  321
Example2: x = -123, return -321

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

你想过这个吗？
在编码之前，这里有一些好问题要问。
如果整数的最后一位是0，那么输出应该是什么？例如，10100。
您注意到反向整数可能溢出了吗？假设输入是32位整数，则与100000003溢出相反。你应该如何处理此类案件？
为了解决这个问题，假设当反向整数溢出时，函数返回0。

注：假设输入为32位有符号整数。当反向整数溢出时，函数应返回0。

Python
class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        sign = x < 0 and -1 or 1
        x = abs(x)
        ans = 0
        while x:
            ans = ans * 10 + x % 10
            x /= 10
        return sign * ans if ans <= 0x7fffffff else 0

AutoHotkey
class Solution
{
    static reverse(x)
    {
        sign := x < 0 and -1 or 1
        x := abs(x)
        ans := 0
        while x
        {
            ans := ans * 10 + mod(x, 10)
            ; 再提示一次ahk除法无论是否均为整数，都返回浮点数
            ; 因此建议整数除法使用//运算符
            x //= 10
        }
        ; ahk没有相应语法，使用三目表达式替代
        return ans <= 0x7fffffff ? sign * ans : 0
    }
}
; Check Solution
; msgBox Solution.reverse(-1234)

第八题 字符串转整数

Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
实现atoi将字符串转换为整数。
提示：仔细考虑所有可能的输入情况。如果你想要挑战，请不要看下面，问问自己可能的输入案例是什么。

Notes: 
It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front. 

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

函数首先根据需要丢弃尽可能多的空白字符，直到找到第一个非空白字符。然后，从这个字符开始，取一个可选的初始加号或减号，后跟尽可能多的数字，并将其解释为数值。
字符串可以在构成整数的字符之后包含其他字符，这些字符将被忽略，并且对该函数的行为没有影响。
如果str中的第一个非空白字符序列不是有效的整数，或者由于str为空或仅包含空白字符而不存在此类序列，则不执行转换。
如果无法执行有效转换，则返回零值。如果正确的值超出可表示值的范围，则返回INT_MAX（2147483647）或INT_MIN（-2147483648）。

Python
class Solution(object):
    def myAtoi(self, s):
        """
        :type str: str
        :rtype: int
        """
        s = s.strip()
        sign = 1
        if not s:
            return 0
        if s[0] in ["+", "-"]:
            if s[0] == "-":
                sign = -1
            s = s[1:]
        ans = 0
        for c in s:
            if c.isdigit():
                ans = ans * 10 + int(c)
            else:
                break
        ans *= sign
        if ans > 2147483647:
            return 2147483647
        if ans < -2147483648:
            return -2147483648
        return ans

AutoHotkey
class Solution
{
    static myAtoi(s)
    {
        s := Trim(s)
        sign := 1
        if not s
            return 0
        s := StrSplit(s, "")
        ; In函数只能用拆分恒等替代，在Sinet库中有更强大的Sinet.In函数
        if s[1] == "+" || s[1] == "-"
        {
            if s[1] == "-"
                sign := -1
            ; 切分这里用循环替代
            tmp := ""
            loop s.length - 1
                tmp .= s[A_Index + 1]
            s := StrSplit(tmp, "")
        }
        ans := 0
        for c in s
        {
            ; ahk的int转换类型函数名为integer
            if isdigit(c)
                ans := ans * 10 + integer(c)
            else
                break
        }
        ans *= sign
        if ans > 2147483647
            return 2147483647
        if ans < -2147483648
            return -2147483648
        return ans
    }
}
; Check Solution
; msgBox Solution.myAtoi("-124534")

第九题 回文数

Determine whether an integer is a palindrome. Do this without extra space.
确定整数是否为回文。在没有额外空间的情况下执行此操作。

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

一些提示：
负整数可以是回文吗？(即, -1)
如果您正在考虑将整数转换为字符串，请注意使用额外空间的限制。
您也可以尝试反转整数。但是，如果您已经解决了“反向整数”问题，您就知道反向整数可能会溢出。你会如何处理这种情况？
有一种更通用的方法来解决这个问题。

Python
class Solution(object):
    # normal way
    def _isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        z = x
        y = 0
        while x > 0:
            y = y * 10 + x % 10
            x /= 10
        return z == y
    
    # faster way
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0 or (x != 0 and x % 10 == 0):
            return False
        half = 0
        while x > half:
            half = half * 10 + x % 10
            x /= 10
        return x == half or half / 10 == x

AutoHotkey
; 这道题都是自然转换，没有特殊处理
class Solution
{
    ; normal way
    static _isPalindrome(x)
    {
        z := x
        y := 0
        while x > 0
        {
            y := y * 10 + mod(x, 10)
            x //= 10
        }
        return z == y
    }
    
    ; faster way
    static isPalindrome(x)
    {
        if x < 0 or (x != 0 and mod(x, 10) == 0)
            return False
        half := 0
        while x > half
        {
            half := half * 10 + mod(x, 10)
            x //= 10
        }
        return x == half or half // 10 == x
    }
}
; Check Solution
; msgBox Solution._isPalindrome(1210121)

第十题 正则表达式匹配

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).
实现正则表达式匹配，并支持“.”和“*”。
'.' 匹配任何单个字符。
“*”与前面的元素中的零个或多个匹配。
匹配应该覆盖整个输入字符串（而不是部分）。

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Python
class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
        dp[0][0] = True
        for j in range(1, len(p) + 1):
            if p[j - 1] == "*":
                dp[0][j] = dp[0][j - 2]
        
        for i in range(1, len(s) + 1):
            for j in range(1, len(p) + 1):
                if p[j - 1] != "*":
                    dp[i][j] = dp[i-1][j-1] and (s[i -1] == p[j - 1] or p[j - 1] == ".")
                else:
                    dp[i][j] = dp[i][j - 2] or dp[i - 1][j] and (p[j - 2] == s[i - 1] or p[j - 2] == ".")
        return dp[-1][-1]

AutoHotkey
; ahk没有range函数，这里提供一个简单版本，在Sinet库中有更好的Range函数
range(length)
{
    arr := []
    loop length
        arr.push(A_Index-1)
    return arr
}

class Solution
{
    static isMatch(s, p)
    {
        ; 这里还是建议对单行表达式拆分，ahk有单行loop表达式，但不建议初学者使用
        dp := []
        for _ in range(strlen(s) + 1)
        {
            tmp := []
            loop strlen(p) + 1
                tmp.push(False)
            dp.push(tmp)
        }
        ; 注意索引更替
        dp[1][1] := True
        ; 时刻注意ahk的String类型不存在索引访问，Sinet库中的Str类型可以
        s := StrSplit(s, "")
        p := StrSplit(p, "")
        ; 我并不想写太复杂的Range公式，就利用索引偏移简化了
        for j in range(p.length)
            if p[j + 1] == "*"
                dp[1][j + 2] := dp[1][j]
        
        for i in range(s.length)
            for j in range(p.length)
            {
                if p[j + 1] != "*"
                    dp[i + 2][j + 2] := dp[i + 1][j + 1] and (s[i + 1] == p[j + 1] or p[j + 1] == ".")
                else
                    dp[i + 2][j + 2] := dp[i + 2][j] or dp[i + 1][j + 2] and (p[j] == s[i + 1] or p[j] == ".")
            }
        return dp[-1][-1]
    }
}
; Check Solution
; msgBox Solution.isMatch("ab", ".*")

第十一题 盛最多水的容器

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

给定n个非负整数a1，a2。。。，an，其中每个代表坐标（i，ai）处的一个点。
绘制n条垂直线，使线i的两个端点位于（i，ai）和（i，0）。
找到两条线，这两条线与x轴一起构成一个容器，使容器包含最多的水。

注意：容器不能倾斜，n至少为2。

Python
class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        ans = left = 0
        right = len(height) - 1
        while left < right:
            ans = max(ans, (right - left) * min(height[left], height[right]))
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1
        return ans

AutoHotkey
class Solution
{
    static maxArea(height)
    {
        ans := left := 1
        right := height.length
        while left < right
        {
            ans := max(ans, (right - left) * min(height[left], height[right]))
            if height[left] <= height[right]
                left += 1
            else:
                right -= 1
        }
        return ans
    }
}
; Check Solution
; msgBox Solution.maxArea([1,2,3,5,7,8,1,2])

第十二题 整数转罗马数字

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
给定一个整数，将其转换为罗马数字。
输入保证在1到3999之间。

Python
class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        ans = ""
        values = {"M": 1000, "D": 500, "C": 100, "L": 50, "X": 10, "V": 5, "I": 1}
        literals = ["M", "D", "C", "L", "X", "V", "I"]
        for idx in [0, 2, 4]:
            k = num / values[literals[idx]]
            re = (num % values[literals[idx]]) / values[literals[idx + 2]]
            ans += k * literals[idx]
            if re >= 9:
                ans += literals[idx + 2] + literals[idx] 
            elif re >= 5:
                ans += literals[idx + 1] + (re - 5) * literals[idx + 2]
            elif re == 4:
                ans += literals[idx + 2] + literals[idx + 1]
            else:
                ans += re * literals[idx + 2]
            num %= values[literals[idx + 2]]
        return ans
        

AutoHotkey
class Solution
{
    static intToRoman(num)
    {
        ans := ""
        ; 注意ahk注意字典创建方式，python写法在ahk中视为创建Object对象
        values := map("M", 1000, "D", 500, "C", 100, "L", 50, "X", 10, "V", 5, "I", 1)
        literals := ["M", "D", "C", "L", "X", "V", "I"]
        for idx in [1, 3, 5]
        {
            k := num // values[literals[idx]]
            re := (mod(num, values[literals[idx]])) // values[literals[idx + 2]]
            ; 注意ahk字符串没有乘法，因此用循环替代
            ; 注意ahk字符串拼接方式为 . 而不是 +
            loop k
                ans .= literals[idx]
            if re >= 9
                ans .= literals[idx + 2] . literals[idx] 
            else if re >= 5
                ans .= literals[idx + 1] . (re - 5) * literals[idx + 2]
            else if re == 4
                ans .= literals[idx + 2] . literals[idx + 1]
            else
                loop re
                    ans .= literals[idx + 2]
            num := mod(num, values[literals[idx + 2]])
        }
        return ans
    }
}
; Check Solution
; msgBox Solution.intToRoman(300)

第十三题 罗马数字转整数

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
给定一个罗马数字，将其转换为整数。
输入保证在1到3999之间。

Python
class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        d = {"I":1, "V": 5, "X":10,"L":50,"C":100, "D":500, "M":1000}
        ans = 0
        for i in xrange(0, len(s) - 1):
            c = s[i]
            cafter = s[i + 1]
            if d[c] < d[cafter]:
                ans -= d[c]
            else:
                ans += d[c]
        ans += d[s[-1]]
        return ans

AutoHotkey
; ahk没有xrange函数，这里提供一个简单版本，在Sinet库中有更好的Range函数
xrange(length)
{
    arr := []
    loop length
        arr.push(A_Index-1)
    return arr
}

class Solution
{
    static romanToInt(s)
    {
        ; 注意ahk注意字典创建方式
        d := map("I", 1, "V", 5, "X", 10, "L", 50, "C", 100, "D", 500, "M", 1000)
        ans := 0
        s := StrSplit(s, "")
        for i in xrange(s.length - 1)
        {
            c := s[i + 1]
            cafter := s[i + 2]
            if d[c] < d[cafter]
                ans -= d[c]
            else
                ans += d[c]
        }
        ans += d[s[-1]]
        return ans
    }
}
; Check Solution
; msgBox Solution.romanToInt("IX")

第十四题 最长公共前缀

Write a function to find the longest common prefix string amongst an array of strings.
编写一个函数，在字符串数组中查找最长的公共前缀字符串。

Python
class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ""
        i = 0
        j = 0
        end = 0
        while j < len(strs) and i < len(strs[j]):
            if j == 0:
                char = strs[j][i]
            else:
                if strs[j][i] != char:
                    break
                
            if j == len(strs) - 1:
                i += 1
                j = 0
                end += 1
            else:
                j += 1

        return strs[j][:end]

AutoHotkey
class Solution
{
    static longestCommonPrefix(strs)
    {
        if strs.length == 0
            return ""
        ; 这里需要做个处理，将strs内的字符串拆分为array类型
        for i in strs
            strs[A_Index] := StrSplit(i, "")
        i := 1
        j := 1
        end := 1
        ; 注意循环中的索引变化
        while j <= strs.length and i <= strs[j].length
        {
            if j == 1
                char := strs[j][i]
            else
                if strs[j][i] != char
                    break
                
            if j == strs.length
            {
                i += 1
                j := 1
                end += 1
            }
            else
                j += 1
        }
        tmp := ""
        for i in strs[j]
        {
            if A_Index == end
                break
            tmp .= i
        }
        return tmp
    }
}
; Check Solution
; strs := ["flower","flow","flight"]
; msgBox Solution.longestCommonPrefix(strs)
; strs := ["dog","racecar","car"]
; msgBox Solution.longestCommonPrefix(strs)

第十五题 三数之和

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
给定一个由n个整数组成的数组S，S中是否有元素a、b、c使得 a + b + c = 0?
在给出零和的数组中查找所有唯一的三元组。
注意：解决方案集不得包含重复的三元组

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Python
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        for i in xrange(0, len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            target = 0 - nums[i]
            start, end = i + 1, len(nums) - 1
            while start < end:
                if nums[start] + nums[end] > target:
                    end -= 1  
                elif nums[start] + nums[end] < target:
                    start += 1
                else:
                    res.append((nums[i], nums[start], nums[end]))
                    end -= 1
                    start += 1
                    while start < end and nums[end] == nums[end + 1]:
                        end -= 1
                    while start < end and nums[start] == nums[start - 1]:
                        start += 1
        return res

AutoHotkey
; ahk没有xrange函数，这里提供一个简单版本，在Sinet库中有更好的Range函数
xrange(length)
{
    arr := []
    loop length
        arr.push(A_Index-1)
    return arr
}

class Solution
{
    static threeSum(nums)
    {
        res := []
        ; ahk关于python的sort函数的替代办法
        for i in nums
        {
            index := A_Index
            for j in nums
            {
                if index < A_Index && i > j
                {
                    temp := nums[index]
                    nums[index] := nums[A_Index]
                    nums[A_Index] := temp
                }
            }
        }
        for i in xrange(nums.length)
        {
            if i > 0 and nums[i + 1] == nums[i]
                continue
            target := 0 - nums[i + 1]
            start := i + 2, end := nums.length
            while start < end
            {
                if nums[start] + nums[end] > target
                    end -= 1
                ; 注意ahk是else if，不是elif
                else if nums[start] + nums[end] < target
                    start += 1
                else
                {
                    ; ahk没有元组类型，这里用array类型替代
                    res.push([nums[i + 1], nums[start], nums[end]])
                    end -= 1
                    start += 1
                    while start < end and nums[end] == nums[end + 1]
                        end -= 1
                    while start < end and nums[start] == nums[start - 1]
                        start += 1
                }
            }
        }
        return res
    }
}
; Check Solution
; 为了便于测试我引入比较简单的Print办法，Sinet库中有更强的Print
; print Solution.threeSum([-1, 0, 1, 2, -1, -4])

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 an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
给定一个由n个整数组成的数组S，在S中查找三个整数，使总和最接近给定的数字目标。
返回三个整数的总和。您可以假设每个输入将恰好有一个解决方案

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Python
class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        ans = 0
        diff = float("inf")
        for i in xrange(0, len(nums)):
            start, end = i + 1, len(nums) - 1
            while start < end:
                sum = nums[i] + nums[start] + nums[end]
                if sum > target:
                    if abs(target - sum) < diff:
                        diff = abs(target - sum)
                        ans = sum
                    end -= 1
                else:
                    if abs(target - sum) < diff:
                        diff = abs(target - sum)
                        ans = sum
                    start += 1
        return ans

AutoHotkey
; ahk没有xrange函数，这里提供一个简单版本，在Sinet库中有更好的Range函数
xrange(length)
{
    arr := []
    loop length
        arr.push(A_Index-1)
    return arr
}

class Solution
{
    static threeSumClosest(nums, target)
    {
        ; ahk关于python的sort函数的替代办法
        for i in nums
        {
            index := A_Index
            for j in nums
            {
                if index < A_Index && i > j
                {
                    temp := nums[index]
                    nums[index] := nums[A_Index]
                    nums[A_Index] := temp
                }
            }
        }
        ans := 0
        ; 这里用0x7fffffff替代最大值
        diff := 0x7fffffff
        for i in xrange(nums.length)
        {
            start := i + 2, end := nums.length
            while start < end
            {
                sum := nums[i + 1] + nums[start] + nums[end]
                if sum > target
                {
                    if abs(target - sum) < diff
                    {
                        diff := abs(target - sum)
                        ans := sum
                    }
                    end -= 1
                }
                else
                {
                    if abs(target - sum) < diff
                    {
                        diff := abs(target - sum)
                        ans := sum
                    }
                    start += 1
                }
            }
        }
        return ans
    }
}
; Check Solution
; msgBox Solution.threeSumClosest([-1,2,1,-4], 1)

第十七题 电话号码的字母组合（内含DFS算法）

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
给定一个数字字符串，返回该数字可能代表的所有可能的字母组合。
下面给出了数字到字母的映射（就像在电话按钮上一样）。

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
注：虽然上面的答案是按字典顺序排列的，但你的答案可以按你想要的任何顺序排列。

Python
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if len(digits) == 0:
            return []
            
        d = {1: "", 2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"}
        
        def dfs(digits, index, path, res, d):
            if index == len(digits):
                res.append("".join(path))
                return 
        
            digit = int(digits[index])
            for c in d.get(digit, []):
                print(d.get(digit, []))
                path.append(c)
                dfs(digits, index + 1, path, res, d)
                path.pop()
        
        res = []
        dfs(digits, 0, [], res, d)
        return res
print(Solution().letterCombinations("23"))

AutoHotkey
class Solution
{
    static letterCombinations(digits)
    {
        if strlen(digits) == 0
            return []
        ; 注意ahk字典创建方式与python不同
        d := map(1, "", 2, "abc", 3, "def", 4, "ghi", 5, "jkl", 6, "mno", 7, "pqrs", 8, "tuv", 9, "wxyz")
        
        dfs(digits, index, path, res, d)
        {
            ; 注意这里的偏移量
            if index == strlen(digits) + 1
            {
                ; ahk关于join函数的替换
                tmp := ""
                for i in path
                    tmp .= i
                res.push(tmp)
                return
            }
            ; 下面两个StrSplit函数都是处理字符串为array列表
            digit := integer(StrSplit(digits, "")[index])
            for c in StrSplit(d.get(digit, ""), "")
            {
                path.push(c)
                dfs(digits, index + 1, path, res, d)
                path.pop()
            }
        }
        
        res := []
        dfs(digits, 1, [], res, d)
        return res
    }
}
; Check Solution
; 为了便于测试我引入比较简单的Print办法，Sinet库中有更强的Print
; print Solution.letterCombinations(23)

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 an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
给定一个由n个整数组成的数组S，S中是否有元素a、b、c和d，使得a+b+c+d=目标？
在给出目标总和的数组中找到所有唯一的四元组。
注意：解决方案集不得包含重复的四元组。

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Python
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        for i in xrange(0, len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in xrange(i + 1, len(nums)):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                start = j + 1
                end = len(nums) - 1
                while start < end:
                    sum = nums[i] + nums[j] + nums[start] + nums[end]
                    if sum < target:
                        start += 1
                    elif sum > target:
                        end -= 1
                    else:
                        res.append((nums[i], nums[j], nums[start], nums[end]))
                        start += 1
                        end -= 1
                        while start < end and nums[start] == nums[start - 1]:
                            start += 1
                        while start < end and nums[end] == nums[end + 1]:
                            end -= 1
        return res

AutoHotkey
; ahk没有xrange函数，这里提供一个简单版本，在Sinet库中有更好的Range函数
xrange(length)
{
    arr := []
    loop length
        arr.push(A_Index-1)
    return arr
}
; 整体思路与三数之和类似，没有太多注释
class Solution
{
    static fourSum(nums, target)
    {
        ; ahk关于python的sort函数的替代办法
        for i in nums
        {
            index := A_Index
            for j in nums
            {
                if index < A_Index && i > j
                {
                    temp := nums[index]
                    nums[index] := nums[A_Index]
                    nums[A_Index] := temp
                }
            }
        }
        res := []
        for i in xrange(nums.length)
        {
            if i > 0 and nums[i + 1] == nums[i]
                continue
            ; 采用偏移量简化xrange函数
            for j in xrange(nums.length - i - 1)
            {
                j += i + 1
                if j > i + 2 and nums[j + 1] == nums[j]
                    continue
                start := j + 2
                end := nums.length
                while start < end
                {
                    sum := nums[i + 1] + nums[j + 1] + nums[start] + nums[end]
                    if sum < target
                        start += 1
                    else if sum > target
                        end -= 1
                    else
                    {
                        res.push([nums[i + 1], nums[j + 1], nums[start], nums[end]])
                        start += 1
                        end -= 1
                        while start < end and nums[start] == nums[start - 1]
                            start += 1
                        while start < end and nums[end] == nums[end + 1]
                            end -= 1
                    }
                }
            }
        }
        return res
    }
}
; Check Solution
; 为了便于测试我引入比较简单的Print办法，Sinet库中有更强的Print
; print Solution.fourSum([-1, 0, 1, 2, -1, -4], 0)

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
}

第十九题 删除链表的倒数第N个结点

Given a linked list, remove the nth node from the end of list and return its head.
给定一个链表，从列表末尾删除第n个节点并返回其头部。

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.
注：给定n将始终有效。试着一次完成。

Python
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head
        fast = slow = dummy

        while n and fast:
            fast = fast.next
            n -= 1
        
        while fast.next and slow.next:
            fast = fast.next
            slow = slow.next
            
        slow.next = slow.next.next
        return dummy.next
            
            
        

AutoHotkey
; Definition for singly-linked list.
class ListNode
{
    __New(x)
    {
        this.val := x
        this.next := ""
    }
}

class Solution
{
    static removeNthFromEnd(head, n)
    {
        dummy := ListNode(-1)
        dummy.next := head
        fast := slow := dummy

        while n and fast
        {
            fast := fast.next
            n -= 1
        }
        
        while fast.next and slow.next
        {
            fast := fast.next
            slow := slow.next
        }
            
        slow.next := slow.next.next
        return dummy.next
    }
}
; 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.removeNthFromEnd(a_head, 2)
; res_text := ""
; while res
; {
    ; res_text .= res.val "->"
    ; res := res.next
; }
msgBox SubStr(res_text, 1, strlen(res_text) - 2)

第二十题 有效的括号

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
给定一个只包含字符“（'，'）”、“{'、“}'、“[”和“]”的字符串，确定输入字符串是否有效。
括号必须按正确的顺序闭合，“()”和“()[]{}”都有效，但“(]”和“([)]”无效。

Python
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        d = ["()", "[]", "{}"]
        for i in xrange(0, len(s)):
            stack.append(s[i])
            if len(stack) >= 2 and stack[-2]+stack[-1] in d:
                stack.pop()
                stack.pop()
        return len(stack) == 0
        

AutoHotkey
; ahk没有xrange函数，这里提供一个简单版本，在Sinet库中有更好的Range函数
xrange(length)
{
    arr := []
    loop length
        arr.push(A_Index-1)
    return arr
}

class Solution
{
    static isValid(s)
    {
        ; 这里的原理是模拟一个栈的压入和弹出
        stack := []
        d := ["()", "[]", "{}"]
        s := StrSplit(s, "")
        for i in xrange(s.length)
        {
            stack.push(s[i + 1])
            ; inarr解释见最底下
            if stack.length >= 2 and inarr(stack[-2] . stack[-1], d)
            {
                stack.pop()
                stack.pop()
            }
        }
        return stack.length == 0
    }
}
; Check Solution
; msgBox Solution.isValid("()[]{}")
; 这里提供了一个简单的in关键字替换方案，Sinet库中的Sinet.In函数更强大
inarr(str, arr)
{
    flag := 0
    for i in arr
        if str == i
            flag := 1
    return flag
}