查找的数字串的所有整数满足一个条件 [英] Find all integers in a string of digits which meet a criteria

问题描述

我想拿出其在给定一串数字可以识别符合以下条件的整数相结合的一种算法的Java

I am trying to come up with an algorithm in Java which when given a string of digits can identify a combination of integers which meets the following criteria

• N = N1 + N2
• N> = 1> = N

where:
   N is the Nth element in the string or element at Nth position;
   N1 is the (N-1) element in the string & N2 is the (N-2) element in the string.

Example 1: 224610
Elements in this string are 2, 2, 4, 6, 10.
First Set:     2+2=4 (N2=2; N1=2 & N= 4);
Second Set: 2+4=6 (N2=2; N1=4 & N=6);
Third Set:    4+6=10 (N2=4; N1=6 & N= 10)

Example 2: 11112233558
Elements in this string are 1, 11, 12, 23, 35, 58

Example 3: 1101102203
Elements in this string are 1, 101, 102, 203.

我已经写了一个功能，可以采取整数一个ArrayList，并告诉你的阵列是否符合要求。

I have already written a function which can take an ArrayList of integers and tell you whether the array complies with the requirements.

public static boolean complies(ArrayList<Integer> al)
{
     boolean result = true;
     int alsize = al.size();

     for (int n = alsize-1; n > 1; n--)
     {
         int N1 = al.get(n-1);
         int N2 = al.get(n-2);
         int N = al.get(n);
         if (N != ( N1 + N2))
            result  = false;
         if ((N < N1) || (N1 <  N2))
            result  = false;
     }
     return(result);
}

部分我挣扎，他找到一个优雅的方式来确定哪些我可以通过上述功能运行的所有可能的整数组合。

The part I am struggling with his finding an elegant way to identify all possible integer combinations which I can run through the above function.

推荐答案

在符合由范上面的解决方案，我可以修改code排除边界情况，并为上述question.This方法解决方案始终返回true，如果它符合模式否则假的，是的，我们必须找到前两个元素，使之work.Checked的所有测试用例：

In line with the above solution from Pham I could modify the code to exclude the edge cases and create a solution for the above question.This method will always return true if it complies with the pattern else false and yes we have to find first two elements to make it work.Checked for all test cases :

public static boolean complies(String input){
    // List<Long> firstTwo = new ArrayList<Long>();
    for(int i = 1; i < input.length(); i++){
        for(int j = 0; j < i; j++){
            long first = Long.parseLong(input.substring(0, j + 1));//substring form 0 to j
            long second = Long.parseLong(input.substring(j + 1, i + 1));//substring from j + 1 to i
            if(second < first)
                  continue;

            String last = "" + first + second;
            System.out.println("first :"+first+" second :"+second);
            if(last.length() == input.length()){
                return false;
            }
           // firstTwo.add(first);
           // firstTwo.add(second);
            while(last.length() < input.length()){
                  long nxt = first + second;
                  last += nxt;
                  first = second;
                  second = nxt;
            } 
            if(last.equals(input)){//Matched!
                System.out.println("matched");
                // dont go further return true
                return true;
            }
           // firstTwo.clear();
        }
    } 
    return false;
}

这篇关于查找的数字串的所有整数满足一个条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！