Given an integer n, find a sequence that satisfies all of the following:
- The integer
1occurs once in the sequence. - Each integer between
2andnoccurs twice in the sequence. - For every integer
ibetween2andn, the distance between the two occurrences ofiis exactlyi.
The distance between two numbers on the sequence, a[i] and a[j], is the absolute difference of their indices, |j - i|.
Return the lexicographically largest sequence. It is guaranteed that under the given constraints, there is always a solution.
A sequence a is lexicographically larger than a sequence b (of the same length) if in the first position where a and b differ, sequence a has a number greater than the corresponding number in b. For example, [0,1,9,0] is lexicographically larger than [0,1,5,6] because the first position they differ is at the third number, and 9 is greater than 5.
Example 1:
Input: n = 3 Output: [3,1,2,3,2] Explanation: [2,3,2,1,3] is also a valid sequence, but [3,1,2,3,2] is the lexicographically largest valid sequence.
Example 2:
Input: n = 5 Output: [5,3,1,4,3,5,2,4,2]
Constraints:
1 <= n <= 20
Solution: Search
Search from left to right, largest to smallest.
Time complexity: O(n!)?
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // Author: Huahua class Solution { public: vector<int> constructDistancedSequence(int n) { const int len = 2 * n - 1; vector<int> ans(len); function<bool(int, int)> dfs = [&](int i, int s) { if (i == len) return true; if (ans[i]) return dfs(i + 1, s); for (int d = n; d > 0; --d) { const int j = i + (d == 1 ? 0 : d); if ((s & (1 << d)) || j >= len || ans[j]) continue; ans[i] = ans[j] = d; if (dfs(i + 1, s | (1 << d))) return true; ans[i] = ans[j] = 0; } return false; }; dfs(0, 0); return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { private boolean dfs(int[] ans, int n, int i, int s) { if (i == ans.length) return true; if (ans[i] > 0) return dfs(ans, n, i + 1, s); for (int d = n; d > 0; --d) { int j = i + (d == 1 ? 0 : d); if ((s & (1 << d)) > 0 || j >= ans.length || ans[j] > 0) continue; ans[i] = ans[j] = d; if (dfs(ans, n, i + 1, s | (1 << d))) return true; ans[i] = ans[j] = 0; } return false; } public int[] constructDistancedSequence(int n) { int[] ans = new int[n * 2 - 1]; dfs(ans, n, 0, 0); return ans; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# Author: Huahua class Solution: def constructDistancedSequence(self, n: int) -> List[int]: l = n * 2 - 1 ans = [0] * l def dfs(i, s): if i == l: return True if ans[i]: return dfs(i + 1, s) for d in range(n, 0, -1): j = i + (0 if d == 1 else d) if s & (1 << d) or j >= l or ans[j]: continue ans[i] = ans[j] = d if dfs(i + 1, s | (1 << d)): return True ans[i] = ans[j] = 0 return False dfs(0, 0) return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment