我有这个序列1,2,3,4,5,6,8,10,11
预期产量为1-6,8,10-11
这个问题是关于以易于阅读的形式格式化序列
我尝试使用 c# 并使用了许多 if & else。
面试官说，有一些简单的算法可以做到这一点。
我不知道如何实现这个非常简单。
同样对于 1,2,3 我显示了 1-3。他们说错了！
此逻辑是否涉及任何设计模式（解释器）？
问问题
11127 次
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 回答