[toc]
去除重复字⺟
给你⼀个仅包含⼩写字⺟的字符串，请你去除字符串中重复的字⺟，使得每个字⺟只出现⼀ 次。需保证返回结果的字典序最⼩（要求不能打乱其他字符的相对位置）
解题思路：
判断字符串可能出现的特殊情况
用一个
record数组记录字符串中字母出现的次数;申请一个字符串栈
stack用来存储去除重复字母的结果,并利用它的特性帮助我们找到正确的次序;遍历字符串
s从
0~top,遍历stack判断当前字符s[i]是否存在于栈stack中
如果当前字符是否存在于栈的定义一个falg标记isExist,0表示不存在,1表示存在如果
isExist存在,record[s[i]]位置上的出现次数减一，并继续遍历下一个字符; 表示当前的stack已经有这个字符了没有必要处理这个重复的字母;如果
isExist不存在,则
如果不存在,则需要循环一个找到一个正确的位置,然后在存储起来;
如果不存在，跳过栈中所有比当前字符大、且后面还会出现的元素，然后将当前字符入栈
top > -1表示栈非空
stack[top] > s[i]表示栈顶元素比当前元素大
record[stack[top]] > 1表示后面还会出现
通过一个while循环找到将栈中位置错误的数据,出栈. 找当前合适的位置,则结束while循环;
找到合理的位置后,则将当前字符s[i]入栈;直到遍历完所有字符后,则为字符串栈
stack添加一个结束符'\0',并返回当前字符串首地址;
char *removeDuplicateLetters(char *s){
//为空 长度为0直接返回
if(*s == NULL || strlen(s) == 0){
return "";
}
//只有一个直接返回
if (strlen(s) == 1){
return *s;
}
int record[26] = {0}; //存放对应26字母出现的次数
int len = strlen(s);
char *stack = (char *)malloc(sizeof(char)*len); //开辟空间
memset(stack, 0, len); //赋值0
//记录
for (int i=0; i<len; i++) {
record[s[i]-'a']++;
}
int top=-1;
int isExist=0;
for (int i=0; i<len; i++) {
//存在 退出循环
for (int j=0; j<=top; j++) {
if (s[i] == stack[j]){
isExist =1;
break;
}
}
if (isExist == 1){
//已经有了 --
record[s[i]-'a']--;
}else{
// 栈有值,栈顶元素大于s[i],且栈顶元素后面还有
while (top>-1 && stack[top] > s[i] && record[stack[top] -'a']>1) {
//记录次数--
record[stack[top] -'a']--;
//出栈
top--;
}
}
//将s[i]存入
top++;
stack[top]=s[I];
}
stack[++top] ='\0';
return stack;
}
字符串查找
- 题目: 有一个主串
S = {a, b, c, a, c, a, b, d, c}, 模式串T = { a, b, d }; 请找到模
式串在主串中第一次出现的位置;
提示: 不需要考虑字符串大小写问题, 字符均为小写字母
BF
-
BF算法-爆发匹配算法
将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。
解题思路:
从
0开始到len-模式串的长度
外圈循环次数是strlen(S)-len
内圈循环模式串
判断S[i+j]!=T[j]是否相等,不相等,i+1,从下一个开始
和模式串匹配,如果最后j=len-1;说明匹配到了
int returnFirstAreaStr(char *S,char *T){
unsigned int len = strlen(T);
for(int i=0;i<(strlen(S)-len);i++){
for(int j=0;j<len;j++){
if (S[i+j]!=T[j]){
break;
}
if (j == len-1){
return (i+1);
}
}
}
return -1;
}
RK
HASH！
如果两个字符串hash后的值不相同，则它们肯定不相同；如果它们hash后的值相同，它们不一定相同。
RK算法的基本思想就是：将模式串P的hash值跟主串S中的每一个长度为|P|的子串的hash值比较。如果不同，则它们肯定不相等；如果相同，则再诸位比较之。
如何将模式串或者主串拆分后的子串换算成一个哈希值?
在十进制下,123 和 456的比较, 能不能将abc和edf的比较,计算成十进制下比较一样?
- 可以将字母转换成进制,在
ASCII中,小写字母a是65,'b'-'a' = 1; - 为了避免冲突,可以构造一个26进制,来记录每个字母对应的数组,
假设 模式串
ccc主串dbcedb
4cfb3990a2ee3d38f82571a7f32708a9
在26进制下
aba65d9bdfc6355dca617a6ad893a03e
串哈希值求解规律
- 相邻的
2个子串s[i]与s[i+1](i表示子串从主串中的起始位置,子串的长度
都为m). 对应的哈希值计算公式有交集. 也就说我们可以使用s[i-1]计算出s[i]
的哈希值;
9c1be5993f230a789c546ea86314e03d -
s[i+1]实现上是上一个s[i]去掉最高位数据,其余的m-1为字符乘以
d进制. 再加上最后一个为字符得到;
主串分割后的哈希值:St[i+1] = (st[i] - d2 ✖ s[i] ) ✖ d + s[i+m]
注意点,虽然哈希值也有存在不相同情况,如果查找到,在判断一下字符是否一样
//为了杜绝哈希冲突. 当前发现模式串和子串的HashValue 是一样的时候.还是需要二次确认2个字符串是否相等.
int isMatch(char *S, int i, char *P, int m)
{
int is, ip;
for(is=i, ip=0; is != m && ip != m; is++, ip++)
if(S[is] != P[ip])
return 0;
return 1;
}
- 上代码
#define d 26 //当前的进制
//4.为了杜绝哈希冲突. 当前发现模式串和子串的HashValue 是一样的时候.还是需要二次确认2个字符串是否相等.
int isMatch(char *S, int i, char *P, int m)
{
int is, ip;
for(is=i, ip=0; is != m && ip != m; is++, ip++)
if(S[is] != P[ip])
return 0;
return 1;
}
int getPower(int m){
int i = 0;
int n =1;
while (i < (m-1)) {
n = n*d;
I++;
}
return n;
}
int RK(char *S, char *P){
unsigned int n = (int)strlen(S); //主串长度
unsigned int m = (int)strlen(P); //模式串长度
unsigned int Pn = 0; //记录模式串哈希值
unsigned int St = 0; //记录主串哈希值
//123 == 0 + 1
// i=0 0 + 1 = 1
// i=1 10+2 = 12
// i=2 12*10 + 3 = 123
for (int i=0; i<m; i++) {
Pn = Pn * d + P[i]-'a';
St = St * d + S[i]-'a';
}
int constPower = getPower(m);
for (int j=0; j<n-m; j++) {
if (Pn == St && isMatch(S,j,P,m))
return j+1;
St = ((St - constPower * (S[j]-'a')) * d + (S[j+m]-'a'));
}
return -1;
}
打印
char *buf="abcabhgsabcabxhsjhgsdjsdhsdjsdh";
char *ptrn="hgs";
printf("主串为%s\n",buf);
printf("子串为%s\n",ptrn);
int index = RK(buf, ptrn);
printf("find index : %d\n",index);
主串为abcabhgsabcabxhsjhgsdjsdhsdjsdh
子串为hgs
find index : 6
