LeetCode num028

Problem

Implement strStr()
Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Update (2014-11-02):
The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char * or String, please click the reload button to reset your code definition.

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
class Solution {
public:
int strStr(char *haystack, char *needle) {
if (needle[0] == '\0')
{
return 0;
}
int i, j, mark = -1;
for (i = 0, j = 0; haystack[i] != '\0'; i++)
{
if (haystack[i] == needle[j])
{
j++;
if (mark == -1)
{
mark = i;
}
if (needle[j] == '\0')
{
return mark;
}
continue;
}
if (mark != -1)
{
i = mark;
}
mark = -1;
j = 0;
}
return -1;
}
};

Comment

  1. 注意匹配一半时的回滚位置。

LeetCode num014

Problem

Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.

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
class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
int i, j, mark = 0;
if (strs.size() == 0)
{
return "";
}
for (i = 0; strs[0][i] != '\0'; i++)
{
for (j = 1; j < strs.size(); j++)
{
if (strs[j][i] != strs[0][i])
{
mark = 1;
break;
}
}
if (mark == 1)
{
break;
}
}
string str = strs[0];
return str.substr(0, i);
}
};

Comment

  1. 需熟悉C++的string类型内部函数

LeetCode num009

Problem

Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.

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 isPalindrome(int x) {
int large = 1000000000, mark = 1, small = 10;
if (x < 0)
{
return false;
}
if (x / 10 == 0)
{
return true;
}
while (large >= small)
{
if (x / large > 0 || mark == 0)
{
mark = 0;
if (x / large == (x % small) / (small / 10))
{
small = small * 10;
x = x % large;
}
else
{
return false;
}
}
large = large / 10;
}
if (small / large == 10 || small / large == 100)
{
return true;
}
return false;
}
};

Comment

  1. 不知道我这个满足“Do this without extra space.”不,但AC了;
  2. 需要考虑的问题还是挺多的;
  3. 负数直接输出为false。

LeetCode num008

Problem

String to Integer (atoi)
Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class Solution {
public:
int atoi(const char *str) {
int result = 0, i, rev = 1, temp, mark = 0;
int dream, int_min = INT_MAX, int_max = INT_MAX;
string love = str;
for (i = 0; i < love.size(); i++)
{
if (love[0] == ' ')
{
love = love.substr(1, love.size() - 1);
continue;
}
else
{
break;
}
}
if (love[0] == '-')
{
love = love.substr(1, love.size() - 1);
rev = -1;
}
else if (love[0] == '+')
{
love = love.substr(1, love.size() - 1);
}
for (i = 0; i < love.size(); i++)
{
if (love[i] < '0' || love[i] > '9')
{
love[i] = '\0';
break;
}
}
love = love.substr(0, i);
if (love.size() > 10 && rev == 1)
{
return INT_MAX;
}
else if (love.size() > 10 && rev == -1)
{
return INT_MIN;
}
for (int i = 0; i < love.size(); i++)
{
temp = pow(10, (love.size() - i - 1));
dream = chtoint(love[i]);
if (rev == 1)
{
if (love.size() == 10 && dream > int_max / temp)
{
return INT_MAX;
}
else if (love.size() == 10 && dream == int_max / temp && mark == 0)
{
int_max = int_max % temp;
result += dream * temp;
continue;
}
mark = 1;
}
else if (rev == -1)
{
if (love.size() == 10 && dream > int_min / temp)
{
return INT_MIN;
}
else if (love.size() == 10 && dream == int_min / temp && mark == 0)
{
int_min = int_min % temp;
if (temp == 1)
{
int_min++;
}
result += dream * temp;
continue;
}
mark = 1;
}
result += dream * temp;
}
return rev * result;
}
int chtoint(char ch)
{

return (int)ch - 48;
}
};

Comment

  1. 没看提示哦;
  2. 坑真的好多啊;
  3. 我还是太水了。