LeetCode 11. 盛最多水的容器
题目链接
思路
双指针问题 比较简单
AC代码1
class Solution {
public:
int maxArea(vector<int>& height) {
// 双指针
int res = 0;
for (int i = 0, j = height.size() - 1; i < j;)
{
// 短板效应
res = max(res, min(height[i], height[j]) * (j - i));
// 如果左边高度比右边高的话 移动右边 反之亦然
if(height[i] > height[j]) j --;
else i ++;
}
return res;
}
};
LeetCode 12. 整数转罗马数字
题目链接
思路
y总总结的规律， 权值表
| M | CM | D | CD | C | XC | L | XL | X | IX | V | IV | I |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1000 | 900 | 500 | 400 | 100 | 90 | 50 | 40 | 10 | 9 | 5 | 4 | 1 |
AC代码1
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;
}
};
LeetCode 13. 罗马数字转整数
题目链接
思路
这题是上一道题的反转，难度比上一题低一点，找好规律只需要注意点，只要该字符比下一个字符权值小，则减去该字符对应的权值即可，该题也是直接一遍就AC
AC代码1
class Solution {
public:
int romanToInt(string s) {
int res = 0;
unordered_map<char, int> hash;
hash['M'] = 1000;
hash['D'] = 500; hash['C'] = 100;
hash['L'] = 50; hash['X'] = 10;
hash['V'] = 5; hash['I'] = 1;
for (int i = 0; i < s.size(); i ++)
{
if (i + 1 < s.size() && hash[s[i]] < hash[s[i + 1]])
{
res -= hash[s[i]];
}
else
{
res += hash[s[i]];
}
}
return res;
}
};
LeetCode 14. 最长公共前缀
题目链接
思路
枚举每个字符串 对比每个字符即可
AC代码1
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;
}
};
LeetCode 15. 三数之和
题目链接
思路
排序 + 双指针
- 先对数组排序
- 对于有序数组nums 固定好i, j = i + 1 ,k = nums.size()对(j , k)双指针查找
- 此时只有当nums[i] + nums[j] + nums [k - 1] >= 0 才能往左边移动k，直到j == k为止
- 后面继续移动i，j设置为 i + 1
AC代码1
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;
//不符合情况的时候向左移动k
//该序列有序 k左移三个数总和会变小 所以只需判断当前三个数之和是否是大于0即可
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;
}
};
LeetCode 16. 最接近的三数之和
题目链接
思路
跟上一题类似 注意一下target左边小和右边大的这两个总和即可
AC代码1
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];
// 找到总和最接近target
res = min(res, make_pair(abs(s - target), s));
// 前面考虑了在target右边的情况 下面考虑在target左边的情况
if (j < k - 1)
{
int s = nums[i] + nums[j] + nums[k - 1];
res = min(res, make_pair(abs(s - target), s));
}
}
}
return res.second;
}
};
LeetCode 17. 电话号码的字母组合
题目链接
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
思路
参考以下题解
https://www.acwing.com/solution/content/15003/
AC代码1
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 == "")
return ans;
dfs(digits, 0, "");
return ans;
}
};
LeetCode 18. 四数之和
题目链接
思路
跟15题三数之和差不多，看前面的LeetCode 15的题解就好了，固定好i j，后面用双指针
AC代码1
class Solution {
public:
typedef long long LL;
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
int n = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < n; i ++)
{
if (i && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n; j ++)
{
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
for (int l = j + 1, r = n - 1; l < r; l ++)
{
if (l > j + 1 && nums[l] == nums[l - 1]) continue;
while(l < r - 1 && (LL)nums[i] + nums[j] + nums[l] + nums[r - 1] >= target) r --;
if ((LL)nums[i] + nums[j] + nums[l] + nums[r] == target)
{
res.push_back({nums[i], nums[j], nums[l], nums[r]});
}
}
}
}
return res;
}
};
LeetCode 19. 删除链表的倒数第N个节点
题目链接
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
思路
注意加个头结点防止只有一个元素，而要删除该元素
方法一：数学方法
- p指向头结点
- 让p走k - n - 1步即可到达删除结点的前驱，其中k为链表长度
方法二：双指针（时间更快）
- 都指向头结点
- q走n + 1步
- p q同时走 当q到达尾部NULL时候，p指向倒数第n个数的前驱
AC代码1
方法一：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy_head = new ListNode(-1);
dummy_head->next = head;
int k = 0;
auto p = dummy_head;
while(p->next)
{
k ++;
p = p->next;
}
auto q = dummy_head;
for (int i = 0; i < k - n; i ++) q = q->next;
q->next = q->next->next;
return dummy_head->next;
}
};
AC代码2
方法二：时间更快
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy_head = new ListNode(-1);
dummy_head->next = head;
ListNode* p = dummy_head;
ListNode* q = dummy_head;
// 先让q走n + 1步 因为前面有虚拟结点
for (int i = 0; i < n + 1; i ++) q = q->next;
while (q)
{
p = p->next;
q = q->next;
}
p->next = p->next->next;
return dummy_head->next;
}
};
LeetCode 20. 有效的括号
题目链接
思路
方法一：
- 使用栈存储，遇到( { [ 压入栈
- 遇到) } ] 查看栈顶是否匹配
- 结束查看栈是否为空
方法二：
- 使用ascii值
AC代码1
// 方法一：
class Solution {
public:
bool isValid(string s) {
stack<int> 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() != '(') return false;
stk.pop();
}
else if (s[i] == '}')
{
if(stk.empty() || stk.top() != '{') return false;
stk.pop();
}
else if (s[i] == ']')
{
if(stk.empty() || stk.top() != '[') return false;
stk.pop();
}
}
return stk.empty();
}
};
AC代码2
// 方法二：
class Solution {
public:
bool isValid(string s) {
stack<int> stk;
for (auto c : s)
{
if (c == '(' || c == '{' || c == '[')
{
stk.push(c);
}
else
{
if (!stk.empty() && abs(stk.top() - c) <= 2) stk.pop();
else return false;
}
}
return stk.empty();
}
};
