PHP之高频考点算法合辑
有效括号
LC: Valid Parentheses - LeetCode
题解：每遇到一个左括号时，在后续遍历中需要有一个相同类型的右括号将其闭合才行。由于后遇到的左括号要先闭合，因此可以将这个左括号放入栈顶，后进先出，正好符合此要求。另外，PHP由于其语言特性，使用数组函数array_pop来 mock 栈操作。
function isValid($s) {
$rcp = [
')' => '(',
'}' => '{',
']' => '[',
];
$stack = [];
$sarr = str_split($s);
$slen = count($sarr);
if ($slen%2!==0) {
return false;
}
for ($i=0; $i < $slen; $i++) {
if (isset($rcp[$sarr[$i]])) {
$leftBracket = array_pop($stack);
if ($leftBracket !== $rcp[$sarr[$i]]) {
return false;
}
} else {
$stack[] = $sarr[$i];
}
}
return empty($stack);
}
$s = "(}";
var_dump(isValid($s));
螺旋矩阵 I
LC: Spiral Matrix - LeetCode
题解：
其实，就是转圈循环，将矩阵看成一个 回字形 de套娃，每一圈作为一层，先循环最外层，然后次外层、、、以此类推；
每一层的循环顺序：上(top)、右(right)、下(bot)、左(left)；每个方位循环完成后对应的值加1；
/**
* @param Integer[][] $matrix
* @return Integer[]
*/
function spiralOrder($matrix) {
$output=[];
$cnt = count($matrix);
$horCnt = count($matrix[0]);
$top = 0;
$bot = $cnt-1;
$left = 0;
$right = $horCnt - 1;
$eleNum = $cnt * $horCnt;
while ($eleNum > 0) {
for ($i=$left; $i <= $right && $eleNum > 0; $i++) {
$output[]=$matrix[$top][$i];
$eleNum--;
}
$top++;
for ($i=$top; $i <= $bot && $eleNum > 0; $i++) {
$output[]=$matrix[$i][$right];
$eleNum--;
}
$right--;
for ($i=$right; $i >= $left && $eleNum > 0; $i--) {
$output[]=$matrix[$bot][$i];
$eleNum--;
}
$bot--;
for ($i=$bot; $i >= $top && $eleNum > 0; $i--) {
$output[]=$matrix[$i][$left];
$eleNum--;
}
$left++;
}
return $output;
}
螺旋矩阵 II
LC: Spiral Matrix II - LeetCode
题解：
参考上面的 螺旋矩阵-I 的解法，按顺序转圈循环赋值即可。
注意： 由于PHP本身是弱类型语言，其数组的实现方式不同于其他类型语言，是以 hash table 实现的（可参考：https://phper.shujuwajue.com/shu-zu/phpshu-zu-de-nei-bu-shi-xian），所以不能像其他类型语言一般，直接给一个 n*n 的矩阵数组赋初值。
所以本文采用了两种方式赋初值：
1、双循环遍历初值（耗时较多，LC 判定的）；
2、单层循环，子数组使用 range 赋初值，或者按题目要求赋值完成后，执行 ksort 排序;
/**
* @param Integer $n
* @return Integer[][]
*/
function generateMatrix($n) {
$ret=[];
$eleNum=$n*$n;
// for ($i=0; $i < $n; $i++) {
// $ret[$i] = range(0, $n-1);
// }
$iniNum = 1;
$top=0;
$bot=$n-1;
$left=0;
$right=$n-1;
while ($eleNum>=$iniNum) {
for ($i=$left; $i<=$right && $eleNum>=$iniNum; $i++) {
$ret[$top][$i]=$iniNum;
$iniNum++;
}
$top++;
for ($i=$top; $i<=$bot && $eleNum>=$iniNum; $i++) {
$ret[$i][$right]=$iniNum;
$iniNum++;
}
$right--;
for ($i=$right; $i>=$left && $eleNum>=$iniNum; $i--) {
$ret[$bot][$i]=$iniNum;
$iniNum++;
}
$bot--;
for ($i=$bot; $i>=$top && $eleNum>=$iniNum; $i--) {
$ret[$i][$left]=$iniNum;
$iniNum++;
}
$left++;
}
for ($i=0; $i < $n; $i++) {
ksort($ret[$i]);
}
return $ret;
}
剑指offer-05：替换字符串
题目：
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1： 输入：s = "We are happy."
输出："We%20are%20happy."
题解：
首先扩充数组到每个空格替换成"%20"之后的大小。
然后从后向前替换空格，也就是双指针法：i指向旧长度的末尾，j指向新长度的末尾。
注意：由于PHP的数组本质为hash table，所以返回前需要对数组进行排序；
So，为什么要从后向前填充，从前向后填充不行么？
从前向后填充就是 的复杂度了：
因为每次添加元素都要将添加元素之后的所有元素向后移动。
其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
这么做有两个好处：
不用申请新数组；
从后向前填充元素，避免了从前先后填充元素要来的 每次添加元素都要将添加元素之后的所有元素向后移动。
function replaceSpace($s) {
$slist = str_split($s);
$spaceCnt = 0;
for ($i=0; $i < count($slist); $i++) {
if ($slist[$i]===' ') {
$spaceCnt++;
}
}
$oldCnt = count($slist);
$newCnt = $oldCnt + $spaceCnt * 2;
$i=$oldCnt-1;
$j=$newCnt-1;
while ($i>=0 && $j>=0) {
if ($slist[$i]===' ') {
$slist[$j]='0';
$slist[$j-1]='2';
$slist[$j-2]='%';
$j = $j-2;
} else {
$slist[$j]=$slist[$i];
}
$i--;
$j--;
}
ksort($slist);
return $slist;
}
旋转图像
LC：Rotate Image - LeetCode
题解：
其实只需要执行两次数据调换；
先水平翻转数据；
再调换主对角线[1]两侧的矩阵数据即可；
function newrotate(&$matrix) {
$cnt = count($matrix);
// 水平翻转
for ($i=0; $i < $cnt/2; $i++) {
$swapi = $cnt-1-$i;
if ($swapi<=$i) {
break;
}
for ($j=0; $j < $cnt; $j++) {
list($matrix[$i][$j], $matrix[$swapi][$j]) = [$matrix[$swapi][$j], $matrix[$i][$j]];
}
}
// 主对角线两侧de数据对调
for ($i=0; $i < $cnt; $i++) {
for ($j=0; $j < $i; $j++) {
list($matrix[$i][$j], $matrix[$j][$i]) = [$matrix[$j][$i], $matrix[$i][$j]];
}
}
return $matrix;
}
$matrix = [[1,2,3],[4,5,6],[7,8,9]];
print_r(newrotate($matrix));
无重复字符的最长子字符串
LC链接：https://leetcode.com/problems/longest-substring-without-repeating-characters/
题解：
// 传统动态规划方法
function lengthOfLongestSubstring($s) {
$slen = strlen($s);
if ($slen<2) {
return $slen;
}
$sarr = str_split($s);
$charAt=[];
$ans=1;
for ($i=0; $i < $slen; $i++) {
for ($j=$i; $j < $slen; $j++) {
if (isset($charAt[$sarr[$j]])) {
$ans = max($ans, count($charAt));
$charAt=[];
break;
}
$charAt[$sarr[$j]]=$j;
}
}
return $ans;
}
$s="dvdf";
print_r([lengthOfLongestSubstring($s)]);die;
// 优化后的算法
function mySolution($s) {
$l = strlen($s);
if ($l<2) {
return $l;
}
$ans = 0;
$slist = str_split($s);
$tmp = [];
$start = 0;
while ($start < $l) {
for ($i = $start; $i < $l; $i++) {
$si = $s[$i];
if (isset($tmp[$si])) {
$ans = max($ans, count($tmp));
$start = $i + 1;
reset($tmp);
$flag = 0;
$newTmp = [];
foreach ($tmp as $tk => $tval) {
if ($flag > 0) {
$newTmp[$tk] = $tval;
}
if ($tk === $si) {
$flag = 1;
}
}
$tmp = $newTmp;
$tmp[$si] = $i;
break;
}
$tmp[$si] = $i;
}
}
return $ans;
}
$s="dvdf";
print_r([mySolution($s)]);die;
-
在一个n阶方阵(或是n阶行列式)中，从左上角到右下角这一斜线方向上的n 个元素所在的对角线，叫做n 阶方阵(或行列式)的主对角线。 ↩
