hihocoder-num1015

I am a coder
KMP算法
时间限制:1000ms
单点时限:1000ms
内存限制:256MB

描述

求一个字符串在另外一个字符串中出现的次数

输入

第一行一个整数N,表示测试数据组数。

接下来的N*2行,每两行表示一个测试数据。在每一个测试数据中,第一行为模式串,由不超过10^4个大写字母组成,第二行为原串,由不超过10^6个大写字母组成。

输出

对于每一个测试数据,按照它们在输入中出现的顺序输出一行Ans,表示模式串在原串中出现的次数。

样例输入

1
2
3
4
5
6
7
8
9
10
11
5
HA
HAHAHA
WQN
WQN
ADA
ADADADA
BABABB
BABABABABABABABABB
DAD
ADDAADAADDAAADAAD

样例输出

1
2
3
4
5
3
1
3
1
0

错误解法(1)

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
#include <iostream>
using namespace std;

int kmpNum(char * str1, char * str2)
{

int i = 0, j = 0, k = 0, num = 0;
while (str2[i])
{
if (!str1[j])
{
num++;
j = k;
k = 0;
}
if (str2[i] == str1[j])
{
if (j != 0)
{
if (str2[i] == str1[k]) k++;
else k = 0;
}
j++;
}
else
{
if (k != 0)
{
j = k + 1;
}
else
{
j = 0;
}
k = 0;
}
i++;
}
if (!str1[j]) num++;
return num;
}

int main()
{

char str1[10005], str2[1000005];
int n;
cin >> n;
while (n--)
{
cin >> str1 >> str2;
int ret = kmpNum(str1, str2);
cout << ret << endl;
}
return 0;
}

