BeautifulArrangementII [source code]

public class BeautifulArrangementII {
static
/******************************************************************************/
class Solution {
    int[] res;
    boolean found = false;

    public int[] constructArray(int n, int k) {
        int[] ar = new int[n];
        for (int i = 0; i < n; i++)
            ar[i] = i + 1;
        permute(ar, 0, k);
        return res;
    }

    public void permute(int[] ar, int start, int k) {
        if (start == ar.length - 1 || found)
            return;
        int count = countK(ar);
        if (count == k) {
            res = Arrays.copyOf(ar, ar.length);
            found = true;
            return;
        }
        for (int i = start; i < ar.length; i++) {
            if (found)
                return;
            swap(ar, i, start);
            permute(ar, start + 1, k);
            swap(ar, i, start);
        }
    }

    public void swap(int[] ar, int i, int j) {
        int tmp = ar[i];
        ar[i] = ar[j];
        ar[j] = tmp;
    }

    public int countK(int[] ar) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < ar.length - 1; i++)
            set.add(ar[i + 1] - ar[i]);
        return set.size();
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        BeautifulArrangementII.Solution tester = new BeautifulArrangementII.Solution();
    }
}

这个题目看题目介绍还是感觉挺牛逼的, 不过想了半天最后为一想到的办法就是backtracking; 然后大概瞄了一眼discussion, 发现甚至有4liner就能解决的, 感觉backtracking肯定是想复杂了; 而且这个题目属于是一个identical domain的题目, 以前也碰到过几次, 当时都是有特殊方法做的, 这里不知道能不能也一样的;

但是这里用backtracking的一个重要的问题是这里的n实际上的范围非常的大, 如果用backtracking最后复杂度会完全无法控制;

最后还是大概根据backtracking的思路写出来一个, 但是这个最后是超时了, 因为这个算法本身的复杂度很高, 所以最后超时的input其实并不大;

92  
80

暂时是没有办法, 只能重新想别的思路;

虽然这个方法最后超时了, 不过还是实践了一些之前练习过技术, 比如backtracking当中的premature exit; 这个这里的实现方式实际上也非常的简单, 直接一个全局的flag来当做标志就行了; 需要注意的是, 这个flag, 不仅要在base case当中判断, 而且还要在fanning当中判断(不过好像不在fanning当中判断也可以, 不对, 判断了要好一些, fanning当中, 即使是Empty的iteration, 最后还是会给复杂度做贡献, 这个本身就是fanning思维的核心);

另外permutation在这里的使用可以认为是利用了identical domain这个性质;

Problem Description

Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1 to n and obeys the following requirement:
Suppose this list is [a1, a2, a3, ... , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] has exactly k distinct integers.

If there are multiple answers, print any of them.

Example 1:

Input: n = 3, k = 1  
Output: [1, 2, 3]  
Explanation: The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.

Example 2:

Input: n = 3, k = 2  
Output: [1, 3, 2]  
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.

Note:

• The n and k are in the range 1 <= k < n <= 10^4.

Difficulty:Medium
Total Accepted:1K
Total Submissions:2.2K
Contributor: CDY_Saikou
Companies
google
Related Topics
array
Similar Questions
Beautiful Arrangement