[算法]leetcode-02:计算字符串中最大无重复子字符串长度

leetcode中有这样一道算法题:
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.
大意是求字符串中的最大无重复字符串,因为leetcode并不支持php,所有这里用C++给出算法,代码如下:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> map;
		int len = s.length();
		int start = 0;
		int max   = 0;
		int cur   = 0;
		for(int i=0; i<len; i++) {
		
			char ch = s[i];
			if(map.find(ch) != map.end()) {

				start = start > (map[ch] + 1) ? start : (map[ch] + 1);
			}
			cur = i - start + 1;
			map[ch] = i;
			max = cur > max ? cur : max;

		}
        //cout<<max<<endl;
		return max;
    }
};

背景:
这里用到了C++中的 unordered_map,其中的map.find()函数是查找这个map中是否保存了这个值。结果可以用auto类型保存。
例如:auto res = map.find(‘a’);而res->first 是其中的key, res->second 是value.
如果在php中,随意的一个array类型都可以实现如上效果,通过isset($str[‘a’])也可以判断是否保存了此变量。
算法:
代码比较短,通过一次遍历O(n),查找字符串中这个值是否在map中,如果没在,存入这个map中,计算长度。如果在map中,start位置变为该map值和start的较大者,防止(“abba”)这种情况。然后计算长度。
总结:
改算法题并不是很难,主要考察是否会应用map这种数据结构类型。当然在php代码中,一个array可以代替同样的效果。

CSRF攻击与防御

一.CSRF是什么?

  CSRF(Cross-site request forgery),中文名称:跨站请求伪造,也被称为:one click attack/session riding,缩写为:CSRF/XSRF。

二.CSRF可以做什么?

  你这可以这么理解CSRF攻击:攻击者盗用了你的身份,以你的名义发送恶意请求。CSRF能够做的事情包括:以你名义发送邮件,发消息,盗取你的账号,甚至于购买商品,虚拟货币转账……造成的问题包括:个人隐私泄露以及财产安全。

三.CSRF漏洞现状

  CSRF这种攻击方式在2000年已经被国外的安全人员提出,但在国内,直到06年才开始被关注,08年,国内外的多个大型社区和交互网站分别爆出CSRF漏洞,如:NYTimes.com(纽约时报)、Metafilter(一个大型的BLOG网站),YouTube和百度HI……而现在,互联网上的许多站点仍对此毫无防备,以至于安全业界称CSRF为“沉睡的巨人”。

四.CSRF的原理

  下图简单阐述了CSRF攻击的思想:

从上图可以看出,要完成一次CSRF攻击,受害者必须依次完成两个步骤:

  1.登录受信任网站A,并在本地生成Cookie。

  2.在不登出A的情况下,访问危险网站B。

  看到这里,你也许会说:“如果我不满足以上两个条件中的一个,我就不会受到CSRF的攻击”。是的,确实如此,但你不能保证以下情况不会发生:

  1.你不能保证你登录了一个网站后,不再打开一个tab页面并访问另外的网站。

  2.你不能保证你关闭浏览器了后,你本地的Cookie立刻过期,你上次的会话已经结束。(事实上,关闭浏览器不能结束一个会话,但大多数人都会错误的认为关闭浏览器就等于退出登录/结束会话了……)

  3.上图中所谓的攻击网站,可能是一个存在其他漏洞的可信任的经常被人访问的网站。

  理解上面的3种攻击模式,其实可以看出,CSRF攻击是源于WEB的隐式身份验证机制!WEB的身份验证机制虽然可以保证一个请求是来自于某个用户的浏览器,但却无法保证该请求是用户批准发送的!

