序列相关的趣题 之三

（6） 给定1-n的一个排列，每次操作定义为把一个数放到序列的末尾，请问把它排好顺序，至少要操作多少次？

这个题好像是tc某个题的变种，也是google的面试题。tc原来的问题略微复杂一点，比方是给定一个序列，至少多少次操作转换成另外一个序列。可是又一次编号之后等价于如上问题——google面试题好像就是上面那个描写叙述，也可能是放到序列开头，可是方法是一样的。

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

其次，我们为什么要移动1？ 假设其它数都移动好了，1不动不就完了么？

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

于是，我们实质是求尽可能大的一个x，把x..n都移动了。那么没移动的那些数，必须是按顺序的，也就是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的一个排列，每次操作定义为把一个数放到序列的末尾或开头，请问把它排好顺序，至少要操作多少次？

我印象中这个题是摩根比赛的一个题的变种。与(6)很相近，可是操作种类很多其它了。延续上一个题的思路，我们终于肯定是把1..y移动倒开头（倒序），把x..n 移动倒末尾（顺序）中间的不动。问题就是中间那部分怎样尽可能长？ 採用dp的思路。

dp[x]表示从往后能够“连接的长度”，即x,x + 1, ...x + dp[x] - 1按顺序出现。 那假设我们倒着循环i,有 dp[a[i]] = dp[a[i] + 1] + 1 ，然后终于结果是n - max(dp[x]), (注意右边没出现的设置为0，＋1后自己主动变为1，符合我们的定义） 

      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;
}