16

我有这个序列1,2,3,4,5,6,8,10,11

预期产量为1-6,8,10-11

这个问题是关于以易于阅读的形式格式化序列

我尝试使用 c# 并使用了许多 if & else。

面试官说，有一些简单的算法可以做到这一点。

我不知道如何实现这个非常简单。

同样对于 1,2,3 我显示了 1-3。他们说错了！

此逻辑是否涉及任何设计模式（解释器）？

4

10 回答 10

16

这是一种方法：

        int[] numbers = { 1, 2, 3, 4, 5, 6, 8, 10, 11 };

        int start, end;
        for (int i = 0; i < numbers.Length; i++)
        {
            start = numbers[i];

            while (i < numbers.Length - 1 && numbers[i] + 1 == numbers[i + 1])
                i++;

            end = numbers[i];

            if(start == end)
                Console.WriteLine(start);
            else
                Console.WriteLine(start + " - " + end);
        }

这将显示随范围递增的后续数字。不线性增加的数字不会写为范围的一部分。

这是第一种方法的另一个版本，它使用相同的for循环来迭代范围：

        int temp = numbers[0], start, end;
        for (int i = 0; i < numbers.Length; i++)
        {
            start = temp;

            if (i < numbers.Length - 1 )
                // if subsequent numbers are incremental loop further
                if (numbers[i] + 1 == numbers[i + 1])
                    continue;
                // if they are not, number at index i + 1 is a new 'start' for the next iteration
                else
                    temp = numbers[i + 1];

            end = numbers[i];

            if (start == end)
                Console.WriteLine(start);
            else
                Console.WriteLine(start + " - " + end);
        }
于 2013-02-19T08:34:40.587 回答
5

C# 中的一个简单实现可能如下所示：

public string Format(IEnumerable<int> input)
{
    var result = string.Empty;

    var previous = -1;
    var start = -1;
    var first = true;

    foreach(var i in input)
    {
        if(start == -1)
            start = i;
        else if(previous + 1 != i)
        {
            result += FormatRange(start, previous, first);
            first = false;
            start = i;
        }

        previous = i;
    }

    if(start != -1)
        result += FormatRange(start, previous, first);

    return result;
}

public string FormatRange(int start, int end, bool isFirst)
{
    var result = string.Empty;
    if(!isFirst)
        result += ", ";
    if(start == end)
        result += start;
    else
        result += string.Format("{0}-{1}", start, end);
    return result;
}

这也将输出1-3input 1,2,3，这是完全有效的。如果没有规范输出应该是什么，则无法回答该部分。

于 2013-02-19T08:35:12.907 回答
3

可能不是面试问题的合适答案，但使用 LINQ 是解决此问题的另一种方法。

int[] numbers = { 1, 2, 3, 4, 5, 6, 8, 10, 11 };
var remains = numbers.AsEnumerable();

while (remains.Any())
{
    int first = remains.First();
    int last = remains.TakeWhile((x, i) => x - first == i).Last();
    remains = remains.Skip(last - first + 1);
    Console.Write(first + (first == last ? "" : "-" + last) + (remains.Any() ? "," : Environment.NewLine));
}
于 2013-02-19T10:07:43.467 回答
2

Java代码：

int[] arr = {1,2,3,4,5,6,8,10,11};
int start = arr[0], last = arr[0];
String output = "";

for (int i = 1; i <= arr.length; i++)
{
  if (i == arr.length || arr[i] != last+1)
  {
    if (output.length() != 0)
      output += ",";
    if (start == last)
      output += start;
    else
      output += start + "-" + last;
    if (i != arr.length)
      start = last = arr[i];
  }
  else
     last = arr[i];
}

System.out.println(output);
于 2013-02-19T08:31:24.027 回答
2

这是我最好的尝试。不聪明，但足够简单，足以满足我相信的要求。我仍然很困惑为什么“1-3”是错误的......

    var numbers = new int[] { 1, 2, 3, 4, 5, 6, 8, 10, 11, 12 };

    var groups = new Dictionary<int, int>();
    groups.Add(numbers.First(), numbers.First());

    foreach (var num in numbers.Skip(1))
    {
        var grp = groups.Last();
        if (grp.Value + 1 == num)
        {
            groups[grp.Key] = num;
        }
        else
        {
            groups.Add(num, num);
        }
    }

    var output = string.Join(",", groups.Select(grp => (grp.Key == grp.Value) ? grp.Value.ToString() : grp.Key.ToString() + "-" + grp.Value.ToString()));

