剑指offer试题（PHP篇二）

11.二进制中1的个数

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

时间限制：1秒   空间限制：32768K

<?php

function NumberOf1($n)

{

    // write code here

    $count = 0;

    if($n<0){

        $n=$n & 0X7FFFFFFF;

        $count++;

    }

    while($n){

        $n=($n-1)&$n;

        $count++;

    }

    return $count;

}

运行时间：11ms   占用内存：2316k

感悟：

　　说实话，这类题是我的弱项，想了大半天，无从下手，后来还是在上网搜了些资料后，才勉强解出。首先判断n是不是负数，当n为负数的时候，直接用后面的循环会导致死循环，因为负数向左移位的话最高位补1！ 因此需要一点点特殊操作，可以将最高位的符号位1变成0，也就是n & 0x7FFFFFFF，这样就把负数转化成正数了，唯一差别就是最高位由1变成0，因为少了一个1，所以count加1。之后再按照while循环里处理正数的方法来操作就可以完美解决。

 

 

12.数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

时间限制：1秒   空间限制：32768K

<?php

function Power($base, $exponent)

{

    // write code here

    return pow($base,$exponent);

}

运行时间：15ms   占用内存：2432k

感悟：

　　这题用php做和作弊一样。。。呃，当然，身为一个正直的人，还是要把用算法思路写的解贴出来。

<?php

function Power($base, $exponent)

{

    if($exponent >= 0){

        $res = 1;

    while($exponent >= 1){

        $res = $res * $base;

        $exponent--;

    }

          return $res;

    }

    if($exponent < 0){

        $exponent2 = abs($exponent);

        $res = 1;

        while($exponent2 >=1){

            $res = $res *$base;

            $exponent2--;

        }

        return 1/$res;

    }

}

其实也不是很难啦= =。

13.调整数组顺序使奇数位于偶数前面

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

时间限制：1秒   空间限制：32768K

<?php

function reOrderArray($array)

{

    // write code here

    $tmp1 = [];

    $tmp2 = [];

    for($i=0;$i<count($array);$i++){

        if($array[$i]%2){

            $tmp1[] = $array[$i];

        }else{

            $tmp2[] = $array[$i];

        }

    }

    for($j=0;$j<count($tmp2);$j++){

        $tmp1[]=$tmp2[$j];

    }

    return $tmp1;

}

运行时间：10ms   占用内存：2432k

感悟：

　　这道题不算难，算法思路：创建两个临时数组，通过对原数组的每个值进行判断，奇偶分别存入两个临时数组中，再将偶数组放入奇数组之后即可。

14.链表中倒数第k个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

时间限制：1秒   空间限制：32768K

<?php

/*class ListNode{

    var $val;

    var $next = NULL;

    function __construct($x){

        $this->val = $x;

    }

}*/

function FindKthToTail($head, $k)

{

    // write code here

    $tmp=$head;

    $len=0;

    while($head!=null){

        $len++;

        $head=$head->next;

    }

    if($k>$len){

        return null;

    }

    for($i=0;$i<$len-$k;$i++){

        $tmp=$tmp->next;

    }

    return $tmp;

}

运行时间：25ms   占用内存：2316k

感悟：

　　这道题的思路非常清晰，即首先求出链表长度，判断k结点是否超出链表长度，若符合要求，则通过循环找到第k个结点并返回。

15.反转链表

题目描述

输入一个链表，反转链表后，输出链表的所有元素。

时间限制：1秒   空间限制：32768K

<?php

/*class ListNode{

    var $val;

    var $next = NULL;

    function __construct($x){

        $this->val = $x;

    }

}*/

function ReverseList($pHead)

{

    // write code here

    if($pHead==null){

        return null;

    }

    $pre=null;

    while($pHead != null){

        $tmp = $pHead->next;

        $pHead->next = $pre;

        $pre = $pHead;

        $pHead = $tmp;

    }

    return $pre;

}

运行时间：9ms   占用内存：3724k

感悟：

　　这道链表题自我感觉还是有点点绕的（个人大脑不是很发达。。。），思路，简单来说就是不断的取出原链表的头，然后存入pre的尾部，这样做的结果就是将整个链表反转。

16.合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

时间限制：1秒    空间限制：32768K

<?php

/*class ListNode{

    var $val;

    var $next = NULL;

    function __construct($x){

        $this->val = $x;

    }

}*/

function Merge($pHead1, $pHead2)

{

    // write code here

    $pHead = new ListNode(null);

    if($pHead1 == null){

        return $pHead2;

    }elseif($pHead2 == null){

        return $pHead1;

    }else{

        if($pHead1->val<$pHead2->val){

            $pHead=$pHead1;

            $pHead->next=Merge($pHead1->next,$pHead2);

        }else{

            $pHead=$pHead2;

            $pHead->next=Merge($pHead1,$pHead2->next);

        }

    }

    return $pHead;

}

运行时间：13ms   占用内存：2560k

感悟：

　　思路很简单，按顺序合并两个有序的链表，只要针对 每个链表的第一个值进行比较，再递归调用Merge函数即可。

