LeetCode1718. 构建字典序最大的可行序列

提示给你一个整数 n ，请你找到满足下面条件的一个序列：
整数 1 在序列中只出现一次。
2 到 n 之间每个整数都恰好出现两次。
对于每个 2 到 n 之间的整数 i ，两个 i 之间出现的距离恰好为 i 。
序列里面两个数 a[i] 和 a[j] 之间的 距离 ，我们定义为它们下标绝对值之差 |j - i| 。
请你返回满足上述条件中 字典序最大 的序列。题目保证在给定限制条件下，一定存在解。
一个序列 a 被认为比序列 b （两者长度相同）字典序更大的条件是： a 和 b 中第一个不一样的数字处，a 序列的数字比 b 序列的数字大。比方说，[0,1,9,0] 比 [0,1,5,6] 字典序更大，因为第一个不同的位置是第三个数字，且 9 比 5 大。
示例 1：
输入：n = 3
输出：[3,1,2,3,2]
解释：[2,3,2,1,3] 也是一个可行的序列，但是 [3,1,2,3,2] 是字典序最大的序列。
示例 2：
输入：n = 5
输出：[5,3,1,4,3,5,2,4,2]
提示：
1 <= n <= 20# 回溯+贪心
use[i] 记录数字i是否已经使用。
ans记录本题结果，ans[i]为-1，表示未选择。
回溯的层次：2n-1。
选择列表：i = n to 1，从大到小枚举起到剪枝的效果。
回溯逻辑：
if(leve >= 2n-1) return true;
if(-1 != ans[leve]) if(Brack(leve+1) ） return true;
枚举选择
选择逻辑：
if(use[i])continue
leve2 = (1==i) ?leve : (leve+i);
if((leve2 >= 2n-1)||(-1!=ans[leve2 ]) {continue;}
user[i] = true
ans[leve] = ans[leve2 ]= i;
if(Brakc(lever+1)) return true
user[i] = false
ans[leve] = ans[leve2]= -1;

代码

核心代码

class Solution {
		public:
			vector<int> constructDistancedSequence(int n) {
				int use[21] = { 0 };
				vector<int> ans(2 * n - 1,-1);
				function<bool(int)> Brack = [&](int leve) {
					if (leve >= 2 * n - 1) { return true; }
					if (-1 != ans[leve]) { return Brack(leve + 1); }
					for (int i = n; i > 0; i--) {
						if (use[i])continue;
						int leve2 = (1 == i) ? leve : (leve + i);
						if ((leve2 >= 2 * n - 1) || (-1 != ans[leve2])) { continue; }
						use[i] = true;
						ans[leve] = ans[leve2] = i;
						if (Brack(leve + 1)) return true;
						use[i] = false;
						ans[leve] = ans[leve2] = -1;
					}
					return false;
				};
				Brack(0);
				return ans;
			}
		};

单元测试

int n;
		TEST_METHOD(TestMethod1)
		{
			n =1;
			auto res = Solution().constructDistancedSequence(n);
			AssertEx({ 1 }, res);
		}
		TEST_METHOD(TestMethod2)
		{
			n = 2;
			auto res = Solution().constructDistancedSequence(n);
			AssertEx({2, 1 ,2}, res);
		}
		TEST_METHOD(TestMethod11)
		{
			n =3;
			auto res = Solution().constructDistancedSequence(n);
			AssertEx({ 3,1,2,3,2 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			n = 5;
			auto res = Solution().constructDistancedSequence(n);
			AssertEx({ 5,3,1,4,3,5,2,4,2 }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			n = 20;
			auto res = Solution().constructDistancedSequence(n);
			AssertEx({ 20,18,19,15,13,17,10,16,7,5,3,14,12,3,5,7,10,13,15,18,20,19,17,16,12,14,11,9,4,6,8,2,4,2,1,6,9,11,8 }, res);
		}