求解决策过程(decision process)最优化的数学方法。

剑指10-1. 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

  • 避免重复计算因此使用动态算法
class Solution:
    def fib(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a % 1000000007

剑指10-2. 青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

  • 本质还是斐波那契数列
  • 注意当n=0时，因为只能不跳所以等于1（这个题的毛病不要太钻牛角尖）
class Solution:
    def numWays(self, n: int) -> int:
        ## 最后一步一定是一阶或是两节
        ## 剩一节时的方法有f(n-1)种，剩两节有f(n-2)种，则f(n)=f(n-1)+f(n-2)
        ## f(0) = 1, f(1) = 1, f(2) = 2

        a, b = 1, 1

        for _ in range(n) :
            a, b = b, a+b

        return a % 1000000007

剑指16. 从尾到头打印链表

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

解题思路：

用list顺序存储单向链表，使用切片直接倒序输出。

Tip：

  • 列表切片规则List[start:stop:step]，不加则是默认全部区间
  • List[::-1]则代表倒置列表

复杂度

  • 时间O(n)， 空间O(n)
# 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]:
        result = []

        while head:
            result.append(head.val)
            head = head.next

        return result[::-1]

剑指24. 翻转链表（中转+递归）

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

解题思路：
需要解决的问题其实有两个：1. 如何改变node之间的指向 2. 如何保存头部节点

  1. 使用中转点对上一个node保存，遍历链表同时改变指向，最后一个到达的就是新链表的头部节点
  2. 递归。只有到达最后一个节点后才开始进行翻转。这里通过返回值不停传递末节点，即新链表的头结点。
    • 传递参数：当前节点和下一节点
    • 停止条件：当前节点为空
    • 返回值：上一节点
    • 执行动作：将下一节点指向当前节点

复杂度

  • 时间：O(n)，空间：O(2)

中转站法

# 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:
        prevNode = None

        while head:
            head.next = prevNode
            prevNode = head
            head = head.next

        return prevNode
  • 时间：O(n)，
  • 空间：O(n):递归深度达到n，需要n的空间

递归

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        def recur(cur: ListNode, prev: ListNode) -> ListNode:

            ## 迭代中止：到达最后一个Node的时候next会变成None，这时返回最后一个Node
            ## 最后一个Node会变成新链表的head，使用变量进行保存
            if cur:
                head = recur(cur.next, cur)
                cur.next = prev
                return head
            else:
                return prev

        return recur(head, None)

剑指18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

时间O(n)， 空间O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if not head : return head
        if head.val == val : return head.next

        result = head 

        while 1 :
            if head.next.val == val :
                head.next = head.next.next
                break
            head = head.next

        return result

剑指22. 链表中倒数第k个字节（快慢指针）

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

遍历法很容易想到就不在这里赘述了

  • 时间O(n) 空间O(1)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        slow, fast = head, head

        for _ in range(k-1) :
            fast = fast.next

        while head and fast.next :
            slow = slow.next
            fast = fast.next

        return slow

剑指25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

  • 善用伪头结点可以减少很多步骤，如判断哪个才是头结点造成的代码行数增加
  • 因为是链表结构而非数组，因此不用考虑最后剩下的需要用while再一个个塞进去
  • 时间O(n)， 空间O(1)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:  
        head = ListNode(0)
        cur = head

        while l1 and l2 :
            if l1.val <= l2.val :
                cur.next, l1 = l1, l1.next
            else :
                cur.next, l2 = l2, l2.next
            cur = cur.next
        
        if l1 :
            cur.next = l1
        if l2 :
            cur.next = l2