【C++】【LeetCode】2020.5.8~2020.5.15
15. 3Sum
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example :
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
class Solution {
public:
/*-4 -1 -1 0 1 2*/
/*问题主要在跳过重复元素*/
void SkipI(vector<int>& nums, int& i)
{
while (i + 1 < nums.size() && nums[i+1] == nums[i])
{
i++;
}
i++;
}
void SkipL(vector<int>& nums, int& l, const int& r)
{
while (l + 1 < r && nums[l] == nums[l+1])
{
l++;
}
l++;
}
void SkipR(vector<int>& nums, const int& l, int& r)
{
while (r - 1 > l && nums[r] == nums[r-1])
{
r--;
}
r--;
}
vector<vector<int>> threeSum(vector<int>& nums) {
if (nums.size() < 3)
{
return {};
}
sort(nums.begin(), nums.end());
vector<vector<int>> Result;
for (int i = 0; i < nums.size();)
{
int l = i + 1;
int r = nums.size() - 1;
while (l < r)
{
int res = nums[i] + nums[l] + nums[r];
if (res < 0)
{
SkipL(nums, l, r);
}
else if (res > 0)
{
SkipR(nums, l, r);
}
else
{
Result.push_back({nums[i], nums[l], nums[r]});
SkipL(nums, l, r);
SkipR(nums, l, r);
}
}
SkipI(nums, i);
}
return Result;
}
};
16. 3Sum Closest
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example :
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
if (nums.size() < 3)
{
return 0;
}
sort(nums.begin(), nums.end());
int bais = 99999;
int res = 1;
for (int i = 0; i < nums.size() - 2; ++i)
{
int a = i + 1;
int b = nums.size() - 1;
while (a < b)
{
int tmp = nums[a] + nums[b] + nums[i];
if (tmp == target)
{
return target;
}
else if (tmp < target)
{
a++;
}
else
{
b--;
}
int tmpBais = tmp - target < 0 ? target - tmp : tmp - target;
if (tmpBais <= bais)
{
bais = tmpBais;
res = tmp;
}
}
}
return res;
}
};
17. Letter Combinations of a Phone Number
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example :
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> res;
vector<string> Demo = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
for (int i = 0; i < digits.size(); ++i)
{
int val = digits[i] - '0';
if (val > 9 || val < 2)
{
continue;
}
static vector<string> tmp;
tmp.clear();
for (int j = 0 ; j < Demo[val - 2].size(); ++j)
{
//res中字符串取出给末位加上新的字符
for (int k = 0; k < res.size(); ++k)
{
string s = res[k];
string x(1, Demo[val-2][j]);
tmp.push_back(s + x);
}
//第一轮推一次
if (tmp.size() == 0)
{
for (int l = 0 ; l < Demo[val - 2].size(); ++l)
{
string x(1, Demo[val-2][l]);
tmp.push_back(x);
}
}
}
res.clear();
res.assign(tmp.begin(), tmp.end());
}
return res;
}
};
18. 4Sum
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
The solution set must not contain duplicate quadruplets.
Example :
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
class Solution {
public:
/*-4 -1 -1 0 1 2*/
const int NUM = 4;
void SkipL(vector<int>& nums, int& l, const int& r)
{
while (l + 1 < r && nums[l] == nums[l+1])
{
l++;
}
l++;
}
void SkipR(vector<int>& nums, const int& l, int& r)
{
while (r - 1 > l && nums[r] == nums[r-1])
{
r--;
}
r--;
}
vector<vector<int>> fourSum(vector<int>& nums, int target) {
if (nums.size() < NUM)
{
return {};
}
sort(nums.begin(), nums.end());
vector<vector<int>> Result;
for (int i = 0; i <= nums.size() - NUM;)
{
for (int j = i + 1; j <= nums.size() - NUM + 1;)
{
int l = j + 1;
int r = nums.size() - 1;
while (l < r)
{
int res = nums[i] + nums[j] + nums[l] + nums[r];
if (res < target)
{
SkipL(nums, l, r);
}
else if (res > target)
{
SkipR(nums, l, r);
}
else
{
Result.push_back({nums[i], nums[j], nums[l], nums[r]});
SkipL(nums, l, r);
SkipR(nums, l, r);
}
}
SkipL(nums, j, nums.size() - NUM + 2);
}
SkipL(nums, i, nums.size() - NUM + 1);
}
return Result;
}
};
19. Remove Nth Node From End of List
Given a linked list, remove the n-th node from the end of list and return its head.
Example :
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Follow up:
Could you do this in one pass?
/**
* 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* pre = head;
ListNode* MoveNode = head;
int count = 0;
while (MoveNode)
{
MoveNode = MoveNode->next;
//达到距离后pre移动
if (count >= n && MoveNode)
{
pre = pre->next;
}
count++;
}
//删除的是第一个
if (count == n && head)
{
return head->next;
}
//删除对应位置
if (pre && pre->next)
{
pre->next = pre->next->next;
}
return head;
}
};
20. Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
class Solution {
public:
bool isValid(string s) {
stack<char> SymStack;
for (size_t i = 0; i < s.size(); ++i)
{
if (s[i] == '(' || s[i] == '[' || s[i] == '{')
{
SymStack.push(s[i]);
}
else
{
if (!SymStack.empty() &&
( (s[i] == ')' && SymStack.top() == '(')
|| (s[i] == ']' && SymStack.top() == '[')
|| (s[i] == '}' && SymStack.top() == '{')))
{
SymStack.pop();
}
else
{
return false;
}
}
}
return SymStack.empty();
}
};
《【C++】【LeetCode】2020.5.8~2020.5.15》有1条留言