错误解法(2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int * jump(char *str)
{

int ret[10005];
int i = 0, j = -1;
int len = strlen(str);
ret[0] = -1;
while (i < len)
{
if (j == -1 || str[i] == str[j])
{
ret[++i] = ++j;
}
else
{
j = ret[j];
}
}
return ret;
}

答案

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
#include <iostream>
#include <cstring>
using namespace std;

int hiho(char *str1, char *str2)
{

int * next, ret = 0;
int n = strlen(str1);
int len = strlen(str2);
next = (int *)malloc(sizeof(int) * (n + 1));
int i = 0, j = -1;
next[0] = -1;
while (i < n)
{
if (j == -1 || str1[i] == str1[j])
{
next[++i] = ++j;
}
else
{
j = next[j];
}
}
i = 0, j = 0;
while (i < len)
{
if (j == -1 || str1[j] == str2[i])
{
i++;
j++;
}
else
{
j = next[j];
}
if (j == n)
{
ret++;
}
}
free(next);
return ret;
}

int main()
{

char str1[10005], str2[1000005];
int n;
cin >> n;
while (n--)
{
cin >> str1 >> str2;
int ret = hiho(str1, str2);
cout << ret << endl;
}
return 0;
}

收获与体会

  1. 以前就听说过KMP解法,但是今天才真正的去写这个代码,确实很牛;
  2. 没有真正掌握,还需加强;
  3. 错误解法(2)中的函数不知为何执行出错。

LeetCode-num020

Valid Parentheses

Problem

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

Solution

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
class Solution
{
public:
bool isValid(string s)
{

stack<char> staStr;
for (int i = 0; i < s.size(); i++)
{
if (staStr.size() == 0)
{
staStr.push(s[i]);
continue;
}
if (isMatch(staStr.top(), s[i]))
{
staStr.pop();
}
else
{
staStr.push(s[i]);
}
}
if (staStr.size() == 0) return true;
else return false;
}

bool isMatch(char ch1, char ch2)
{

if ((ch1 == '(' && ch2 == ')') ||
(ch1 == '{' && ch2 == '}') ||
(ch1 == '[' && ch2 == ']'))
return true;
else
return false;
}
};

Comment

  1. 思路:利用栈,与栈顶元素匹配出栈,否则压栈,循环结束如果栈为空则返回true,否则返回false。

LeetCode num038

Count and Say

Problem

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, …

1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.
Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

Solution

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
class Solution
{
public:
string countAndSay(int n)
{

string str = "1", temp = "11";
int num = 1, markPosition = 0, i, j;
for (i = 1; i < n; i++)
{
for (j = 1; j < str.size(); j++)
{
if (str[j] == str[j - 1])
{
num++;
}
else if (str[j] != str[j - 1])
{
temp[0] = '0' + num;
temp[1] = str[j - 1];
str.replace(markPosition, num, temp);
num = 1;
markPosition += 2;
j = markPosition;
}
}
temp[0] = '0' + num;
temp[1] = str[j - 1];
str.replace(markPosition, num, temp);
num = 1;
markPosition = 0;
}
return str;
}
};

Comment

  1. 题目较简单
  2. 对字符串操作不够熟练

LeetCode num165

Compare Version Numbers

Problem

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

1
0.1 < 1.1 < 1.2 < 13.37

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Solution

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
class Solution
{
public:
int compareVersion(string version1, string version2)
{

vector<int> numSet1 = deNum(version1);
vector<int> numSet2 = deNum(version2);
int size = numSet1.size() > numSet2.size() ? numSet1.size() : numSet2.size();
for (int i = 0; i < size - numSet1.size(); i++)
{
numSet1.push_back(0);
}
for (int i = 0; i < size - numSet2.size(); i++)
{
numSet2.push_back(0);
}
for (int i = 0; i < size; i++)
{
if (numSet1[i] > numSet2[i]) return 1;
else if (numSet1[i] < numSet2[i]) return -1;
}
return 0;
}

vector<int> deNum(string version)
{
int num = 0, size = version.size(), i, j;
vector<int> ret;
for (i = size - 1, j = 0; i >= 0; i--, j++)
{
if (version[i] == '.')
{
ret.insert(ret.begin(), num);
num = 0;
j = -1;
}
else
{
num += pow(10, j) * (version[i] - '0');
}
}
ret.insert(ret.begin(), num);
return ret;
}
};

###Comment

  1. 开始理解题意有误
    2,用0补全

LeetCode num067

Problem

Add Binary
Given two binary strings, return their sum (also a binary string).

For example,
a = “11”
b = “1”
Return “100”.

Solution

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
class Solution {
public:
string addBinary(string a, string b) {
int i, j, mark = 0;
char ch;
string temp;
if (a.size() < b.size())
{
temp = a;
a = b;
b = temp;
}
for (i = a.size() - 1, j = b.size() - 1; i >= 0; i--, j--)
{
if (j < 0)
{
ch = '0';
}
else
{
ch = b[j];
}
if (a[i] == '1' && ch == '1' && mark == 1)
{
a[i] = '1';
mark = 1;
}
else if (a[i] == '1' && ch == '1' && mark == 0)
{
a[i] = '0';
mark = 1;
}
else if (((a[i] == '0' && ch == '1') || (a[i] == '1' && ch == '0')) && mark == 1)
{
a[i] = '0';
mark = 1;
}
else if (((a[i] == '0' && ch == '1') || (a[i] == '1' && ch == '0')) && mark == 0)
{
a[i] = '1';
mark = 0;
}
else if (a[i] == '0' && ch == '0' && mark == 1)
{
a[i] = '1';
mark = 0;
}
else if (a[i] == '0' && ch == '0' && mark == 0)
{
a[i] = '0';
mark = 0;
}
}
if (mark == 1)
{
a.insert(0, "1");
}
return a;
}
};

Comment

  1. 题比较简单。

LeetCode num058

Problem

Length of Last Word
Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = “Hello World”,
return 5.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int lengthOfLastWord(const char *s) {
int i, count = 0;
for (i = 0; s[i] != '\0'; i++)
{
if (s[i] != ' ')
{
count++;
}
else if (s[i + 1] != ' ' && s[i + 1] != '\0')
{
count = 0;
}
}
return count;
}
};

Comment

  1. 题比较简单。