Joyce' Blog
0%

spiral-matrix-ii & permutation-sequence

发表于

题目描述

给定一个正整数 n，生成一个包含 1 到 $n^2$ 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

题解

与上次螺旋矩阵思路类似，还是按照顺时针的顺序，先把空填了，再按顺序读出来。看起来效率还不错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
vector<vector<int>> generateMatrix(int n) {
	vector<vector<int>> res;
	int **tmp = new int*[n];
	for (int i = 0; i < n; i++)
		tmp[i] = new int[n];
	int i = 0, j = 0;
	int base_i = 0, base_j = 0;
	int value = 1;
	int m = n;
	int p = n;

	while (true)
	{
		while (j < p)
		{
			tmp[i][j] = value++;
			j++;
		}
		j = p - 1;
		base_i++;
		if (base_i == m)break;
		i = base_i;
		while (i < m)
		{
			tmp[i][j] = value++;
			i++;
		}
		i = m - 1;
		p--;
		if (p == base_j)break;
		j = p - 1;
		while (j >= base_j)
		{
			tmp[i][j] = value++;
			j--;
		}
		j = base_j;
		m--;
		if (base_i == m)break;
		i = m - 1;
		while (i >= base_i)
		{
			tmp[i][j] = value++;
			i--;
		}
		i = base_i;
		base_j++;
		if (base_j == p)break;
		j = base_j;
	}
	for (int i = 0; i < n; i++)
	{
		vector<int> k;
		for (int j = 0; j < n; j++)
			k.push_back(tmp[i][j]);
		res.push_back(k);
	}
	return res;
}

题目描述

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

  1. “123”

  2. “132”

  3. “213”
  4. “231”
  5. “312”
  6. “321”

给定 n 和 k，返回第 k 个排列。

说明：

给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。

题解

有一说一，我觉得我的思路不错。不用挨着找出每个排列，而是计算k与(n-1)! 的关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int fac(int n)
{
	if (n == 1)return 1;
	return n * fac(n - 1);
}
string res = "";
void getNext(vector<char>& number, int n, int k)
{
	if (n == 1)
	{
		res = res + number[0];
		return;
	}
	int f = fac(n - 1);
	int w = (k - 1) / f;
	res = res + number[w];
	number.erase(number.begin() + w);
	getNext(number, n - 1, k-w*f);
}
string getPermutation(int n, int k) {
	vector<char> number;
	for (int i = 1; i <= n; i++)
		number.push_back('0'+i);
	getNext(number, n, k);
	return res;
}