笔者按照目录刷题，对于每一道题，力争使用效率最高（时间复杂度最低）的算法，并全部通过C++代码实现AC。(文中计算的复杂度都是最坏情况复杂度)
因为考虑到大部分读者已经在Leetcode浏览过题目了，所以每道题都按照 解题思路、实现代码 的顺序进行讲解。
(笔者目前已刷 120 题，已更新解法 20 题，最近一段时间会频繁更新)可以点击下方链接，直达gitbook：
https://codernie.gitbooks.io/leetcode-solutions/content/
也欢迎大家关注我的同名微信公众号(大雄的学习人生)，有问题可以随时后台回复我，多多探讨。
11. Container With Most Water【medium】
解题思路：
这道题可以考虑暴力枚举的方式，复杂度应该是O(N^2)，嵌套循环即可实现，下面重点讲复杂度只有O(N)的头尾标记法。
考虑到：
容器的容量 = 两端中较矮的板子长度（L） * 两端的距离（d）
在数组两端设置头尾标记，以头尾标记为容器的两端，假设头标记对应的板子长度比较短，那么现在 容器的容量 = 头标记板子 * 头尾标记的距离。那么以头标记为一端的所有容器的容量必然小于当前容器，因为其他以头标记为一端的容器的L一定小于或等于当前容器，而距离d一定小于当前容器。所以这些容器都可以无需遍历，因此让头标记向尾部移动一个单位；假设尾标记对应的板子长度比较短，则以此类推，让尾标记向头部移动一个单位，直至头尾标记相遇则停止寻找。
实现代码：
// 11. Container With Most Water
int maxArea(vector<int>& height) {
int res = 0, i = 0, j = height.size() - 1;
while (i != j) {
res = max(res, (j - i) * min(height[i], height[j]));
if (height[i] > height[j]) {
j--;
} else {
i++;
}
}
return res;
}
12. Integer To Roman【medium】
解题思路：
这道题没有特别多技巧，直接按照转换规则进行转换即可，对每一位进行遍历，注意考虑4和9的特殊情况即可。
在查看Leetcode讨论区的时候还看到了一种脑洞大开的“全部映射法”，这里贴上来给大家欣赏一下，也开拓了一下思路，这种方法告诉我们在情况不多的时候，可以考虑一下这种思路，代码更为简洁。
实现代码：
// 12. Integer to Roman
string intToRoman(int num) {
map<int, char> romanMap;
romanMap[1] = 'I';
romanMap[5] = 'V';
romanMap[10] = 'X';
romanMap[50] = 'L';
romanMap[100] = 'C';
romanMap[500] = 'D';
romanMap[1000] = 'M';
string res;
for (int i = 3; i >= 0; i--) {
int fold = pow(10, i);
if (num / fold == 9) {
res += romanMap[fold];
res += romanMap[fold * 10];
} else if (num / fold == 4) {
res += romanMap[fold];
res += romanMap[fold * 5];
} else if (num / fold > 0) {
if (num / fold >= 5) {
res += romanMap[fold * 5];
num -= 5 * fold;
}
for (int i = 0; i < num / fold; i++) {
res += romanMap[fold];
}
}
num %= fold;
}
return res;
}
// 脑洞大开的全部映射法
string intToRoman(int num) {
string M[] = {"", "M", "MM", "MMM"};
string C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
string X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
string I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
}
13. Roman To Integer【easy】
解题思路：
这道题和上一题一样，直接按照转换规则进行转换即可，对每一位进行遍历，注意考虑4和9的特殊情况即可。
实现代码：
// 13. Roman To Integer
int romanToInt (string s) {
int res = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == 'I') {
res += 1;
} else if (s[i] == 'V') {
res += 5;
if (i - 1 >= 0 && s[i - 1] == 'I') {
res -= 2;
}
} else if (s[i] == 'X') {
res += 10;
if (i - 1 >= 0 && s[i - 1] == 'I') {
res -= 2;
}
} else if (s[i] == 'L') {
res += 50;
if (i - 1 >= 0 && s[i - 1] == 'X') {
res -= 20;
}
} else if (s[i] == 'C') {
res += 100;
if (i - 1 >= 0 && s[i - 1] == 'X') {
res -= 20;
}
} else if (s[i] == 'D') {
res += 500;
if (i - 1 >= 0 && s[i - 1] == 'C') {
res -= 200;
}
} else if (s[i] == 'M') {
res += 1000;
if (i - 1 >= 0 && s[i - 1] == 'C') {
res -= 200;
}
}
}
return res;
}
14. Longest Common Prefix【easy】
解题思路：
这道题从头到尾每一个字符遍历，如果出现不同或者已经不够长，则把已知的共同前缀返回即可。
考虑边界条件：
当输入字符串数组为空时，返回空字符串""。
实现代码：
// 14. Longest Common Prefix
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0) return "";
int length = 0;
while (true) {
if (strs[0].size() < length + 1) break;
for (int i = 0; i < strs.size() - 1; i++)
if (strs[i + 1].size() < length + 1 || strs[i][length] != strs[i + 1][length])
return strs[0].substr(0, length);
length++;
}
return strs[0].substr(0, length);
}
15. 3Sum【medium】
解题思路：
双指针法枚举，复杂度O(N^2)。
首先，对数组进行排序。然后，从第一个数字 i 开始遍历，每一层遍历中有两个指针 p, q 分别指向该数字后续的数组中的头尾两端，通过判断这三个数组的和与0的关系，移动头尾指针：
如果和大于0，尾指针前移；如果和小于0，头指针后移；如果和等于0，分别移动头尾指针。
这里注意要考虑到数组中处理出现重复数字的情况。
如果 i 与 i - 1重复则直接跳过该项的遍历，如果 p 重复则 p++，如果 q 重复则 q++。
考虑边界条件：
当输入数组长度不足3时，返回空字符串数组。
实现代码：
// 15. 3Sum
vector<vector<int> > threeSum(vector<int>& nums) {
vector<vector<int> > res;
if (nums.size() < 3) return res;
sort(nums.begin(), nums.end());
int p, q, sum;
for (int i = 0; i < nums.size() - 2; i++) {
if (nums[i] > 0)
break;
else if (i > 0 && nums[i] == nums[i - 1])
continue;
p = i + 1;
q = nums.size() - 1;
while (p < q) {
sum = nums[i] + nums[p] + nums[q];
if (sum == 0) {
res.push_back({nums[i], nums[p], nums[q]});
while (nums[p] == nums[p + 1] && p < q)
p++;
p++;
while (nums[q] == nums[q - 1] && p < q)
q--;
q--;
} else if (sum > 0) {
while (nums[q] == nums[q - 1] && p < q)
q--;
q--;
} else {
while (nums[p] == nums[p + 1] && p < q)
p++;
p++;
}
}
}
return res;
}
16. 3Sum Closest
解题思路：
与15题如出一辙，采用双指针法枚举，复杂度O(N^2)。
首先，对数组进行排序。然后，从第一个数字 i 开始遍历，每一层遍历中有两个指针 p, q 分别指向该数字后续的数组中的头尾两端，通过判断这三个数组的和与0的关系，移动头尾指针：
如果和大于0，返回target；如果和小于0，头指针后移；如果和等于0，分别移动头尾指针。
这里注意要考虑到数组中处理出现重复数字的情况。
如果 i 与 i - 1重复则直接跳过该项的遍历，如果 p 重复则 p++，如果 q 重复则 q++。
实现代码：
// 16. 3Sum Closest
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int p, q, sum;
int gap = INT_MAX;
int res;
for (int i = 0; i < nums.size() - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
p = i + 1;
q = nums.size() - 1;
while (p < q) {
sum = nums[i] + nums[p] + nums[q];
if (sum == target) {
return target;
} else if (sum > target) {
if (sum - target < gap) {
gap = sum - target;
res = sum;
}
while (nums[q] == nums[q - 1] && p < q)
q--;
q--;
} else {
if (target - sum < gap) {
gap = target - sum;
res = sum;
}
while (nums[p] == nums[p + 1] && p < q)
p++;
p++;
}
}
}
return res;
}
17. Letter Combinations of a Phone Numbe
解题思路：
经典的排列问题，直接用回溯法解决。
下面的解法是使用循环实现非递归的回溯法。linshi作为中间变量，每一个数字按下之后的结果。
实现代码：
// 17. Letter Combinations of a Phone Number
vector<string> letterCombinations(string digits) {
if (digits.size() == 0) return {};
map<int, string> digitalMap;
digitalMap[2] = "abc";
digitalMap[3] = "def";
digitalMap[4] = "ghi";
digitalMap[5] = "jkl";
digitalMap[6] = "mno";
digitalMap[7] = "pqrs";
digitalMap[8] = "tuv";
digitalMap[9] = "wxyz";
vector<string> linshi;
vector<string> res = {""};
for (int i = 0; i < digits.size(); i++) {
string tails = digitalMap[digits[i] - 48];
for (int j = 0; j < res.size(); j++) {
for (int n = 0; n < tails.size(); n++) {
linshi.push_back(res[j] + tails[n]);
}
}
res = linshi;
linshi = {};
}
return res;
}
18. 4Sum
解题思路：
和15题3Sum如出一辙，在3Sum的解法外面再套一层即可。
实现代码：
// 18. 4Sum
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int> > res;
if (nums.size() < 4) return res;
sort(nums.begin(), nums.end());
int p, q, sum;
for (int j = 0; j < nums.size() - 3; j++) {
if (j > 0 && nums[j] == nums[j - 1])
continue;
int target3 = target - nums[j];
for (int i = j + 1; i < nums.size() - 2; i++) {
if (i > j + 1 && nums[i] == nums[i - 1])
continue;
p = i + 1;
q = nums.size() - 1;
while (p < q) {
sum = nums[i] + nums[p] + nums[q];
if (sum == target3) {
res.push_back({nums[j], nums[i], nums[p], nums[q]});
while (nums[p] == nums[p + 1] && p < q)
p++;
p++;
while (nums[q] == nums[q - 1] && p < q)
q--;
q--;
} else if (sum > target3) {
while (nums[q] == nums[q - 1] && p < q)
q--;
q--;
} else {
while (nums[p] == nums[p + 1] && p < q)
p++;
p++;
}
}
}
}
return res;
}
19. Remove Nth Node From End of List
解题思路：
快慢指针思想，让两个指针 p, q都指向头结点，p 先向后移动 n + 1 步，然后p, q一起向后移动，当 p 到达尾结点时，q指向目标节点的前驱结点，做删除操作，然后按照题目要求返回头结点即可。
实现代码：
// 20. Valid Parentheses
bool isValid(string s) {
stack<char> brackets;
map<char, char> bracketMap;
bracketMap[')'] = '(';
bracketMap[']'] = '[';
bracketMap['}'] = '{';
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
brackets.push(s[i]);
} else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
if (!brackets.empty() && brackets.top() == bracketMap[s[i]]) {
brackets.pop();
} else {
return false;
}
}
}
if (brackets.empty()) return true;
else return false;
}
20. Valid Parentheses
解题思路：
栈思想，从左往右遍历，如果是左括号则入栈，右括号则出栈，最后判断栈是否为空，空则为有效括号组，否则无效。
实现代码：
// 20. Valid Parentheses
bool isValid(string s) {
stack<char> brackets;
map<char, char> bracketMap;
bracketMap[')'] = '(';
bracketMap[']'] = '[';
bracketMap['}'] = '{';
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
brackets.push(s[i]);
} else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
if (!brackets.empty() && brackets.top() == bracketMap[s[i]]) {
brackets.pop();
} else {
return false;
}
}
}
if (brackets.empty()) return true;
else return false;
}
网友评论