1~3 개월의 준비 기간을 가지고 풀기에 좋은 문제들을 가지고 있는 특징이 있다.
이번 내용은 Two Pointers + Sliding Window 주제다.
Move Zeroes
link: https://leetcode.com/problems/move-zeroes/submissions/
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int start = 0, end = 0;
while(end < nums.size()){
if(nums[end] != 0){
swap(nums[start++], nums[end]);
}
end++;
}
for(int i = start; i < nums.size(); i++){
nums[i] = 0;
}
}
};Is Subsequence
link: https://leetcode.com/problems/is-subsequence/description/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
bool isSubsequence(string s, string t) {
if(s.empty() && t.empty()) return true;
int start = 0, end = 0;
while(end < t.length()){
if(t[end] == s[start]){
start++;
}
if(start >= s.length()) return true;
end++;
}
return false;
}
};Container With Most Water
link: https://leetcode.com/problems/container-with-most-water/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
int maxArea(vector<int>& height) {
int start = 0, end = height.size()-1;
int answer = INT_MIN;
while(start < end){
int x = end - start;
int y = min(height[start], height[end]);
int curr_area = x * y;
answer = max(answer, curr_area);
if(height[start] < height[end]){
start++;
} else if(height[start] > height[end]){
end--;
} else{
start++;
end--;
}
}
return answer;
}
};Max Number of K-Sum Pairs
link: https://leetcode.com/problems/max-number-of-k-sum-pairs/description/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
map<int,int> hashMap;
int answer = 0;
for(int n : nums){
if(hashMap.count(k - n)){
answer++;
if(--hashMap[k-n] <= 0) hashMap.erase(k - n);
} else{
hashMap[n]++;
}
}
return answer;
}
};#개선 된 코드
class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int start = 0, end = nums.size()-1;
int count = 0;
while(start < end){
int sum = nums[start] + nums[end];
if(sum == k){
start++;
end--;
count++;
} else if(sum > k){
end--;
} else{
start++;
}
}
return count;
}
};Maximum Average Subarray I
link: https://leetcode.com/problems/maximum-average-subarray-i/description/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
double answer = INT_MIN;
int start = 0, end = 0;
double curr_sum = 0;
while(end < nums.size()){
curr_sum += nums[end];
if((end - start) + 1 == k){
answer = max(answer, curr_sum / k);
curr_sum -= (nums[start]);
start++;
}
end++;
}
return answer;
}
};Maximum Number of Vowels in a Substring of Given Length
link: https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
int maxVowels(string s, int k) {
map<char,int> hashMap = {{'a',1}, {'e',1}, {'i',1}, {'o',1}, {'u',1}};
int answer = INT_MIN, curr_max = 0;
int start = 0, end = 0;
while(end < s.length()){
curr_max += hashMap.count(s[end]) ? 1 : 0;
if((end - start) + 1 >= k){
answer = max(answer, curr_max);
curr_max -= hashMap.count(s[start]) ? 1 : 0;
start++;
}
end++;
}
return answer;
}
};Max Consecutive Ones III
link: https://leetcode.com/problems/max-consecutive-ones-iii/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int answer = INT_MIN, curr_max = 0;
int start = 0, end = 0;
while(end < nums.size()){
if(nums[end] == 0 && k <= 0){
//move
while(start < nums.size() && k <= 0){
k += nums[start] == 0 ? 1 : 0;
start++;
}
}
k -= nums[end] == 0 ? 1 : 0;
curr_max = (end - start) + 1;
answer = max(answer, curr_max);
end++;
}
return answer;
}
};Longest Subarray of 1's After Deleting One Element
link: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/?envType=study-plan-v2&envId=leetcode-75
class Solution {
public:
int longestSubarray(vector<int>& nums) {
int can_delete = 0;
int start = 0, end = 0;
int answer = 0;
while(end < nums.size()){
if(can_delete >= 1 && nums[end] == 0){
while(start < nums.size() && can_delete >= 1){
can_delete -= nums[start] == 0 ? 1 : 0;
start++;
}
}
can_delete += nums[end] == 0 ? 1 : 0;
answer = max(answer, (end - start));
end++;
}
return answer;
}
};복습할 문제
- Max Number of K-Sum Pairs : 분명히 생각은 했었는데 확신이 없어서 처음에 비효율 적으로 풀었다. 다시 한번 풀어보고 자신감을 얻어보자.