五.CSRF的防御

  我总结了一下看到的资料,CSRF的防御可以从服务端和客户端两方面着手,防御效果是从服务端着手效果比较好,现在一般的CSRF防御也都在服务端进行。

  1.服务端进行CSRF防御

  服务端的CSRF方式方法很多样,但总的思想都是一致的,就是在客户端页面增加伪随机数。

  (1).Cookie Hashing(所有表单都包含同一个伪随机值):

  这可能是最简单的解决方案了,因为攻击者不能获得第三方的Cookie(理论上),所以表单中的数据也就构造失败了:>

  
  在表单里增加Hash值,以认证这确实是用户发送的请求。

  <?php
    $hash = md5($_COOKIE['cookie']);
  ?>
  <form method=”POST” action=”transfer.php”>
    <input type=”text” name=”toBankId”>
    <input type=”text” name=”money”>
    <input type=”hidden” name=”hash” value=”<?=$hash;?>”>
    <input type=”submit” name=”submit” value=”Submit”>
  </form>

  然后在服务器端进行Hash值验证

      <?php
        if(isset($_POST['check'])) {
             $hash = md5($_COOKIE['cookie']);
             if($_POST['check'] == $hash) {
                  doJob();
             } else {
        //...
             }
        } else {
      //...
        }
      ?>

  这个方法个人觉得已经可以杜绝99%的CSRF攻击了,那还有1%呢….由于用户的Cookie很容易由于网站的XSS漏洞而被盗取,这就另外的1%。一般的攻击者看到有需要算Hash值,基本都会放弃了,某些除外,所以如果需要100%的杜绝,这个不是最好的方法。
  (2).验证码

  这个方案的思路是:每次的用户提交都需要用户在表单中填写一个图片上的随机字符串,厄….这个方案可以完全解决CSRF,但个人觉得在易用性方面似乎不是太好,还有听闻是验证码图片的使用涉及了一个被称为MHTML的Bug,可能在某些版本的微软IE中受影响。

  (3).One-Time Tokens(不同的表单包含一个不同的伪随机值)

  在实现One-Time Tokens时,需要注意一点:就是“并行会话的兼容”。如果用户在一个站点上同时打开了两个不同的表单,CSRF保护措施不应该影响到他对任何表单的提交。考虑一下如果每次表单被装入时站点生成一个伪随机值来覆盖以前的伪随机值将会发生什么情况:用户只能成功地提交他最后打开的表单,因为所有其他的表单都含有非法的伪随机值。必须小心操作以确保CSRF保护措施不会影响选项卡式的浏览或者利用多个浏览器窗口浏览一个站点。

  以下我的实现:

  1).先是令牌生成函数(gen_token()):

     <?php
     function gen_token() {
     //这里我是贪方便,实际上单使用Rand()得出的随机数作为令牌,也是不安全的。
    //这个可以参考我写的Findbugs笔记中的《Random object created and used only once》
          $token = md5(uniqid(rand(), true));
          return $token;
     }

  2).然后是Session令牌生成函数(gen_stoken()):

     <?php
       function gen_stoken() {
      $pToken = "";
      if($_SESSION[STOKEN_NAME]  == $pToken){
        //没有值,赋新值
        $_SESSION[STOKEN_NAME] = gen_token();
      }    
      else{
        //继续使用旧的值
      }
       }
     ?>

  3).WEB表单生成隐藏输入域的函数:  

     <?php
       function gen_input() {
            gen_stoken();
            echo “<input type=\”hidden\” name=\”" . FTOKEN_NAME . “\”
                 value=\”" . $_SESSION[STOKEN_NAME] . “\”> “;
       }
     ?>

  4).WEB表单结构:

     <?php
          session_start();
          include(”functions.php”);
     ?>
     <form method=”POST” action=”transfer.php”>
          <input type=”text” name=”toBankId”>
          <input type=”text” name=”money”>
          <? gen_input(); ?>
          <input type=”submit” name=”submit” value=”Submit”>
     </FORM>

  5).服务端核对令牌:

  这个很简单,这里就不再啰嗦了。
