给定长度平方和的递推求阶

Question

一个写函数，给定一个整数N，返回整数数组1..N以某种方式排列，因此每2个连续数的和是一个平方。

当且仅当满足以下两个条件时，解是有效的：

范围1..n中的每个数字使用一次且仅使用一次。

[9,7,2,14,11,5,4,12,13,3,6,10,15,1,8]

检查-

   16    16     16     16     16     16     16
   /+\   /+\    /+\    /+\    /+\    /+\    /+\
[ 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8 ]
      \+/    \+/    \+/    \+/    \+/    \+/    \+/
       9     25      9     25      9     25      9


9 = 3*3
16 = 4*4
25 = 5*5

length of the returned list is n=15 and uses numbers from 1-n(15)

如果没有解，则返回null（例如，如果n=5，则数字1、2、3、4、5不能放入平方和行:1+3=4、4+5=9，但2没有对，不能链接[1,3]和[4,5]。

import java.util.*;

public class SquareSums {
   public static List<Integer> gg= new ArrayList<Integer>() ;

    public static List<Integer> buildUpTo(int n) {
        int checkCurrent=1,firstInList=1;
        while(checkCurrent<=n+1){
          boolean[] flag= new boolean[n+1];
          List<Integer> l= new ArrayList<Integer>();
          l=checker(n,checkCurrent,l,1,flag,firstInList, true);//n, prev, list, current, flag
          checkCurrent++;
          if(l.size()==n) {System.out.println("true "+ n);return l;}
        }
         return null;
}
  public static List<Integer> checker(int num, int current,List<Integer> l,int prev, boolean[] flag,int k, boolean one){
      if(l.size()==num) {return l;}
      else if(prev>num+1 || current>num) {return l;}
      if(one) {
          flag[current]=true;
          l.add(current);print(l);
          l=checker(num,1,l,current,flag,1,false);
      }
          flag[prev]=true;
          System.out.println("check if square root: "+" num1: "+prev+ " num2: "+current+" sum is: "+(prev+current)+" sqrt: "+Math.sqrt(prev+current)+ " sqrt int: "+Math.floor(Math.sqrt(prev+current)));

          if(current<flag.length &&!flag[current] && Math.sqrt(prev+current)==Math.floor(Math.sqrt(prev+current))) {
            l.add(current);print(l);
            l=checker(num,1,l,current,flag,1,false);
          }
          else {
              print(l);
              l=checker(num,k++,l,prev,flag,k,false); 
          }
    return l;
  }
  
  public static void main(String[] args) {
      List<Integer> l= buildUpTo(15);
      print(l);
      }
  static void print(List<Integer> l) {
      System.out.println(" -------------------- ");
      for(int i=0;i<l.size();i++) {
          System.out.println(l.get(i));
      }
      System.out.println(" --------------------- ");
      System.out.println(" ");
      System.out.println(" ");


  }
  }

下面是测试代码：

import org.junit.Test;
import org.junit.runners.JUnit4;
import java.util.List;

public class Tests {
    
    @Test
    public void sampleTests() {
        
        List.of(5,15,16,23,37).forEach(Check::isGood); 
    }
}

编辑：

然后，在下面发布的代码解决方案的帮助下，我对代码进行了一点编辑，但它仍然不能正常工作。

public class SquareSums {
   public static List<Integer> gg= new ArrayList<Integer>() ;

    public static List<Integer> buildUpTo(int n) {
        int checkCurrent=1;
        while(checkCurrent<=n+1){
          List<Integer> l=checker(n,checkCurrent,new ArrayList<Integer>(),1,new boolean[n+1],1);//n, prev, list, current, flag
          checkCurrent++;
          if(l.size()==n) {System.out.println("true "+ n);return l;}
        }
         return gg;
         
}
  static boolean checkPerfectSquare(double x)
  {
      double sq = Math.sqrt(x);
      return ((sq - Math.floor(sq)) == 0);
  }
  public static List<Integer> checker(int num, int current,List<Integer> l,int prev, boolean[] flag,int k){
      if(l.size()==num) {return l;}
      else if(prev>num+1 || current>num) {return l;}
      if(l.size()==0) {
          flag[current]=true;
          l.add(current);System.out.println(l);
          l=checker(num,1,l,current,flag,1);
      }
          flag[prev]=true;
          if(current<flag.length &&!flag[current] && checkPerfectSquare(prev+current)) {
            l.add(current);System.out.println(l);
            l=checker(num,1,l,current,flag,1);
            l.remove(l.size()-1);
            flag[l.size()-1]=false;
          }
          else {
              System.out.println(l);
              l=checker(num,k++,l,prev,flag,k); 
          }
    return l;
  }
  
  public static void main(String[] args) {
      List<Integer> l= buildUpTo(15);
      System.out.println("\n"+"Answer is: ");
      System.out.println(" -------------------- ");
      System.out.println(l);
      System.out.println(" -------------------- ");

      }
  }

Answer 1

我已经实现了代码，可以给你一个特别给定的范围内的连续平方和的序列。

所以你可以根据你的要求修改它。

  public static void main(String[] args) {
        //n -> 0 will be starting point
        // size-> 15 size of sequence
        //range-> range for which you want to find. Example value should include between 1 to 30
        //check-> so that now value should be repeated so

        //if you want to repeat value just remove boolean flag it will work and put all if else into one code
        getvalue(0,15, new ArrayList<>(),20,new boolean[20]);
    }
    static void getvalue(int n, int size, ArrayList<Integer> ar, int range, boolean check[]) {
        if(n==size)
        {
            System.out.println(ar);
            return;
        }
        for (int i = 1; i < range; i++) {
            if (ar.size() == 0) {
                ar.add(i);
                check[i] = true;
                getvalue(n+1,size, ar,range, check);
                check[i] = false;
            }
            else if(check[i]==false)
            {
                int val=ar.get(ar.size()-1);
                if(checkPerfectSquare(val+i))
                {
                    check[i]=true;
                    ar.add(i);
                    getvalue(n+1,size, ar,range, check);
                    ar.remove(ar.size()-1);
                    check[i]=false;
                }
            }
        }
    }
    static boolean checkPerfectSquare(double x)
    {
        double sq = Math.sqrt(x);
        return ((sq - Math.floor(sq)) == 0);
    }

您也可以在这里查看->https://github.com/murari99732/solutionleetcode-adventofcode/blob/master/practicealgo/src/concretivesquare.java