假设我有一些 1-n 单位宽的序列号项目,需要按行显示。每行是 m 个单位宽。我需要一些伪代码来输出行,以便保持 m 宽度限制。这不是背包问题,因为物品必须按序列号顺序排列 - 行尾的空格很好。
我一直在追我的尾巴,部分原因是我在 PHP 和 jQuery/javascript 中都需要它,因此请求伪代码....
假设我有一些 1-n 单位宽的序列号项目,需要按行显示。每行是 m 个单位宽。我需要一些伪代码来输出行,以便保持 m 宽度限制。这不是背包问题,因为物品必须按序列号顺序排列 - 行尾的空格很好。
我一直在追我的尾巴,部分原因是我在 PHP 和 jQuery/javascript 中都需要它,因此请求伪代码....
while (!items.isEmpty()) {
rowRemain = m;
rowContents = [];
while (!items.isEmpty() && rowRemain > items[0].width) {
i = items.shift();
rowRemain -= i.width
rowContents.push(i);
}
rows.push(rowContents);
}
运行时间是Θ(项目数)
模数是你的朋友。我会做类似的事情:
$items = array(/* Your list of stuff */);
$count = 0;
$maxUnitsPerRow = 4; // Your "m" above
while ($item = $items[$count]) {
if ($count % $maxUnitsPerRow == 0) {
$row = new row();
}
$row->addItemToRow($item);
$count++;
}
对于它的价值,我想我有我想要的,对于 PHP - 但不确定是否有更简单的方法......
<?php
// working with just a simple array of widths...
$items = array(1,1,1,2,1,1,2,1);
$row_width = 0;
$max_width = 2;
echo "Begin\n"; // begin first row
foreach($items as $item=>$item_width) {
// can we add item_width to row without going over?
$row_width += $item_width;
if($row_width < $max_width) {
echo "$item_width ";
} else if($row_width == $max_width) {
echo "$item_width";
echo "\nEnd\nBegin\n"; // end last row, begin new row
$row_width = 0;
} else if($row_width == 2* $max_width) {
echo "\nEnd\nBegin\n"; // end last row, begin new row
echo "$item_width";
echo "\nEnd\n"; // end new row
$row_width = 0;
if($item < count($items)) echo "Begin\n"; // new row
} else if($row_width > $max_width) {
echo "\nEnd\nBegin\n"; // end last row, begin new row
echo "$item_width";
$row_width = $item_width;
}
}
echo "\nEnd\n"; // end last row
?>
这是一个替代的php代码......
function arrayMaxWidthString($items, $maxWidth) {
$out = array();
if (empty($items)) {
return $out;
}
$row = $maxWidth;
$i = 0;
$item = array_shift($items);
$row -= strlen($item);
$out[0] = $item;
foreach ($items as $item) {
$l = strlen($item);
$tmp = ($l + 1);
if ($row >= $tmp) {
$row -= $tmp;
$out[$i] = (($row !== $maxWidth) ? $out[$i] . ' ' : '') . $item;
} elseif ($row === $maxWidth) {
$out[$i] = $item;
++$i;
} else {
++$i;
$row = $maxWidth - $l;
$out[$i] = $item;
}
}
return $out;
}