Double段

Double段 查看完整档案

北京编辑河北科技大学  |  计算机科学与技术 编辑  |  填写所在公司/组织 segmentfault.com/blog/duanzhichao 编辑
编辑

穿过旷野的风,你慢些走~

个人动态

Double段 赞了回答 · 2020-05-23

解决关于怎么让div宽度自适应文字内容?

直接用css3的fit-content:

width:fit-content;
width:-webkit-fit-content;
width:-moz-fit-content;

关注 8 回答 5

Double段 发布了文章 · 2019-06-24

PHP初级开发知识体系图

赞 6 收藏 5 评论 0

Double段 评论了文章 · 2019-05-14

PHP高效导出Excel(CSV)

CSV,是Comma Separated Value(逗号分隔值)的英文缩写,通常都是纯文本文件。
如果你导出的Excel没有什么高级用法的话,只是做导出数据用那么建议使用本方法,要比PHPexcel要高效的多。
二十万数据导出大概需要23秒。

 /**
 * 导出excel(csv)
 * @data 导出数据
 * @headlist 第一行,列名
 * @fileName 输出Excel文件名
 */
function csv_export($data = array(), $headlist = array(), $fileName) {
  
    header('Content-Type: application/vnd.ms-excel');
    header('Content-Disposition: attachment;filename="'.$fileName.'.csv"');
    header('Cache-Control: max-age=0');
  
    //打开PHP文件句柄,php://output 表示直接输出到浏览器
    $fp = fopen('php://output', 'a');
    
    //输出Excel列名信息
    foreach ($headlist as $key => $value) {
        //CSV的Excel支持GBK编码,一定要转换,否则乱码
        $headlist[$key] = iconv('utf-8', 'gbk', $value);
    }
  
    //将数据通过fputcsv写到文件句柄
    fputcsv($fp, $headlist);
    
    //计数器
    $num = 0;
    
    //每隔$limit行,刷新一下输出buffer,不要太大,也不要太小
    $limit = 100000;
    
    //逐行取出数据,不浪费内存
    $count = count($data);
    for ($i = 0; $i < $count; $i++) {
    
        $num++;
        
        //刷新一下输出buffer,防止由于数据过多造成问题
        if ($limit == $num) { 
            ob_flush();
            flush();
            $num = 0;
        }
        
        $row = $data[$i];
        foreach ($row as $key => $value) {
            $row[$key] = iconv('utf-8', 'gbk', $value);
        }

        fputcsv($fp, $row);
    }
  }
查看原文

Double段 关注了用户 · 2018-02-05

soledad @soledad

我们努力的付出想换来的是什么,我只想让自己过得快乐点

关注 26

Double段 关注了用户 · 2017-10-20

fighter @fighter_58f5bf2d120bd

A phper and gopher :)

关注 1

Double段 发布了文章 · 2017-10-20

Docker中配置Nginx与PHP

最近在学docker,顺便配置了一下docker中的nginx与php,发现网上的关于docker中配置nginx与php的资料很少,而且有的也很旧,没有太多的参考性,所以决定自己写一篇,分享一下其中的经验。

版本说明

  1. docker: Version 17.06.2-ce-mac27 (19124)
  2. PHP:7.1
  3. Nginx:1.13.3
  4. 操作系统 Mac 10.12.6

安装docker

直接上docker的官网https://www.docker.com下载docker For Mac这个版本,是docker专门为mac系统编写的软件,相当于一个app,下载安装好后,打开docker App,然后在App中启动docker即可。

安装Nginx

启动docker之后,打开命令行,你的命令行里面就有了docker这个命令:

clipboard.png

然后我直接使用的是官方的nginx镜像,下载方法:

docker pull nginx

等待下载完即可。

安装PHP

同理,我也是使用的官方的PHP镜像,其实nginx和php我都推荐官方的镜像,毕竟官方镜像代表着安全和稳定。

docker pull php:7.1-fpm

你如果想下载其他的版本,上官方镜像上面去看一下,都有各种版本的说明,想下载什么版本的都有。我这里就用的最新的php版本了。

启动Nginx

安装好nginx之后,便用命令启动它:

