[leetcode]第三十一部分(202-208)

202. Happy Number

问题难度: ♣

问题描述

写一个算法确定数字是否”快乐”.

“快乐数”的定义过程如下: 以任意正整数开头, 将数字替换为各个位数的平方和, 然后重复这个过程直到数字等于1, 或者无限循环不包含1. 以这个过程结束的数字为”快乐数”.

Example: 

Input: 19
Output: true
Explanation: 
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

解题思路

看懂了它们的定义即可. 针对数字num, 当num != 0时:

  • cur = num % 10, sum += cur ^2
  • num = num / 10

每次判断下sum是否等于1, 或者是否已经出现.

代码

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        def nextNum(num):
            num_sum = 0
            while num != 0:
                cur = num % 10
                num_sum += cur * cur
                num = num / 10
            return num_sum
        data_dict = dict()
        while True:
            n = nextNum(n)
            if n == 1:
                return True
            elif n in data_dict:
                return False
            data_dict[n] = 1
s = Solution()
n = 19
print(s.isHappy(n))
n = 18
print(s.isHappy(n))
True
False

203. Remove Linked List Elements

问题难度: ♣

问题描述

删除链表中所有值为val的元素.

示例

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

解题思路

从前往后遍历, 使用两个指针, 分别为前序节点和当前节点, 如果当前节点的值为val, 那么将当前节点指向当前节点的next, 并且将前序节点的next移动到当前节点, 再继续往前遍历即可. 需要特别注意当碰到连续val时需要继续遍历, 直到节点值不为val为止.

代码

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

class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        dummpy = ListNode(0)
        dummpy.next = head
        pre = dummpy
        while head is not None:
            while head is not None and head.val == val:
                #如果节点的值等于目标值
                head = head.next
            pre.next = head
            if head is not None:
                pre = pre.next
                head = head.next
        return dummpy.next

204. Count Primes

问题难度: ♣

问题描述

计算小于num数的质数个数.

示例

Input: 10
Output: 4
解释: 有4个小于10的质数: 2, 3, 5, 7.

解题思路

首先, 思考怎么判断一个数为质数: 除了1个它本身没别的整除数的整数. 所以逐个遍历即可. 然后…这种方法的时间复杂度果然超了…

参考了以下讨论区的做法, 使用一个数组来存储该数是否为质数, 对于当前值, 如果其为质数, 那么就更新它的倍数, 从i*in, 每次增加i. 最后求sum的总数即可.

