存档

作者存档

字符串翻转算法

2018年2月8日 没有评论
void ReverseString(char *s,int from , int to){
    char temp;
    while (from <to){
        temp=*(s+from);
        *(s+from)=*(s+to);
        *(s+to)=temp;
        from++;
        to--;
    }
}
void LeftShiftOne(char* s,int n){
    char temp=s[0];
    int i=0;
    while (i<n-1){
        s[i]=s[i+1];
        i++;
    }
    s[n-1]=temp;
}
/**
 * (X^TY^T)^T=YX
 * n字符串长度,m旋转前m位
 */
void LeftRotateString(char* s,int n,int m){
    ReverseString(s,0,m-1);
    ReverseString(s,m,n-1);
    ReverseString(s,0,n-1);
}
void LeftRotateString2(char* s,int n,int m){
    while (m--){
        LeftShiftOne(s,n);
    }
}
void RightRotateString(char* s,int n,int m){
    ReverseString(s,0,n-m-1);
    ReverseString(s,n-m,n-1);
    ReverseString(s,0,n-1);
}
void ReverseWords(char* s){
    ReverseString(s,0,strlen(s)-1);
    int x=0;
    for (int j = 0; j <strlen(s) ; ++j) {
        if(s[j]==' '){
            ReverseString(s,x,j-1);
            x=j+1;
        }
    }
}

分类: 算法 标签:

字符串字母包含算法

2018年2月8日 没有评论

给定两个分别由字母组成的字符串A和字符串B,字符串B的长度比字符串A短。请问,如何最快地判断字符串B中所有字母是否都在字符串A里?

为了简单起见,我们规定输入的字符串只包含大写英文字母,请实现函数bool StringContains(string &A, string &B)



/**
 * 穷举查找O(nm)
 * @param A
 * @param B
 * @return
 */
bool StringContains(string &A, string &B) {
    typedef string::const_iterator it;
    int num=0;
    for (it i = B.begin(); i < B.end(); i++) {
        for (it j = A.begin(); j < A.end(); j++) {
            if (*i == *j) {
                num++;
                break;
            }
        }
    }
    return num==B.length();
}
int  cmp(const void* a,const void*  b){
    return ( *(char*)a - *(char*)b );
}
/**
 * 排序查找O(nlogN+mlogM+m)
 * @param A
 * @param B
 * @return
 */
bool StringContains2(string &A, string &B) {
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    typedef string::const_iterator it;
    it j=A.begin();
    for (it i = B.begin(); i < B.end(); i++) {
        for (; j < A.end(); ) {
            if (*i == *j) {
                break;
            }
            j++;
        }
        if(j==A.end()){
            return false;
        }
    }
    return true;
}
/**
 * 使用map O(n+m)
 * @param A
 * @param B
 * @return
 */
bool StringContains3(string &A, string &B) {
    map<int,char> bulk;
    typedef string::const_iterator it;
    for (it i = A.begin();  i<A.end() ; i++) {
        bulk.insert(pair<char,int>(*i,1));
    }
    for (it i = B.begin();  i<B.end() ; i++) {
        if(bulk.find(*i)==bulk.end()){
            return false;
        }
    }
    return true;
}
/**
 * 使用位计算 O(n+m)
 * @param A
 * @param B
 * @return
 */
bool StringContains4(string &A, string &B) {
    int bit_counter=0;
    typedef string::const_iterator it;
    for (it i = A.begin(); i <A.end() ; i++) {
        bit_counter|=1<<((*i)-'a');
    }
    for (it i = B.begin(); i <B.end() ; i++) {
        if((bit_counter&(1<<((*i)-'a')))==0){
            return false;
        }
    }
    return true;
}
void testStringContain(){
    string  s1="aafgrsdfsdfsdafsdafsefwefsdacsdfvdgdfhfgjuytnwabcde";
    string s2="absdffsdafsddafqwrwesdfrsdafsvxcvasdfc";
    cout<<StringContains(s1,s2)<<endl;
    s1="aafgrsdfsdfsdafsdafsefwefsdacsdfvdgdfhfgjuytnwabcde";
    s2="absdffsdafsddafqwrwesdfrsdafsvxcvasdfc";
    cout<<StringContains2(s1,s2)<<endl;
    cout<<s1<<endl;
    map<char,int> bulk;
    typedef map<char,int>::const_iterator it;
    pair<char,int> data('s',11);
    bulk.insert(data);
    data={'s',100};
    pair<it,bool> temp=bulk.insert(data);
    cout <<temp.second<<endl;
    it iii=temp.first;
    cout <<iii->first<<iii->second<<endl;
    s1="aafgrsdfsdfsdafsdafsefwefsdacsdfvdgdfhfgjuytnwabcde";
    s2="ab";
    cout<<StringContains3(s1,s2)<<endl;
    s1="aafgrsdfsdfsdafsdafsefwefsdacsdfvdgdfhfgjuytnwabcde";
    s2="abgfex";
    cout<<StringContains4(s1,s2)<<endl;
}