17.树的子结构

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

时间限制：1秒    空间限制：32768K

<?php

/*class TreeNode{

    var $val;

    var $left = NULL;

    var $right = NULL;

    function __construct($val){

        $this->val = $val;

    }

}*/

function HasSubtree($pRoot1, $pRoot2)

{

    // write code here

    if($pRoot1 == null || $pRoot2 == null){

        return false;

    }

    return isSubtree($pRoot1,$pRoot2) || isSubtree($pRoot1->left,$pRoot2) || isSubtree($pRoot1->right,$pRoot2);

}

function isSubtree($pRoot1,$pRoot2){

    if($pRoot2 == null){

        return true;

    }

    if($pRoot2 == null){

        return false;

    }

    return $pRoot1->val == $pRoot2->val && isSubtree($pRoot1->left,$pRoot2->left) && isSubtree($pRoot1->right,$pRoot2->right);

}

运行时间：11ms   占用内存：2432k

感悟：

　　首先判断两个链表是否为空，若空则返false，若不空，则递归调用isSubtree函数，这里要注意调用时要将链表1本身，其左子树，其右子树分别和链表2进行比较,若链表1的比较不成立，再进行其左子树和右子树的调用比较，若链表1本身就成立，则后面的两次调用就没有必要。再来说isSubtree函数，题目要求判断b是不是a的子结构，所以分别判断传入参数的两个链表是否为空，若1空，则返回false，若2空，则肯定是子结构，返回true，最后用与运算递归调用isSubtree函数进行子树的比较。

18.二叉树的镜像

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

输入描述:

二叉树的镜像定义：源二叉树

    	    8

    	   /  \

    	  6   10

    	 / \  / \

    	5  7 9 11

    	镜像二叉树

    	    8

    	   /  \

    	  10   6

    	 / \  / \

    	11 9 7  5
时间限制：1秒   空间限制：32768K

<?php

/*class TreeNode{

    var $val;

    var $left = NULL;

    var $right = NULL;

    function __construct($val){

        $this->val = $val;

    }

}*/

function Mirror(&$root)

{

    // write code here

    if($root == null || ($root->left == null && $root->right == null)){

        return;

    }

    $tmp = $root->left;

    $root->left = $root->right;

    $root->right = $tmp;

    if($root->left){

        Mirror($root->left);

    }

    if($root->right){

        Mirror($root->right);

    }

    return $root;

}

运行时间：12ms   占用内存：2428k

感悟：

　　首先判断该二叉树是否为空树或者是否只有一个节点，若不是，则进行左右子节点的交换，最后将左右节点分别判断，再递归调用原函数Mirror()。

19.顺时针打印矩阵

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

时间限制：1秒   空间限制：32768K

function printMatrix($matrix)

{

    // write code here

    $output = [];

    $left = 0;

    $right = count($matrix[0]);

    $top = 0;

    $buttom = count($matrix);

    if ($right == 0 && $buttom == 0) {

        return $output;

    }

    $right--;

    $buttom--;

    while($left <= $right && $top <= $buttom) {

        for ($i = $left; $i <= $right; $i++) $output[] = $matrix[$top][$i];

         if ($top + 1 > $buttom) break;

        for ($i = $top + 1; $i <= $buttom; $i++) $output[] = $matrix[$i][$right];

         if ($right - 1 < $left) break;

        for ($i = $right - 1; $i >= $left; $i--) $output[] = $matrix[$buttom][$i];

         if ($buttom - 1 <= $top) break;

        for ($i = $buttom -1 ; $i > $top; $i--) $output[] = $matrix[$i][$left];

        $left++;

        $right--;

        $top++;

        $buttom--;

    }

    return $output;

}

运行时间：22ms   占用内存：7808k

感悟：

　　顺时针打印矩阵中的数值，把握好变量的取值，先判断给出的数组是否为空，之后根据top，buttom，left，right四个变量进行左到右，上到下，右到左，下到上的遍历赋值，进行一遍循环后，矩形缩小一圈，左加右减，上加下减，继续遍历，直到left大于等于right且top大于等于buttom，循环结束，输出output数组。

20.包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

时间限制：1秒   空间限制：32768K

<?php

global $mystack;

$mystack = [];

function mypush($node)

{

    // write code here

    global $mystack;

    array_push($mystack,$node);

}

function mypop()

{

    // write code here

    global $mystack;

    array_pop($mystack);

}

function mytop()

{

    // write code here

    global $mystack;

    if(count($mystack) == 0){

        return null;

    }

    return $mystack[count($mystack)-1];

}

function mymin()

{

    // write code here

    global $mystack;

    $min = $mystack[0];

    for($i=0;$i<count($mystack);$i++){

        if($mystack[$i]<$min){

            $min = $mystack[$i];

        }

    }

    return $min;

}

运行时间：11ms   占用内存：2432k

感悟：

　　考察栈的操作，注意定义global变量，进栈出栈，返回栈顶元素，求栈中最小元素，按照一般思路求解即可。

 注：以上均为个人理解，如有错误，请提出，必改正。