注意：当然，使用字典和 linq 等是完全没有必要的（对于需要算法的答案来说太具体了），但我认为它很好地突出了问题的分组方面

于 2013-02-19T08:47:54.807 回答
2

以下对连续整数进行分组，并为每个组输出一个字符串。但是，它还允许您指定要连字的组的最小长度；少一点只会给你个人数字。因此，如果您只想连接 4 个或更多的组，则可以传入 4；如果你想连字符对，你可以传入 2。（我想自己使用 3，但我不知道他们想要什么。）

它也不会保留任何数字集合，因为您不需要。

方法：

static IEnumerable<string> Group(IEnumerable<int> input, int minLength)
{
    int currentStart = int.MinValue;
    int currentLength = 0;
    foreach (int c in input)
    {
        if (currentLength > 0)
            if (currentStart + currentLength == c)
                currentLength++;
            else
            {
                if (currentLength >= minLength)
                    yield return string.Format("{0}-{1}",
                        currentStart, currentStart + currentLength - 1);
                else
                    for (int i = currentStart; i < currentStart + currentLength; i++)
                        yield return i.ToString();
                currentStart = c;
                currentLength = 1;
            }
        else
        {
            currentStart = c;
            currentLength = 1;
        }
    }
    if (currentLength >= minLength)
        yield return string.Format("{0}-{1}",
            currentStart, currentStart + currentLength + 1);
    else
        for (int i = currentStart; i < currentStart + currentLength; i++)
            yield return i.ToString();
}

用法：

int minCount = 3;
int[] input = new[] { 1, 2, 3, 4, 5, 6, 8, 10, 11 };
Console.WriteLine(String.Join(",", Group(input, minCount)));
于 2013-02-19T08:49:15.447 回答
1

这不是有效的 C# 代码，而是显示想法。

从 Min 到 Max 对列表进行排序，然后执行以下操作：

For i = Min to Max
{
  if i < MaxFound
    continue;

  int step = 1;
  Output = i;
  while Found(i + Step)
  {
     Step++;
     MaxFound = i + Step;
  }
  if i < MaxFound 
    Output = (i + "-" + MaxFound);

  Output += ", ";
}
于 2013-02-19T08:35:36.483 回答
1

这是一种方法：

public static void main(String[] args) {
    print(1, 2, 3, 4, 5, 7, 9, 10, 12);
}

public static void print(int ... nums) {
    System.out.print(nums[0]);
    int idx = 1;

    for(int i = 1; i < nums.length; i++, idx++) {
        if(nums[i] - nums[i - 1] != 1) {
            if(idx > 1) {
                System.out.print(" - " + nums[i - 1]);
            }
            System.out.print(", " + nums[i]);
            idx = 0;
        }
    }

    if(idx > 1)
        System.out.println(" - " + nums[nums.length - 1]);
}
于 2013-02-19T08:45:17.710 回答
1

这是一个 Haskell 版本：

import Data.List

parseRange [] = ""
parseRange n = 
  let range = takeWhile (\x -> isInfixOf [x,x+1] n) n
  in if not (null range)
        then show (head range) ++ "-" ++ show (last range + 1) 
             ++ (if length (tail n) > 1 then "," else "") 
             ++ parseRange (drop (length range + 1) n) 
        else show (head n) ++ (if null (tail n) then "" else ",") 
             ++ parseRange (drop 1 n)

输出：

*Main> parseRange [1,2,3,4,5,6,8,10,11]
"1-6,8,10-11"
于 2013-02-19T22:28:04.203 回答
0

还有一种在 F# 中使用 fold 的方法——只是为了好玩。

let parseRange numbers = 
  numbers 
  |> Seq.fold 
    (fun list n -> 
      match list with
      |(a,b) :: tail when b+1 = n -> (a, n) :: tail
      |_ -> (n,n) :: list) []
  |> List.rev 
  |> Seq.map (fun (a,b) -> if a = b then sprintf "%i" a else sprintf "%i-%i" a b)
  |> String.concat ","
于 2013-12-16T14:30:32.263 回答