分类: 算法 标签:

最长回文串算法

2018年2月8日 没有评论
给定一个字符串,求它的最长回文子串的长度。
/**
 * @param s 
 * @param n 
 * @return 
 */
bool IsPalindrome(const char *s, int n){
    if(s== NULL||n<1){
        return false;
    }
    for (int i = 0; i < n/2; ++i) {
        if(s[i]!=s[n-i-1]){
            return false;
        }
    }
    return true;
}/**
 * 穷举法遍历所有长度 O(n^3)
 * @param s
 * @param n
 * @return
 */
int LongestPalindrome(const char *s, int n){
    if(s== nullptr||n<1){
        return 0;
    }
    int longest=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n-i;j++){
            if(IsPalindrome(s+j,i)){
                longest=longest<i?i:longest;
            }
        }
    }
    return longest;
}
/**
 * 找中心点向外扩散 O(n^2)
 * @param s
 * @param n
 * @return
 */
int LongestPalindrome2(const char *s, int n){
    if(s== nullptr||n<1){
        return 0;
    }
    int longest=0;//长度
    //i是中心点下标
    for (int i = 0; i <n ; ++i) {
        //j是长度
        //奇数串
        for (int j = 0;(i-j)>=0&&(i+j)<n; ++j) {
            if(s[i-j]!=s[i+j]){
                break;
            }
            int c=j*2+1;
            longest=longest<c?c:longest;
        }
        for (int j = 0;(i-j)>=0&&(i+j+1)<n; ++j) {
            if(s[i-j]!=s[i+j+1]){
                break;
            }
            int c=j*2+2;
            longest=longest<c?c:longest;
        }
    }
    return longest;

}
/**
 * Manacher算法 O(n)
 * @param s
 * @param n
 * @return
 */
int LongestPalindrome3(const char *s, int n){
    if(s== nullptr||n<1){
        return 0;
    }
    char str[n*2+4];
    int j=0;
    str[j++]='$';
    str[j++]='#';

    for (int i = 0; i < n; ++i) {
        //使回文串长度变成偶数
        str[j++]=*(s+i);
        str[j++]='#';
    }
    str[j]='\0';
    int p[j-1];//保存以下标为中心点的最长回文串长度
    memset(p,0, sizeof(p));
    int mx=0;//回文串最右边界
    int idx=0;//回文串中心点
    int longest=0;//最长子串
    for(int i=1;i<j-1;i++){
        p[i]=mx>i?min(mx-i,p[2*idx-i]):1;//2*idx-i 与i关于idx对称,如果p[2*idx-i]比mx-i长则说明p[i]>=p[2*idx-i] 短的话 p[i]=p[2*idx-i]
        while(str[i-p[i]]==str[i+p[i]]){
            p[i]++; //继续求p[i]的最长回文串
        }
        longest=p[i]>longest?p[i]:longest;
        if(p[i]+i>mx){
            mx=p[i]+i;
            idx=i;
        }
    }
    return longest-1;
} 

 

分类: 算法 标签:

squid 配置HTTPS代理

2017年8月17日 没有评论

从源代码编译:(编译的squid必须是3.3或以上的版本。2.x版好像没有加密代理功能)