6)验证http refere
根据HTTP协议,在HTTP头中有一个字段叫Referer,它记录了该HTTP请求的来源地址。在通常情况下,访问一个安全受限页面的请求必须来自于同一个网站。比如某银行的转账是通过用户访问http://bank.test/test?page=10&userID=101&money=10000页面完成,用户必须先登录bank. test,然后通过点击页面上的按钮来触发转账事件。当用户提交请求时,该转账请求的Referer值就会是转账按钮所在页面的URL(本例中,通常是以bank. test域名开头的地址)。而如果攻击者要对银行网站实施CSRF攻击,他只能在自己的网站构造请求,当用户通过攻击者的网站发送请求到银行时,该请求的Referer是指向攻击者的网站。因此,要防御CSRF攻击,银行网站只需要对于每一个转账请求验证其Referer值,如果是以bank. test开头的域名,则说明该请求是来自银行网站自己的请求,是合法的。如果Referer是其他网站的话,就有可能是CSRF攻击,则拒绝该请求。

phpunit的安装与使用

phpunit是php的单元测试框架,安装起来十分方便。
一 安装phpunit
下载phpunit然后移动到bin目录下即可
wget https://phar.phpunit.de/phpunit.phar
chmod +x phpunit.phar
mv phpunit.phar /usr/local/bin/phpunit
之后就可以通过phpunit执行测试脚本了。
二 使用phpunit
一个简单的例子,比较结果是否一致

<?php
 
class ArrayTest extends PHPUnit_Framework_TestCase
{
    public function testNewArrayIsEmpty()
    {
        // 创建数组fixture。
        $fixture = array();
 
        // 断言数组fixture的尺寸是0。
        $this->assertEquals(0, sizeof($fixture));
    }
}
?>

同时可以用dataProvider 提供参数,其中provider函数必须是静态工有函数

class FeedTest extends UnitTestBase {

    /**
     *@dataProvider provider
     */
    public function testArray($a, $b) {

        $this->assertEquals($a, $b);


    }
    
    public static function provider() {
    
        return array(
                array(0, 0),
                array(1, 1),
                array(1, 0),
                array(1, 1),
                array(2, 2),
    
        );
    }   
}

git多分支自动补全

1,下载安装一个git的脚本

git clone https://github.com/markgandolfo/git-bash-completion.git 
cp git-bash-completion/git-completion.bash ~/.git-completion.bash 
source ~/.git-completion.bash

2,修改~/.bashrc
增加以下内容
source ~/.git-completion.bash
3,最后
source ~/.bashrc
之后通过tab键就可以实现分支的自动补全了

[fisp]windows平台安装fisp

fis-plus 是扩展自FIS的前端集成解决方案。其提供 后端框架、前端框架、自动化工具、辅助开发工具等开发套件,被百度广泛应用

Windows安装fisp步骤
1, 安装nodejs
2, 安装 fis-plus: npm install –f fis-plus
3, 安装lights: npm install –g lights
4, 安装java (配置环境变量)
5, 安装php-cgi(配置环境变量)
这个步骤可以下载任何xampp或者wamp安装包
6, 操作 fisp server init
7, 下载demo 到www目录:https://github.com/fex-team/fis-plus-pc-demo
默认的www目录在C:\Users\will\AppData\Local\.fis-plus-tmp\www
8, 进入到www目录发布 fisp release –r comman ; fisp release –r home
9, fisp server start

完成!
fisp环境 还是很好安装的!

数据库的简单介绍

文章原地址:http://www.ruanyifeng.com/blog/2014/07/database_implementation.html
所有应用软件之中,数据库可能是最复杂的。
MySQL的手册有3000多页,PostgreSQL的手册有2000多页,Oracle的手册更是比它们相加还要厚。

但是,自己写一个最简单的数据库,做起来并不难。Reddit上面有一个帖子,只用了几百个字,就把原理讲清楚了。下面是我根据这个帖子整理的内容。
一、数据以文本形式保存
第一步,就是将所要保存的数据,写入文本文件。这个文本文件就是你的数据库。
为了方便读取,数据必须分成记录,每一条记录的长度规定为等长。比如,假定每条记录的长度是800字节,那么第5条记录的开始位置就在3200字节。
大多数时候,我们不知道某一条记录在第几个位置,只知道主键(primary key)的值。这时为了读取数据,可以一条条比对记录。但是这样做效率太低,实际应用中,数据库往往采用B树(B-tree)格式储存数据。
二、什么是B树?
要理解B树,必须从二叉查找树(Binary search tree)讲起。

