算法函数
1、1234567890 显示 1,234,567,890
//1. 先反转字符串
//2. 3个字符切割数据
//3. 把切割的数组以 “，”拼接为字符串
//4. 再次反转数据
$str = 1234567890；
var_dump( strrev(implode(',',str_split(strrev($str),3))) );
或：
echo number_format('123456789')."<br>";2、将 "1234567890" 转换成 "0987654321"? 不使用php 字符串内置函数--strrev
//第一种方式
function strrev2($str)
{
$len = strlen($str);
$string = '';
for ($i=$len; $i > 0 ; $i--) {
# code...
$string .= $str[$i-1];
}
return $string;
}
var_dump(strrev2('1234567890'));
// 第二种---递归调用
function reverse($str){
if(strlen($str)>0){
reverse(substr($str,1));
echo substr($str,0,1);
return;
}
}
$res = reverse("abcdefg");//gfedcba
var_dump($res);
//第三种 abcdefg -> gfedcba
$s = '1234567890';
$o = '';
$i = 0;
while(isset($s[$i]) && $s[$i] != null) {
$o = $s[$i++].$o;
}
echo $o;
//第四种 abcdefg -> gfedcba
//将字符串看做数组来处理 [a,b,c,d,e,f,g]
function str_rev($str){
for ($i = 0; true; $i++){
// 判断字符串长度
if (!isset($str[$i])){
break;
}
}
$return = '';
for ($j = $i-1; $j >= 0; $j--){
$return .= $str[$j];
}
return $return;
}
echo str_rev('abcdefg'); // 调用函数
// 第五种方式
//10 9 8 7 6 5 4 3 2 1 0 <-->0 1 2 3 4 5 6 7 8 9 10
function test($n){
echo $n." ";
if($n>0)
test($n-1);
else
echo "<-->";
echo $n." ";
}
test(10);3、反转数组，不使用数组内部函数--array_reverse
/**
* 反转数组
* @param array $arr
* @return array
*/
function reverse($arr)
{
$n = count($arr);
$left = 0;
$right = $n - 1;
while ($left < $right) {
$temp = $arr[$left];
$arr[$left++] = $arr[$right];
$arr[$right--] = $temp;
}
return $arr;
}4、给一个有数字和字母的字符串，让连着的数字和字母对应 1a3bb44a2ac => 1:a 3:bb 44:a 2:ac
function number_alphabet($str)
{
$number = preg_split('/[a-z]+/', $str, -1, PREG_SPLIT_NO_EMPTY);
$alphabet = preg_split('/\d+/', $str, -1, PREG_SPLIT_NO_EMPTY);
var_dump($number);
var_dump($alphabet);
$n = count($number);
for ($i = 0; $i < $n; $i++) {
echo $number[$i] . ':' . $alphabet[$i] . '</br>';
}
}
$str = '1a3bb44a2ac';
number_alphabet($str);//1:a 3:bb 44:a 2:ac5、写一个函数，要求不使用array_merge完成多个数组的合并。
function array_mer()
{
$return = [];
$arrays = func_get_args();
foreach($arrays as $arr)
{
if(is_array($arr))
{
foreach($arr as $val)
{
$return[] = $val;
}
}
}
return $return;
}6、php实现长数字相加的函数，保留精度
思路：将数字的字串形式相加，注意小数与整数部分分开运算
这里以PHP两个大整数相加为例
function big_integer_add($num1, $num2) {
$str1 = strval($num1);
$str2 = strval($num2);
$len = strlen($num1) > strlen($num2) ? strlen($num1) : strlen($num2);
$num1s = strrev($num1);
$num2s = strrev($num2);
$val = 0;
$res = '';
for($i = 0; $i < $len; $i++) {
$num1s[$i] = isset($num1s[$i]) ? $num1s[$i] : 0;
$num2s[$i] = isset($num2s[$i]) ? $num2s[$i] : 0;
$tmp = $num1s[$i] + $num2s[$i] + $val;
$val = 0;
if ($tmp >= 10) {
$val = 1;
$tmp = $tmp-10;
}
$res = (string)$tmp.$res;
}
if ($val == 1) {
$res = $val.$res;
}
return (string)$res;
}
$a = "111111111111555555";
$b = "666666999999999999999999999999999";
$value = big_integer_add($a,$b);
print_r($value);7、PHP解决多进程同时写一个文件的问题。
function write($str)
{
$fp = fopen($file, 'a');
do
{
usleep(100);
} while (!flock($fp, LOCK_EX));
fwrite($fp, $str . PHP_EOL);
flock($fp, LOCK_UN);
fclose($fp);
}8、求n以内的质数
质数的定义：在大于1的自然数中，除了1和它本身意外，无法被其他自然数整除的数
思路：1.（质数筛选定理）n不能够被不大于根号n的任何质数整除，则n是一个质数
2.除了2的偶数都不是质数
/**
* 求n内的质数
* @param int $n
* @return array
*/
function getPrime($n)
{
$prime = array(2);//2为质数
for ($i = 3; $i <= $n; $i += 2) {//偶数不是质数，步长可以加大
$sqrt = intval(sqrt($i));//求根号n
for ($j = 3; $j <= $sqrt; $j += 2) {//i是奇数，当然不能被偶数整除，步长也可以加大。
if ($i % $j == 0) {
break;
}
}
if ($j > $sqrt) {
array_push($prime, $i);
}
}
return $prime;
}
var_dump(getPrime(20));9、斐波那契数列的递推、递归实现
/**
* 斐波那契数列：1 1 2 3 5 8 13 21 ...
*
* 需求：求指定位置的数列的值
* 规律：第一个和第二个为1,从第三个开始为前两个数之和.
*/
//递推思想(把要求位置之前的所有值列出来，那么要求的数就可以通过前两个数之和计算出来【使用数组存储】)
function my_recursive($des){
//判断：如果第一个或者第二个
if($des == 1 || $des == 2) return 1;
//开始计算
$f[1] = 1;
$f[2] = 1;//如果想要第一个或者第二个结果，那么刻意直接给出
for ($i = 3; $i <= $des; $i++) {
$f[$i] = $f[$i-1] + $f[$i-2];
}
//返回最后一个位置的结果
return $f[$des];
}
echo my_recursive(15);
//递归思想(函数调用自己)
function recursion($n){
//递归出口
if($n == 1 || $n == 2) return 1;
//递归点：求N的值，与求N-1的值一模一样
return recursion($n - 1) + recursion($n - 2);
}
echo recursion(15);10、约瑟夫环问题--猴子找大王
相关题目：一群猴子排成一圈，按1,2,…,n依次编号。然后从第1只开始数，数到第m只,把它踢出圈，从它后面再开始数， 再数到第m只，在把它踢出去…，如此不停的进行下去， 直到最后只剩下一只猴子为止，那只猴子就叫做大王。要求编程模拟此过程，输入m、n, 输出最后那个大王的编号。
/**
* 获取大王
* @param int $n
* @param int $m
* @return int
*/
function get_king_mokey($n, $m)
{
$arr = range(1, $n);
$i = 0;
while (count($arr) > 1) {
$i++;
$survice = array_shift($arr);
if ($i % $m != 0) {
array_push($arr, $survice);
}
}
return $arr[0];
}
var_dump(get_king_mokey(10, 2));
function monkey($m,$n){
$arr=range(1,$m);
$i=0;
while(count($arr)>1){
if(($i+1)%$n==0){
unset($arr[$i]);
}else{
$arr[]=$arr[$i];
unset($arr[$i]);
}
$i++;
}
return $arr[$i];
}
var_dump(monkey(10,4));//511、如何快速寻找一个数组里最小的1000个数
思路：假设最前面的1000个数为最小的，算出这1000个数中最大的数，然后和第1001个数比较，如果这最大的数比这第1001个数小的话跳过，如果要比这第1001个数大则将两个数交换位置，并算出新的1000个数里面的最大数，再和下一个数比较，以此类推。
//寻找最小的k个数
//题目描述
//输入n个整数，输出其中最小的k个。
/**
* 获取最小的k个数
* @param array $arr
* @param int $k [description]
* @return array
*/
function get_min_array($arr, $k)
{
$n = count($arr);
$min_array = array();
for ($i = 0; $i < $n; $i++) {
if ($i < $k)
{
$min_array[$i] = $arr[$i];
}
else
{
if ($i == $k) {
$max_pos = get_max_pos($min_array);
$max = $min_array[$max_pos];
}
if ($arr[$i] < $max) {
$min_array[$max_pos] = $arr[$i];
$max_pos = get_max_pos($min_array);
$max = $min_array[$max_pos];
}
}
}
return $min_array;
}
/**
* 获取最大的位置
* @param array $arr
* @return array
*/
function get_max_pos($arr)
{
$pos = 0;
for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] > $arr[$pos]) {
$pos = $i;
}
}
return $pos;
}
$arr = array(1,2,2,6,20,14,32,15,12,20,39,49,95,85,83,1);
var_dump( get_min_array($arr, 5) );12、如何在有序的数组中找到一个数的位置（二分查找）
/**
* 二分查找
* @param array $array 数组
* @param int $n 数组数量
* @param int $value 要寻找的值
* @return int
*/
function binary_search($array, $n, $value)
{
$left = 0;
$right = $n - 1;
while ($left <= $right)
{
$mid = intval(($left + $right) / 2);
if($array[$mid] == $value)
{
return $mid;
}
elseif($array[$mid] > $value)
{
$right = $mid - 1;
}
else
{
$left = $mid + 1;
}
}
return -1;
}
$array = array(1,2,3,4,5,6,7,8,9,10);
var_dump(binary_search($array, count($array), 4));13、给定一个有序整数序列，找出绝对值最小的元素（二分查找）
思路：二分查找
/**
* 获取绝对值最小的元素
* @param array $arr
* @return int
*/
function get_min_abs_value($arr)
{
//二分查找
$n = count($arr);
//如果符号相同，直接返回
if (is_same_sign($arr[0], $arr[$n - 1])) {
return $arr[0] >= 0 ? $arr[0] : $arr[$n - 1];
}
$left = 0;
$right = $n - 1;
while ($left <= $right) {
if ($left + 1 === $right) {
return abs($arr[$left]) < abs($arr[$right]) ? $arr[$left] : $arr[$right];
}
$mid = intval(($left + $right) / 2);
if ($arr[$mid] < 0) {
$left = $mid + 1;
} else {
$right = $mid - 1;
}
}
return $arr[$mid];
}
/**
* 判断符号是否相同
* @param int $a
* @param int $b
* @return boolean
*/
function is_same_sign($a, $b)
{
if ($a * $b > 0) {
return true;
} else {
return false;
}
}
//$array = array(1,2,3,4,5,6,7,8,9,10);
//$array = array(-10,-9,-8,-7,-6,-5,-4,-3,-2,-1);
$array = array(-1,0,2,3,4,6,7,9,10);
var_dump(get_min_abs_value($array));14、找出有序数组中随机3个数和为0的所有情况
思路：动态规划
function three_sum($arr)
{
$n = count($arr);
$return = array();
for ($i=0; $i < $n; $i++) {
$left = $i + 1;
$right = $n - 1;
while ($left <= $right) {
$sum = $arr[$i] + $arr[$left] + $arr[$right];
if ($sum < 0)
{
$left++;
}
elseif ($sum > 0)
{
$right--;
}
else
{
$numbers = $arr[$i] . ',' . $arr[$left] . ',' . $arr[$right];
if (!in_array($numbers, $return))
{
$return[] = $numbers;
}
$left++;
$right--;
}
}
}
return $return;
}
$arr = [-10, -9, -8, -4, -2, 0, 1, 2, 3, 4, 5, 6, 9];
var_dump(three_sum($arr));15、编写一个PHP函数，求任意n个正负整数里面最大的连续和，要求算法时间复杂度尽可能低。
思路：动态规划
/**
* 获取最大的连续和
* @param array $arr
* @return int
*/
function max_sum_array($arr)
{
$currSum = 0;
$maxSum = 0;//数组元素全为负的情况，返回最大数
$n = count($arr);
for ($i = 0; $i < $n; $i++) {
if ($currSum >= 0) {
$currSum += $arr[$i];
} else {
$currSum = $arr[$i];
}
}
if ($currSum > $maxSum) {
$maxSum = $currSum;
}
return $maxSum;
}
$arr = array(-1, 0, 1, 2, 3, 4, -2, 5, 1, 2);
var_dump(max_sum_array($arr));16、php 统计出两个数组(长度10000)中同时出现过的，并且总出现次数最多的单词
$arr1 = array(1, "hello", 1, "world", "hello",2,2);
$arr2 = array(1, "hello", 11, "world1", "hello1",2,2);
$arr_count1=array_count_values($arr1);
$arr_count2=array_count_values($arr2);
$arr=array_intersect($arr1,$arr2);
$arr_result=array();
foreach ($arr as $v){
$arr_result[$v]=$arr_count1[$v]+$arr_count2[$v];
}
asort($arr_result);
var_dump($arr_result);17、PHP计算两个坐标之间的距离
/**
* 计算两点之间的距离
* @param $lng1 经度1
* @param $lat1 纬度1
* @param $lng2 经度2
* @param $lat2 纬度2
* @param int $unit m，km
* @param int $decimal 位数
* @return float
*/
function getDistance($lng1, $lat1, $lng2, $lat2, $unit = 2, $decimal = 2)
{
$EARTH_RADIUS = 6370.996; // 地球半径系数
$PI = 3.1415926535898;
$radLat1 = $lat1 * $PI / 180.0;
$radLat2 = $lat2 * $PI / 180.0;
$radLng1 = $lng1 * $PI / 180.0;
$radLng2 = $lng2 * $PI / 180.0;
$a = $radLat1 - $radLat2;
$b = $radLng1 - $radLng2;
$distance = 2 * asin(sqrt(pow(sin($a / 2), 2) + cos($radLat1) * cos($radLat2) * pow(sin($b / 2), 2)));
$distance = $distance * $EARTH_RADIUS * 1000;
if ($unit === 2) {
$distance /= 1000;
}
return round($distance, $decimal);
}
// 起点坐标
$lng1 = 118.34593200683594;
$lat1 = 33.9527587890625;
// 终点坐标
$lng2 = 118.301612;
$lat2 = 33.936781;
$distance = getDistance($lng1, $lat1, $lng2, $lat2, 1);
echo $distance . 'm' . PHP_EOL; // 4457.64m
$distance = getDistance($lng1, $lat1, $lng2, $lat2);
echo $distance . 'km' . PHP_EOL; // 4.46km18、两个有序int集合是否有相同元素的最优算法
/**
* 寻找两个有序数组里相同的元素
* @param array $arr1
* @param array $arr2
* @return array
*/
function find_common($arr1, $arr2){
$common = array();
$i = $j = 0;
$count1 = count($arr1);
$count2 = count($arr2);
while ($i < $count1 && $j < $count2) {
if ($arr1[$i] < $arr2[$j]) {
$i++;
} elseif ($arr1[$i] > $arr2[$j]) {
$j++;
} else {
$common[] = $arr[$i];
$i++;
$j++;
}
}
return array_unique($common);
}19、给一个有数字和字母的字符串，让连着的数字和字母对应
function number_alphabet($str){
$number = preg_split('/[a-z]+/', $str, -1, PREG_SPLIT_NO_EMPTY);
$alphabet = preg_split('/\d+/', $str, -1, PREG_SPLIT_NO_EMPTY);
$n = count($number);
for ($i = 0; $i < $count; $i++) {
echo $number[$i] . ':' . $alphabet[$i] . '</br>';
}
}
$str = '1a3bb44a2ac';
number_alphabet($str);//1:a 3:bb 44:a 2:ac20、PHP实现无限极分类的方式
$array = array(
array('id' => 1, 'pid' => 0, 'name' => '1级'),
array('id' => 2, 'pid' => 0, 'name' => '1级'),
array('id' => 3, 'pid' => 1, 'name' => '2级'),
array('id' => 4, 'pid' => 2, 'name' => '2级'),
array('id' => 5, 'pid' => 2, 'name' => '2级'),
array('id' => 6, 'pid' => 4, 'name' => '3级'),
array('id' => 7, 'pid' => 4, 'name' => '3级'),
array('id' => 8, 'pid' => 3, 'name' => '3级'),
array('id' => 9, 'pid' => 1, 'name' => '2级'),
array('id' => 10, 'pid' => 8, 'name' => '4级'),
array('id' => 11, 'pid' => 10, 'name' => '5级'),
array('id' => 12, 'pid' => 11, 'name' => '6级'),
//...
);
//递归算法
function getTree($array, $pid =0, $level = 0){
//声明静态数组,避免递归调用时,多次声明导致数组覆盖
static $list = [];
foreach ($array as $key => $value){
//第一次遍历,找到父节点为根节点的节点 也就是pid=0的节点
if ($value['pid'] == $pid){
//父节点为根节点的节点,级别为0，也就是第一级
$value['level'] = $level;
//把数组放到list中
$list[] = $value;
//把这个节点从数组中移除,减少后续递归消耗
unset($array[$key]);
//开始递归,查找父ID为该节点ID的节点,级别则为原级别+1
getTree($array, $value['id'], $level+1);
}
}
return $list;
}
/************** 调用递归方法后遍历新数组 ****************/
$tree1 = getTree($array);
foreach($tree1 as $val){
echo str_repeat('--', $val['level']).$val['name'].'<br />';
}
//引用算法
function generateTree($array){
//第一步 构造数据
$items = array();
foreach($array as $value){
$items[$value['id']] = $value;
}
//第二步 遍历数据 生成树状结构
$tree = array();
foreach($items as $key => $value){
if(isset($items[$value['pid']])){
//存在父级
/************** 引用了$items[$value['pid']] 所以$items[$value['pid']]改变,$tree的关联的键元素也会发生改变 ****************/
/************** 看不懂这一步的建议去了解一下引用的原理 ****************/
$items[$value['pid']]['children'][] = &$items[$key];
}else{
//不存在父级的顶级元素才会走到这一步
/************** 看不懂这一步的建议去了解一下引用的原理 ****************/
$tree[] = &$items[$key];
}
}
return $tree;
}
$tree2 = generateTree($array);
function ergoTree($arr,$level=0){
foreach ($arr as $item){
if(isset($item['children'])){
echo str_repeat('--', $level).$item['name']."<br>";
ergoTree($item['children'],$level+1);
}else{
echo str_repeat('--', $level).$item['name']."<br>";
}
}
}
ergoTree($tree2);21、笛卡尔积-商品库存添加
// 笛卡尔积
$input = [
["16G", "128G", "64G"],
["深灰色", "银色", "金色"],
["XXX", "MM", "PPP"],
];
$output = array_reduce($input, function($result, $cross_item){
if(!$result){
return array_map(function($item){
return [$item];
}, $cross_item);
}
return array_reduce($cross_item, function($acc, $target) use ($result){
return array_merge($acc, array_map(function($result_item) use ($target){
$result_item[] = $target;
return $result_item;
}, $result));
}, []);
}, []);
echo "<pre>";
print_r($output);本文为崔凯原创文章,转载无需和我联系,但请注明来自冷暖自知一抹茶ckhttp://www.cksite.cn
- 上一篇： 网站登录接入第三方接口--github登录
- 下一篇： Redis数据库都有哪些用处？
请先登录后发表评论
- 最新评论
- 总共0条评论
