leetcode 21-30

21.合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。

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

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        ans = ListNode(0)
        tmp = ans
        while l1 and l2:
            if l1.val <= l2.val:
                tmp.next = l1
                tmp = l1
                l1 = l1.next
            else:
                tmp.next = l2
                tmp = l2
                l2 = l2.next
        if l1: tmp.next = l1
        if l2: tmp.next = l2
        return ans.next

22.括号生成

给出n代表生成括号的对数，要求生成所有可能并且有效的括号组合。

class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """

        def dfs(L, R, s, ans):
            if L < 0 or R < 0 or L > R:
                return
            if L == 0 and R == 0:
                ans.append(s)
                return
            dfs(L-1, R, s+'(', ans)
            dfs(L, R-1, s+')', ans)

        ans = []
        dfs(n, n, '', ans)
        return ans

23.合并K个排序链表

合并K个排序链表，返回合并后的排序链表。

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

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """

        def merge(self, A, B):
            X = ListNode(0)
            t = X
            while A and B:
                if A.val <= B.val:
                    t.next = A
                    t = A
                    A = A.next
                else:
                    t.next = B
                    t = B
                    B = B.next
            if A: t.next = A
            if B: t.next = B
            return X.next

        ans = []
        if not lists: return ans
        while len(lists) > 1:
            for i in range(0, len(lists), 2):
                j = i+1
                if j < len(lists):
                    t = merge(lists[i], lists[j])
                    ans.append(t)
                else:
                    ans.append(lists[i])
            lists = ans
            ans = []
        return lists[0]

24.两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

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

class Solution:
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        ans = ListNode(0)
        tmp = ans
        stk = []
        while head:
            stk.append(head)
            head = head.next
            if len(stk) == 2:
                for j in range(2):
                    t = stk.pop()
                    tmp.next = t
                    tmp = t
        while stk:
            t = stk.pop()
            tmp.next = t
            tmp = t
        tmp.next = None
        return ans.next

25.K个一组翻转链表

给出一个链表，每K个节点一组进行翻转，并返回翻转后的链表。K为正整数，它的值不超过链表长度。如果节点数不是K的倍数，那么最后整余节点保持原来的顺序。

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

class Solution:
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        ans = ListNode(0)
        tmp = ans
        stk = []
        while head:
            stk.append(head)
            head = head.next
            if len(stk) == k:
                for i in range(k):
                    t = stk.pop()
                    tmp.next = t
                    tmp = t
        while stk:
            t = stk.pop(0)
            tmp.next = t
            tmp = t
        tmp.next = None
        return ans.next

26.删除排序数组中的重复项

给定一个排序数组，原地删除重复出现的元素，返回新数组的长度。

class Solution:
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = -1
        j = 0
        while j < len(nums):
            if i < 0 or nums[i] != nums[j]:
                i += 1
                nums[i] = nums[j]
            j += 1
        return i+1

27.移除元素

给定一个数组nums和一个值val，原地移除所有数值等于val的元素，返回新数组的长度。注意，元素的顺序可以改变，不需要考虑数组中超出新长度后面的元素。

class Solution:
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        i, j, k = 0, len(nums)-1, 0
        while i <= j:
            while i <= j and nums[i] != val:
                i += 1
            while i <= j and nums[j] == val:
                j -= 1
                k += 1
            if i <= j:
                nums[i], nums[j] = nums[j], nums[i]
                k += 1
                i += 1
                j -= 1
        return len(nums)-k

28.实现strstr()

给定一个haystack字符串和一个needle字符串，在haystack中找出第一次出现needle的位置，如不存在则返回-1。

class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        try:
            idx = haystack.index(needle)
        except ValueError:
            idx = -1
        return idx

29.两数相除

给定两个32位有符号的整数，返回它们的商，保证除数不为0。如果溢出，则返回最大值。

class Solution:
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        ret = abs(dividend) // abs(divisor)
        if dividend * divisor < 0:
            ret = -ret
        ret = min(ret, 2**31-1)
        return ret

30.与所有单词相关联的字串

给定一个字符串s和一些长度相同的单词words，在s中找出可以恰好串联words中所有单词的子串的起始位置。注意子串要与words中的单词完全匹配，中间不能有其他字符，但顺序不做要求。

class Solution:
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        if not words: return []
        std = sorted(words)
        siz = len(words[0])
        cnt = len(words)
        ans = []
        for i in range(0, len(s)-siz*cnt+1):
            tmp = []
            for j in range(i, i+siz*cnt, siz):
                tmp.append(s[j:j+siz])
            tmp.sort()
            if tmp == std:
                ans.append(i)
        return ans