leetcode 11-20
11.盛最多水的容器
解题思路
单调栈+二分
首先可以想到一个贪心的思路：对于每个候选的右边界j，它应该匹配的左边界i是最靠左的且满足h[i]>=h[j]的那个位置(当然还有另外一种情况，左侧边界i充当最小值，这个只要把数组反一下再做一次上面的算法，更新答案就好了。)。
两种情况：固定左端点，找右端点的最大值；固定右端点，找左端点的最大值，最后取max
代码
const int N = 3e4 + 10;
class Solution {
public:
int maxArea(vector<int>& height) {
memset(q, -1, sizeof q);
int res = -1, len = 0;
for(int i = 0; i < height.size(); ++i){
if(!len || height[i] > q[len - 1].first){
if(len) res = max(res, min(height[i], q[len - 1].first) * (i - q[len - 1].second));
q[len++] = {height[i], i};
}else{
int ll = 0, rr = len - 1;
while(ll < rr){
int mid = ll + rr >> 1;
if(q[mid].first >= height[i]) rr = mid;
else ll = mid + 1;
}
res = max(res, min(height[i], q[rr].first) * (i - q[rr].second));
}
}
memset(q, -1, sizeof q);
len = 0;
for(int i = height.size() - 1; i >= 0; --i){
if(!len || height[i] > q[len - 1].first){
if(len) res = max(res, min(height[i], q[len - 1].first) * (i - q[len - 1].second));
q[len ++] = {height[i], i};
}else{
int ll = 0, rr = len - 1;
while(ll < rr){
int mid = ll + rr >> 1;
if(q[mid].first >= height[i]) rr = mid;
else ll = mid + 1;
}
res = max(res, min(height[i], q[rr].first) * (q[rr].second - i));
}
}
return res;
}
private:
pair<int, int> q[N];
};
12.整数翻转罗马数字
解题思路
查表法，当前值无非就是表中这几种情况的组合，比如 600 = 500 + 100，查表可算出
代码
class Solution {
public:
string intToRoman(int num) {
int values[] = {
1000,
900, 500, 400, 100,
90, 50, 40, 10,
9, 5, 4, 1
};
string reps[] = {
"M",
"CM", "D", "CD", "C",
"XC", "L", "XL", "X",
"IX", "V", "IV", "I"
};
string res;
for(int i = 0; i < 13; ++i){
while(num >= values[i]){
num -= values[i];
res += reps[i];
}
}
return res;
}
};
13.罗马数字转整数
解题思路
除了4和9，其他的都可以通过查表然后加上对应的值，
对于4和9，我们只需要特判一下，如果下一个值大于当前的值，那么结果减去当前的值，例子："LXIV" = 64中，L X V我们都需要加，I我们需要减
代码
class Solution {
public:
int romanToInt(string s) {
unordered_map<char, int> umap;
umap['I'] = 1, umap['V'] = 5;
umap['X'] = 10, umap['L'] = 50;
umap['C'] = 100, umap['D'] = 500;
umap['M'] = 1000;
int res = 0;
for(int i = 0; i < s.size(); ++i){
if(i + 1 < s.size() && umap[s[i + 1]] > umap[s[i]]){
res -= umap[s[i]];
}else res += umap[s[i]];
}
return res;
}
};
14.最长公共前缀
解题思路
对比对各对应位置的字符是否相等，全相等时则进入下一个字符匹配
代码
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string res;
if(strs.empty()) return res;
for(int i = 0;; i++){
if(i >= strs[0].size()) return res;
char c = strs[0][i];
for(auto& str : strs){
if(i >= str.size() || str[i] != c) return res;
}
res += c;
}
return res;
}
};
15.三数之和
解题思路
三个指针：枚举最小的指针i，对于每一个i，用双指针j,k算出剩余两数之和
复杂度：O(n^2)
代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); ++i){
if(i && nums[i] == nums[i - 1]) continue;
for(int j = i + 1, k = nums.size() - 1;j < k; ++j){
if(j != i + 1 && nums[j] == nums[j - 1]) continue;
while(j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) --k;
if(nums[i] + nums[j] + nums[k] == 0)
res.push_back({nums[i], nums[j], nums[k]});
}
}
return res;
}
};
16.最接近的三数之和
解题思路
和15题相同，用pair存最小差值和对应的和。
代码
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
pair<int, int> res(INT_MAX, INT_MAX);
for(int i = 0; i < nums.size(); ++i){
for(int j = i + 1, k = nums.size() - 1; j < k; ++j){
while(j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= target) --k;
int s = nums[i] + nums[j] + nums[k];
res = min(res, make_pair(abs(s - target), s));
if(j < k - 1){
s = nums[i] + nums[j] + nums[k - 1];
res = min(res, make_pair(target - s, s));
}
}
}
return res.second;
}
};
17.电话号码的字母组合
解题思路
经典递归
代码
class Solution {
public:
vector<string> ans;
string strs[10] = {
"", "", "abc", "def",
"ghi", "jkl", "mno",
"pqrs", "tuv", "wxyz"
};
void dfs(string& digits, int u, string path){
if(u == digits.size()) ans.push_back(path);
else{
for(auto c : strs[digits[u] - '0'])
dfs(digits, u + 1, path + c);
}
}
vector<string> letterCombinations(string digits) {
if(digits.empty()) return ans;
dfs(digits, 0, "");
return ans;
}
};
18.四数之和
解题思路
参考15.三数之和，固定两个数，剩余两个数采用双指针算法。
代码
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); ++i){
if(i && nums[i] == nums[i - 1]) continue;
for(int j = i + 1; j < nums.size(); ++j){
if(j > i + 1 && nums[j] == nums[j - 1]) continue;
for(int k = j + 1, l = nums.size() - 1; k < l; ++k){
if(k > j + 1 && nums[k] == nums[k - 1]) continue;
while(k < l - 1 && nums[k] + nums[l - 1] >= target - nums[i] - nums[j]){
--l;
}
if(nums[k] + nums[l] == target - nums[i] - nums[j] )
res.push_back({nums[i], nums[j], nums[k], nums[l]});
}
}
}
return res;
}
};
19.删除链表的倒数第N个节点
解题思路
对于链表，如果可能改变头指针，那么就申请一个虚拟节点；
使用双指针，快指针先从dummy节点走n步，然后slow指针和fast指针同时走，直到fast->next==nullptr，此时，slow->next指向的即为需要删除的节点
代码
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
auto dummy = new ListNode(-1, head);
auto fast = dummy;
while(n > 0 && fast->next){
fast = fast->next;
n--;
}
auto slow = dummy;
while(fast->next){
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return dummy->next;
}
};
20.有效的括号
解题思路
维持一个栈，遇到(、[、{则入栈，其余时刻判断栈是否为空且栈顶元素是否配对；
遍历结束后判断栈是否为空，不为空，则说明有多余的括号未匹配
代码
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
for(int i = 0; i < s.size(); ++i){
if(s[i] == '(' || s[i] == '[' || s[i] == '{') stk.push(s[i]);
else if(s[i] == ')'){
if(!stk.empty() && stk.top() == '(') stk.pop();
else return false;
}else if(s[i] == ']'){
if(!stk.empty() && stk.top() == '[') stk.pop();
else return false;
}else{
if(!stk.empty() && stk.top() == '{') stk.pop();
else return false;
}
}
if(stk.size()) return false;
return true;
}
};
|