题目:
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.

思路:
使用map来保存每个字符出现的位置,key:字符,value:最后一次出现的位置,遍历一次后,保存该字符到map中,并同时保存一个max结果和当前计数的索引index,index取值是取最后一次重复任何一个字符出现的位置,max(取当前索引-最后一次出现位置)的最大值。算法复杂度:O(n)!!

代码:

class Solution {
public:

int lengthOfLongestSubstring(string s)
{
    int max_result = 0;
    map<char, int> vaule_map;
    int index = -1;
    for (unsigned int i = 0; i < s.size(); i++)
    {
        map<char, int>::iterator iItr = vaule_map.find(s[i]);
        if (iItr != vaule_map.end())
        {
            index = iItr->second > index ? iItr->second : index;
        }
         
        max_result = (i - index) > max_result ? (i - index) : max_result;
         
        vaule_map[s[i]] = i;
    }
 
    return max_result;
}

};
总结:
1、当你感觉一个算法很够复杂的时候,说明这个算法还不够顺通,真正优秀的算法是很简洁且高效的。
2、尽量减少中间变量,保证代码可读性。

题目:

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

思路:
同时循环两个链表,如果都不为空,则相加并加上次的进位值(0/1),然后再判断是否进位;如果一个链表为空,则相加上次进位值(0/1);如果都为空,则退出;最后判断最后一次是否有进位。算法复杂度:O(n),代码如下

/**

  • Definition for singly-linked list.
  • struct ListNode {
  • int val;
  • ListNode *next;
  • ListNode(int x) : val(x), next(NULL) {}
  • };
    */

class Solution {
public:
void NewNode(ListNode pCurPos, ListNode pResultList, int num)
{

if (*pCurPos == NULL)
{
    *pResultList = new ListNode(num);
    *pCurPos = *pResultList;
}
else
{
    ListNode *pNewNode = new ListNode(num);
    (*pCurPos)->next = pNewNode;
    *pCurPos = pNewNode;
}

}

ListNode addTwoNumbers(ListNode l1, ListNode* l2) {

ListNode *pResultList = NULL;
ListNode *pCurPos = NULL;

int need_carry = 0;
ListNode *pCur1 = l1;
ListNode *pCur2 = l2;

while (pCur1 != NULL || pCur2 != NULL)
{
    if (pCur1 != NULL && pCur2 != NULL)
    {
        int sum = pCur1->val + pCur2->val + need_carry;
        need_carry = sum / 10;
        sum = sum {b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c} 10;

        NewNode(&pCurPos, &pResultList, sum);
    }
    else if (pCur1 == NULL && pCur2 != NULL)
    {
        int sum = pCur2->val + need_carry;
        need_carry = sum / 10;
        sum = sum {b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c} 10;
         
        NewNode(&pCurPos, &pResultList, sum);
    }
    else if (pCur1 != NULL && pCur2 == NULL)
    {
        int sum = pCur1->val + need_carry;

        need_carry = sum / 10;
        sum = sum{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}10;

        NewNode(&pCurPos, &pResultList, sum);
    }

    if (pCur1 != NULL)
    {
        pCur1 = pCur1->next;
    }

    if (pCur2 != NULL)
    {
        pCur2 = pCur2->next;
    }
}

if (need_carry != 0)
{
    NewNode(&pCurPos, &pResultList, need_carry);
}

return pResultList;

}

};
总结:
1、该题本身不是特别难,思路很简单,考察的仅是链表的应用。
2、算法效率跟语言有很大关系。

比如官方的图片如下,同样的算法,不同的语言,效率真的会差很多。c > c++ > python > c# > javascript > java

题目:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

思路一:
按照第1~n每个数据遍历循环,当前指向为i的时候,则从i开始,再次向下循环对应的值与i相加是否为target,使用两次for循环。

class Solution {
public:

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> nResult;
    for( unsigned int i = 0; i < nums.size(); i++ )
    {
        int nFirstKey = nums[i];
        if( (nFirstKey >= target) || (nFirstKey == 0))
            continue;
         
        bool bFind = false;
        for( unsigned int k = (i + 1); k < nums.size(); k++ )
        {
            int nSecondKey = nums[k];
            if( (nFirstKey + nSecondKey) > target )
                continue;
             
            if( (nFirstKey + nSecondKey) == target )
            {
                bFind = true;
                int nIndex1;
                int nIndex2;
                if( nFirstKey > nSecondKey )
                {
                    nIndex1 = k + 1;
                    nIndex2 = i + 1;
                }
                else
                {
                    nIndex1 = i + 1;
                    nIndex2 = k + 1;
                }
                break;
            }
        }
         
        if( bFind )
            break;
    }
     
    return nResult;
}

};
这种方式的思路比较简单,但是复杂度较高为O(n^2)。在提交时候出现 Time Limit Exceeded 错误。