二叉查找树是一种查找效率非常高的数据结构,它有三个特点。
(1)每个节点最多只有两个子树。
(2)左子树都为小于父节点的值,右子树都为大于父节点的值。
(3)在n个节点中找到目标值,一般只需要log(n)次比较。
二叉查找树的结构不适合数据库,因为它的查找效率与层数相关。越处在下层的数据,就需要越多次比较。极端情况下,n个数据需要n次比较才能找到目标值。对于数据库来说,每进入一层,就要从硬盘读取一次数据,这非常致命,因为硬盘的读取时间远远大于数据处理时间,数据库读取硬盘的次数越少越好。
B树是对二叉查找树的改进。它的设计思想是,将相关数据尽量集中在一起,以便一次读取多个数据,减少硬盘操作次数。

这种数据结构,非常有利于减少读取硬盘的次数。假定一个节点可以容纳100个值,那么3层的B树可以容纳100万个数据,如果换成二叉查找树,则需要20层!假定操作系统一次读取一个节点,并且根节点保留在内存中,那么B树在100万个数据中查找目标值,只需要读取两次硬盘。
三、索引
数据库以B树格式储存,只解决了按照”主键”查找数据的问题。如果想查找其他字段,就需要建立索引(index)。
所谓索引,就是以某个字段为关键字的B树文件。假定有一张”雇员表”,包含了员工号(主键)和姓名两个字段。可以对姓名建立索引文件,该文件以B树格式对姓名进行储存,每个姓名后面是其在数据库中的位置(即第几条记录)。查找姓名的时候,先从索引中找到对应第几条记录,然后再从表格中读取。
这种索引查找方法,叫做”索引顺序存取方法”(Indexed Sequential Access Method),缩写为ISAM。它已经有多种实现(比如C-ISAM库和D-ISAM库),只要使用这些代码库,就能自己写一个最简单的数据库。
四、高级功能
部署了最基本的数据存取(包括索引)以后,还可以实现一些高级功能。
(1)SQL语言是数据库通用操作语言,所以需要一个SQL解析器,将SQL命令解析为对应的ISAM操作。
(2)数据库连接(join)是指数据库的两张表通过”外键”,建立连接关系。你需要对这种操作进行优化。
(3)数据库事务(transaction)是指批量进行一系列数据库操作,只要有一步不成功,整个操作都不成功。所以需要有一个”操作日志”,以便失败时对操作进行回滚。
(4)备份机制:保存数据库的副本。
(5)远程操作:使得用户可以在不同的机器上,通过TCP/IP协议操作数据库。

Yii通过preload组件,使得https跳转到http

之前文章有涉及到http跳转到https的nginx跳转,这里是它的相反操作。
有时候网站并没有对https访问做到很好的支持,所以要让某些https的链接跳转到http.
对于Yii框架,可以利用preload这个组件,每次进入网站前先判断是否https安全链接,如果是安全链接则直接301跳转到相应的http页面。
一 配置config

'components' => array(
        'httpsRedirect' => array(
            'class' => 'HttpsRedirect',
        ),
),
'preload' => array(
        'httpsRedirect',
    )

二 添加HttpsRedirect类

<?php
/*
 * PC站https redirect
 * 请求到PC站的https 暂时301跳转到http
 */
class HttpsRedirect extends CComponent {
    
    public function init() {
        $request = Yii::app()->getRequest();
        if ($request->getIsSecureConnection() == false) {
        	return;
        }
        $host = $_SERVER['HTTP_HOST'];
        $uri  = $request->requestUri;
        switch($host) {
        	case 'your pass host':  $flag = true; break;
                case 'your pass host':  $flag = true; break;
                case 'your pass host':  $flag = true; break;
                case 'your pass host':  $flag = true; break;
        	default:                $flag = false;          
        }
        if($flag) {
            Header("HTTP/1.1 301 Moved Permanently");
            Header("Location: http://{$host}{$uri}");
        } 
    } 
}

