Top 100 Linked Question 修炼------第139题、第141题

139. Word Break

题目链接

题目解释：给出一个非空的字符串和一个包含多个单词的wordDict，判断s是否能够被划分为包含wordDIct中的单词的序列。

注意：

• 在划分的过程中，在词典中相同的单词可能会被使用多次；
• wordDict中不包含重复的元素

Example1

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example2

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

题目分析：判断一个列表的字符串是否能够组成另外一个长的字符串，那么我们可以进行对列表中的每一个字符串都进行判断，可以采用动态规划的方法，这里我们就用一个一维的dp数组，其中dp[i]表示范围[0, i)内的子串是否可以拆分，注意这里dp数组的长度比s串的长度大1，是因为我们要处理空串的情况，我们初始化dp[0]为true，然后开始遍历。注意这里我们需要两个for循环来遍历，遍历所有的子串，我们用j把[0, i)范围内的子串分为了两部分，[0, j) 和 [j, i)，其中范围 [0, j) 就是dp[j]，范围 [j, i) 就是s.substr(j, i-j)，其中dp[j]是之前的状态，我们已经算出来了，可以直接取，只需要在字典中查找s.substr(j, i-j)是否存在了，如果二者均为true，将dp[i]赋为true，，此时就不需要再用j去分[0, i)范围了，因为[0, i)范围已经可以拆分了。最终我们返回dp数组的最后一个值，就是整个数组是否可以拆分的布尔值了，代码如下：

PS：感觉动态规划还是有点难，一开始都想不到使用动态规划来解题.......

class Solution:
    def wordBreak(self, s,wordDict):
        len_s = len(s)
        # 初始化mem,将全部的位置置为False
        mem = [False]*(len_s+1)
        mem[0] = True
        for i in range(1, len_s + 1):
            for word in wordDict:
                if i >= len(word) and mem[i - len(word)] and word == s[i-len(word):i]:
                    mem[i] = True
        return mem[-1]

141. Linked List Cycle

题目链接

题目解释：给出一个链表，判断这个链表是否有环。

为了表示给定的链表里面是否有环，我们给定一个标志位pos,如果pos等于0，最后一个结点是指向头结点，如果pso= -1，那么这个给定的链表里面没有环。

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true

Example 2:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

这里只含有一个结点，pos=-1,故不含有环。

题目分析：我们需要一次遍历，然后得到最终的结果。考虑到链表有环，那么必然有结点出现两次，那么我们可以借助Python中的set来进行判断：若某个结点出现两次，那么必然是个有环链表，否则，是个无环链表：

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        nodes_seen=set()
        while head is not None:
            if nodes_seen.__contains__(head):
                return True
            else:
                # 将结点加入到set中，而不是结点的值，因为结点的值可能出现多次
                nodes_seen.add(head)
            head=head.next
        return False

时间复杂度为O(n)，空间复杂度为O(n)

那么可不可以继续优化空间复杂度呢？当然是可以的，我们可以借助于快慢指针来进行判断，

具体的见下一篇文章，eager to see......

总结

昨天搞得太晚了，导致没有更新，一直在做题，希望忙起来的时候也要记得做题，keep running，keep fighting.....