Permutation Sequence@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"
Given n and k, return the k^th permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
» Solve this problem

小小感叹一下，最近老是犯困，刷题太慢，智商又捉急，那群一周刷完leetcode的娃们佩服毅力，总是刷一会儿玩儿一会儿，真想踹自己。

   嗯好吧，第一个按照之前permutation的思路，老解法递归去做，时间超了，显然就不行了。和之前permutation不同的是，它不需要把所有的permutation都输出，所以只需要找到这个东东排序的规律就好啦。所以直接loop搞起。

后一种做法，数学找规律，就是按照k和n来计算每一位是哪个数字，思路不难，就是中间细节处理麻烦。比如第一个数字是 k/(n-1)!, 然后再同样去考虑后面n-1个数。

	class Solution {
	public:
	int count=0;
	void findPermute(int n, int k, int step, int &count, string &solution, string &res, vector<int> &visited)
	{
	if(step==n)
	{
	count++;
	if(count==k)
	{
	res.assign(solution);
	}
	return;
	}
	for(int i=1; i<=n; i++)
	{
	if(visited[i-1]==0)
	{
	visited[i-1]=1;
	solution.push_back(i+'0');
	findPermute(n, k, step+1, count, solution, res, visited);
	visited[i-1]=0;
	solution.pop_back();
	}
	}
	}
	string getPermutation(int n, int k) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(n==0) return "0";
	string solution, res;
	vector<int> visited(n,0);
	int count=0;
	findPermute(n, k, 0, count, solution, res, visited);
	return res;
	}
	};

view raw Permutation Sequence @recursion hosted with ❤ by GitHub

	class Solution {
	public:
	string getPermutation(int n, int k) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	vector<int> nums(n);
	int permCount =1;
	for(int i =0; i< n; i++)
	{
	nums[i] = i+1;
	permCount *= (i+1);
	}
	// change K from (1,n) to (0, n-1) to accord to index
	k--;
	string targetNum;
	for(int i =0; i< n; i++)
	{
	permCount = permCount/ (n-i);
	int choosed = k / permCount;
	targetNum.push_back(nums[choosed] + '0');
	//restruct nums since one num has been picked
	for(int j =choosed; j< n-i; j++)
	{
	nums[j]=nums[j+1];
	}
	k = k%permCount;
	}
	return targetNum;
	}
	};

view raw Permutation Sequence hosted with ❤ by GitHub