思路二:
一次循环 0~n,新建一个map表,map 的key值存数字,value存索引,每次循环时,先算出需求值=target-当前值,然后去map里查找是否存在,如果存在,一切ok,如果不存在,导入,再循环下一个值,总计一个for循环。算法复杂度:O(n)!!!

class Solution {
public:

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> nResult;
    map<int, int> nMap;//key: the num, value: the index
    for( unsigned int i = 0; i < nums.size(); i++ )
    {
        int nWantNum = target - nums[i];
        map<int, int>::iterator iItr;
        iItr = nMap.find(nWantNum);
        if( iItr != nMap.end() )
        {
            int nIndex1 = 0;
            int nIndex2 = 0;
            if (i > iItr->second)
            {
                nIndex1 = iItr->second + 1;
                nIndex2 = i + 1;
            }
            else
            {
                nIndex1 = i + 1;
                nIndex2 = iItr->second + 1;
            }
             
            nResult.push_back(nIndex1);
            nResult.push_back(nIndex2);
            break;
        }
         
        iItr = nMap.find(nums[i]);
        if( iItr == nMap.end() )
        {
            nMap[nums[i]] = i;
        }
    }
     
    return nResult;
}

};
总结:
1、算法复杂度最忌讳的是for循环嵌套。
2、换种思路,考虑map、hash这种现有的数据结果去存储结果。

ssl 编程服务器和客户端完整demo c++版,编译环境:cent os 64, g++

安装openssl:

yum search opensll #查找可用的openssl开发包
yum install opensll-devel.x86_64 #从查找结果中选择安装 devel 版本
生成ca文件和key文件,供服务器使用

openssl genrsa -out privkey.pem 2048
openssl req -new -x509 -key privkey.pem -out cacert.pem -days 1095
服务器代码:

include <stdio.h>

include <stdlib.h>

include <errno.h>

include <string.h>

include <sys/types.h>

include <netinet/in.h>

include <sys/socket.h>

include <sys/wait.h>

include <unistd.h>

include <arpa/inet.h>

include <openssl/ssl.h>

include <openssl/err.h>

define MAXBUF 1024

const int s_myport = 8081;

int main(int argc, char **argv)
{

int sockfd, new_fd;
socklen_t len;
struct sockaddr_in my_addr, their_addr;
char buf[MAXBUF + 1];
SSL_CTX *ctx;

SSL_library_init();
OpenSSL_add_all_algorithms();

SSL_load_error_strings();

ctx = SSL_CTX_new(SSLv23_server_method());

if (ctx == NULL) 
{
    ERR_print_errors_fp(stdout);
    printf("---1\n");
    exit(1);
}

if (SSL_CTX_use_certificate_file(ctx, argv[1], SSL_FILETYPE_PEM) <= 0)
{
    ERR_print_errors_fp(stdout);
     printf("---2:{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s\n", argv[1]);
    exit(1);
}

if (SSL_CTX_use_PrivateKey_file(ctx, argv[2], SSL_FILETYPE_PEM) <= 0)
{
    ERR_print_errors_fp(stdout);
     printf("---3:{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s\n", argv[2]);
    exit(1);
}

if (!SSL_CTX_check_private_key(ctx)) 
{
     printf("---4\n");
    ERR_print_errors_fp(stdout);
    exit(1);
}


if ((sockfd = socket(PF_INET, SOCK_STREAM, 0)) == -1) 
{
     printf("---5\n");
    perror("socket");
    exit(1);
} 
else
{
    printf("socket created\n");
}

bzero(&my_addr, sizeof(my_addr));
my_addr.sin_family = PF_INET;
my_addr.sin_port = htons(s_myport);
my_addr.sin_addr.s_addr = INADDR_ANY;

if (bind(sockfd, (struct sockaddr *) &my_addr, sizeof(struct sockaddr)) == -1) 
{
    perror("bind");
    exit(1);
} 
else
{
    printf("binded\n");
}
unsigned int lisnum = 1;
if (listen(sockfd, lisnum) == -1) 
{
    perror("listen");
    exit(1);
} 
else
{
    printf("begin listen\n");
}
 
while (1) 
{
    SSL *ssl;
    len = sizeof(struct sockaddr);

    if ((new_fd = accept(sockfd, (struct sockaddr *) &their_addr, &len)) == -1)
    {
        perror("accept");
        exit(errno);
    } 
    else
    {
    printf("server: got connection from {b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s, port {b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}d, socket {b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}d\n", inet_ntoa(their_addr.sin_addr), ntohs(their_addr.sin_port), new_fd);
    }

    ssl = SSL_new(ctx);

    SSL_set_fd(ssl, new_fd);

    if (SSL_accept(ssl) == -1) 
    {
        perror("accept");
        close(new_fd);
        break;
    }


    bzero(buf, MAXBUF + 1);
    strcpy(buf, "hello, this is server");

    len = SSL_write(ssl, buf, strlen(buf));

    if (len <= 0) 
    {
        printf("{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s,{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}d,{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s\n",buf, errno, strerror(errno));
        goto finish;
    } 
    else
    {
        //printf("{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s, {b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}d\n", buf, len);
    }

    bzero(buf, MAXBUF + 1);

    len = SSL_read(ssl, buf, MAXBUF);
    if (len > 0)
    {
        printf("{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s, {b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}d\n", buf, len);
    }
    else
    {
        printf("{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}d,{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s'\n", errno, strerror(errno));
    }

finish:

    SSL_shutdown(ssl);
    SSL_free(ssl);
    close(new_fd);
}


close(sockfd);

SSL_CTX_free(ctx);
return 0;

}
客户端代码:

