2021/08/08

1、1137. 第 N 个泰波那契数 (opens new window)（自底向上）

波那契序列 Tn 定义如下： 
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

# 递归做法（超时）
class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        elif n == 2:
            return 1
        else:
            return self.tribonacci(n-3) + self.tribonacci(n-2) + self.tribonacci(n-1)
        
# 自底向上
class Solution:
    def tribonacci(self, n: int) -> int:
        a, b, c = 0, 1, 1
        for i in range(n):
            a, b, c = b, c, a+b+c
        return a
# 打表
class Solution:
    def tribonacci(self, n: int) -> int:
        Ts = [0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064, 15902591, 29249425, 53798080, 98950096, 181997601, 334745777, 615693474, 1132436852, 2082876103]
        return Ts[n]

2、剑指 Offer 09. 用两个栈实现队列 (opens new window)

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

class MinStack:
    def __init__(self):
        self.A, self.B = [], []
    def push(self, x: int) -> None:
        self.A.append(x)
        if not self.B or self.B[-1] >= x:
            self.B.append(x)
    def pop(self) -> None:
        if self.A.pop() == self.B[-1]:
            self.B.pop()
    def top(self) -> int:
        return self.A[-1]
    def min(self) -> int:
        return self.B[-1]

3、剑指 Offer 30. 包含min函数的栈 (opens new window)

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

class CQueue:

    def __init__(self):
        self.stack_A = []
        self.stack_B = []
    def appendTail(self, value: int) -> None:
        self.stack_A.append(value)
    def deleteHead(self) -> int:
        if self.stack_B:
            return self.stack_B.pop()
        if not self.stack_A:
            return -1;
        while(self.stack_A):
            self.stack_B.append(self.stack_A.pop())
        return self.stack_B.pop()

2021/08/09

1、剑指 Offer 06. 从尾到头打印链表 (opens new window)

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        stack = []
        while(head != None):
            stack.append(head.val)
            head = head.next
        return stack[::-1]

2、剑指 Offer 24. 反转链表 (opens new window)

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        point1 = None
        point2 = head
        while point2:
            cur = point2
            point2 = point2.next
            cur.next = point1
            point1 = cur
        return point1
            

3、剑指 Offer 35. 复杂链表的复制 (opens new window)

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

4、313. 超级丑数 (opens new window)（动态规划）

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。
给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。
题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        dp = [0] * (n+1)
        dp[1] = 1
        len_primes = len(primes)

        # pointers记录质数应该与哪个丑数做乘积
        pointers = [1] * len_primes 
        
        for i in range(2, n+1):
            list1 = []
            for j in range(len_primes):
                list1.append(dp[pointers[j]] * primes[j])
            
            min_num = min(list1)
            dp[i] = min_num
            for j in range(len_primes):
                if dp[pointers[j]] * primes[j] == min_num:
                    pointers[j] += 1
        return dp[n]

参考资料

• 常见面试算法题突击手册：https://github.com/yifeikong/interview