【C++】演算法集錦（2）：遞回精講

前言

之前是寫過一篇“遞回”的博客，但是感覺有點水，例題沒有給到位，細節也沒有點明白，所以今天再寫一遍，前面那篇就刪了吧，

從“樓梯事件”說起

在這個古老的國度，流傳著一個經久不衰的問題：爬樓梯問題，
在你面前，有N層樓梯，對于你來說，一次只能爬一層或兩層樓梯，試問，你知道自己有多少種不同的方法爬上這N層樓梯嗎？

解決方案

如果你的第一反應是暴力列舉，那是很正常的，因為我還沒學遞回的時候也是想著暴力列舉，但是列舉到后面就會發現行不通了，

不過，再沒有辦法的情況下，也只能暴力列舉，列舉一下，找出規律

先看4層樓梯的情況：

1（1） 1（2） 1（3） 1（4）
1（1） 1（2） 2（4）
1（1） 2（3） 1（4）
2（2） 1（3） 1（4）
2（2） 2（4）

括號中是爬完之后的具體層數，

我們可以發現，要一步登頂的樓層，有且僅有：2層，或者3層，
那也就是說，到達頂層（N）的方法數，就是到達（N-1）層和到達（N-2）層方法數的和，

那要怎么知道到達（N-1）層和到達（N-2）層的方法數呢？
往下遞推，到達（N-1）層的方法數就是到達（N-2）層和（N-3）層方法數的和，
遞推到什么時候結束呢，遞回到某一層的方法數可以唯一確定的時候，比方說遞推到了1層和2層，

令 dp[i] 表示能到達第 i 階的方法總數：

dp[i]=dp[i?1]+dp[i?2]

自下而上

我看到好多地方都在說什么，自上而下，自下而上，是吧，
這個遞回問題呢，我們采用自下而上的方式，為什么呢？

假設現在有10層臺階，那么自上而下的遞回方式是：

10層
8層+9層
6層+7層+7層+8層
4層+5層+5層+6層+5層+6層+6層+7層

···

這些層數，都不用去儲存的嗎？
在遞回中，每一層的狀態都要存盤到堆疊空間中

我試過30層這樣遞回下去，堆疊空間直接爆了，

記憶化

那又什么辦法來消除這些重復項呢？有的，采用遞回記憶化的方式，也就是備忘錄模式，

為了消除上述情況中的重復計算，其中一個想法是將中間結果存盤在快取中，以便我們以后可以重用它們，而不需要重新計算，

這個想法也被稱為記憶化，這是一種經常與遞回一起使用的技術，

我們可以使用哈希表來跟蹤每個以 n 為鍵的 F(n) 的結果， 散串列作為一個快取，可以避免重復計算， 記憶化技術是一個很好的例子，它演示了如何通過增加額外的空間以減少計算時間，

現在，我們只需要存盤30個遞回堆疊了，

這就是最優方案了嗎？很顯然，并不是，我們還可以精益求精，

如果說，4層 = 3層+2層，那我們為什么不給它倒過來呢？

1層+2層 = 3層
2層+3層 = 4層

···

這是斐波那契數列，在這里，也不需要啥記憶化了，咱只需要儲存兩個節點就行了，又快，

所以最后的代碼實作為：

代碼實作

int climbStairs(int n) {
    if(n == 1)
        return 1;

    int n1 = 1,n2 = 2;
    int temp = n2;

    while(n>2){
        temp = n1+temp;
        n1 = n2;
        n2 = temp;
        n--;
    }
    return temp;
}

遞回的解題步驟

當你的技術已經爐火純青的時候，自然是可以一眼就看出其中的遞推關系式，
但現實是我們很多人還沒到那個水平，
所以還是老老實實的一步一步來吧，

1、明確你要干嘛
2、明確遞回的結束條件
3、尋找遞推關系式
4、注意邊界條件與呼叫方式

遞回精練

1、列印楊輝三角的第k行

代碼實作：

	vector<int> getRow(int rowIndex) {
        vector<int> ret(rowIndex+1,0);

        ret[0] = 1;
        if (rowIndex == 0)
            return ret;

        for (int j = 1; j <= rowIndex; j++) {
            for (int i = j-1; i >0; i--) {
                ret[i] = ret[i - 1] + ret[i];
            }
            ret[j] = 1;
        }
        return ret;
    }

