Skip to content

Latest commit

 

History

History
275 lines (183 loc) · 7.17 KB

1.1 字符串-查找.md

File metadata and controls

275 lines (183 loc) · 7.17 KB
Raw

#字符串-查找

  • 子串查找

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

在一个字符串中找到第一个只出现一次的字符。如输入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 的范围是 -128127，unsigned char 才是0255

示例代码：

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个指针，第一个指针指向一个当前最长数字串的第一个数字，第二个指针指向第二个数字串的第一个数字，第三个指针是遍历指针，且统计第二个数字串的长度；当统计出来的长度大于第一个数字串的长度，第一个指针指向第二个指针指向的数字，相反，第二个指针和第三个指针继续向后查找。

  1. 当end首次碰到数字时，且tmp=0，说明是首次出现数字，第二个指针移到该数字，继续遍历
  2. 如果数字后面还是数字，tmp!=0 就是第二个数字串，因此 tmp += 1;
  3. 当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)