LeetCode 15 - 20 记录

15

https://leetcode.com/problems/3sum/

求所有满足三数之和为 0 的子数组。

这道题主要是利用双指针来做。

from typing import List
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        leng = len(nums)
        if (nums == None or leng < 3):
            return res
        nums.sort() # sort the nums list
        for i in range(leng):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i - 1]: # remove the dumplicated
                continue
            # double pointers
            L = i + 1
            R = leng - 1
            while L < R:
                sum = nums[i] + nums[L] + nums[R]
                if sum == 0:
                    res.append([nums[i], nums[L], nums[R]])
                    while L < R and nums[L] == nums[L + 1]:
                        L = L + 1
                    while L < R and nums[R] == nums[R - 1]:
                        R = R - 1
                    L = L + 1
                    R = R - 1
                elif sum < 0:
                    L = L + 1
                else:
                    R = R - 1
        return res

if __name__ == '__main__':
    solu = Solution()
    input = [-1,0,1,2,-1,-4]
    output = solu.threeSum(input)
    print(output)

16

https://leetcode.com/problems/3sum-closest/

求三数之和最接近给定的 target 的情况。返回找到的三个数之和。

依然是双指针。

from typing import List
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = nums[0] + nums[1] + nums[2]
        for i in range(len(nums)):
            start = i + 1
            end = len(nums) - 1
            while start < end:
                sum = nums[i] + nums[start] + nums[end]
                if abs(target - sum) < abs(target - res):
                    res = sum
                if sum > target:
                    end = end - 1
                elif sum < target:
                    start = start + 1
                else:
                    return res
        return res
if __name__ == '__main__':
    solu = Solution()
    input = [-1,2,1,-4]
    target = 1
    output = solu.threeSumClosest(input, target)
    print(output)

17

from typing import List
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = []
        if len(digits) == 0 or digits == None:
            return  res
        mydict = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
        # print(len(digits))
        res = [[] for i in range(len(digits))]
        # print(res)
        res[0] = [s for s in mydict[digits[0]]]
        for i in range(1, len(digits)):
            for mystr in res[i - 1]:
                for s in mydict[digits[i]]:
                    res[i].append(mystr + s)
        return res[len(digits) - 1]

if __name__ == '__main__':
    solu = Solution()
    input = "23" 
    input = ""
    input = "2"
    output = solu.letterCombinations(input)
    print(output)

直观的想法是把这个电话号码的组合想象成一棵树，根节点是一个空字符串，然后根据输入的数字，一层一层地向下面生长。但是，这个和那种简单地暴力循环一样，是不容易实现的。注意到，这里的最终的结果字符串是有顺序的，所以，我们可以把上一次的结果暂存起来，然后把接下来一次的所有情况给遍历一下，生成新的一次的情况，直至最后得到想要的结果。上面的代码是把所有的中间结果都存储了起来。但是，实际上，我们只需要 size 为 2 的数组。因此，下面的代码进行了优化：

from typing import List
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = []
        if len(digits) == 0 or digits == None:
            return  res
        mydict = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
        # print(len(digits))
        res = [[] for i in range(len(digits))]
        # print(res)
        res[0] = [s for s in mydict[digits[0]]]
        for i in range(1, len(digits)):
            for mystr in res[i - 1]:
                for s in mydict[digits[i]]:
                    res[i].append(mystr + s)
        return res[len(digits) - 1]

if __name__ == '__main__':
    solu = Solution()
    input = "23" 
    input = ""
    input = "2"
    output = solu.letterCombinations(input)
    print(output)

18

from typing import List
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        res = set()
        nums.sort()
        # print(nums)
        for i in range(len(nums) - 3):
            num1 = nums[i]
            # print('num1:', num1)
            for j in range(i + 1, len(nums) - 2):
                num2 = nums[j]
                left = j + 1
                right = len(nums) - 1
                while left < right:
                    num3 = nums[left]
                    num4 = nums[right]
                    sum = num1 + num2 + num3 + num4
                    # print('sum:', sum)
                    if sum == target:
                        res.add((num1, num2, num3, num4))
                        left = left + 1
                    elif sum > target:
                        right = right - 1
                    else:
                        left = left + 1
        res = [list(each) for each in res]
        return res

if __name__ == '__main__':
    solu = Solution()
    input = [1, 0, -1, 0, -2, 2]
    input = [2, 2, 2, 2, 2]
    target = 0
    target = 8
    output = solu.fourSum(input, target)
    print(output)

一言以蔽之，双指针。

注意一点，最后要去重。所以我一开始使用了 set，最后再转化成 list。可是，这样似乎有效率问题，而且，本题应该有更好的方法。抽时间研究。

19

# use fast and slow pointer
# this method can't be forgot any more!!
from typing import Optional, List
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        slow = head
        fast = head
        for i in range(n):
            fast = fast.next
        if fast == None:
            return slow.next
        while fast.next != None:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return head

def generate_linked_list(data:List):
    nodelist = []
    for d in data:
        nodelist.append(ListNode(d))
    for i in range(len(nodelist) - 1):
        nodelist[i].next = nodelist[i + 1]
    return nodelist[0]

def print_linked_list(head:ListNode):
    cursor = head
    print('Linked List: ', end='')
    while cursor != None:
        print(cursor.val, end=' ')
        cursor = cursor.next
    # print('head: ', head.val)
    print()

if __name__ == '__main__':
    headlist = [1, 2, 3, 4, 5]
    head = generate_linked_list(headlist)
    print('before removed:')
    print_linked_list(head)
    # print_linked_list(head)
    solu = Solution()
    n = 2
    res = solu.removeNthFromEnd(head, n)
    print('after removed:')
    print_linked_list(res)

经典快慢指针。

20

class Solution:
    def isValid(self, s: str) -> bool:
        strstack = []
        strstack.append(s[0])
        for ch in s[1:]:
            if len(strstack) == 0:
                strstack.append(ch)
                continue
            ch_lists = ['{', '[', '(']
            if strstack[-1] == '{':
                if ch == '}':
                    strstack.pop()
                    continue
                elif ch in ch_lists:
                    strstack.append(ch)
                    continue
                else:
                    return False
            if strstack[-1] == '[':
                if ch == ']':
                    strstack.pop()
                    continue
                elif ch in ch_lists:
                    strstack.append(ch)
                    continue
                else:
                    return False
            if strstack[-1] == '(':
                if ch == ')':
                    strstack.pop()
                    continue
                elif ch in ch_lists:
                    strstack.append(ch)
                    continue
                else:
                    return False
        return len(strstack) == 0

if __name__ == '__main__':
    solu = Solution()
    Input = "()"
    Input = "()[]{}"
    Input = "(]"
    Input = "([)]"
    # Input = "{[]}"
    # Input = "([])"
    Output = solu.isValid(Input)
    print(Output)

经典堆栈问题。