2、合并兩個有序鏈表

如題，

代碼實作：

	ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == NULL) {
            return l2;
        }
        else if (l2 == NULL) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

3、快速排序

雙邊遍歷

這個方法呢，如果對快慢指標和雙指標不是很了解的朋友可以現在了解一下，

首先啊，確定基準為4，左指標指向第一個元素，右指標指向尾巴，

右指標開始，向前遍歷，找到第一個大于基準的元素就停下，輪到左指標，同理，

當兩個指標都停下之后，將兩個指標所指向的值互換位置，

重復上述步驟直到左右指標重合，

重合之后，將基準元素與左右指標當前位置元素進行互換，

一次回圈之后，重復上述動作，對劃分出的部分再次回圈，直到每個部分都只有一個元素為止，

單邊遍歷

這個是快慢指標實作，

這個mark，是慢指標，快指標沒標出來，，依舊找好了基準，快指標從慢指標后一位開始快速遍歷，直到遍歷到小于基準元素的元素時停滯，

將慢指標前移一位，將當前快慢指標位置元素互換（如果重疊就算了），然后快指標繼續向后走，

重復上述步驟直到左右指標重合，

重合之后，將基準元素與左右指標當前位置元素進行互換，

一次回圈之后，重復上述動作，對劃分出的部分再次回圈，直到每個部分都只有一個元素為止，

雙邊回圈代碼實作

#include<iostream>
#include<vector>

using namespace std;

void doubleSideSort(vector<int> &vec1,int left,int right)	//序列與左右指標傳入
{
	//結束語
	if (right == left)
		return;

	//基準確定
	int flag = vec1[left];

	int keep_right = right;
	int keep_left = left;
	int change_temp;

	//當左右指標還沒重合
	while (left<right)
	{
		//左指標先走
		while (left<right && vec1[left]<=flag)
		{
			left++;
		}//當遇到比基準大的數，停下來

		//輪到右指標走
		while (left < right && vec1[right] >= flag)	//可以都等，反正最后都會歸并
		{
			right--;
		}//當遇到比基準小的數，停下來

		if (left < right)
		{
			change_temp = vec1[left];
			vec1[left] = vec1[right];
			vec1[right] = change_temp;
		}

		//然后繼續回圈
	}

	//left--;

	//接著將基準放進去，此時必定是左右相合，則左值若大于左值左邊一位，和左值左邊一位換，若小，則和左值換
	if (vec1[left] > vec1[left - 1])
	{
		vec1[keep_left] = vec1[left-1];
		vec1[left-1] = flag;
	}
	else
	{
		vec1[keep_left] = vec1[left];
		vec1[left] = flag;
	}

	doubleSideSort(vec1,0,left-1);
	doubleSideSort(vec1, right, keep_right);
}

int main()
{
	vector<int> vec1 = { 4,6,8,7,9,3,1};	//測驗用2個數測驗最直觀，因為最后都要通過這一步才能正常
	int left = 0;
	int right = vec1.size() - 1;

	doubleSideSort(vec1, left, right);

	for (; left <= right; left++)
		cout << vec1[left] << " ";
	cout << endl;

	return 0;
	
}

2、單邊回圈代碼實作

void oneSideSort(vector<int>& vec1, int slow, int hight)
{
	//設定退出條件
	if (slow >= hight)
		return;

	//將標志位留住
	int flag = vec1[slow];

	int keep_slow = slow;
	int keep_hight = hight;

	//使用快指標遍歷，將小于標志位的前移
	for (int quick = slow + 1; quick <= hight; quick++)
	{ 
		if (vec1[quick] < flag)
		{ 
			slow++;
			int change_temp = vec1[slow];
			vec1[slow] = vec1[quick];
			vec1[quick] = change_temp;
		} 
	}
	vec1[keep_slow] = vec1[slow];
	vec1[slow] = flag;

	oneSideSort(vec1, keep_slow,slow-1);
	oneSideSort(vec1,slow+1, keep_hight);
}

int main()
{
	vector<int> vec1 = {2,1,2,3};	//測驗用2個數測驗最直觀，因為最后都要通過這一步才能正常
	int left = 0;
	int right = vec1.size() - 1;

	oneSideSort(vec1, left, right);

	for (; left <= right; left++)
		cout << vec1[left] << " ";
	cout << endl;

	return 0;
	
}

我講明白了嗎？