卡蒂斯挑战:电话列表，超过4秒时间限制，c#

本文关键字：4秒 超过 时间 列表 挑战 电话 | 更新日期: 2023-09-27 18:18:31

使用在线自动测试系统Kattis，我面临的挑战是(用c#)创建一个电话号码列表，然后找出其中是否有任何一个是前缀。

(参见:https://ncpc.idi.ntnu.no/ncpc2007/ncpc2007problems.pdf，任务A)

提供答案相对容易，但无论我如何尝试，我都无法逃脱得到的结果:时间限制超出，一些进一步的信息说，它需要超过4秒来运行程序(由一个自动程序)。

我试着从头开始重写了好几次，我试过了我能在网上找到的每一个现有的建议。我发现自己完全不知道该做什么，主要是因为到最后我不能确定到底是哪里出了问题。

这段代码是在一个类似的(但未解析的)线程上提出的，并没有发挥神奇的作用——但它是迄今为止我见过的最好的代码:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace PhoneList
{
class Program
{
    static void Main(string[] args)
    {
        // Save number of test cases.
        var numTestCases = int.Parse(Console.ReadLine());
        // Do this for each test case.
        for (int i = 0; i < numTestCases; i++)
        {
            // Save number of phone numbers.
            var numPhoneNumbers = int.Parse(Console.ReadLine());
            // Save all phonenumbers in the list.
            var phoneNumbersList = new List<string>();
            for (int j = 0; j < numPhoneNumbers; j++)
            {
                string number = Console.ReadLine().Trim();
                // Add to list.
                phoneNumbersList.Add(number);
            }
            // Write output.
            if (phoneNumbersList.All(n => !phoneNumbersList.Except(new[] { n }).Any(o => o.StartsWith(n))))
            {
                Console.WriteLine("YES");
            }
            else
            {
                Console.WriteLine("NO");
            }
        }
    }
}
}

有什么建议吗?

卡蒂斯挑战:电话列表，超过4秒时间限制，c#

您是否尝试过在所有数字相加后对电话号码列表(按字母顺序)进行排序，然后检查项目n+1是否以项目n开头?

phoneNumbersList.Sort((x,y) => string.Compare(x, y));
var consistent = true;
for (var j = 0; j < phoneNumbersList.Count - 1; ++j)
{
   if (phoneNumbersList[j + 1].StartsWith(phoneNumbersList[j]))
   {
        consistent = false;
        break;
   }
}
Console.WriteLine(consistent ? "YES" : "NO");

不总是最短和最好的:-)试试下面的:

using System;
using System.Collections.Generic;
using System.Linq;
namespace Samples
{
    class PhoneListProcessor
    {
        const int MaxCount = 10000;
        const int MaxDigits = 10;
        Dictionary<int, bool> phoneNumberInfo = new Dictionary<int, bool>(MaxCount * MaxDigits);
        public bool Process(IEnumerable<string> phoneNumbers, bool readToEnd)
        {
            phoneNumberInfo.Clear();
            using (var e = phoneNumbers.GetEnumerator())
            {
                while (e.MoveNext())
                {
                    if (Process(e.Current)) continue;
                    if (readToEnd)
                    {
                        while (e.MoveNext()) { }
                    }
                    return false;
                }
            }
            return true;
        }
        bool Process(string phoneNumber)
        {
            var phoneNumberInfo = this.phoneNumberInfo;
            int phoneCode = 0;
            int digitPos = 0;
            bool hasSuffix = true;
            while (true)
            {
                phoneCode = 11 * phoneCode + (phoneNumber[digitPos] - '0' + 1);
                bool isLastDigit = ++digitPos >= phoneNumber.Length;
                bool isPhoneNumber;
                if (hasSuffix && phoneNumberInfo.TryGetValue(phoneCode, out isPhoneNumber))
                {
                    if (isPhoneNumber || isLastDigit) return false;
                }
                else
                {
                    phoneNumberInfo.Add(phoneCode, isLastDigit);
                    if (isLastDigit) return true;
                    hasSuffix = false;
                }
            }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            var processor = new PhoneListProcessor();
            int testCount = int.Parse(Console.ReadLine());
            for (int testIndex = 0; testIndex < testCount; testIndex++)
            {
                int count = int.Parse(Console.ReadLine());
                var numbers = Enumerable.Range(0, count).Select(_ => Console.ReadLine());
                bool readToEnd = testIndex + 1 < testCount;
                bool valid = processor.Process(numbers, readToEnd);
                Console.WriteLine(valid ? "YES" : "NO");
            }
        }
    }
}

基本上，它所做的是动态构建，并在任务约束和细节下使用字典前缀树的变体。每个电话号码或前缀都被编码为以11为基数的无零整数(每个数字都是递增的，所以我们有1-10而不是0-9)，以便根据要求区分有前导零的数字和没有前导零的相同数字。

我有两个建议:

  1. 用phoneNumbers.Sort();代替按字母顺序排序，尝试按长度:numbers.Sort((a, b) => a.Length - b.Length);排序。直觉是，由于长度较长的字符串不可能成为较短字符串的前缀，因此我们可以跳过检查这些字符串并节省一些工作(一旦发现不一致就尽早进行救助是很重要的)。
  2. 由于电话长度只有10位数字长，所以迭代它并将每个前缀存储在HashSet中是可行的。HashSet在所有先前计算的前缀上给我们O(1)查找时间，因此每个测试用例的时间复杂度为检查O(n)，而预先排序成本为O(n log(n))。

代码如下:

using System;
using System.Collections.Generic;
namespace PhoneList
{
    class Program
    {
        static bool IsConsistent(List<string> numbers)
        {
            numbers.Sort((a, b) => a.Length - b.Length);
            var prefixes = new HashSet<string>();
            foreach (var n in numbers)
            {
                for (int i = 1; i < n.Length; i++)
                {
                    if (prefixes.Contains(n.Substring(0, i)))
                    {
                        return false;
                    }
                }
                prefixes.Add(n);
            }
            return true;
        }
        static void Main(string[] args)
        {
            int testCases = Int32.Parse(Console.ReadLine());
            for (int i = 0; i < testCases; i++)
            {
                int phoneNumbersCount = Int32.Parse(Console.ReadLine());
                var numbers = new List<string>();
                for (int j = 0; j < phoneNumbersCount; j++)
                {
                    numbers.Add(Console.ReadLine());
                }
                Console.WriteLine(IsConsistent(numbers) ? "YES" : "NO");
            }
        }
    }
}
相关文章：