6

我正在练习面试算法，并在职业杯和SO上遇到了这个问题 。

Ex: 1235 (split it 1,2,3,5) Ex: 12122436(split 12,12,24,36) 给定一个范围找到所有加法序列号？

以下是我尝试过的，我知道它效率不高，并且不确定它的复杂性。此外，它没有找到我感兴趣的 53811 和 12122436 之类的数字。如果有人能指导我正确的方向或想出更简单有效的方法，我将非常感激。谢谢！

#include <stdio.h>

void check_two_num_sum(int,int);
void check_sum(int);
int flag = 0;

int main(){

int high,low;
printf("Enter higher range\n");
scanf("%d",&high);
printf("Enter lower range\n");
scanf("%d",&low);
check_two_num_sum(high,low);

return 0;
}

void check_two_num_sum(int high, int low)
{
  flag=0;
  for(low;low<high;low++)
  {
    check_sum(low);  
    if(flag==1)
    {
       printf("this value has additive sequence %d \n",low);
       flag = 0; 
     }
  }
}

void check_sum(int input)
{
   int count = 1;
   int capture, result, temp_res=0, n=0;

   if(n==0){
    result = input%10;
        n++;
        input = input/10;
        capture = input;
    }

   while(input!=0)
   {
     temp_res = temp_res + input%10;    

     if(count ==2)
      {
         if(result == temp_res)
          { 
         if(capture < 100)
        {       flag = 1;
                    break; 
        }

         else{
              check_sum(capture);
        }
           }

          else {
          break;
        }
        } 
    count++;
    input = input/10;
  }
}
4

2 回答 2

1

我不确定它的效率如何，但我可能会尝试一些递归的东西。

例如，53811

指向字符串的结尾，比如说。

Var2 = 1
Var1 = 1

检查是否Var0等于Var2 - Var1

1 - 1不等于8，所以这个函数链被终止。

在函数的下一个链中，Var2等于最后两位数字，11;Var1 = 8

检查是否Var0等于Var2 - Var1

11 - 8等于3所以这个函数链继续Var2 = 8：Var1 = 3

检查是否Var0等于Var2 - Var1

8 - 3等于5，这也是字符串的结尾，所以函数返回True


基本情况似乎是指针位于字符串的开头或无法测试可行的变量。在每个连接点，Var2都会Var1相应地改变以开始一个新的链；Var0是从另外两个推导出来的。

于 2013-11-12T23:02:49.997 回答
0

假设原始序列的长度为n。一个明显可行的方法是强行枚举第一个和第二个元素的长度，并在线性时间内检查它是否正确。这种方法需要O(n ^ 3)时间。

您声称您的方法需要O(n)时间，但从您的实施来看，我怀疑您是否n表示原始序列的长度。

于 2013-11-12T05:35:37.890 回答