include <stdio.h>

include <string.h>

include <errno.h>

include <sys/socket.h>

include <resolv.h>

include <stdlib.h>

include <netinet/in.h>

include <arpa/inet.h>

include <unistd.h>

include <openssl/ssl.h>

include <openssl/err.h>

define MAXBUF 1024

void ShowCerts(SSL * ssl)
{

X509 *cert;
char *line;

cert = SSL_get_peer_certificate(ssl);
if (cert != NULL)
{
    printf("show:\n");
    line = X509_NAME_oneline(X509_get_subject_name(cert), 0, 0);
    printf("one: {b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s\n", line);
    free(line);
    line = X509_NAME_oneline(X509_get_issuer_name(cert), 0, 0);
    printf("two {b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s\n", line);
    free(line);
     
    char commonName [512] = {0};
    X509_NAME * name = NULL;
    name = X509_get_subject_name(cert);
    X509_NAME_get_text_by_NID(name, NID_commonName, commonName, 512);
    printf("debug-name:{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s\n", commonName);
     
    X509_free(cert);
} 
else
{
    printf("error\n");
}

}

int main(int argc, char **argv)
{

int sockfd, len;
struct sockaddr_in dest;
char buffer[MAXBUF + 1];
SSL_CTX *ctx;
SSL *ssl;

if (argc != 3)
{
    printf("please use command:{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s 127.0.0.1 8081\n", argv[0]);
    exit(0);
}


SSL_library_init();
OpenSSL_add_all_algorithms();
SSL_load_error_strings();
ctx = SSL_CTX_new(SSLv23_client_method());
if (ctx == NULL) 
{
    ERR_print_errors_fp(stdout);
    exit(1);
}


if ((sockfd = socket(AF_INET, SOCK_STREAM, 0)) < 0) 
{
    perror("Socket");
    exit(errno);
}
printf("socket created\n");


bzero(&dest, sizeof(dest));
dest.sin_family = AF_INET;
dest.sin_port = htons(atoi(argv[2]));
if (inet_aton(argv[1], (struct in_addr *) &dest.sin_addr.s_addr) == 0)
{
    perror(argv[1]);
    exit(errno);
}
printf("address created\n");


if (connect(sockfd, (struct sockaddr *) &dest, sizeof(dest)) != 0)
{
    perror("Connect ");
    exit(errno);
}
printf("server connected\n");


ssl = SSL_new(ctx);
SSL_set_fd(ssl, sockfd);

if (SSL_connect(ssl) == -1)
{
    ERR_print_errors_fp(stderr);
}
else
{
    printf("Connected with {b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s encryption\n", SSL_get_cipher(ssl));
    ShowCerts(ssl);
}


bzero(buffer, MAXBUF + 1);

len = SSL_read(ssl, buffer, MAXBUF);
if (len > 0)
{
    printf("{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s:{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}d\n", buffer, len);
}
else
{
    printf("{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}d,{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s'\n", errno, strerror(errno));
    goto finish;
}
bzero(buffer, MAXBUF + 1);
strcpy(buffer, "hello this is client.");

len = SSL_write(ssl, buffer, strlen(buffer));
if (len < 0)
{
    printf("{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s,{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}d,{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s\n", buffer, errno, strerror(errno));
}
else
{
    //printf("{b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}s, {b75a474a571334bb08f4db31fa80d7688c6401b1dcf97fb55e06ed241b59472c}d\n", buffer, len);
}

finish:

SSL_shutdown(ssl);
SSL_free(ssl);
close(sockfd);
SSL_CTX_free(ctx);
return 0;

}
编译命令:

gcc -Wall -lssl server.cpp -lstdc++ -o server
gcc -Wall -lssl client.cpp -lstdc++ -o client
执行:

./server cacert.pem privkey.pem
./client 127.0.0.1 8081
OK,这样就能建立连接发送数据了。