字符串翻转算法

#ifndef XINWEI_ROTATESTRING_H_
#define XINWEI_ROTATESTRING_H_
#include <iostream>

using namespace std;
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;
        }
    }
}

#endif

字符串字母包含算法


给定两个分别由字母组成的字符串A和字符串B,字符串B的长度比字符串A短。请问,如何最快地判断字符串B中所有字母是否都在字符串A里?为了简单起见,我们规定输入的字符串只包含大写英文字母,请实现函数
bool StringContains(string &A, string &B)


// Created by Lv,Xinwei on 2018/2/5.
/**
 * 穷举查找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="aafgrsdf fsefvdgdfhfg";
    string s2="absdff afsvxcvasdfc";
    cout<<StringContains(s1,s2)<<endl;
    s1="aafgrsdfsdfscde";
    s2="absdffsdafsddafqwdfc";
    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="aafsdfsdawefscde";
    s2="ab";
    cout<<StringContains3(s1,s2)<<endl;
    s1="aafgrsdefwfgjuytnwabcde";
    s2="abgfex";
    cout<<StringContains4(s1,s2)<<endl;
}
#endif //THEARTOFPROGRAMING_STRINGCONTAIN_H

最长回文串算法

给定一个字符串,求它的最长回文子串的长度。

/**
 * @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代理

从源代码编译:(编译的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支持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的认证机制。

随便聊聊

又好久没更新了,随便聊聊吧。
随着媳妇产期来临,开始慢慢接受当爹了这个事实,挺好的,为人父就要做出表率,控制好自己的情绪,照顾好家人。
最近搞了烘培,挺有意思的,发现比面食简单多了,只要按照固定的比例做就行了,味道都还不错,做面食影响的因素就太多了。
最近对交易有了更深入的理解,换句话说对人性更加理解了,在这个地方捡块肉是件很不容易的事,忠于自己的内心,控制好风险,分散仓位。
最近两年错失了几个机会,希望后面可以更加努力,改变命运。
突然不想喝酒了,一辈子很短,好好珍惜。