这样就在php代码层面做到简单的https跳转到http啦。

nginx强制使用https访问的三种方法(http跳转到https)

原文:http://blog.csdn.net/wzy_1988/article/details/8549290

需求简介

基于nginx搭建了一个https访问的虚拟主机,监听的域名是test.com,但是很多用户不清楚https和http的区别,会很容易敲成http://test.com,这时会报出404错误,所以我需要做基于test.com域名的http向https的强制跳转

我总结了三种方式,跟大家共享一下

nginx的rewrite方法

思路

这应该是大家最容易想到的方法,将所有的http请求通过rewrite重写到https上即可

配置

  1. server {
  2.     listen  192.168.1.111:80;
  3.     server_name test.com;
  4.     rewrite ^(.*)$  https://$host$1 permanent;
  5. }

搭建此虚拟主机完成后,就可以将http://test.com的请求全部重写到https://test.com上了

nginx的497状态码

 

error code 497

  1. 497 – normal request was sent to HTTPS

解释:当此虚拟站点只允许https访问时,当用http访问时nginx会报出497错误码

思路

利用error_page命令将497状态码的链接重定向到https://test.com这个域名上

配置

  1. server {
  2.     listen       192.168.1.11:443;  #ssl端口
  3.     listen       192.168.1.11:80;   #用户习惯用http访问,加上80,后面通过497状态码让它自动跳到443端口
  4.     server_name  test.com;
  5.     #为一个server{……}开启ssl支持
  6.     ssl                  on;
  7.     #指定PEM格式的证书文件
  8.     ssl_certificate      /etc/nginx/test.pem;
  9.     #指定PEM格式的私钥文件
  10.     ssl_certificate_key  /etc/nginx/test.key;
  11.     #让http请求重定向到https请求
  12.     error_page 497  https://$host$uri?$args;
  13. }

index.html刷新网页

 

思路

上述两种方法均会耗费服务器的资源,我们用curl访问baidu.com试一下,看百度的公司是如何实现baidu.com向www.baidu.com的跳转
可以看到百度很巧妙的利用meta的刷新作用,将baidu.com跳转到www.baidu.com.因此我们可以基于http://test.com的虚拟主机路径下也写一个index.html,内容就是http向https的跳转

index.html

  1. <html>
  2. <meta http-equiv=”refresh” content=”0;url=https://test.com/”>
  3. </html>

nginx虚拟主机配置

  1. server {
  2.     listen 192.168.1.11:80;
  3.     server_name test.com;
  4.     location / {
  5.                 #index.html放在虚拟主机监听的根目录下
  6.         root /srv/www/http.test.com/;
  7.     }
  8.         #将404的页面重定向到https的首页
  9.     error_page  404 https://test.com/;
  10. }

后记

上述三种方法均可以实现基于nginx强制将http请求跳转到https请求,大家可以评价一下优劣或者根据实际需求进行选择。

【转】微信公众平台配置

http://www.cnblogs.com/mchina/archive/2013/06/05/3108618.html

微信公众平台开发(二) 微信公众平台示例代码分析http://www.cnblogs.com/mchina/archive/2013/06/07/3120592.html

一、简介

微信公众平台是腾讯公司在微信的基础上新增的功能模块,通过这一平台,个人和企业都可以打造一个微信的公众号,并实现和特定群体的文字、图片、语音的全方位沟通、互动。

二、通讯机制

三、注册微信平台公众帐号

注册地址:https://mp.weixin.qq.com

四、服务器端配置

4.1 示例代码设置

微信公众平台提供了一个php示例代码:

http://mp.weixin.qq.com/mpres/htmledition/res/wx_sample.zip

下载下来,解压缩,打开编辑。

