2 回答

TA贡献1811条经验 获得超6个赞
您可以采用迭代方法,并将其视为处理每个级别的值,每个下一个级别的总值都会减少 1 个值。换句话说,您可以将其视为逐级进行的广度优先搜索。因此,您可以使用一种queue
数据结构一次处理每个级别。
您可以使用 PHP 的SplQueue
类来实现这一点。请注意,我们可以利用此类,因为它在double-ended queue
以下 4 个操作的帮助下充当 a:
enqueue
- 将值排入队列末尾。dequeue
- 将值从队列顶部出列。push
- 将值推送到双向链表的末尾(这里,队列是作为双向链表实现的)。pop
- 从双向链表的末尾弹出一个节点。
毫无疑问,以上 4 个操作都可以在 O(1) 时间内完成。
算法:
将所有数组元素添加到队列中。
我们将循环直到队列大小大于 1。
现在,如果队列级别大小为奇数,
pop
则使用最后一个并将其保存在缓冲区中(在变量中)。dequeue
通过一次 ing 2来添加所有成对元素,然后enqueue
将它们添加到下一个级别。级别迭代后,如果前一个级别大小为奇数,则添加最后一个元素。
打印这些添加的元素并相应地为每个级别回显新行。
片段:
<?php
function sumForTwos($arr){
if(count($arr) == 1){
echo $arr[0];
return;
}
$queue = new SplQueue();
foreach($arr as $val){
$queue->enqueue($val); // add elements to queue
}
while($queue->count() > 1){
$size = $queue->count();
$last = false;
if($size % 2 == 1){
$last = $queue->pop(); // pop the last odd element from the queue to make queue size even
$size--;
}
for($i = 0; $i < $size; $i += 2){
$first = $queue->dequeue();
$second = $queue->dequeue();
echo $first + $second," ";
$queue->enqueue($first + $second);
}
if($last !== false){// again add the last odd one out element if it exists
echo $last; // echo it too
$queue->push($last);
}
echo PHP_EOL;// new line
}
}
sumForTwos([1, 2, 3, 4, 5, 6, 8, 9, 9]);

TA贡献1784条经验 获得超8个赞
这是你想要的吗?
function pairBySums($inputArray)
{
if (sizeof($inputArray) % 2 == 1) {
$lastEntry = array_pop($inputArray); //$inputArray now has even number of elements
}
$answer = [];
for ($ii = 0; $ii < sizeof($inputArray) / 2; $ii++) {
$firstIndexOfPair = $ii * 2; // 0 maps to 0, 1 maps to 2, 3 maps to 4 etc
$secondIndexOfPair = $firstIndexOfPair + 1; // 0 maps to 1, 1 maps to 3, 2 maps to 5 etc
$answer[$ii] = $inputArray[$firstIndexOfPair] + $inputArray[$secondIndexOfPair];
}
if (isset($lastEntry)) {
array_push($answer, $lastEntry);
}
echo implode(' ', $answer) . "<br>";
if (sizeof($answer) > 1) {
pairBySums($answer);
}
}
该算法确保它在偶数数组上运行,然后将奇数条目附加回数组(如果有)。
$input = [1, 2, 3, 4, 5, 6, 8, 9, 9];
pairBySums($input);
产生:
3 7 11 17 9
10 28 9
38 9
47
对于偶数个项目,
$input = [1, 2, 3, 4, 5, 6, 8, 9];
pairBySums($input);
产生:
3 7 11 17
10 28
38
- 2 回答
- 0 关注
- 123 浏览
添加回答
举报