有道算法题之一

 

 

一个大公司的笔试题目如下:

  题目如下: 写一个类，实现这样一个方法，此方法给定两个参数N、L（均为整数） N是一个自然数，L表示一个长度。要求此函数输出一个最小长度的连续数的数组，此数组的几个连续数的和要等于给定的N，并且该数组的长度 要大于等于给定的L。如没有满足该条件的则返回一个空数组{}。

eg1: (18，3)则应该return {5,6,7}; 分析满足和为18的连续数的数组有两个：{3，4，5，6}、{5，6，7} 应题目要求输出最短的数组，所以结果如上。

eg2: (18,4) 则应该返回结果{3,4,5,6};

eg3:(45,10)则返回结果为{0，1，2，3，4，5，6，7，8，9}；

 

本人尝试着写出了一个算法,现在贴出来,跟大家讨论一下.希望大家提供最好的解决方案.

package cn.edu.ccnu.inc.algorithm;

/**
 * 题目如下: 写一个类，实现这样一个方法，此方法给定两个参数N、L（均为整数） N是一个自然数，L表示一个长度。要求此函数输出一个最小长度的连续
 * 数的数组，此数组的几个连续数的和要等于给定的N，并且该数组的长度 要大于等于给定的L。如没有满足该条件的则返回一个空数组{}。 eg1:
 * (18，3)则应该return {5,6,7}; 分析满足和为18的连续数的数组有两个：{3，4，5，6}、{5，6，7}
 * 应题目要求输出最短的数组，所以结果如上。 eg2: (18,4) 则应该返回结果{3,4,5,6}; eg3:
 * (45,10)则返回结果为{0，1，2，3，4，5，6，7，8，9}；
 *
 * @author 桂子山上一棵草
 * @email :[e-mail]
 * @date 2009年10月21日
 *
 */

public class NL {

 static int min; // 记录连续数组的最小长度

 static int start; // 最小连续数组的起始位置

 public static void showResults(int N, int L)
 {
  int array[] = new int[N + 1];
  for (int i = 0; i <= N; i++)
  { // 如: array[3] ={0,1,2,3}
   array[i] = i; // 初始化

  }
  int total = 0;
  int num = 0;
  for (int i = 0; i <= N; i++)
  {
   total += array[i];
   num++;
   if (total == N && num >= L)
   {
    System.out.print("找到了一组结果:");
    int k = i - num + 1;
    if (min == 0)
    {
     min = num;
     start = k;
    } else if (num < min)
    {
     min = num;
     start = k;
    }
    while (k <= i)
    {
     System.out.print(array[k] + "  ");
     k++;
    }
    System.out.println("");
   }
   if (total > N)
   {
    total = 0;
    i = i - num + 1;
    num = 0;
   }
  }
  if (min == 0)
  {
   System.out.println("{}");
  } else
  {
   System.out.print("最小长度连续数组为: ");
   int i = 0;
   System.out.print("{");
   while (i < min)
   {
    System.out.print(" " + array[start + i]);
    i++;
   }
   System.out.print("}");
  }
 }

 public static void main(String[] args)
 {

  int N = 45;
  int L = 3;
  showResults(N, L);

 }

}

 

 

测试结果如下:

 

评论

1 楼 slowman 2009-10-23  

怎么没有人讨论一下呢。