LeetCode 1718. 构建字典序最大的可行序列（贪心+回溯）

Michael阿明

发布于 2021-09-06 10:47:31

5610

发布于 2021-09-06 10:47:31

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

给你一个整数 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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/construct-the-lexicographically-largest-valid-sequence 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

贪心，从大数往小的找，回溯找到一个解就是最大的。

class Solution {
	int N;
	vector<int> res;
public:
    vector<int> constructDistancedSequence(int n) {
    	N = n;
    	vector<int> ans(2*n-1);
        vector<bool> visnum(n+1, 0);
    	dfs(ans, 0, visnum);
    	return res;
    }
    void dfs(vector<int>& ans, int idx, vector<bool>& visnum)
    {
        if(!res.empty())//因为是从大往小找的，找到一个答案就是最大的
            return;
    	if(idx == ans.size())
    	{
    		res = ans;
    		return;
    	}
        if(ans[idx])//idx处已经填过数字，直接下一个
            dfs(ans, idx+1, visnum);
        else
            for(int num = N; num >= 1; num--)
            {
                if(visnum[num]) continue; // 数字填过
                if(!ans[idx] && num == 1)
                {
                    ans[idx] = num;
                    visnum[num] = true;
                    dfs(ans, idx+1, visnum);
                    visnum[num] = false;
                    ans[idx] = 0;
                }
                else if(!ans[idx] && num > 1 && idx+num < ans.size()
                        && !ans[idx+num])
                {
                    ans[idx] = ans[idx+num] = num;
                    visnum[num] = true;
                    dfs(ans, idx+1, visnum);
                    visnum[num] = false;
                    ans[idx] = ans[idx+num] = 0;
                }
            }
    }
};

4 ms 6.2 MB C++

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/04/17 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https