细节题主要是要胆大心细,不要畏畏缩缩就好。

Restore IP Addresses

主要注意以0开头的情况,还有就是字符串访问不要越界

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:
vector<string> restoreIpAddresses(string s) {
if (s.size() == 0) return {};
vector<string> result;
vector<string> item;
helper(result, item, s, 0);
return result;
}
void helper(vector<string> &result, vector<string> &item, string s, int pos) {
if (pos >= s.size()) {
if (item.size() != 4) return; // 注意点一:注意结果处理的条件,
result.push_back(item[0] + "." + item[1] + "." + item[2] + "." + item[3]);
return;
}
int size = item.size();
// 注意点二:适当剪枝,其实不剪枝也可以,但是这样可以降低一点时间复杂度
if ((s.size() - pos) > (4 - size) * 3 || (s.size() - pos) < (4 - size)) return;
int num = 0;
for (int i = pos; i < pos + 3 && i < s.size(); i++) {
num = num * 10 + (s[i] - '0');
// 注意点三: 数值不能大于255
if (num > 255)
break;
item.push_back(s.substr(pos, i - pos + 1));
helper(result, item, s, i + 1);
item.pop_back();
// 注意点四:注意0这个特殊情况,ip地址中每一个字节都不能出现01这种
if (num == 0) break;
}
}
};

String to Integer (atoi)

  1. 注意处理前面的空格
  2. 正负号的处理
  3. 非数字字符的处理
  4. 注意不要溢出
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
class Solution {
public:
int myAtoi(string str) {
if (str.size() == 0) return 0;
int sign = 1;
int pos = 0;
while (pos < str.size() && str[pos] == ' ')
pos++;
if (str[pos] == '+' || str[pos] == '-')
sign = str[pos++] == '+' ? 1 : -1;
int num = 0;
for (pos; pos < str.size(); pos++) {
if (str[pos] < '0' || str[pos] > '9')
return sign * num;
if (num > INT_MAX / 10)
return sign == 1 ? INT_MAX : INT_MIN;
if (num == INT_MAX / 10 && (str[pos] - '0') > 7)
return sign == 1 ? INT_MAX : INT_MIN;
num = num * 10 + (str[pos] - '0');
}
return sign * num;
}
};

Reverse Integer

注意溢出的条件,和atoi的题差不多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int reverse(int x) {
int num = 0;
while (x != 0) {
if (abs(num) > INT_MAX / 10)
return 0;
if (abs(num) == INT_MAX / 10 && abs(x % 10) > 7)
return 0;
num = num * 10 + x % 10;
x = x / 10;
}
return num;
}
};