[leetcode]第五部分

19-Remove Nth Node From End of List

问题描述

给定一个linked list,删除从列表中从末尾起的第n个节点,并且返回head

示例

Input: 1->2->3->4->5, n = 2
Output: 删除从后向前数的第2个节点,linked list 变为 1->2->3->5

注意:给定的n为有效的n

延伸:是否能在一次遍历解决该问题?

解题思路

解法1
我们先使用最常规的方式来解决这个问题,给定的是head,删除的是从后往前的第n个节点,因此首先需要遍历知道linked list的长度m,再计算需要删除从前往后数的第m-n个(从0开始计数)个节点。

解法2
上面的算法可以优化到一步完成。我们可以使用两个指针,第一个指针指向列表开头之前的前一个节点,而第二个指针也从列表头开始。现在,将后面的指针向前移动n+1步,使得这两个指针之间的距离正好是n个节点。我们通过同时向前移动两个指针来维持固定间隔,直到后面的指针到达最后一个节点。前面的指针则正好指向从后往前数的第n个节点。然后我们只要将该节点的next指向它现在的nextnext即可。

上述两种方法的时间复杂度均为O(L)L表示linked list的长度。

代码

解法1

# 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
        """
        len = self.getLen(head)
        idx = len - n
        print len, idx
        if idx < 0:
            return head
        if idx == 0:
            return head.next
        ret = ListNode(0)
        ret.next = head
        while idx > 0:
            ret = ret.next
            idx -= 1
        ret.next = ret.next.next
        return head

    def getLen(self, head):
        len = 0
        tmp = ListNode(0)
        tmp.next = head
        while tmp.next is not None:
            len += 1
            tmp = tmp.next
        return len

解法2

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dumpy = ListNode(0)
        dumpy.next = head
        first = dumpy
        second = dumpy
        while n >= 0:
            first = first.next
            n -= 1
        while first is not None:
            first = first.next
            second = second.next
        second.next = second.next.next
        return dumpy.next

20-Valid Parentheses

问题描述

给定一个只包含以下字符的字符串(,),{,},[,],判断该输入字符串是否有效。

当且仅当字符串满足下面条件时有效:
– 左边的括号必须匹配相同类型右边括号
– 匹配的顺序必须正确

注意:空字符串也是一个有效字符串。

示例1

Input: "()"
Output: true

示例2

Input: "()[]{}"
Output: true

示例3

Input: "(]"
Output: false

示例4

Input: "([)]"
Output: false

示例5

Input: "{[]}"
Output: true

解题思路

使用一个类似于堆栈的东西,来存储对应关系。遍历字符串,如果当前字符为左括号,则加到栈顶;如果当前字符为右括号,则与栈顶元素进行匹配,如果能匹配上,则弹出栈顶;否则的话直接返回无效;最后判断堆栈大小是否为0,如果为0则表示有效,否则表示无效。

代码

这里用了个小技巧,为了避免第一个字符就为右括号导致堆栈没有元素的情况,我们预先向里面加了一个#进行区分,这样就避免了分情况讨论。

class Solution(object):
    rightDict = {"}": "{", ")":"(", "]":"["}
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stackList = ['#']
        for i in range(len(s)):
            c = s[i]
            if c in self.rightDict:
                left = self.rightDict[c]
                if stackList[-1] != left:
                    return False
                else:
                    stackList = stackList[:-1]
            else:
                stackList.append(c)
        if len(stackList) == 1:
            return True
        else:
            return False

21-Merge Two Sorted Lists

问题描述

合并两个有序的linked list然后返回一个新的列表。新列表应该由前两个列表的节点连接构造而成。

示例

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

解题思路

使用两个指针,分别指向两个linked list的头部,比较当前值的大小,将retnext指向较小的值,直到遍历到某个list的结尾为止;最后将retnext指向未到结尾的指针即可。算法复杂度为O(n)nlinked list中较短的

代码

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dumpy = ListNode(0)
        head = dumpy
        while l1 is not None and l2 is not None:
            if l1.val < l2.val:
                dumpy.next = ListNode(l1.val)
                l1 = l1.next
            else:
                dumpy.next = ListNode(l2.val)
                l2 = l2.next
            dumpy = dumpy.next
        if l1 is None:
            dumpy.next = l2
        else:
            dumpy.next = l1
        return head.next

22-Generate Parentheses

问题描述

给定一个整数n,完成一个函数生成所有成对括号的组合。

例如,给定n=3,一个解决方案如下:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

解题思路

这一题可以分解到最简单的情况:
– 当n=1时,返回()
– 当n=2时,只需要在n=1的情况下添加一对括号即可,在最左边添加一个左括号,然后分别在倒数第i个左括号右边添加一个右括号,即可获得最新的组合
– 当n=3时,也可以基于n=2的情况进行组合。

代码

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if n == 1:
            return "()"
        i = 1
        parentSet = set()
        parentSet.add("()")
        while i < n:
            nowSet = set()
            for parent in parentSet:
                nowStr = "(" + parent + ")"
                nowSet.add(nowStr)
                nowStr = "()" + parent
                nowSet.add(nowStr)
                for j in range(len(parent), 1, -1):
                    if parent[j-1] == "(":
                        nowStr = "(" + parent[:j-1] + ")" + parent[j-1:]
                        nowSet.add(nowStr)
            parentSet = nowSet
            i+=1
        return list(parentSet)

23-Merge k Sorted Lists

问题描述

合并k个排好序的linked list,返回一个合并的数组。分析并描述它的复杂性。

示例

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

解题思路

最简单的思路是:维护一个长度为k的数组,分别指向当前的值,找到当前最小的值,将其添加到需要返回的链表中,并且将数组中该list对应的指针向后移动一位,然后进行下一轮遍历,这种方法的时间复杂度为:O(N*k)

代码

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        dumpyNode = ListNode(0)
        retList = dumpyNode
        currentK = self.getCurrentK(lists)
        while len(currentK) > 1:
            minIdx = 0
            minVal = currentK[minIdx].val
            for i in range(1, len(currentK)):
                nowVal = currentK[i].val
                if minVal > nowVal:
                    minVal = nowVal
                    minIdx = i
            retList.next = currentK[minIdx]
            retList = retList.next
            #print minIdx
            currentK[minIdx] = currentK[minIdx].next
            currentK = self.getCurrentK(currentK)
        if len(currentK) == 1:
            retList.next = currentK[0]
        return dumpyNode.next


    def getCurrentK(self, lists):
        retList = list()
        for i in range(len(lists)):
            if lists[i] is not None:
                retList.append(lists[i])
        return retList

24-Swap Nodes in Pairs

问题描述

给定一个链表,交换没两个相邻的节点,返回头部指针。

示例

Input: 1->2->3->4
Output: 2->1->4->3.

注意
– 只能使用一个额外的常数空间
不能修改节点的值,只能修改节点本身

解题思路

考虑只有两个节点的时候,交换两个节点:

1->2
---
tmp = 1.next
tmpNext = tmp.next
tmp.next = 1
1.next = tmpNext

特别注意:不要丢掉对1的指针链,需要使用一个额外的变量指向该zhi

代码

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dumpy = ListNode(0)
        dumpy.next = head
        nowTmp = dumpy
        while head is not None and head.next is not None:
            tmp = head.next
            tmpNext = tmp.next
            tmp.next = head
            head.next = tmpNext
            nowTmp.next = tmp
            nowTmp = head
            head = head.next
        return dumpy.next

25-Reverse Nodes in k-Group

问题描述

给定一个链表,每次反转链表的k个节点,然后返回修改后的链表。

k是一个正整数,并且小于或等于链表的长度。如果节点的数目不是k的整数倍,那么后面的节点就不用翻转了。

示例1

Input: 1->2->3->4->5 k=2
Output: 2->1->4->3->5

示例2

Input: 1->2->3->4->5 k=3
Output: 3->2->1->4->5

注意
– 只允许使用常数的内存
– 不能修改节点的值,只能修改节点本身

解决思路

翻转k个数,由于是单向链表,如果想一次翻转比较困难。那么我们应该使用分治的思想来解决:每次数到k之后就直接翻转即可,需要注意边界情况。

代码

class Solution:
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        h = ListNode(-1)
        h.next = head
        pre = h
        cur = head

        while cur != None:
            t = cur
            count = 1
            while count < k and t != None:
                t = t.next
                count += 1
            if count == k and t != None:             
                for _ in range(k - 1):
                    lat = cur.next
                    cur.next = lat.next
                    lat.next = pre.next
                    pre.next = lat 

                pre = cur
                cur = pre.next
            else:
                break

        return h.next
打赏

mickey

记录生活,写给几十年后的自己。