21.栈的压入、弹出序列
题目描述
<?php function IsPopOrder($pushV, $popV)
{
// write code here
$stack = new SplStack;
$count = count($pushV);
for($i=0,$j=0;$i<$count;$i++){
$stack->push($pushV[$i]);
while(!$stack->isEmpty()&&$stack->top()==$popV[$j]&&$j<$count){
$stack->pop();
$j++;
}
}
return $stack->isEmpty();
}
运行时间：9ms 占用内存：3840k
思路：
借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1≠4，所以我们继续压栈，直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。
22.从上往下打印二叉树
题目描述
<?php
/*class TreeNode{
var $val;
var $left = NULL;
var $right = NULL;
function __construct($val){
$this->val = $val;
}
}*/
function PrintFromTopToBottom($root)
{
// write code here
$queue = array();
$list = array();
array_push($queue,$root);
while(count($queue)>0){
array_push($list,$queue[0]->val);
$tmp = array_splice($queue,0,1);
if($tmp[0]->left != null){
array_push($queue,$tmp[0]->left);
}
if($tmp[0]->right != null){
array_push($queue,$tmp[0]->right);
}
}
return $list;
}
题目描述
<?php function VerifySquenceOfBST($sequence)
{
// write code here
$size = count($sequence);
if($size == 0){
return false;
}
$i = 0;
while($size--){
while($sequence[$i++]<$sequence[$size]);
while($sequence[$i++]>$sequence[$size]);
if($i<$size){
return false;
}
$i = 0;
}
return true;
}
运行时间：12ms 占用内存：2572k
思路：
只要想清楚左节点比根节点小，右节点比根节点大就很容易解出，首先将数组的大小赋给$size，对$size进行while循环，这里有一个很重要的变量$i，两个while循环一个判断左节点和根节点的大小关系，若左小于根，则$i++，继续循环，之后判断右是否大于根，若大于，$i++，然后判断变量i和变量size的大小关系，如果i小于size，则说明没有循环完，即这不是一个二叉搜索树，返回false，反之则继续size--循环，当然要将i重新赋值0，直到size为0时，循环结束，返回true。
24.二叉树中和为某一值的路径
题目描述
<?php
/*class TreeNode{
var $val;
var $left = NULL;
var $right = NULL;
function __construct($val){
$this->val = $val;
}
}*/
function FindPath($root, $expectNumber)
{
// write code here
$arr = $tmp = [];
if(!$root){
return $arr;
}
find($root,$expectNumber,$arr,$tmp);
return $arr;
}
function find($root,$sum,&$arr,$tmp){
if($root!= null){
$sum-=$root->val;
$tmp[] = $root->val;
if($sum>0){
find($root->left,$sum,$arr,$tmp);
find($root->right,$sum,$arr,$tmp);
}elseif($sum==0 && $root->left == null && $root->right == null){
$arr[] = $tmp;
}
}
}
运行时间：12ms 占用内存：2316k
思路：
一个简单的递归函数，通过把每次减去的根节点的值存入临时数组tmp中，最后进行判断是否减到了零，并且是叶子节点，若是，再将tmp数组中的数转移到arr数组中，输出。
25.复杂链表的复制
题目描述
<?php
/*class RandomListNode{
var $label;
var $next = NULL;
var $random = NULL;
function __construct($x){
$this->label = $x;
}
}*/
$r = [];
function MyClone($pHead)
{
// write code here
global $r;
if($pHead == NULL){
return NULL;
}
$PnewHead=new RandomListNode($pHead->label);
$PnewHead->next=MyClone($pHead->next);
$PnewHead->random=$pHead->random;
return $PnewHead;
}
运行时间：16ms 占用内存：2432k
思路：
复杂链表是一种不太常见的数据结构，而且复制这种链表的过程也较为复杂，这里有一个小坑，就是找当前节点的下一个节点时用的是递归，但找他的random节点时只需要复制$pHead->random就行了，用不到递归。
26.二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
时间限制：1秒 空间限制：32768K
<?php
/*class TreeNode{
var $val;
var $left = NULL;
var $right = NULL;
function __construct($val){
$this->val = $val;
}
}*/
$nodes = array();
function Convert($pRootOfTree)
{
// write code here
GLOBAL $nodes;
$nodes = array();
inOrder($pRootOfTree);
for($i=0;$i<count($nodes)-1;$i++){
$nodes[$i]->right = $nodes[$i+1];
$nodes[$i+1]->left = $nodes[$i];
}
return $nodes[0];
} function inOrder($root){
GLOBAL $nodes;
if($root == null){
return;
}else{
inOrder($root->left);
$nodes[] = $root;
inOrder($root->right);
}
}
运行时间：9ms 占用内存：4060k
思路：
这种方法的思路就是首先递归将搜索二叉树中的节点按照中序遍历的顺序存入到nodes中，然后对nodes进行遍历，使他相邻两个值互为左右子节点（双向链表）。
27.字符串的排列
题目描述
<?php function Permutation($str)
{
$ans = array();
permutation2(0,$str,$ans);
$ans = array_unique($ans);
sort($ans);
return $ans;
} function permutation2($step,&$str,&$ans){
if($step==strlen($str)-1){
$ans[] = $str;
}
for($i=$step;$i<strlen($str);$i++){
$tmp = $str[$step]; $str[$step] = $str[$i]; $str[$i] = $tmp;
permutation2($step+1,$str,$ans);
$tmp = $str[$step]; $str[$step] = $str[$i]; $str[$i] = $tmp;
}
}
运行时间：12ms 占用内存：3936k
思路：
利用递归，通过对step位数的控制，每次交换两个字母的位置，将所有可能的情况罗列出来，存入ans数组中，最后将其去重，排序，即可得到最终结果。
28.数组中出现次数超过一半的数字
题目描述
时间限制：1秒 空间限制：32768K
<?php function MoreThanHalfNum_Solution($numbers)
{
// write code here
if(count($numbers) <= 0)
return 0;
$list = array_count_values($numbers);
$max = max($list);
if(2*$max > count($numbers))
return array_search($max, $list);
else
return 0;
}
运行时间：12ms 占用内存：2432k
思想：
博主在这里偷懒了，使用了php的函数array_count_values，将数组中所有值当做下标，出现的次数当做值放入一个新的数组中，瞬间发现这个题简单了好多，找到数组中最大值的那一项，判断最大值的二倍与原数组长度谁大，来返回结果。
29.最小的K个数
题目描述
<?php function GetLeastNumbers_Solution($input, $k)
{
// write code here
sort($input);
$res = [];
if(count($input)>0 && count($input)>=$k){
$res = array_slice($input,0,$k);
return $res;
}else{
return $res;
} }
运行时间：17ms 占用内存：3940k
思路：
先排序，然后使用array_slice，取出数组中前k个值，放入res数组中，返回即可，注意判断输入的数组和k是否符合范围，若不符合就返回空数组。
30.连续子数组的最大和
题目描述
<?php function FindGreatestSumOfSubArray($array)
{
// write code here
$count = count($array);
$max = $array[0];
for($i=0;$i<$count;$i++){
$sum = 0;
for($j=$i;$j<$count;$j++){
$sum+=$array[$j];
if($sum>$max){
$max = $sum;
}
}
}
return $max;
}
运行时间：10ms 占用内存：2432k
思路：
双层循环遍历，找出一个和最大的值，并返回这个和。
注：以上均为个人理解，如有错误，请提出，必改正。