小兴的博客

0%

leetcode_string

发表于 更新于 分类于

leetcode_string

传统字符串匹配：

  • 简单写写,变量命名等就先不纠结了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
int strStr(char s[],char p[])
{
		if(s[0]=='\0'||p[0]=='\0')
				cout<<"p or s is null"<<endl;
		int k=0,j=0,i=0;
		for(i=0,j=0;s[i]!='\0'&&s[k]!='\0';)
		{
		     if(p[j]=='\0')
				   break;	 
			 if(s[k]==p[j])
			 {
					 k++;
					 j++;
			 }
			 else //不匹配时重新来过
			 {
					 i++;
					 k=i;
					 j=0;
			 }
		}
        if(p[j]=='\0')
				return i;
        else 
				return -1;
}```
#### kmp匹配算法
kmp算法：基本过程见另一篇文章数据结构之字符串<!--more-->，这里贴写代码(未经大数据检验，谨慎观看)
```cpp
int nextfunc(char p[],int next[])
{
   next[0]=-1;
   next[1]=0;
   int j=1;
   int k=0;
   while(p[j]!='\0')
   {
		   if(k==0||p[j]==p[k])
		   {
				   ++j;
				   ++k;
				   next[j]=k;
		   }
		   else
				   k=next[k];
   }
   return 0;
}

int kmp(char s[],char p[])
{
   int i=0;
   int j=0;
   int next[100];
   nextfunc(p,next);
   for (i=0;s[i]!='\0'&&p[j]!='\0';i++)
   {
		   //if(j==-1)j=0;
		   if(s[i]==p[j])
		   {
		     j++;
			 continue;
		   }
		   while(s[i]!=p[j]&&j>=0)j=next[j];
		   j++;
   }
  if(p[j]=='\0')
		 return i-j;
  else 
		 return -1;
}

简单测试

1
2
3
4
5
6
7
8
9
10
int main ()
{
		char a[19]={'a','b','c','a','b','c','a','s','s','f','r','e','r'};
		char b[10]={'a','b','c','a','s'};
		int pos=strStr(a,b);
		cout<<pos<<endl;
		int pos2=kmp(a,b);
		cout<<pos2<<endl;
		return 0;
}

其他字符串算法题目：

判读字符串是否为回文串
  • 所谓回文串即正者读反着读都一样：
  • 解决方案：
    • 1.设置两个索引，一个从字符串开始位置往后走，一个从字符串最后的位置往前走，比较这两个索引指向的字符是否相等，直到遍历完整个字符串；注意这里其实并不需要遍历整个字符串，一个索引只需要走一半就可以，回文串两边对称的。
    • 2.利用栈，思路类似
字符串转整数(atoi)
  • 分析：这个题目需要注意的是各种不规则的输入和其他边缘条件如int整数的范围等
  • 解决方案:
    • 若是严格的检查，则判断字符ASCII码是否在0-9之间，注意整数的首位不能为0）；整数的正负；数据是否溢出；是否数据的表现形式如33x8fe；等等。
    • 非严格的检查，如遇到非法的字符跳过即可；首位为0时跳过或者当成八进制等等
对两个二进制字符串求和
  • 如”111”+”101”=”1100”
  • 解决方案：
      1. 像十进制那样直接求和，进位，从最右边的字符开始，若相加大于1则进位，注意两个字符串可能一个很长一个很短，而进位可能一直需要延续
    • 2.将两个字符串分别转换为十进制再做运算，结果再转为二进制
最长回文子串
  • 暴力方法：将所有子串列出来先判断哪些是回文串，再取长度最长的；
    正则表达式
  • 我对正则表达式的处理方案一直很倾向于用状态机，这种方法可以用图表示出来，方案的完备性好判断，别人也好理解；
  • 递归方案
    最长公共前缀
  • 找出字符串数组中的最长公共前缀：给定一个字符串数组，找出他们的最长公共前缀
  • 分析：这道题目需求不明确，是需要 所有的字符串=都有的公共前缀还是若只有部分字符串有公共前缀也可以？也可能我理解有误~
实现strtod()函数
  • 即判断一个字符串是否表示一个数字如:”1.0”
  • 分析：可以用状态机实现
整数和罗马数字的相互转换
  • 这道题有些无聊
    count and say
  • 一个数列如下：
    1 11 21 1211 111221,…
    意思是1,第二个表示第一个的情况，即1个1故为11,第三个数表示第二个数的情况，即两个1,21，以此类推
  • 求数列中的第n个数
  • 解决方案，直接模拟，一个一个算出来
Anagrams:
  • 字符串中的打乱字母顺序从而得到新的单词如eat打乱后得到tea等
给定绝对路径简化它
在一个英文句子中找到最后一个单词的长度