docker run -p 80:80 --name mynginx -v /Users/Doubleduan/Documents/project:/home -v /Users/Doubleduan/Documents/conf:/etc/nginx/conf.d -d nginx 
  • -p 代表着把容器中的80端口绑定到宿主机的80端口,所以以后访问宿主机的80端口就会转发到nginx容器的80端口
  • --name 启动的容器的名称,自己定义,方便好记就行
  • -v 就是把我主机的/Users/Doubleduan/Documents/project目录映射到容器中的/home目录中,在容器中访问/home你就会发现是我/Users/Doubleduan/Documents/project目录中的东西。我映射了项目目录和配置文件,你也可以把日志目录也映射了,这样你以后操作什么东西直接在主机中操作了,就不用登录容器中去查看了。
  • -d 后台运行容器
  • 后面的那个nginx就是镜像的名称了

启动PHP

docker run -p 9000:9000 --name myphp -v /Users/Doubleduan/Documents/project:/home -d php:7.1-fpm

配置nginx的配置文件

下面贴出我的配置

server {
    listen       80;
    server_name  algo.test.com;
    root /home/algorithm;

    access_log  /var/log/nginx/access.log  main;
    error_log /var/log/nginx/error.log error;

    location / {
        index  index.html index.htm index.php;
    }

    location ~ \.php$ {
        fastcgi_pass   172.17.0.3:9000;
        fastcgi_index  index.php;
        fastcgi_param  SCRIPT_FILENAME  $document_root$fastcgi_script_name;
        include        fastcgi_params;
    }
}

这个algo.test.com我在主机的hosts文件中配置的指向127.0.0.1,其实就是访问的本机80端口。这里要特别注意两个点:

第一点:是fastcgi_pass 172.17.0.3:9000,这里的172.17.0.3就是php容器的ip,查询容器IP的方法:

docker inspect 容器ID或容器名 |grep '"IPAddress"'

你自己配置的话要替换成你自己的php容器ip,注意不能用127.0.0.1,因为我用的是docker默认的网络连接模式,也就是docker bridge模式,这种模式下你要访问另一个容器就必须用那个容器的虚拟ip,而且端口也必须要与宿主机的相应端口绑定,因为宿主机是一个网关,nginx容器访问php容器要经过宿主机的网关转发的,所以不绑定端口肯定访问不了。

第二点
关于fastcgi_param SCRIPT_FILENAME $document_root$fastcgi_script_name这个配置,如果你想用$document_root变量,那就必须把nginx容器的数据目录与php容器的数据目录弄成一致的,比如我的nginx容器的数据目录是/home/algorithm,在php容器中依然是这个,如果php容器中的目录改变了,不是这个了,那么php容器就会找不到请求的这个文件的。因为两个容器相当于两套文件系统,路径有可能是不一样的。但是呢,如果你偏要设置成不一样的,那么只能写死地址了,比如弄成这样:fastcgi_param SCRIPT_FILENAME /home/algorithm/$fastcgi_script_name,就可以让php容器访问到相应的文件了。

弄好配置文件之后,重启nginx容器,就可以访问了。

查看原文

赞 12 收藏 15 评论 2

Double段 关注了用户 · 2017-09-28

苏生不惑 @sushengbuhuo

同名公众号:苏生不惑

关注 1825

Double段 关注了用户 · 2017-09-28

vimac @vimac

关注 684

Double段 关注了用户 · 2017-09-28

joyqi @joyqi

我的生涯一片无悔,想起那天夕阳下的奔跑,那是我逝去的青春

关注 1332

Double段 关注了用户 · 2017-09-28

daryl @daryl

2018 年上半年要做的事情:

[] 读完《现代操作系统》
[x] 读完《数据结构与算法分析(C 语言描述)》
[] 读《UNIX 环境高级编程》
[] 读《UNIX 网络编程(卷1)》
[] 尝试完成自己的一个 PHP 框架
[] 尝试实现一个 Workman
[] 至少读完一半《C++ Primer》

关注 138

Double段 关注了用户 · 2017-09-28

lifesign @lifesign

  • Learn From Life.
  • ST 重度用户,效率爱好者. 公众号: Sublime Text

关注 3

Double段 发布了文章 · 2017-07-25

top-k 算法浅析

简介

