（6） 給定1-n的一個排列，每次操作定義為把一個數(shù)放到序列的末尾，請問把它排好順序，至少要操作多少次？

這個題好像是tc某個題的變種，也是google的面試題。tc原來的問題略微復(fù)雜一點，比方是給定一個序列，至少多少次操作轉(zhuǎn)換成另外一個序列。可是又一次編號之后等價于如上問題——google面試題好像就是上面那個描寫敘述，也可能是放到序列開頭，可是方法是一樣的。

首先，至多n次操作是能夠做到的，我們按順序把1,2,3,4……n放到末尾就能夠了。

其次，我們?yōu)槭裁匆苿?？ 假設(shè)其它數(shù)都移動好了，1不動不就完了么？

再次，假設(shè)我們某部操作把x放到了末尾，那么以后的操作肯定是把(x + 1)放到末尾，把(x + 2)放到末尾……把n放到末尾，所以要動x，比x大的那些所有都要動，一個都不能少。

于是，我們實質(zhì)是求盡可能大的一個x，把x..n都移動了。那么沒移動的那些數(shù)，必須是按順序的，也就是1..x - 1必須是按順序出如今原始序列里的，僅僅有這樣，我們動了>=x的才干形成一個排好順序的序列。

問題簡單了O(n)解決……

      int solution(vector<int> &a) {
int n = a.size(), want = 1;
	for (int i = 0; i < n; ++i) {
		if (a[i] == want) {
			++want;
		}
	}	
	// want .. n must be moved
	return n - want + 1;
}

    

（7）?給定1-n的一個排列，每次操作定義為把一個數(shù)放到序列的末尾或開頭，請問把它排好順序，至少要操作多少次？

我印象中這個題是摩根比賽的一個題的變種。與(6)很相近，可是操作種類很多其它了。延續(xù)上一個題的思路，我們終于肯定是把1..y移動倒開頭（倒序），把x..n 移動倒末尾（順序）中間的不動。問題就是中間那部分怎樣盡可能長？ 採用dp的思路。

dp[x]表示從往后能夠“連接的長度”，即x,x + 1, ...x + dp[x] - 1按順序出現(xiàn)。 那假設(shè)我們倒著循環(huán)i,有 dp[a[i]] = dp[a[i] + 1] + 1 ，然后終于結(jié)果是n - max(dp[x]), (注意右邊沒出現(xiàn)的設(shè)置為0，＋1后自己主動變?yōu)?，符合我們的定義）?

      int solution(vector<int> &a) {
int n = a.size(), m = 0;
vector<int> dp(n + 2, 0);  //使用1..n + 1 注意下標范圍
	for (int i = n - 1; i >= 0; --i) {
		m = max(m, dp[a[i]] = dp[a[i] + 1] + 1);
		
	}
	return n - m;
}