给定一个电话号码列表，请从一个数字确定为另一个号码的前缀的角度确定是否一致。假设电话目录列出了以下数字:
紧急911
爱丽丝97625999
鲍勃91 12 54 26
在这种情况下，无法拨打Bob的电话，因为一旦您拨打了Bob的电话号码的前三位数，中心就会将您的调用转接到紧急电话。因此，此列表将不一致。
输入
输入的第一行给出一个整数，即1≤t≤40，即测试用例的数量。每个测试用例都以n(电话号码的数量)开头，在单独的行中1≤n≤10000。然后跟随n行，每行上有一个唯一的电话号码。电话号码是最多十位数字的序列。
输出
对于每个测试用例，如果列表一致，则输出“YES”，否则输出“NO”。
该程序应该读入fron标准，然后写出标准。我们还可以假设输入将符合规范。这是我的代码:
<?php
fscanf(STDIN, "%d", $numOfTestCases);
for ($i = 0; $i < $numOfTestCases; $i++) { //Loop for reading test cases
fscanf(STDIN, "%d", $numOfPhoneNumbers);
$phoneNumbers = array();
$isConsistent = true;
for ($j = 0; $j < $numOfPhoneNumbers; $j++) { //Loop for reading phone numbers of each test case
fscanf(STDIN, "%d", $newNumber);
if ($isConsistent != false) { //If list already inconsistent, we dont need to check further input
if (empty($phoneNumbers)) { // If the array of phone numbers is empty, we just add the new one
$phoneNumbers[$j] = $newNumber;
} else {
foreach ($phoneNumbers as $k => $testNumber) { //Loop for checking if new number is consistent or not
$newNumLen = strlen($newNumber);
$testNumlen = strlen($testNumber);
$newBeginning = substr($newNumber, 0, $testNumlen);
$testBeginning = substr($testNumber, 0, $newNumLen);
if ($newNumber == $testBeginning || $testNumber == $newBeginning) {
$isConsistent = false;
break;
}
}
if ($isConsistent == true) $phoneNumbers[$j] = $newNumber;
}
}
}
$newAnswer = ($isConsistent) ? "YES" : "NO";
$ansString = ($i == 0) ? $newAnswer : $ansString."\n".$newAnswer;
}
fwrite(STDOUT, $ansString);
exit(0);
?>
我的问题是有一个正在运行的测试程序，它的超时为4秒。第二个测试文件总是超时。我没有访问测试程序或文件的权限，但我认为文件很长，甚至可能有40个测试用例，每种情况下都有10000个电话号码。
谁能看到我如何使该代码以任何方式更快地运行？
这是一个示例运行:
Sample Input:
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
Sample Output:
NO
YES
最佳答案
众所周知，树是您的解决方案。
创建一棵树，每个节点代表一个数字中的一个数字。
每个数字的最后一位将标记为isNumber = true，其余数字将标记为isNumber = false。
将数字添加到树时，遍历树的节点，并检查是否遍历isNumber = true的节点。如果是这样，则返回false/打印一些内容。
例如:请参阅下面的图示
添加数字21:对数字进行迭代。创建新节点= 1，新节点= 2(isNumber = true)
添加数字911:按数字进行迭代。创建新节点= 9，新节点= 1，新节点= 1(isNumber = true)
添加数字9125:按数字进行迭代。创建新节点= 9，新节点= 1，新节点= 2，新节点= 5(isNumber = true)
添加数字91 1 2:对数字进行迭代。创建新节点= 9，新节点= 1，新节点= 1(错误:由于isNumber = true 失败)
希望对您有所帮助。
编辑:
好的，因为它引起了我的兴趣，所以我尝试实现该解决方案，并且我与您的解决方案非常接近。
我编写了一个简单的脚本来创建一个 testcase.txt ，其中包含10000个数字(1≤n≤10000)。
我制作了一个简单的 unittest.php 脚本，该脚本在同一文件上运行40次(1≤t≤40)。
<?php
// create_testcase.php
$handle = fopen("testcase.txt",'w');
for($i=0 ; $i < 10000 ; $i++){
$number = rand(1,9999999999);
fwrite($handle,$number."\n");
}
fclose($handle);
// unittest.php
class Node{
private $digit;
private $leaf = false;
private $children = array();
function __construct($digit,$leaf = false){
$this->digit = $digit;
$this->leaf = $leaf;
}
function isLeaf(){
return $this->leaf;
}
function hasChild($digit){
return array_key_exists($digit,$this->children);
}
function hasChildren(){
return count($this->children);
}
function addChild($digit,$isLeaf){
$this->children[$digit] = new Node($digit,$isLeaf);
return $this->children[$digit];
}
function getChild($digit){
return $this->children[$digit];
}
}
for($i=0 ; $i < 40 ; $i++){
$anchor = new Node(0,false);
$isConsistent = true;
$handle = fopen("testcase.txt",'r');
while(($number = fgets($handle)) != false){
$node = $anchor;
$number = rtrim($number);
$number_length = strlen($number);
foreach(str_split($number) as $index => $digit){
if($node->hasChild($digit)){
$node = $node->getChild($digit);
if($node->isLeaf()){
$isConsistent = false;
break;
}
}
else{
(($index+1) == $number_length) ? ($isLeaf = true) : ($isLeaf = false);
$node = $node->addChild($digit,$isLeaf);
}
}
if($node->hasChildren()){
$isConsistent = false;
}
if(!$isConsistent){
break; // don't continue to next number in test case
}
}
if($isConsistent){
print "Consist list\n";
}
else{
print "Not Consist list\n";
}
fclose($handle);
}
对于我仍然使用的旧版本，结果是用了2GB的core2duo:
实际 0m26.123s
用户0m26.064s
sys 0m0.048s
适用于:40x10000 = 400,000个数字。
对于一个测试用例，它花费了:
实际 0m0.554s
用户0m0.544s
sys 0分0.008秒