将列表<int>隐藏到范围列表

Question

我需要将list整数转换为范围列表.

我有一个List<int>包含8, 22, 41.这些值是分节符,从一个完整的清单1来47.

我想获得一个包含起始行和结束行的范围列表.输出应该是

{(1,7),(8,21),(22,40),(41,47)}

我试图从这个问题调整解决方案,但无法使其工作.

看起来应该很简单,但也许不是.

Answer 1

即使程序有效,在查询期间应该变异本地的答案也是危险的; 不要陷入这个坏习惯.

解决问题的最简单方法是编写迭代器块.我们假设你有明显的Pair<T>类型; 在C#7中你可能会使用一个元组; 适应这个使用元组是一个简单的练习:

static IEnumerable<Pair<int>> MakeIntervals(
  /* this */ IEnumerable<int> dividers, /* You might want an extension method.*/
  int start,
  int end)
{
  // Precondition: dividers is not null, but may be empty.
  // Precondition: dividers is sorted.  
  // If that's not true in your world, order it here.
  // Precondition: dividers contains no value equal to or less than start.
  // Precondition: dividers contains no value equal to or greater than end.
  // If it is possible for these preconditions to be violated then
  // the problem is underspecified; say what you want to happen in those cases.
  int currentStart = start;
  for (int divider in dividers) 
  {
    yield return new Pair<int>(currentStart, divider - 1);
    currentStart = divider;
  }
  yield return new Pair<int>(currentStart, end);
}

这是解决这个问题的正确方法.如果你想变得有点傻,你可以使用Zip.从两个有用的扩展方法开始:

static IEnumerable<T> Prepend<T>(this IEnumerable<T> items, T first)
{
  yield return first;
  foreach(T item in items) yield return item;
}
static IEnumerable<T> Append<T>(this IEnumerable<T> items, T last)
{
  foreach(T item in items) yield return item;
  yield return last;
}

现在我们有:

static IEnumerable<Pair<int>> MakeIntervals(
  IEnumerable<int> dividers,
  int start,
  int end)
{
  var starts = dividers.Prepend(start);
  // This is the sequence 1, 8, 22, 41
  var ends = dividers.Select(d => d - 1).Append(end);
  // This is the sequence 7, 21, 40, 47
  var results = starts.Zip(ends, (s, e) => new Pair<int>(s, e));
  // Zip them up: (1, 7), (8, 21), (22, 40), (41, 47)
  return results;
}

但与简单地直接编写迭代器块相比,这似乎是不必要的巴洛克式.此外,这会将集合重复两次,这被许多人认为是糟糕的风格.

一个解决问题的可爱方法是概括第一个解决方案:

static IEnumerable<R> SelectPairs<T, R>(
  this IEnumerable<T> items,
  IEnumerable<T, T, R> selector
)
{
  bool first = true;
  T previous = default(T);
  foreach(T item in items) {
    if (first) {
      previous = item;
      first = false;
    }
    else
    {
      yield return selector(previous, item);
      previous = item;
    }
  }
}

现在你的方法是:

static IEnumerable<Pair<int>> MakeIntervals(
  IEnumerable<int> dividers,
  int start,
  int end)
{
  return dividers
    .Prepend(start)
    .Append(end + 1)
    .SelectPairs((s, e) => new Pair<int>(s, e - 1);
}

我非常喜欢最后一个.也就是说,我们被给予8, 22, 41,我们构建1, 8, 22, 41, 48,然后从中我们挑选对和构造(1, 7), (8, 21),等等.