LeetCode day9

4 minutes read
LeetCode
#LeetCode
views 672 words

202. Happy Number

Topic: Hash Table, Math

Write an algorithm to determine if a number n is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Return True if n is a happy number, and False if not.

Example: 

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

Approach1

遍历 n 的每一位是个套路模板：

while n != 0:
    deal(n % 10) # 处理末位数字
    n /= 10 # 把自身除10
def isHappy(n: int) -> bool:
    # 初始化 visited
    visited = set()
    # 当 n != 1，并且没见过 n 时进行判断
    while n != 1 and n not in visited:
        # 把 n 放入 visited
        visited.add(n)
        # 计算下一轮的数字
        nxt = 0
        # 计算 n 的各位数字平方和
        while n != 0:
            nxt += (n % 10) ** 2
            n //= 10
        # 把下一轮的数字设定为 n
        n = nxt
    # 判断 n 的最终结果是否为 1
    return n == 1

Approach2

my, faster but space for time

def isHappy(n: int) -> bool:
    visited = set()

    while n != 1 and n not in visited:
        visited.add(n)
        s = str(n)
        tmp = [int(i)**2 for i in s]
        n = sum(tmp)
        if n == 1:
            return True
    return n ==1

204. Count Primes

Topic: Hash Table, Math

Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Approach1

厄拉多塞筛法: 把满足条件的数留下来，把不满足条件的数筛掉. 0,1不是质数, 所以由2开始, 选中2, 划去所有2的倍数, 然后下一个未被划去的数是3, 划去所有3的倍数, 下一个未被划去的数是5, …以此类推.

7d1d460357a7d0bca1ea99aec455377243013c65b16f64efefe3639f86af555f-100以内的质数筛选-埃式筛法

23d348bef930ca4bb73f749500f664ccffc5e41467aac0ba9787025392ca207b-1

def countPrimes(n: int) -> int:
    # 最小的质数是 2
    if n < 2:
        return 0

    isPrime = [1] * n
    isPrime[0] = isPrime[1] = 0   # 0和1不是质数，先排除掉

    # 下面的思路是在 2 到 根号n 的范围内，当一个数是质数，将它所有的比n小的倍数设置成0
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            isPrime[i * i:n:i] = [0] * ((n - 1 - i * i) // i + 1)
    # 现在每个质数位的flag为1，其余的位数为0.由于不需要知道质数是什么只要总数，因此直接返回list里面所有1的和就行
    return sum(isPrime)

Approach2

my

def countPrimes(n: int) -> int:
    isPrimes = [1] * n
    res = 0
    for i in range(2, n):
        if isPrimes[i] == 1: 
            res += 1
        
        j = i
        while i * j < n:
            isPrimes[i * j] = 0
            j += 1
    return res

206. Reverse Linked List

Topic: Linked list

Reverse a singly linked list.

Example:

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

Follow up:

  • A linked list can be reversed either iteratively or recursively. Could you implement both?

Approach1

iter:

使用一个变量记录前驱pre, 一个变量记录后继next, 不断更新current.next = pre 就好了

def reverseList(head: ListNode) -> ListNode:
    # print(head) # ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}}}
    if not head: return None
    prev = None
    cur = head
    while cur:
        print(prev, '-----')
        '''
None -----
ListNode{val: 1, next: None} -----
ListNode{val: 2, next: ListNode{val: 1, next: None}} -----
ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}} -----
ListNode{val: 4, next: ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}} -----
        '''
        cur.next, prev, cur = prev, cur, cur.next
    return prev

Approach2

recur:

def reverseList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    nextNode = self.reverseList(head.next)
    head.next.next = head
    head.next = None
    return nextNode

217. Contains Duplicate

Topic: Array, Hash Table

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Approach1

my

def containsDuplicate(self, nums: List[int]) -> bool:
    visited = set()
    for i in nums:
        if i in visited:
            return True
        visited.add(i)
    return False

Approach2

neat

def containsDuplicate(nums: List[int]) -> bool:
    return len(nums) > len(set(nums))