填入分隔的序列

本文关键字：分隔 | 更新日期: 2023-09-27 17:54:23

我有一个文件，其中包含一个分隔的序列号列表作为记录键。我需要填补缺失的序列。如果我输入

8
8.2
8.3.4.1

我需要添加

8.1
8.3
8.3.1
8.3.2
8.3.3
8.3.4

我已经提出了一些算法，但它们都非常复杂，而且有太多的情况。有简单的方法来做这件事吗，还是我必须要费力地完成?我用c#，但Java也可以

填入分隔的序列

不确定我的解决方案是否容易理解，但让我们试试。这个想法是我们递归地在现有序列之间插入缺失序列。

首先，您需要解析您的文件，以创建一个表示现有序列的项目列表。每一项都应该有对下一项的引用(链表的想法)。

public class Item
{
    public int Value { get; set; }
    public Item SubItem { get; set; }
    public Item NextItem { get; set; }
    public Item(int value, Item subItem)
    {
        Value = value;
        SubItem = subItem;
    }
    public Item CreatePreviousItem()
    {
        if (SubItem == null)
        {
            return Value == 1 ? null : new Item(Value - 1, null);
        }
        return new Item(Value, SubItem.CreatePreviousItem());
    }
    public bool IsItemMissingPrior(Item item)
    {
        if (item == null)
        {
            return false;
        }
        return 
            item.Value - Value > 1 
            || (SubItem == null && item.SubItem != null && item.SubItem.Value > 1) //edge case
            || (SubItem != null && SubItem.IsItemMissingPrior(item.SubItem));
    }
    public override string ToString()
    {
        return Value + (SubItem != null ? "." + SubItem : "");
    }
}

假设序列由新行符号分隔，您可以使用以下Parse方法。

private List<Item> Parse(string s)
{
    var result = new List<Item>();
    var numberLines = s.Split(new[] {Environment.NewLine}, StringSplitOptions.RemoveEmptyEntries);
    foreach (var numberLine in numberLines)
    {
        var numbers = numberLine.Split(new[] {'.'}).Reverse();
        Item itemInstance = null;
        foreach (var number in numbers)
        {
            itemInstance = new Item(Convert.ToInt32(number), itemInstance);
        }
        if (result.Count > 0)
        {
            result.Last().NextItem = itemInstance;
        }
        result.Add(itemInstance);
    }
    return result;
}

这是一个递归方法，它在两个现有序列之间插入缺失序列

private void UpdateSequence(Item item)
{
    if (item.IsItemMissingPrior(item.NextItem))
    {
        var inBetweenItem = item.NextItem.CreatePreviousItem();
        inBetweenItem.NextItem = item.NextItem;
        item.NextItem = inBetweenItem;
        UpdateSequence(item);
    }
}

最后是用例:

var inputItems = Parse(inputString);
foreach (var item in inputItems)
{
    UpdateSequence(item);
}

就是这样。要查看结果，您只需要从列表中获取第一项，并使用NextItem属性继续前进。例如

var displayItem = inputItems.FirstOrDefault();
while (displayItem != null)
{
    Console.WriteLine(displayItem.ToString());
    displayItem = displayItem.NextItem;
}

希望能有所帮助。

一种简单的方法(尽管在某些情况下不是最佳的)是维护一组现有的键。对于初始序列中的每个键，您可以将前面的所有键添加到该集合中。这可以在两个循环中完成:在内部循环中，您向集合中添加一个键，并在该键的最后一个数字大于0时将其减少1，在外部循环中，您将键的长度减少1。

然后你只需要按顺序输出集合

相关文章：