将token值设置为你所需要的值,token可由开发者任意填写,用作生成签名。

编辑完保存并关闭文件,将文件wx_sample.php 更改成自定义的名字,这里改为wxapi.php,再次打包成wxapi.zip。

4.2 服务器平台设置

如果有自己的服务器,而且支持php,可以将接口文件上传至服务器,如果没有自己的服务器,则可以选择部分免费的云平台进行开发,如百度应用引擎BAE(http://developer.baidu.com/bae),新浪云平台SAE(http://sae.sina.com.cn/)。

4.2.1 百度BAE设置

a. 注册BAE帐户并登录

https://passport.baidu.com/v2/?reg&regType=1&tpl=mn&u=http%3A%2F%2Fwww.baidu.com%2F

b. 加入开发者中心

c. 创建应用

接入方式选择 “手机web应用”。

d. 托管设置

选择云环境(BAE)-> 托管设置。

环境类型 选择 “PHP”。

e. 创建新版本,上传接口文件

f. 上线并获取链接

获得的URL为:http://zhuojin.duapp.com/

注:zhuojinsz 之前已经被我注册过了,所以不能再次注册。这里应该获得的二级域名应该和上面的截图中写的一样。

BAE 设置完毕。

4.2.2 新浪SAE设置

a. 注册SAE帐户并登录

http://sae.sina.com.cn/

b. 创建新应用

我的首页 -> 创建新应用

c. 配置应用

d. 上传代码

应用管理 -> 代码管理 -> 上传代码包

e. 获取URL地址

获得的URL 地址为:http://1.zhuojin.sinaapp.com/

SAE 配置完毕。

五、配置接口

5.1 登录微信公众平台 -> 高能功能 -> 开发模式

5.2 成为开发者

5.3 接口配置信息

URL填写上面得到的BAE URL:http://zhuojin.duapp.com/,再加上上传的php文件名。即 http://zhuojin.duapp.com/wxapi.php

Token 填写自定义的token 值,这里为zhuojinsz。

对于SAE,URL填写 http://1.zhuojin.sinaapp.com/wxapi.php

5.4 提交

点击 “提交”,若一切设置正确,则会提示 “提交成功”。

5.5 查看接口配置信息

BAE 接口信息

SAE 接口信息

5.6 开启开发模式

至此,配置完毕。

六、关注

请关注 卓锦苏州 微信公众帐号,卓锦苏州 基于SAE 平台开发,针对于主流的微信功能进行开发测试。

您可以关注 卓锦苏州 公众帐号进行功能测试,以及获取新的应用开发。

1. 登录微信客户端,通讯录 -> 添加朋友 -> 查找公众号 -> zhuojinsz,查找并关注。

2. 扫描二维码:

卓锦苏州 小黄鸡测试。

[算法]求最大连续子数组和的PHP程序

之前遇到过这样一道题目:一个任意长度的整数数组{1,-3,4,5,6,7,-6,10,-15},求最大的连续子数组和。这里就是4,5,6,7,-6,10的和。这道题运用动态规划的思想,找以数组下标i位置的最大和Max[i]。
Max[i] = (Max[i-1] > 0) ? (Max[i-1] + Max[i] ) : Max[i];
之后在所有Max[i]中求一个最大值即可,时间复杂度为O(n),以下程序用php代码写出:

&lt;?php  
function maxArr($arr) {  
  
    $max    = $arr[0]; //最大值  
    $endMax = $arr[0]; //以KEY结尾的最大值  
  
    foreach($arr as $key =&gt; $value) {  
        if($key == 0) {  
            //以0结尾作为开始,这里直接跳过  
            continue;  
        }  
  
        $endMax = ($endMax &gt; 0) ?  ($endMax + $value) : $value;  //以$key结尾的数组最大值  
        $max    = ($endMax &gt; $max) ? $endMax : $max;             //总的最大值  
    }  
    return $max;  
}  
//测试用例  
$test = array(-1,4,5,6,-10,12,-2,1);  
echo maxArr($test);