本文共 1657 字，大约阅读时间需要 5 分钟。

找出最小的 n>1，使得存在一个存储了 [1, n] 的某个排列的循环数组，数组中任意相邻两项之和都是完全平方数。

题解：构造一个无向图，循环数组中的每一个元素作为图中的点，图中的每一个点的值与它的邻接点的值相加为平方和，利用回溯法找图中的哈密顿回路（一次经过图中的所有点（只经过一次）并能回到出发点的回路）。我们逐渐增大图的大小，找图中的哈密顿回路，第一个能找到哈密顿回路的图大小即为最小的n

class Solution {
       public int getAns(){
           for(int i=1;i
   
     ans = new LinkedList<>();    Map
    
     > edge = new HashMap<>();    Set
     
       nums = new HashSet<>();    public map(int n) {
           searched = new boolean[n];        int max = (int) Math.sqrt((double)n*(n-1)/2);        for (int i = 2; i < max; i++) {
               nums.add(i * i);        }        //哈希存储图中每个点的邻接点        for (int i = 1; i <= n; i++) {
               ArrayList
      
        To = new ArrayList<>();            for (int x : nums) {
                   if (x - i != i&&x-i>0&&x-i<=n) {
                       To.add(x - i);                }            }            edge.put(i, To);        }    }    //求图中的哈密顿回路    public void dfs(int pos, int n) {
           if (found)            return;        if (ans.size() == n) {
               //判断终点与起点能否向连接            if (!ans.isEmpty()&&nums.contains(pos + ans.peekFirst())) {
                   found = true;            }        }        for (int x : edge.get(pos)) {
               if (!searched[x - 1]) {
                   ans.addLast(x);                searched[x - 1] = true;                dfs(x, n);                if(!found) {
                       ans.pollLast();                    searched[x - 1] = false;                }            }        }    }}
      
     
    
   

运行结果：

[3, 6, 30, 19, 17, 32, 4, 21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13]n=32

转载地址：http://kosl.baihongyu.com/