top-k算法,其实就是寻找最大的k个数(具体详见《编程之美》第2.5节“寻找最大的k个数”)。比如一个数组:1,2,5,9,4,3,7 需要寻找最大的2个数,那么就是9和7。最早之前我接触到topk算法的时候,觉得解决思路就是排序,排完序之后,取前k个数就可以了。但是这种思路虽然简单,但是效率是很差的。因为题目只要求最大的k个数,并不需要k个数有序,也不需要后n-k个数有序。

解决方法

我用的是解法四,用一个容量为k的最小堆来储存最大的k个数。最小堆的堆顶元素就是最大k个数中最小的一个。每次新考虑一个数x,如果x比堆顶的元素y小,则不需要改变原来的堆,因为这个元素比最大的k个数小。如果x比堆顶的元素大,那么用x替换堆顶的元素y。在x替换堆顶元素y后,x可能破坏最小堆的结构(每个结点都比它的父亲结点大),需要更新堆来维持堆的性质。

代码实现(C语言)

#include <stdio.h>
#include <stdlib.h>

// 定义取最大N个数
#define TOP_K 6
int heap[6];

// 交换数据
void swap(int *a, int *b)
{
    int temp = *b;
    *b = *a;
    *a = temp;
}

// 调整最小堆
void min_heapify(int arr[], int start, int end)
{
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end)
    {
        if (son + 1 <= end && arr[son] > arr[son + 1])
            son++;
        if (arr[dad] < arr[son])
            return;
        else
        {
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

// 建立最小堆
void buid_heap(int heap[])
{
    int i;
    for (i = TOP_K / 2; i >= 0; i--)
    {
        min_heapify(heap, i, TOP_K - 1);
    }
}

// 8,8,8,9,9,9
int main()
{
    int arr[] = {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
    int len = (int)sizeof(arr) / sizeof(*arr);
    int i;

    // 堆赋值
    for (i = 0; i < TOP_K; i++)
    {
        heap[i] = arr[i];
    }

    buid_heap(heap); // 建立最小堆

    // 循环遍历整个数组
    for (i = TOP_K + 1; i <= len; i++)
    {
        if (arr[i] > heap[0]) // 只有大于根节点才处理
        {
            heap[0] = arr[i];
            min_heapify(heap, 0, TOP_K - 1); // 向下调整堆
        }
    }

    // 打印最大key个数
    for (i = 0; i < TOP_K; i++)
    {
        printf("%d ", heap[i]);
    }
}
查看原文

赞 0 收藏 1 评论 0

Double段 赞了文章 · 2017-06-10

使用 OpCache 提升 PHP 性能

OpCache 通过对 opcode 的缓存和优化来提升 PHP 执行速度。在 PHP 5.5、5.6 版本中 OpCache 已内建,编译安装时使用 --enable-opcache 即可。PHP 5.2 - 5.4 也可手动安装。

项目主页

http://pecl.php.net/package/ZendOpcache

开启方法

修改 php.ini 文件sudo vim /etc/php.ini

在文件最后面加入:

; 开关打开
opcache.enable=1

; 可用内存, 酌情而定, 单位 megabytes
opcache.memory_consumption=256

; 最大缓存的文件数目, 命中率不到 100% 的话, 可以试着提高这个值
opcache.max_accelerated_files=5000

; Opcache 会在一定时间内去检查文件的修改时间, 这里设置检查的时间周期, 默认为 2, 单位为秒
opcache.revalidate_freq=240

; interned string 的内存大小, 也可调
opcache.interned_strings_buffer=8   

; 是否快速关闭, 打开后在PHP Request Shutdown的时候回收内存的速度会提高
opcache.fast_shutdown=1

; 不保存文件/函数的注释
opcache.save_comments=0

检查安装:

    php -v

    PHP 5.5.3-1ubuntu2.2 (cli) (built: Feb 28 2014 20:06:05) 
    Copyright (c) 1997-2013 The PHP Group
    Zend Engine v2.5.0, Copyright (c) 1998-2013 Zend Technologies
        with Zend OPcache v7.0.3-dev, Copyright (c) 1999-2013, by Zend Technologies

重启服务

sudo /etc/init.d/php-fpm restart
sudo /etc/init.d/nginx restart

查看效果

小提示

如果在更新代码之后,发现没有执行的还是旧代码,可使用函数 opcache_reset() 来清除缓存。该函数将重置整个字节码缓存。 在调用 opcache_reset() 之后,所有的脚本将会重新载入并且在下次被点击的时候重新解析。

参考:

1、使用 OpCache 提升 PHP 5.5+ 程序性能:https://phphub.org/topics/301
2、ZendOpcache 官方下载:http://pecl.php.net/package/ZendOpcache
3、一个关于Zend O+的小分享:http://www.laruence.com/2013/11/11/2928.html
4、OCP -Opcache Control Panel:https://gist.github.com/ck-on/4959032
5、PHP WIKI 关于整合 ZendOpcache 进入发行版的讨论:https://wiki.php.net/rfc/optimizerplus

查看原文

赞 7 收藏 37 评论 2

Double段 回答了问题 · 2017-06-02

解决天猫首页首屏数据来源

研究了一下午,大概是明白了,天猫首页在服务端使用node做的,所以html渲染的时候就会把数据带上。楼上说的比较对,这种查看源代码就有的数据肯定是服务端直出的。不知道的同学可以搜索一下同构渲染,就是同一份js代码,先在服务端完成页面结构和数据的渲染,然后给到浏览器,浏览器只执行一些事件绑定相关的东西,这样的话会大大提高首屏的加载速度。现在前端最火的vue和react都有相关的服务端渲染的功能。

关注 7 回答 7

Double段 提出了问题 · 2017-06-02

解决天猫首页首屏数据来源

我在研究天猫首页的代码,感觉它的首屏数据并不像是ajax加载的,所以我想问一下,它的首屏数据是利用什么方式加载的?

比如:

window.g_config.serverTime = 1496370628991;   // "1496370628991"这个数字每次刷新都是变化的
<div id="J_defaultData" style="display:none;"> ………… </div> // 这个div(div中的json数据太长,所以省略了)里面的数据查看源代码的时候就有,并不像是ajax请求的。

下图是div中的数据

clipboard.png

关注 7 回答 7

Double段 关注了用户 · 2017-05-11

和平老三 @huangjuyuan

二他妈妈,快拿大木盆来,可赶上这波了!

关注 9

Double段 发布了文章 · 2017-05-11

MYSQL中的乐观锁实现(MVCC)简析

什么是MVCC

MVCC即Multi-Version Concurrency Control,中文翻译过来叫多版本并发控制。

MVCC是解决了什么问题

众所周知,在MYSQL中,MyISAM使用的是表锁,InnoDB使用的是行锁。而InnoDB的事务分为四个隔离级别,其中默认的隔离级别REPEATABLE READ需要两个不同的事务相互之间不能影响,而且还能支持并发,这点悲观锁是达不到的,所以REPEATABLE READ采用的就是乐观锁,而乐观锁的实现采用的就是MVCC。正是因为有了MVCC,才造就了InnoDB强大的事务处理能力。

MVCC具体实现分析

InnoDB的MVCC,是通过在每行记录后面保存两个隐藏的列来实现的,这两个列,分别保存了这个行的创建时间,一个保存的是行的删除时间。这里存储的并不是实际的时间值,而是系统版本号(可以理解为事务的ID),每开始一个新的事务,系统版本号就会自动递增,事务开始时刻的系统版本号会作为事务的ID.下面看一下在REPEATABLE READ隔离级别下,MVCC具体是如何操作的。


首先创建一张表:

create table yang( 
    id int primary key auto_increment, 
    name varchar(20)
);

假设系统的版本号从1开始.

INSERT

InnoDB为新插入的每一行保存当前系统版本号作为版本号。第一个事务ID为1:

start transaction; 
insert into yang values(NULL,'yang');
insert into yang values(NULL,'long');
insert into yang values(NULL,'fei');
commit;

对应在数据中的表如下(后面两列是隐藏列,我们通过查询语句并看不到)

idname创建时间(事务ID)删除时间(事务ID)
1yang1undefined
2long1undefined
3fei1undefined

SELECT

InnoDB会根据以下两个条件检查每行记录:

  1. InnoDB只会查找版本早于当前事务版本的数据行(也就是,行的系统版本号小于或等于事务的系统版本号),这样可以确保事务读取的行,要么是在事务开始前已经存在的,要么是事务自身插入或者修改过的.

  2. 行的删除版本要么未定义,要么大于当前事务版本号(这可以确保事务读取到的行,在事务开始之前未被删除),
    只有条件1、2同时满足的记录,才能返回作为查询结果.

DELETE

InnoDB会为删除的每一行保存当前系统的版本号(事务的ID)作为删除标识.

看下面的具体例子分析: 第二个事务,ID为2:

start transaction; 
select * from yang; 
select * from yang; 
commit;

假设1:
假设在执行这个事务ID为2的过程中,刚执行到(1),这时,有另一个事务ID为3往这个表里插入了一条数据; 第三个事务ID为3;

start transaction;
insert into yang values(NULL,'tian');
commit;

这时表中的数据如下:

idname创建时间(事务ID)删除时间(事务ID)
1yang1undefined
2long1undefined
3fei1undefined
4tian3undefined

然后接着执行事务2中的(2),由于id=4的数据的创建时间(事务ID为3),执行当前事务的ID为2,而InnoDB只会查找事务ID小于等于当前事务ID的数据行,所以id=4的数据行并不会在执行事务2中的(2)被检索出来,在事务2中的两条select 语句检索出来的数据如下:

idname创建时间(事务ID)删除时间(事务ID)
1yang1undefined
2long1undefined
3fei1undefined

假设2
假设在执行这个事务ID为2的过程中,刚执行到(1),假设事务执行完事务3后,接着又执行了事务4;
第四个事务:

start transaction; 
delete from yang where id=1; 
commit;

此时数据库中的表如下:

idname创建时间(事务ID)删除时间(事务ID)
1yang14
2long1undefined
3fei1undefined
4tian3undefined

接着执行事务ID为2的事务(2),根据SELECT 检索条件可以知道,它会检索创建时间(创建事务的ID)小于当前事务ID的行和删除时间(删除事务的ID)大于当前事务的行,而id=4的行上面已经说过,而id=1的行由于删除时间(删除事务的ID)大于当前事务的ID,所以事务2的(2)select * from yang也会把id=1的数据检索出来.所以,事务2中的两条select 语句检索出来的数据都如下:

idname创建时间(事务ID)删除时间(事务ID)
1yang14
2long1undefined
3fei1undefined

UPDATE

InnoDB执行UPDATE,实际上是新插入了一行记录,并保存其创建时间为当前事务的ID,同时保存当前事务ID到要UPDATE的行的删除时间。
假设3:
假设在执行完事务2的(1)后又执行,其它用户执行了事务3,4,这时,又有一个用户对这张表执行了UPDATE操作:
第5个事务:

start transaction; 
update yang set name='Long' where id=2;
commit;

根据update的更新原则:会生成新的一行,并在原来要修改的列的删除时间列上添加本事务ID,得到表如下:

idname创建时间(事务ID)删除时间(事务ID)
1yang14
2long15
3fei1undefined
4tian3undefined
2Long5undefined

继续执行事务2的(2),根据select 语句的检索条件,得到下表:

idname创建时间(事务ID)删除时间(事务ID)
1yang14
2long15
3fei1undefined

还是和事务2中(1)select 得到相同的结果.

查看原文

赞 7 收藏 13 评论 10

Double段 回答了问题 · 2017-05-10

ajax请求问题

应该是服务器有什么特殊的配置吧。个人认为你的服务器应该配置了一些转发的规则

关注 2 回答 1

Double段 发布了文章 · 2017-04-26

关于求杨辉三角形mn值的算法

杨辉三角形,又称贾宪三角形、帕斯卡三角形、海亚姆三角形,是二项式系数在的一种写法,形似三角形,在中国首现于南宋杨辉的《详解九章算术》得名,书中杨辉说明是引自贾宪的《释锁算术》,故又名贾宪三角形。

前9层写出来如下:
        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1
   1 5 10 10 5 1
  1 6 15 20 15 6 1
 1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1


递归法

首先给大家介绍一种最简单的求杨辉三角mn值的方法(m为行,n为列,比如(5,3)即为第五行第三个,值为6)即为递归法:

function recursion($m, $n) {
    if ($n == 1 || $n == $m || $m == 1) {
        return 1;
    }

    $val = recursion($m-1, $n - 1) + recursion($m-1, $n);

    return $val;
}

这种方法实现最简单,但是如果mn的值特别大的话,性能会非常差,我试了个100,78,就把机器卡死了。。

迭代法

迭代法从第一层开始循环,只循环每行中必要的列,最后求出mn位置的值。代码如下:

function setNum($row, $list)
{
    $arr = array();
    for ($i = 0; $i < $row; $i++) {
        $start = ($list - ($row - $i)) < 0 ? 0 : ($list - ($row - $i));
        $end = ($list - 1) > $i ? $i : ($list - 1);
        for ($j = $start; $j <= $end; $j++) {
            if ($i == 0 || $i == 1 || $j == 0 || $i == $j) {
                $arr[$i][$j] = 1;
            } else {
                $arr[$i][$j] = $arr[$i - 1][$j] + $arr[$i - 1][$j - 1];
            }
        }
    }
    return $arr[--$row][--$list];
}

公式法

当然了,根据杨辉三角的性质:第n行的m个数可表示为 C(n-1,m-1),用排列组合的公式也可以获得mn的值,代码如下:

function express($m, $n) {
    $up = 1;
    for ($i = $m - 1; $i > ($m - $n); $i--) {
        $up *= $i;
    }


    $down = 1;
    for ($i = $n - 1; $i > 0; $i--) {
        $down *= $i;
    }

    return $up / $down;
}
查看原文

赞 0 收藏 1 评论 0

Double段 发布了文章 · 2017-03-13

剑指offer中的算法题(PHP版)

二维数组中的查找

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

function search($target, $array)
{
    $i = count($array[0]) - 1;
    $j = 0;

    if ($array[count($array) - 1][$i] < $target || $array[0][0] > $target) {
        return false;
    }

    for ($i; $i >= 0; $i--) {
        if ($array[$j][$i] <= $target) {
            for ($j; $j < count($array); $j++) {
                if ($array[$j][$i] == $target) {
                    return true;
                } else if ($array[$j][$i] > $target) {
                    break;
                }
            }
        }
    }

    return false;
}


$s = [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]];
var_dump(search(1, $s));

替换空格

请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

function replace($str) {
    $len = strlen($str);
    if ($len <= 0 ) {
        return false;
    }
    $blank = 0;
    for ($i = 0; $i < $len; $i++) {
        if ($str[$i] == ' ') {
            $blank++;
        }
    }
    if ($blank == 0) {
        return false;
    }

    $new_length = ($len + $blank * 2) - 1;

    for ($i = $len-1; $i >=0; $i--) {
        if ($str[$i] == ' ') {
            $str[$new_length--] = '0';
            $str[$new_length--] = '2';
            $str[$new_length--] = '%';
        } else {
            $str[$new_length--] = $str[$i];
        }
    }

    return $str;
}


var_dump(replace('We Are Happy'));

斐波那契数列

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。解法有两种,一种是递归法,一种是迭代法,但是递归法计算的时间复杂度是以n的指数的方式递增的,如果面试中千万不要用递归法,一定要用迭代法。

递归法

function a($n) {
    if ($n == 0) {
        return 0;
    } else if ($n == 1) {
        return 1;
    }

    return a($n-1) + a($n - 2);
}


echo a(10);

迭代法

function a($n) {

    $ret = array();

    for ($i=0; $i <= $n; $i++) {
        if ($i == 0) {
            $ret[$i] = 0;
            continue;
        }else if ($i == 1) {
            $ret[$i] = 1;
            continue;
        }

        $ret[$i] = $ret[$i-1] + $ret[$i-2];
    }

    return $ret[$n];
}

echo a(10);

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

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分

function test($array) {

    if (count($array) < 2) {
        return false;
    }

    $start = 0;
    $end = count($array) - 1;

    while ($start < $end) {
        while ($array[$end] % 2 == 0 && $start < $end) {
            $end--;
        }

        while ($array[$start] % 2 == 1 && $start < $end) {
            $start++;
        }

        if ($array[$start] % 2 == 0 && $array[$end] % 2 == 1) {
            $temp = $array[$end];
            $array[$end] = $array[$start];
            $array[$start] = $temp;
        }
    }

    return $array;
}

顺时针打印矩阵

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字

这个是书上的方法

function printMatrixMain($data) {
    $start = 0;
    $columns = count($data);
    $rows = count($data[0]);

    while ($columns > $start * 2 && $rows > $start * 2) {
        printMatrix($data, $columns, $rows, $start);
        ++$start;
    }
}


function printMatrix($data, $columns, $rows, $start)
{
    $endx     = $columns - 1 - $start;
    $endy     = $rows - 1 - $start;

    for ($i = $start; $i <= $endx; $i++) {
        echo $data[$start][$i], '/';
    }

    for ($i = $start + 1; $i <= $endy; $i++) {
        echo $data[$i][$endx], '/';
    }

    for ($i = $endx - 1; $i >= $start; $i--) {
        echo $data[$endy][$i], '/';
    }

    for ($i = $endy - 1; $i > $start; $i--) {
        echo $data[$i][$start], '/';
    }
}


$s = array(
    array(1, 2, 3, 4, 5),
    array(5, 6, 7, 8, 9),
    array(9, 10, 11, 12, 13),
    array(13, 14, 15, 16, 17),
    array(1, 2, 3, 4, 5),
);

printMatrixMain($s);

这个是我自己写的方法

function printMatrix($data)
{
    $start    = 0;
    $num      = 0;
    $can_loop = true;
    $endx     = count($data[0]) - 1;
    $endy     = count($data) - 1;

    while ($can_loop) {
        if (($endx - $num - $start < 2) || ($endy - $num - $start) < 2) {
            $can_loop = false;
        }

        for ($i = $start; $i <= $endx - $num; $i++) {
            echo $data[$start][$i], '/';
        }

        for ($i = $start + 1; $i <= $endy - $num; $i++) {
            echo $data[$i][$endx - $num], '/';
        }

        for ($i = $endx - $num - 1; $i >= $start; $i--) {
            echo $data[$endy - $num][$i], '/';
        }

        for ($i = $endy - $num - 1; $i > $start; $i--) {
            echo $data[$i][$start], '/';
        }

        $start++;
        $num++;
    }
}


$s = array(
    array(1, 2, 3, 4, 5),
    array(5, 6, 7, 8, 9),
    array(9, 10, 11, 12, 13),
    array(13, 14, 15, 16, 17),
    array(1, 2, 3, 4, 5),
);

printMatrix($s);

二叉搜索树的后序遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出true,否则输出false.

function VerifySquenceOfBST($data) {
    if(empty($data)){
        return false;
    }
    
    $length = count($data);
    $root   = $data[$length - 1];

    for($i = 0; $i<$length-1; $i++) {
        if($data[$i] > $root) {
            break;
        }
    }

    $j = $i;

    for($j; $j < $length -1; $j++) {
        if ($data[$j] < $root) {
            return false;
        }
    }

    $left = true;
    $right = true;

    if($i > 0) {
        $left = VerifySquenceOfBST(array_slice($data, 0, $i));
    }

    if($j < $length - 1) {
        $right = VerifySquenceOfBST(array_slice($data, $i, $length-1-$i));
    }

    return ($left&&$right);
}

var_dump(VerifySquenceOfBST([5,7,6,9,11,10,8]));

字符串的排列

输入一个字符串,打印出所有字符串的组合,例如:abc 会打印出abc,acb bac bca cab cba

function Permutation($str) {
    if ($str == NULL)
        return false;
    if (!is_string($str))
        return false;
    echo_child($str, 0);             /*书上用指针,这里我们用下标*/
}

function echo_child($str, $index) {
    $len = strlen($str);
    if ($len == ($index + 1)) {
        echo $str . "    ";
        return false;
    } else {
        for ($i = $index; $i < $len; $i++) {
            $new_str         = $str;
            $tmp             = $new_str[$index];
            $new_str[$index] = $new_str[$i];
            $new_str[$i]     = $tmp;              /*以上是和第一个字符交换*/
            echo_child($new_str, $index + 1);  /*运用递归不断对余下的部分进行交换*/
        }
    }
}

Permutation('abc');

数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

function MoreThanHalfNum_Solution($data)
{
   if (empty($data)) {
        return false;
    }

    $ret = array();

    foreach ($data as $key => $val) {
        if (empty($ret)) {
            $ret['value'] = $val;
            $ret['count'] = 1;
        } else {
            if ($val == $ret['value']) {
                $ret['count']++;
            } else {
                if (--$ret['count'] == 0) {
                    $ret['value'] = $val;
                    $ret['count'] = 1;
                }
            }
        }
    }

    if (checkMoreThanHalf($data, $ret['value'])) {
        return $ret['value'];
    } else {
        return 0;
    }
}

function checkMoreThanHalf($data, $number) {
    $time = 0;

    foreach ($data as $key => $val) {
        if ($val == $number) {
            $time++;
        }
    }

    if ($time * 2 > count($data)) {
        return true;
    } else {
        return false;
    }
}

连续子数组的最大和

输入一个整形数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

function FindGreatestSumOfSubArray($data)
{
    if (empty($data)) {
        return false;
    }

    $ret = 0;
    $max = $data[0];

    for ($i = 0; $i < count($data); $i++) {
        $ret = $ret + $data[$i];

        if ($ret > $max) {
            $max = $ret;
        }

        if ($ret < 0) {
            $ret = 0;
        }
    }

    return $max;
}

整数中1出现的次数(从1到n整数中1出现的次数)

例如输入12,从1到12这些整数中包含1的数字有1,10,11和12,1一共出现了5次

function NumberOf1Between1AndN_Solution($str)
{
    settype($str, 'string');

    if ($str == 0 || strlen($str) == 0) {
        return 0;
    }

    $first = $str[0];

    if (strlen($str) == 1 && $first > 0) {
        return 1;
    }

    if ($first > 1) {
        $numFirstDigit = powerBase10(strlen($str) - 1);
    } else {
        $numFirstDigit = substr($str, 1) + 1;
    }

    $numOtherDigits = $first * (strlen($str)-1) * powerBase10(strlen($str)-2);
    $numRecursive = NumberOf1Between1AndN_Solution(substr($str, 1));

    return $numFirstDigit + $numOtherDigits + $numRecursive;
}

function powerBase10($number) {
    return pow(10, $number);
}

数组中只出现一次的数字

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

function FindNumsAppearOnce($array) {
    if (empty($array)) {
        return false;
    }

    $xor = 0;
    foreach ($array as $key => $val) {
        $xor ^= $val;
    }

    $indexOf1 = findFirstBit1($xor);

    $result = array(0,0);
    foreach ($array as $key => $value) {
        if (isBit1($value, $indexOf1)) {
            $result[0] ^= $value;
        } else {
            $result[1] ^= $value;
        }
    }

    return $result;
}


function findFirstBit1($num) {
    $index = 0;

    while (($num & 1) == 0) {
        $num >>= 1;
        $index++;
    }

    return $index;
}

function isBit1($num, $indexBit) {
    $num >>= $indexBit;

    return (($num & 1) === 1);
}

$ret = FindNumsAppearOnce(array(2, 4, 3, 6, 3, 2,5,5));
echo $ret[0],$ret[1];

和为S的两个数字

输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出任意一对即可。

function FindNumbersWithSum($array, $sum) {
    if (empty($array)) {
        return false;
    }

    $start = 0;
    $end   = count($array) - 1;

    while ($start < $end) {
        if ($array[$start] + $array[$end] < $sum) {
            ++$start;
        } else if ($array[$start] + $array[$end] > $sum) {
            --$end;
        } else {
            return $array[$start].'/'.$array[$end];
        }
    }

    return false;
}

圆圈中最后剩下的数字

0,1,...,n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字,求出这个圆圈里剩下的最后一个数字。

//通过总结出的公式提供的算法,公式证明过程不展开。
function LastRemaining_Solution($n, $m) {
    if ($n < 1 || $m < 1) {
        return -1;
    }

    $last = 0;

    for($i = 2; $i <= $n; $i++) {
        $last = ($last + $m) % $i;
    }

    return $last;
}



//模拟环形链表,这个效率和性能都不如前一个,但是思路简单
function LastRemaining_Solution2($n, $m) {
    if ($n < 1 || $m < 1) {
        return -1;
    }

    $data = array();
    for ($i=0; $i< $n; $i++) {
        $data[] = $i;
    }

    $p = 0;
    while (count($data) >1 ) {
        for ($i=1; $i<$m; $i++) {
            ++$p;
            $p = isset($data[$p]) ? $p : 0;
        }
        unset($data[$p]);
        $data = array_values($data);
        $p = isset($data[$p]) ? $p : 0;
    }

    return reset($data);
}
查看原文

赞 9 收藏 26 评论 0