yum install openssl openssl-devel  gcc-c++ bzip2 gcc perl
(如果你的系统是DEBIAN/UBUNTU,则需运行命令:apt-get install openssl libssl-dev gcc g++ bzip2 perl,否则
编译时,会遇到错误提示:configure: error: library ‘crypto’ is required for OpenSSL。参见
http://superuser.com/questions/371901/openssl-missing-during-configure-how-to-fix)

wget http://www.squid-cache.org/Versions/v3/3.5/squid-3.5.7.tar.bz2
tar jxvf squid-3.5.7.tar.bz2
cd squid-3.5.7
./configure –prefix=/usr –sysconfdir=/etc/squid –libdir=/usr/lib –with-openssl
–enable-basic-auth-helpers=”LDAP,MSNT,NCSA,PAM,SASL,SMB,YP,DB,POP3,getpwnam,squid_radius_auth,multi-domain-NTLM” –with-swapdir=/var/spool/squid –libexecdir=/usr/lib/squid
make (此步骤耗时15分钟)
make install

配置squid,(修改SQUID的配置文件squid.conf)

然后修改Squid的配置文件。把http_port变成https_port ,修改监听的端口号为443:
https_port 443 cert=/etc/squid/public.crt key=/etc/squid/private.key
其中cert和key分别是网站的HTTPS证书和私钥。在/etc/squid/目录中,运行openssl req -x509 -nodes -days 3650 -newkey rsa:2048 -keyout private.key -out public.crt即可生成public.crt和private.key 。注意:监听的端口号必须设为443.否则squid启动不了。

chrome

chrome支持https类型的代理。启动chrome的时候在末尾加上–proxy-server=https://vps-ip:443 –ignore-certificate-errors即可。注意,把这里的vps-ip换成你的服务器的ip。
全配置好之后,用chrome浏览器即可翻墙。

证书可以用商业证书,自己生成的比较麻烦。。

启用用户认证了。

具体方法如下:yum install httpd (debian/ubuntu系统下,则apt-get install apache2)这样你的系统上就会出现htpasswd命令。然后在/etc/squid/目录里,运行htpasswd -cb /etc/squid/users jones fx5rm31s上述命令将生成密码文件users.(jones和fx5rm31s分别为你指定的用户名和密码)然后,编辑/etc/squid/squid.conf文件,在http_access deny all那一段的上方,插入:

auth_param basic program /usr/lib/squid/basic_ncsa_auth /etc/squid/users
auth_param basic children 5
auth_param basic realm Squid proxy-caching web server
auth_param basic credentialsttl 2 hours
acl normal proxy_auth REQUIRED
http_access allow normal
auth_param basic casesensitive off

然后重启squid,即可启用squid的认证机制。

分类: UNIX 标签:

随便聊聊

2017年6月26日 没有评论

又好久没更新了,随便聊聊吧。

随着媳妇产期来临,开始慢慢接受当爹了这个事实,挺好的,为人父就要做出表率,控制好自己的情绪,照顾好家人。

最近搞了烘培,挺有意思的,发现比面食简单多了,只要按照固定的比例做就行了,味道都还不错,做面食影响的因素就太多了。

最近对交易有了更深入的理解,换句话说对人性更加理解了,在这个地方捡块肉是件很不容易的事,忠于自己的内心,控制好风险,分散仓位。

最近两年错失了几个机会,希望后面可以更加努力,改变命运。

突然不想喝酒了,一辈子很短,好好珍惜。

 

分类: 随笔 标签:

前端接口防刷方法探究

2017年2月21日 没有评论

暴露在前端的接口被刷是件很头疼的事,这件事情无解,根据我观察,目前主流有三种方法:
1.通过JS注入cookie数据,此cookie数据会在后端进行校检,此种方式必须采用渲染js来进行破解,提高了刷接口成本。

2.在前端对请求参数进行加密,加密方法采用代码混淆技术,这种成本比较低,效果还不错。

3.每次请求生成一个唯一字符串,把该字符串注入cookie中,此串只能用一次,当访问接口时会校检该串是否有效或是否被用过,无效串直接403。

出于成本考虑我采用1和2两种方法的结合,具体流程如下:

1.生成一个与时间戳有关系的字符串K,该字符串可采用RC4加密算法生成,保证加密串可以被还原成时间戳。

2.将K注入cookie中

3.前端拿到K,根据请求参数算出SIGN

4.前端把SIGN和请求参数传递到后端,后端首先提取出K计算是否有效、是否过期了一定时间间隔,然后计算SIGN是否有效

 

 /**
     * 获取与时间戳有关的加密串
     * @return string
     */
    public static function getEncryptionKey() {
        $timeStamp = strval(time());
        $rc4Ret = self::rc4(self::COMMON_SECRET_KEY, $timeStamp);
        return base64_encode($rc4Ret);
    }

    /**
     * 从加密串中解出时间戳
     * @param $key
     * @return string
     */
    public static function decodeEncryptionKey($key) {
        return self::rc4(self::COMMON_SECRET_KEY, base64_decode($key));
    }

    /**
     * 验证加密串是否有效,考虑时间戳的失效时间。
     * @param $key
     * @return bool
     */
    public static function checkEncryptionKey($key) {
        $nowTimeStamp = intval(time());
        if (!empty($key)) {
            $encyptionTimeStamp = intval(self::decodeEncryptionKey($key));
            return (($encyptionTimeStamp + self::MAX_VALID_TIME_INTERVAL) >= $nowTimeStamp);
        }
        return false;
    }

分类: WEB开发 标签:

git rebase

2016年12月9日 没有评论

简介

在Git中,用两种方法将两个不同的branch合并。一种是通过git merge,一种是通过git rebase。然而,大部分人都习惯于使用git merge,而忽略git rebase。本文将介绍git rebase的原理、使用方式及应用范围。

git merge 做些什么

当我们在开发一些新功能的时候,往往需要建立新的branch。

在上图中,每一个绿框均代表一个commit。除了c1,每一个commit都有一条有向边指向它在当前branch当中的上一个commit。

图中的项目,在c2之后就开了另外一个branch,名为experiment。在此之后,master下的修改被放到c4 commit中,experiment下的修改被放到c3 commit中。

如果我们使用merge合并两个分支
$ git checkout master
$ git merge experiment

得到的commit log如下图所示

我们看到,merge所做的事情实际上是:

  1. 首先找到masterexperiment中最新的commit的最近公共祖先,在这里就是c4c3的最近公共祖先c2
  2. experiment分支上在c2以后的所有commit合并成一个commit,并与master合并
  3. 如有合并冲突(两个分支修改了同一个文件),首先人工去除重复。
  4. 在master上产生合并后的新commit

git rebase做些什么

rebase所做的事情也是合并两个分支,但是它的方式略有不同。基于上例描述,rebase的工作流程是

  1. 首先找到masterexperiment中最新的commit的最近公共祖先,在这里就是c4c3的最近公共祖先c2
  2. experiment分支上在c2以后的所有commit*全部移动到*master分支的最新commit之后,在这里就是把c3移动到c4以后。

由于git的每一个commit都只存储相对上一个commit的变化(或者说是差值,delta)。我们通过移动c3到master,代表着在master上进行c3相应的修改。为了达成这一点,只需在experiment分支上rebase master
$ git checkout experiment
$ git rebase master

需要注意的是,rebase并不是直接将c3移动到master上,而是创建一个副本。我们可以通过实际操作发现这一点。在rebase前后,c3的hash code是不一样的。

rebase前的commit log是
* 1b4c6d6 (master) <- c4
| * 66c417b (experiment) <- c3
|/
* 972628d

rebase后的commit log是
* d9eeb1a - (experiment) <- c3'
* 1b4c6d6 - (master) <- c4
* 972628d

可以发现c3的hash code从66c417b变到了d9eeb1a

在这之后,我们只需要在master上进行一次前向合并(fast-forward merge)
$ git checkout master
$ git merge experiment

rebase之后的commit log呈线性,更加清晰。此时如果experiment分支不再被需要,我们可以删除它。
$ git branch -d experiment

何时使用

我们一般只在本地开发的时候rebase一个自己写出来的branch。

谨记,千万不要rebase一个已经发布到远程git服务器的分支。例如,你如果将分支experiment发布到了GitHub,那么你就不应该将它rebasemaster上。因为如果你将它rebasemaster上,将对其他人造成麻烦。

总结

git rebase帮助我们避免merge带来的复杂commit log,允许以线性commit的形式进行分支开发。

分类: 零碎 标签:

关于做面食

2016年9月28日 没有评论

和面粉打交道十几年了吧,也做了快20年的饭,想起以前五岁的时候,妈妈在地里干活,我和我姐做的炒南瓜丝,当时火候没控制好,炒糊了,其实也不是火候的问题吧,那时候吃不起油,不放油干炒确实容易糊。七八岁的时候,暑假会回老家,家里种的还有小麦,收割的时候会有零散的麦穗落在地里面,我妈便让我和我姐提着篮子去捡,捡一个下午确实能捡一篮子,也走了很久很久的路,最后得到几毛钱的奖励,可以买几根辣条或冰袋。再然后就是炒面了,当时也没有方便面可吃,就把面粉放锅里小火炒熟,不放任何东西包括油和盐,炒熟后可以放很长时间,饿了就用开水冲,放点白砂糖,特别香,估计现在难以下咽吧。说到糖,想起馒头的一种吃法,馒头除了可以夹方便面调料外还可以夹白砂糖,夹白砂糖口感确实好。上了初中,方便面就吃得起了,有一天我同桌发明了一种特殊的吃法,让我馋了好久,他用方便面蘸酱包吃,感觉还是蛮有味道的,而且还可以把粉包省出来以后夹馒头吃。有点扯远了,说说本文的正事吧,关于做面食。

做面食无外乎五种吃法,煮、蒸、烤、煎、炸,我不太喜欢把面食做的太油腻,前三种做的多,第一种做的比较出神入化,开个面馆绰绰有余。

煮。要使用煮这种做法,那面粉要做成什么呢?首先想到的是面片、宽面条、细面条、烩面、水疙瘩、小疙瘩以及由面条演化出来的捞面条、炸酱面等等,这些面食的口感大不相同,形状也肯定不一样,影响面食口感的因素主要是温度、醒面、揉面、面的形状、面的水分、面的盐分。面可以加盐也可以不加,在冬天基本可以不用加,加了面的柔性就没了而且不容易做好,因为温度低,面上筋也比较慢,如果急着吃可以把面盆放在温水锅上面,但是口感不好说了。盐这东西,我发现对于面食来说可有可无,面食的口感最关键的因素是揉面、醒面和水分。醒面有两种方法,第一种用湿布盖在面团的上面,湿布只能湿不能带过多的水,另一种就是拿个碗扣住,防止面里面的水分流失,第一种适合做水疙瘩,第二种应用就比较广泛了。醒一会要揉一次,揉要有力气,软绵绵的捏几下那可不行。揉了接着醒,醒一会接着揉,看你的时间和耐心了。不管什么面,揉的越多越好吃。水分,好多人都掌握不了,可以这样搞,把面粉放在盆里面,水龙头流下来水滴,拿筷子不停的搅拌,成絮状即可。

手烫伤 待续

 

 

 

 

分类: 随笔 标签:

研三了

2016年8月31日 2 条评论

进入研三每天像打了鸡血一样,忙不完的事。每个月都要外出上万公里,不是在写代码、写文档就是在路上,感觉一件件事压在心头,让我每天都需要计划一周后的事。八月初去了趟南昌,将近40℃的天气,找老道、老王喝二锅头,睡了一天一夜才醒。第二天回北京,感觉整个人都不行了。八月底去了趟徐州,去的前一天喝酒喝到三点半,睡了五个小时就起来了。去徐州那晚上也是疯狂喝到两点,五点多起床。感觉就要猝死了,只要有睡觉的机会就想睡觉。和兄弟在一起的时间总是太短暂,总是不想就拿睡觉去浪费了,当喝多了,想说啥说啥,感谢这些朋友,感谢这些酒友。

该写论文了,花了一周,累死累活写了三万字,勉强交了初稿,然后就要准备笔试、面试,还有公司的事、项目的事、远程办公的事,期间又约了几个天使投资,被洗脑了一番,生意的事真是看的不太懂。如果一个期间只有一个目标,一个压力就好了,当你想着校招、论文、工作,还有北京、合肥两地的距离时,你总要盘算着怎样弄好些。每个人总要处理各种压力,权衡时间的分配与管理,当承受该承受的,做该做的,而不是马马虎虎,总有很好的机会给你。

分类: 随笔 标签:

谈谈抓取与反抓取

2016年8月24日 没有评论

抓取是采集竞品或其它源网站数据,反抓取就是防止别人的抓取行为。目前来说,没有一家公司在反抓取方面做的比较好。举个例子,搜狗运维部门用机器学习搞反抓取策略,在业界也挺得意的,被我花了一周攻克,只用了四十个IP,一天请求上百万,两个多月了,照样好好的用着。

业界反抓取无非以下几种策略:

  1. 按照请求频率封禁IP(现在只有比较low的公司会用这种,这种方法的负面伤害更大)
  2. 按照 IP和请求头部(agent 等信息)封禁
  3. 通过执行Javascript程序注入动态cookie
  4. 通过机器学习策略分析用户行为
  5. 探测到用户有抓取行为,丢一些假数据给用户,比如某地图商

主流是第三种和第四种,第三种的门槛主要是是需要渲染JS才能得到正确的cookie,而普通抓取程序不具备这个功能,并且渲染JS速度太慢,在大规模抓取中不适用。但是第三种我有一套解决方案,是cookie分发机制,出于一些考虑,这套技术不做分享。(在搜狗公共号抓取中,使用cookie分发机制,四十IP可以做到10个/s 请求速度而不遭遇封禁)

第四种那就要好好伪装自己的请求了,比如请求的refer、user-agent、请求的文件类型等,需要自己去做随机请求,难度不大。

抓取解析,那就太简单了,分析DOM结构、使用正则等等,看你具体使用场景吧。

 

分类: WEB开发 标签: