construct-the-lexicographically-largest-valid-sequence

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an integer <code>n</code>, find a sequence with elements in the range <code>[1, n]</code> that satisfies all of the following:

<ul>
	<li>The integer <code>1</code> occurs once in the sequence.</li>
	<li>Each integer between <code>2</code> and <code>n</code> occurs twice in the sequence.</li>
	<li>For every integer <code>i</code> between <code>2</code> and <code>n</code>, the distance between the two occurrences of <code>i</code> is exactly <code>i</code>.</li>
</ul>

The distance between two numbers on the sequence, <code>a[i]</code> and <code>a[j]</code>, is the absolute difference of their indices, <code>|j - i|</code>.

Return the lexicographically largest sequence. It is guaranteed that under the given constraints, there is always a solution. 

A sequence <code>a</code> is lexicographically larger than a sequence <code>b</code> (of the same length) if in the first position where <code>a</code> and <code>b</code> differ, sequence <code>a</code> has a number greater than the corresponding number in <code>b</code>. For example, <code>[0,1,9,0]</code> is lexicographically larger than <code>[0,1,5,6]</code> because the first position they differ is at the third number, and <code>9</code> is greater than <code>5</code>.

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:

<pre>
Input: n = 5
Output: [5,3,1,4,3,5,2,4,2]
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 20</code></li>
</ul>

constructDistancedSequence

Construct the Lexicographically Largest Valid Sequence

The Number of Beautiful Subsets

the-number-of-beautiful-subsets

美丽子集的数目

Find the Lexicographically Largest String From the Box I

find-the-lexicographically-largest-string-from-the-box-i

从盒子中找出字典序最大的字符串 I

Array

Backtracking

给你一个整数 <code>n</code> ，请你找到满足下面条件的一个序列：

<ul>
	<li>整数 <code>1</code> 在序列中只出现一次。</li>
	<li><code>2</code> 到 <code>n</code> 之间每个整数都恰好出现两次。</li>
	<li>对于每个 <code>2</code> 到 <code>n</code> 之间的整数 <code>i</code> ，两个 <code>i</code> 之间出现的距离恰好为 <code>i</code> 。</li>
</ul>

序列里面两个数 <code>a[i]</code> 和 <code>a[j]</code> 之间的 距离 ，我们定义为它们下标绝对值之差 <code>|j - i|</code> 。

请你返回满足上述条件中 字典序最大 的序列。题目保证在给定限制条件下，一定存在解。

一个序列 <code>a</code> 被认为比序列 <code>b</code> （两者长度相同）字典序更大的条件是： <code>a</code> 和 <code>b</code> 中第一个不一样的数字处，<code>a</code> 序列的数字比 <code>b</code> 序列的数字大。比方说，<code>[0,1,9,0]</code> 比 <code>[0,1,5,6]</code> 字典序更大，因为第一个不同的位置是第三个数字，且 <code>9</code> 比 <code>5</code> 大。

 

示例 1：

<pre>输入：n = 3
输出：[3,1,2,3,2]
解释：[2,3,2,1,3] 也是一个可行的序列，但是 [3,1,2,3,2] 是字典序最大的序列。
</pre>

示例 2：

<pre>输入：n = 5
输出：[5,3,1,4,3,5,2,4,2]
</pre>

 

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 20</code></li>
</ul>