代码

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        def check(num):
            max_num = num // 2
            for i in range(2, max_num + 1):
                if num % i == 0:
                    return False
            return True
        count = 0
        for i in range(2, n+1):
            if check(i):
                count += 1
        return count

    def countPrimesArr(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 3:
            return 0
        primes = [True] * n
        primes[0], primes[1] = False, False
        for i in range(2, n//2 + 1):
            if primes[i]:
                # start_idx, end_idx, steps
                primes[i*i : n : i] = [False] * len(primes[i*i: n: i])
        return sum(primes)
s = Solution()
n = 10
print(s.countPrimes(n))
n = 10
print(s.countPrimesArr(n))
4
4

205. Isomorphic Strings

问题难度: ♣

问题描述

给定两个字符串st, 判断他们是否为同构的.

如果替换s中的字符可以得到t, 那么这两个字符串就是同构的.

在保持字符串顺序的同时, 必须同时替换该字符串中所有的字符, 两个不同的字符无法映射到相同的字符, 但是一个字符可以映射到它自己.

示例1

Input: s = "egg", t = "add"
Output: true

示例2

Input: s = "foo", t = "bar"
Output: false

示例3

Input: s = "paper", t = "title"
Output: true

注意:
可以假设st长度相同.

解题思路

使用两个dict分别存储两个字符串之间的对应关系(s_dict/t_dict), 分别使用两个指针指向当前值, 对于当前s[i], 判断其是否在s_dict中:
– 如果在, 判断t[i] == s_dict[s[i]], 如果相等, 那么i+=1; 否则, 直接返回false
– 否则, 判断t[i]是否已经在t_dict中:
– 如果在, 直接返回false
– 否则s_dict[s[i]] = t[i], t_dict[t[i]] = s[i]

代码

class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        s_dict = dict()
        t_dict = dict()
        if len(s) != len(t):
            return False
        for i in range(len(s)):
            if s[i] in s_dict:
                if t[i] != s_dict[s[i]]:
                    return False
            else:
                if t[i] in t_dict:
                    return False
                else:
                    s_dict[s[i]] = t[i]
                    t_dict[t[i]] = s[i]
        return True
sl = Solution()
s = "egg"
t = "add"
print(sl.isIsomorphic(s, t))
s = "foo"
t = "bar"
print(sl.isIsomorphic(s, t))
s = "paper"
t = "title"
print(sl.isIsomorphic(s, t))
True
False
True

206. Reverse Linked List

问题难度: ♣

问题难度

翻转一个单向链表.

示例

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:
– 可以使用迭代法和递归法实现单向链表的翻转, 能否同时实现?

解题思路

迭代法: 使用一个栈的结构存储节点, 利用栈的特性来进行翻转.

递归法: 自己调用自己, 终止条件-如果当前节点或者next值为None直接返回当前值, 否则, 将递归调用, 再将头结点和next进行翻转, 并且将当前头结点的next设置为None.

代码

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

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        stack = []
        while head is not None:
            stack.append(head)
            head = head.next
        dummy = ListNode(0)
        cur_node = dummy
        while len(stack) > 0:
            last_node = stack.pop()
            last_node.next = None
            cur_node.next = last_node
            cur_node = cur_node.next
        return dummy.next

    def reverseListRec(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        #进行翻转
        next_node = self.reverseListRec(head.next)
        head.next.next = head
        head.next = None
        return next_node

207. Course Schedule

问题难度: ♣ ♣ ♣

问题描述

假设我们需要完成n门课, 标识为0n-1.

一些课程有一些预备知识, 例如在上课程1之前需要先上课程0, 表示为[0,1]对.

给定课程的总数n和一系列的预备课程对, 需要判断一下能否完成课程.

示例1

Input: 2, [[1,0]] 
Output: true
解释: 一共需要上2门课. 在上课程1之前需要上课程0, 因此, 我们是有可能完成课程的.

示例2

Input: 2, [[1,0],[0,1]]
Output: false
解释: 一共需要上2门课. 在上课程1之前需要完成课程0, 而完成课程0有需要完成课程1, 因此这是不可能的.

注意:
– 给定的预备课程对是一个由一系列边构成的图, 而不是连接矩阵
– 可以假设在输入的预备课程中没有重复的边

解题思路

很明显, 这是一个与 图 这个数据结构相关的题目, 最终的目的其实是想看看图中是否构成环了, 如果有环, 那么就返回false, 否则直接返回true. 在这里, 使用一个二维数组来存储节点的前序节点, 使用另一个数组来判断该节点所在的子图中是否形成环了, 在这里我们使用深度优先进行遍历.

  • 对于当前节点, 当节点未被访问过, 那么将其标识为0
  • 如果当前节点正在被访问, 将其设置为-1, 然后遍历其前序节点, 如果前序节点中出现了该节点的依赖节点, 直接返回false
  • 如果没有出现该节点, 就将值直接设置为1, 表明已经便利过了.

代码

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        graph = [[] for _ in range(numCourses)]
        visit = [0 for _ in range(numCourses)]
        # init the graph
        for i,j in prerequisites:
            graph[i].append(j)
        print(graph)
        def dfs(i):
            if visit[i] == 0:
                # node has not been visited
                visit[i] = -1
                for j in graph[i]:
                    if not dfs(j):
                        return False
                visit[i] = 1
                return True
            else:
                return visit[i] == 1
        for i in range(numCourses):
            if not dfs(i):
                return False
        return True
s = Solution()
prerequisites = [[1,0],[0,1]]
numCourses = 2
print(s.canFinish(numCourses, prerequisites))

prerequisites = [[1,0]]
print(s.canFinish(numCourses, prerequisites))
[[1], [0]]
False
[[], [0]]
True

208. Implement Trie (Prefix Tree)

问题描述

实现一个有insert, search, 以及 startsWith等方法的前缀数.

示例

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

注意:
– 可以假设所有输入都由小写字母a-z组成
– 可以假设所有输入均为非空

解题思路

这一题主要考察的是前缀树, 其实从架构上来看, 这是一个二十六叉树. 在这里, 我们需要存储一个树的结构, 当然, root第一层为空节点, 然后下面每一层为所有单词的首字母, 因此层叠下去. 最后形成一个单词树的结构.

208_TrieInsert.png

大致架构如上图所示.

其实内部结构, 这个树是由节点构成的, 每个节点有两个属性: 孩子节点以及是否为单词结尾.

下面, 我们逐个分析每个函数的操作:

insert操作: 首先, 使用current指向root节点, 遍历单词时,对于当前字母: 判断其是否在current的孩子节点中, 如果已经有了, 就不做任何处理了; 否则的话, 将当前节点加入current的孩子节点, 然后将当前节点指向当前节点的孩子节点中当前字母对应的节点: current = current.children[w]. 到达最后一个字母之后, 只需要将当前节点的is_end标识设置为true即可.

search操作: 同样地, 首先, 使用current指向root节点, 遍历单词时,对于当前字母: 判断其是否在current的孩子节点中, 如果已经有了, 则将当前节点指向当前节点的孩子节点中当前字母对应的节点: current = current.children[w]; 否则的话, 直接返回false. 到最后, 直接判断current是否为终点节点即可.

startsWith操作: 其它的操作与search相似, 最后不用判断current是否为当前节点, 直接返回True即可.

代码

class TrieNode(object):
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie(object):


    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()



    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: None
        """
        current = self.root
        for w in word:
            if w not in current.children:
                current.children[w] =  TrieNode()
            current = current.children[w]
        current.is_end = True


    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        current = self.root
        for w in word:
            if not w in current.children:
                return False
            current = current.children[w]
        return current.is_end


    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        current = self.root
        for w in prefix:
            if w not in current.children:
                return False
            current = current.children[w]
        return True



# Your Trie object will be instantiated and called as such:
obj = Trie()

obj.insert("word")
obj.insert("leet")
obj.insert("lee")
param_2 = obj.search("word")
param_3 = obj.startsWith("wo")
param_4 = obj.search("lee")
param_5 = obj.startsWith("l")


print(param_2)
print(param_3)
print(param_4)
print(param_5)

True
True
True
True
打赏

mickey

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

发表评论

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