1.反转链表

1.1迭代法,容易想到:

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* p=NULL;
        ListNode* target=head;
        while(target!=NULL&&target->next!=NULL)
        {
           p=target->next->next;
           target->next->next=head;
           head=target->next;
           target->next=p;  
        }
        return head;
    }
};

用target标记固定的链表项通过->next遍历,不断调整头节点。

1.2 递归法

最重要的是求出递归关系式,

设列表为:n1 → … → nk-1 → nk → nk+1 → … → nm → Ø

若从节点 nk+1 到 nm 已经被反转,而我们正处于 nk

n1 → … → nk-1 → nk → nk+1 ← … ← nm

我们希望 nk+1 的下一个节点指向 nk,所以,nk.next.next = nk

通过这样我们可以用递归不断解决

代码:

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        if(head==NULL||head->next==NULL)
            return head;//空链表及尾节点
        ListNode* p=reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return p;
    }
};
另注明:若是没有head->next=NULL;在递归出口前的链表节点->next可变更方向,但作为递归出口的n1将无法改
变方向指向n2,则形成循环链表,应注重代码风格的严谨和干净。

 

2. 记忆化搜索

就是用数组/哈希表/临时变量储存先前生成的计算结果避免重复计算,典型实例:计算斐波那契数列

class Solution {
public:
    int fib(int N) 
    {
        int a=1,b=1,ans=0;
        if(N==0)
            return 0;
        if(N==1||N==2)
            return 1;
        for(int i=3;i<=N;i++)
        {
            ans=a+b;
            a=b;
            b=ans;
        }
        return ans;
    }
};
或者用数组存,用java的hashmap存都可以,这是更通用的用空间换时间的做法
HashMap<Integer, Integer> cache = new HashMap<Integer, Integer>();
private int fib(int N)
{
if (cache.containsKey(N))
{ return cache.get(N); }
int result;
if (N < 2)
{ result = N; }
else
{ result = fib(N-1) + fib(N-2);
}}
  

3. 斐波那契数列的两种数学推导计算法

Binets 方法
算法
这里有一种有趣的解法,它使用矩阵乘法来得到第 n 个斐波那契数。矩阵形式如下:
[Fn+1FnFnFn−1]=[1110]
Q=[Fn+1FnFnFn−1]。按照此方法,第 n 个斐波那契数可以由 Qn−1[0,0] 给出。
让我们试着证明一下。
我们可以使用数学归纳法来证明这一方法。易知,该矩阵给出了第 3 项(基本情况)的正确结果。由于 Q2=[2111]。这证明基本情况是成立的。
假设此方法适用于查找第n个斐波那契数,即 Fn=Qn−1[0,0],那么:
Qn−1=[FnFn−1Fn−1Fn−2]
现在,我们需要证明在上述两个条件为真的情况下,该方法可以有效找出第 (n+1) 个斐波那契数,即,Fn+1=Qn[0,0]
证明:
Qn=[FnFn−1Fn−1Fn−2][1110]
Qn=[Fn+Fn−1Fn−1+Fn−2FnFn−1]
Qn=[Fn+1FnFnFn−1]
从而, Fn+1=Qn[0,0]。得证。
我们需要为我们的问题做的唯一改动就是将斐波那契数列的初始项修改为 2 和 1 来代替原来的 1 和 0 。或者,另一种方法是使用相同的初始矩阵 Q 并使用 result=Qn[0,0] 得出最后结果。发生这种情况的原因是我们必须使用原斐波那契数列的第 2 项和第 3 项作为初始项。
复杂度分析
  • 时间复杂度:O(log(n))。遍历 log(n) 位。
  • 空间复杂度:O(1)。使用常量级空间。
对时间复杂度的证明:

假设我们需要计算矩阵 Mn 次幂。假设,n 是 2 的幂。因此,n=2ii∈N,其中 N 表示自然数的集合(包括 0)。我们可以用树形结构进行表示:

Climbing Stairs

 
这意味着:Mn=Mn/2.Mn/2=….=∏1nM1
所以,要计算 Mn,我们先要计算 Mn/2 并将其与自身相乘。而为了计算 Mn/2,我们需要对 Mn/4 进行类似的操作,并依此类推。
显然,树的高度为 log2n
让我们来估计一下 Mn 计算所需要的时间。矩阵 $$M$$ 在幂运算过程中大小保持不变。因此,进行两矩阵幂乘的空间复杂度是 O(1) 。我们需要执行 log2n 次这样的乘法。所以,计算 Mn 的时间复杂度为 O(log2n)
如果数字 n 不是2的幂,我们可以使用其二进制表示将其转化为 2 的幂次项之和:
n=pP2p,where P⊂N
因此,我们可以使用以下方法获得最终结果:
Mn=pPM2p
这是我们在实现中使用的方法。 时间复杂度仍为 O(log2n),因为乘法次数的限制为 O(log2n)
 
斐波那契公式
算法
我们可以使用这一公式来找出第 n 个斐波那契数:
Fn=1/5[(21+5)n−(21−5)n]
对于给定的问题,斐波那契序列将会被定义为 F0=1F1=1F1=2Fn+2=Fn+1+Fn。尝试解决这一递归公式的标准方法是设出 Fn,其形式为 Fn=an。然后,自然有 Fn+1=an+1Fn+2=an+2,所以方程可以写作 an+2=an+1+an。如果我们对整个方程进行约分,可以得到 a2=a+1 或者写成二次方程形式 a2a−1=0
对二次公式求解,我们得到:
a=1/5((21±5))
一般解采用以下形式:
Fn=A(21+5)n+B(21−5)n
n=0 时,有 A+B=1
n=1 时,有 A(21+5)+B(21−5)=1
解上述等式,我们得到:
A=(251+5),B=(251−5)
AB 的这些值带入上述的一般解方程中,可以得到结果。
复杂度分析

  • 时间复杂度:O(log(n))pow 方法将会用去 log(n) 的时间。
  • 空间复杂度:O(1)。使用常量级空间。

尾递归: