小鹅通笔试题 - PHP后端开发技术学习

使用php实现快速排序（非递归方式）

function quickSort($arr = [])
    {
        if (empty($arr) || count($arr) == 1) {
            return $arr;
        }
        $stack = [[0,count($arr)-1]];
        while ($stack) {
            $indexRange = array_pop($stack);
            $leftIndex = $indexRange[0];
            $rightIndex = $indexRange[1];
            $flag = $arr[$leftIndex];
            while ($leftIndex < $rightIndex) {
                while ($leftIndex < $rightIndex && $arr[$rightIndex] >= $flag) {
                    $rightIndex--;
                }
                $arr[$leftIndex] = $arr[$rightIndex];
                while ($leftIndex < $rightIndex && $arr[$leftIndex] < $flag) {
                    $leftIndex++;
                }
                $arr[$rightIndex] = $arr[$leftIndex];
            }
            $arr[$leftIndex] = $flag;
            if ($indexRange[0] < $leftIndex - 1) {
                $stack[] = [$indexRange[0],$leftIndex-1];
            }
            if ($indexRange[1] > $leftIndex + 1) {
                $stack[] = [$leftIndex+1,$indexRange[1]];
            }
        }
        return $arr;
    }

写出查找发贴数最多的十个人名字的sql，表结构如下：

用户表：t_users(id,username,password ,email,created_at)
帖子表：t_post(id,user_id,title,content,created_at)

SELECT a.username,COUNT(b.id)  AS amount FROM t_users AS a LEFT JOIN t_post AS b ON a.id = b.user_id GROUP BY a.id ORDER_BY amount DESC LIMIT 10;

**以下代码需要实现批量(>=100)注册用户到数据库中的功能，要求uname 和 email
不能重复，请找出代码中的错误，并尽可能给出优化建议：**

<?php
$mysqli= new Mysqli($host,$user,$pass);
for($i=0;$i<count($_POST['user_info']);$i++) {
    $info= $_POST['user_info'][$i];
    
    $sql1= "SELECT * FROM `demo` WHERE `uname`=$info['uname']"
$re_1= $mysqli->query($sql1);
$sql2= "SELECT * FROM `demo` WHERE `email`=$info['email']"
    $re_2= $mysqli->query($sql2);
     
    if(!$re_1|| !$re_2) {
        $mysqli->query("INSERT INTO `demo` (`uname`, `email`) VALUES('$info['email']', '$info['uname']')");
    }
}
?>

代码中的错误与优化建议：

(1)没有选择数据库进行操作，需要在实例化Mysqli对象时在第4个参数传入数据库名，或者使用$mysqli->select_db($db_name)方法进行选择

(2)$sql1和$sql2行尾要以英文分号结束，并且行中的$info[‘uname’]和$info[‘email’]需要用单引号’’以及花括号{}括起来，如’{$info[‘uname’]}’

(3)Insert语句的$info[‘uname’],$info[‘email’]数组变量会导致语法错误，需要用花括号{}括起来,并且字段名和值对应顺序错了，VALUES后面应该$info[‘uname’]在前，$info[‘’email]在后

(4)$re_1和$re_2不能判断是否存在记录，只能判断是否执行成功，需要用$re_1->num_rows和$re_2->num_rows来判断是否存在记录，并且条件判断不是(!$re_1 || !re_2)，而是(!$re_1->num_rows&&!$re_2->num_rows)

(5)count($_POST['user_info'])应该放在for循环外，避免每次循环都count一次数组，并且$_POST数据没有进行过滤，需要验证$_POST数据是否有需要的字段，以及过去掉敏感字符，预防SQL注入。

(6)$sql1和$sql2应该整合成一条语句来查询，且查询字段不用全部(*)，语句如SELECT uname FROM WHERE (uname=’{$info[‘uname’]}’) OR (email=’{$info[‘email’]}’)。

(7)代码没有进行错误处理，需要对MySQL的连接和查询进行错误处理。

(8)可以拼接SQL语句一次性查询已经存在的记录，然后再一次性插入不存在的记录
为了避免其他用户也在同一时刻插入相同的用户数据，可以使用事务加行锁或者给uname和email加unique索引，防止插入相同的记录。

给定一个由 n 个正整数组成的数组，正整数的范围为[1, n-1]，数组中只有一个数字是重复的，如何快速找出这个数字？

假定数组为$arr = [8,5,9,2,4,10,6,7,1,3,10];//n=11,正整数范围[1,10]。
第一种方法：
通过观察可发现，数组之和等于1到10(1到n-1)的自然数之和加上重复数字，则重复数字等于数组之和减去1到10自然数之和。

function findSameElement($arr)
    {
        $amount = count($arr);
        $nutrualNumSum = ($amount-1)*($amount-1+1)/2;//自然数求和公式
        $sum = array_sum($arr);
        return $sum-$nutrualNumSum;
    }

第二种方法：
首先将数组进行从小到大排序；然后遍历数组，比较相邻两个元素，相等时的元素便是这个重复的数字。

function findSameElement($arr)
    {
        sort($arr);
        $index = count($arr)-1;
        for ($i=0; $i < $index; $i++) { 
            if ($arr[$i+1] == $arr[$i]) {
                return $arr[$i];
            }
        }
        return 0;
    }

第三种方法：
定义一个$temp数组并只有一个零或者负数的元素，遍历正整数组成的数组，每次遍历判断当前元素是否存在$temp数组中，如果存在，则这个数就是重复的数字，如果不存在，则将当前元素push到$temp数组中，然后继续判断，直到找出存在于数组的元素。

function findSameElement($arr)
    {
        $temp = [0];
        foreach ($arr as $v) {
            if (in_array($v, $temp)) {
                return $v;
            }
            $temp[] = $v;
        }
        return 0;
    }