[leetcode]第二十二部分(139-145)

139. Word Break

问题难度: ♣ ♣ ♣

问题描述

给定一个非空的字符串s和一个包含非空单词列表的词典wordDict,判断其是否能被分割为一个或多个使用空格分隔的词典单词序列.

注意:

词典中的相同单词可以在分词中多次重复使用. 可以假设词典中不包含重复的单词.

示例1

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
解释: 由于 "leetcode" 可以被分割为 "leet code", 因此返回true.

示例2

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
解释: 由于 "applepenapple" 可以被分割为: "apple pen apple", 因此返回true.注意: 我们可以重复使用字典中的单词.

示例3

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

解题思路

暴力破解法

用递归的方法进行求解,对于当前字符串:

  • 如果其在dict中或者长度为0, 则直接返回true
  • 否则, start = 0, current = "", 当遇到currentdict中时, 继续遍历

然后…超时了.好吧, 思考一下减少判断的方法…

记忆法

将一个记忆数组memo[i]定义为范围为[0, i)的子字符串是否可以拆分,初始化为-1,表示没有计算过,如果可以拆分,则赋值为1,反之为0

动态规划法

emmm…还是那句话, 所有字符串的问题都可以用动态规划法进行求解. 首先, 形式化问题: 使用dp[i]用来存储[0,i)之间是否可拆, 假设中间存在一个j, 使得[0,j)并且s[j:i] in wordDict即可.

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        m = len(s)
        memo = [-1 for _ in range(m+1)]
        word_set = set()
        for word in wordDict:
            word_set.add(word)
        def helper(start):
            if start >= m:
                return True
            if memo[start] != -1:
                return memo[start] == 1
            for i in range(start + 1, m + 1):
                if s[start: i] in word_set and helper(i):
                    memo[start] = 1
                    return True
            memo[start] = 0
            return False
        return helper(0)

    def wordBreakDP(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        num = len(s)
        dp = [False for _ in range(num+1)]
        dp[0] = True
        word_set = set()
        for word in wordDict:
            word_set.add(word)
        for i in range(num + 1):
            for j in range(i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break
        return dp[-1]

140. Word Break II

问题难度: ♣ ♣ ♣ ♣ ♣

问题描述

给定一个非空的字符串s和一个包含非空单词列表的词典wordDict,在s中增加空格来构造一个句子, 其中句子中的每个单词都是一个有效的词典单词, 返回所有可能的句子.

注意:

词典中的相同单词可以在分词中多次重复使用. 可以假设词典中不包含重复的单词.

示例1

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

示例2

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
解释: 注意-我们可以重复使用字典中的单词.

示例3

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

解题思路

一般这种需要遍历所有情况的题目, 十有八九需要用递归来做.
以示例1为例, s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"], 需要进行分割:

  • cat: 继续往下遍历, sand, dog, 解决一个
  • cats: 继续向下遍历, and, dog, 解决一个

结束.

代码

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        word_dict = dict()

        def helper(s):
            if s in word_dict:
                return word_dict[s]
            if len(s) == 0:
                return [""]
            res = []
            for word in wordDict:
                if s[:len(word)] != word:
                    continue
                rem = helper(s[len(word):])
                for tmp in rem:
                    res.append(word +  ("" if len(tmp) == 0 else " ") + tmp)
            word_dict[s] = res
            return res
        return helper(s)

141. Linked List Cycle

问题难度: ♣

问题描述

给定一个链表, 判断是否有环.为了表示给定链表中的环, 我们使用一个整数的pos, 标识链表中的位置索引(从0开头)来记录结尾连到的节点. 如果pos-1. 那么说明链表中无环.

示例1

Input: head = [3,2,0,-4], pos = 1
Output: true
解释: 链表中有环, 其中结尾连向第二个节点.


示例2

Input: head = [1,2], pos = 0
Output: true
解释: 链表中有环, 其中结尾连向第一个节点.

示例3

Input: head = [1], pos = -1
Output: false
解释: 链表中无环

进一步:
能否使用O(1) (常数) 内存来解决这个问题?

解题思路

o(╯□╰)o 这道题目看了很久的题目没看懂, 既然已经给了pos了, 不就可以直接判断是否有环了吗… 然后看了看右边的示例代码, 发现…果然有猫腻! pos是肯定不会存在的. 因此, 已知条件只有一个链表.

使用两个指针fastslow, 其中fast的移动速度是slow2倍, 如果链表有环, 那么fast总有一天会和slow相遇, 否则的话, 直接返回无环.

代码

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

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None:
            return False
        fast, slow = head, head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

142. Linked List Cycle II

问题难度: ♣ ♣ ♣

问题描述

给定一个链表, 返回环开始的节点. 如果没有环, 则返回null.为了表示给定链表中的环, 我们使用一个整数的pos, 标识链表中的位置索引(从0开头)来记录结尾连到的节点. 如果pos-1. 那么说明链表中无环.

注意: 不要修改链表.

示例1

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
解释: 链表中有一个环, 结尾连到第二个节点上.

示例2

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: 链表中有一个环, 结尾连到第一个节点上.

示例3

Input: head = [1], pos = -1
Output: no cycle
Explanation: 链表中没有环.

Follow up:

能否不使用额外空间解决该问题?

解题思路

这道题目和上一道题目的解法类似, 先判定是否有环, 如果无环的话, 直接返回None, 否则, 从头开始遍历, 直到两个指针相遇为止.

代码

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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return None
        fast, slow = head, head
        has_cycle = False
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                has_cycle = True
                break
        if not has_cycle:
            return None
        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next
        return slow

143. Reorder List

问题难度: ♣ ♣ ♣

问题描述

给定一个单向链表L: L0→L1→…→Ln-1→Ln,
将其重排序为:L0→Ln→L1→Ln-1→L2→Ln-2→…

注意: 不能修改列表节点的值, 只可以修改节点本身.

示例1

给定 1->2->3->4, 将其重排为: 1->4->2->3.

示例2

给定 1->2->3->4->5, 将其重排为: 1->5->2->4->3.

解题思路

单链表没有前序指针, 因此可以先使用一个栈来存储节点, 根据节点数可以算出需要操作的次数: len(stack)/2.

具体操作如下, 将当前节点的next节点先存储下来, 然后将当前节点的next指针指向结尾节点, 然后将结尾节点指向之前的next节点.

特别注意的是: 需要将最后节点的next设置为None.

  tail = stack.pop()
  cur = head.next
  head.next = tail
  tail.next = cur
  head = cur

代码

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

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        stack = []
        cur = head
        while cur is not None:
            stack.append(cur)
            cur = cur.next
        num_iter = len(stack) / 2
        idx = 0
        cur = None
        while idx < num_iter:
            idx += 1
            tail = stack.pop()
            cur = head.next
            head.next = tail
            tail.next = cur
            head = cur
        if head is not None:
            head.next = None

144. Binary Tree Preorder Traversal

问题难度: ♣ ♣ ♣

问题描述

给定一个二叉树, 返回其节点值的前序遍历.

示例

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

Follow up:

能否同时实现迭代版和递归版?

解题思路

前序遍历的顺序为: 中-前-后, 使用一个栈来存储待访问的节点, 首先将root节点加进去, 然后进行遍历:

  • root = stack.pop(), res.append(root.val)
  • 增加新鲜血液: 如果root.left is not None, stack.append(root.left)(注意: 我们需要先遍历左边, 所以先增加右边节点. 保证下次pop时先获取左边节点)
  • 如果root.right is not None, stack.append(root.right)

这样一直遍历, 直到stack为空则停止, 最后返回res.

代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []
        stack, res = [root, ], []
        while stack:
            root = stack.pop()
            res.append(root.val)
            if root.right is not None:
                stack.append(root.right)
            if root.left is not None:
                stack.append(root.left)
        return res

145. Binary Tree Postorder Traversal

问题难度: ♣ ♣ ♣ ♣ ♣

问题描述

给定一个二叉树, 返回其节点值的后序遍历.

示例

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

Follow up:

能否同时实现迭代版和递归版?

解题思路

回顾一下, 后序遍历的顺序为左-右-中. 使用一个栈来存储待访问的节点, 首先将root节点加进去, 然后进行遍历:

  • root = stack.pop(), res.append(root.val)
  • 增加新鲜血液: 如果root.right is not None, stack.append(root.right)(注意: 我们在最终返回的时候逆序, 因此,先遍历右边, 所以先增加左边节点)
  • 如果root.left is not None, stack.append(root.left)

这样一直遍历, 直到stack为空则停止, 最后返回res[::-1]

代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []
        stack, res = [root, ], []
        while stack:
            root = stack.pop()
            res.append(root.val)
            if root.left is not None:
                stack.append(root.left)
            if root.right is not None:
                stack.append(root.right)
        return res[::-1]
打赏

mickey

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注