找到第一个只出现一次的字符¶

在一个字符串中找到第一个只出现一次的字符。如输入 ahbaccdeff，则输出 h。

char char_first_appear_once(const char *source)

思路一：蛮力统计， O(n^2) 复杂度思路二：使用 hash 表，2 次扫描 * 第一次建立 hash 表 key 为字符，value 为出现次数； * 第二次扫描找到第一个 value 为 1 的 key，时间复杂度 O(n)

hash 表长度 256，字符直接作为 key 值。需要注意的是 char 的范围是 -128~127，unsigned char 才是 0~255

示例代码：

char char_first_appear_once(const unsigned char *source){
    int hash[256]={0};
    char *tmp = source;
    if (tmp == NULL) return '\0';

    //第一次建立hash表 key为字符，value为出现次数
    while(*tmp != '\0'){
        hash[*tmp]++;
        tmp++;
    }

    //第二次扫描找到第一个value为1的key
    tmp = source;
    while(*tmp != '\0'){
        if (hash[*tmp] == 1) return *tmp;
        tmp++;
    }
    return '\0';
}

题目扩展：这里的字符换成整数，整数数量几十 TB，海量数据处理，显然 hash 方法不可能，没有那么大得内容

字符串中找出连续最长的数字子串¶

写一个函数,功能：

在字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串赋值给其中一个函数参数 outputstr 所指内存。

例如："abcd12345ed125ss123456789" 的首地址传给 intputstr 后，函数将返回 9，outputstr 所指的值为 123456789

它的原形是：

int longest_continuious_number(const char *input,char *output)

应该有 3 个指针，第一个指针指向一个当前最长数字串的第一个数字，第二个指针指向第二个数字串的第一个数字，第三个指针是遍历指针，且统计第二个数字串的长度；当统计出来的长度大于第一个数字串的长度，第一个指针指向第二个指针指向的数字，相反，第二个指针和第三个指针继续向后查找。

当 end 首次碰到数字时，且 tmp=0，说明是首次出现数字，第二个指针移到该数字，继续遍历
如果数字后面还是数字，tmp!=0 就是第二个数字串，因此 tmp += 1;
当 end 从数字到普通字符时，如果 tmp > max ,就要修改 max 和第一个指针 start ,并把 tmp 归为 0

int longest_continuious_number(const char *input,char *output){
    int max = 0;
    char *start= input;
    char *mid = input;
    char *end = input;
    int tmp = 0;
    if (input == NULL || output == NULL) return 0;

    while (*end != '\0'){
        if (*end < '0' || *end < '9'){//字母
            if(tmp > max){
                max = tmp;
                start = mid;
            }
            tmp = 0;
        }else{//数字
            if (tmp == 0){//发现数字    
                mid = end;
            }
            tmp++;
        }
        end++;
    }

    //修改已数字结尾的bug
    if(tmp > max){
        max = tmp;
        start = mid;
    }

    //copy
    int i=0;
    while(i<max){
        *(output+i) = *(start+i);
        i++;
    }
    *(output+i)='\0';

    return max;
}

最长无重复子串问题¶

给一个字符串，找出不包含有重复字符的最长子串的长度如 ”abcabbcbb“ 输出 3

思路 1：两个指针思路 2：窗口函数

两个指针窗口函数实现

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> window;

    int left = 0, right = 0;
    int res = 0; // 记录结果
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        window[c]++;
        // 判断左侧窗口是否要收缩
        while (window[c] > 1) {
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            window[d]--;
        }
        // 在这里更新答案
        res = max(res, right - left);
    }
    return res;
}

对称子字符串的最大长度 (最长回文子串)¶

题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出 4。

分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。

int max_symmetrical_char_length(const char *scr);

思路一：蛮力法，3 重循环（类似求子数组的最大和 fmax(i,j) 问题）， fmax(i,j) 区间 i，j 是最长的对称字符
思路二：遍历所有子串，然后判读是否对称 O(n^2)
思路三：有个 O(n) 复杂度的算法 http://www.cnblogs.com/McQueen1987/p/3559497.html 分析过程如下：

int max_symmetrical_char_length(const char *scr){

}

    public String longestPalindrome(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            // 以 s[i] 为中心的最长回文子串
            String s1 = palindrome(s, i, i);

            // 以 s[i] 和 s[i+1] 为中心的最长回文子串
            String s2 = palindrome(s, i, i + 1);

            // res = longest(res, s1, s2)
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        return res;
    }

    //实现一个函数来寻找最长回文串
    String palindrome(String s, int l, int r) {
        // 防止索引越界
        while (l >= 0 && r < s.length()
                && s.charAt(l) == s.charAt(r)) {
            // 向两边展开
            l--; r++;
        }
        // 返回以 s[l] 和 s[r] 为中心的最长回文串
        return s.substring(l + 1, r);
    }

最小覆盖子串¶

（难度 hard） 滑动窗口

给定字符串 s, t ; 在字符串 s 里找出包含 t 所有字母的最小子串 eg: s = "ADOBECODEBANC" t = "ABC" 输出： "BANC"

最长公共子串问题¶

请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。

例如：输入两个字符串 BDCABA 和 ABCBDAB，字符串 BCBA 和 BDAB 都是是它们的最长公共子串，则输出它们的长度 4，并打印任意一个子串。

int longest_common_subsequence(const char *s1,const char *s2, char *common)

分析：求最长公共子串（Longest Common Subsequence,LCS）是一道非常经典的动态规划题，因此一些重视算法的公司像 MicroStrategy 都把它当作面试题。如 "abccade","dgcadde" 的最大子串为 "cad"

实例代码：

int longest_common_subsequence(const char *s1,const char *s2, char *common){

}

求最大连续递增数字子串¶

如“ads3sl456789DF3456ld345AA”中的“456789”就是所求。这道题在上一道题目的基础上增加了数字要递增的条件。思路跟上面差不多，碰到不递增的数字就相当于第二个数字串了。

请编写能直接实现 strstr() 函数功能的代码。¶

strstr(str1,str2) 判断 str2 是否是 str1 的子串。

/*
@ret 有就返回第一次出现子串的地址,否则返回NULL
*/
char *strstr(const char *source, const char *target){

}

子串匹配的个数¶

已知一个字符串，比如 asderwsde,寻找其中的一个子字符串比如 sde 的个数，如果没有返回 0，有的话返回子字符串的个数。

char *substr_count(const char *src, const char *substr, int *count)