# Leetcode daily challenge & weekly contest
# 229. Majority Element II
## Question (Medium)
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Example 1:
Input: nums = [3,2,3]
Output: [3]
Example 2:
Input: nums = [1]
Output: [1]
Example 3:
Input: nums = [1,2]
Output: [1,2]
Constraints:
1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109
Follow up: Could you solve the problem in linear time and in O(1) space?
## Solution (C++)
```c=
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> ans;
int threshold = nums.size() / 3;
int count = 1;
sort(nums.begin(), nums.end());
if(nums.size()==1)
return nums;
for(int i=1; i<nums.size(); i++){
cout<<nums[i]<<" "<<nums[i-1]<<endl;
if(nums[i]==nums[i-1]){
count++;
}
if(nums[i]!=nums[i-1]){
if(count>threshold){
ans.push_back(nums[i-1]);
}
count=1;
}
if(i==nums.size()-1){
if(count>threshold){
ans.push_back(nums[i]);
}
count=1;
}
}
return ans;
}
};
```
## Notes:
* 這題可以用map來記錄每個元素出現的次數，但空間複雜度就不是O(1)
* 我先使用sort，再判斷每個元素出現的頻率，就能達到O(1)的空間複雜度，但時間複雜度就是O(NlogN)，不算是最佳解。
---
# 2038. Remove Colored Pieces if Both Neighbors are the Same Color
## Question (Medium)
There are n pieces arranged in a line, and each piece is colored either by 'A' or by 'B'. You are given a string colors of length n where colors[i] is the color of the ith piece.
Alice and Bob are playing a game where they take alternating turns removing pieces from the line. In this game, Alice moves first.
Alice is only allowed to remove a piece colored 'A' if both its neighbors are also colored 'A'. She is not allowed to remove pieces that are colored 'B'.
Bob is only allowed to remove a piece colored 'B' if both its neighbors are also colored 'B'. He is not allowed to remove pieces that are colored 'A'.
Alice and Bob cannot remove pieces from the edge of the line.
If a player cannot make a move on their turn, that player loses and the other player wins.
Assuming Alice and Bob play optimally, return true if Alice wins, or return false if Bob wins.
Example 1:
Input: colors = "AAABABB"
Output: true
Explanation:
AAABABB -> AABABB
Alice moves first.
She removes the second 'A' from the left since that is the only 'A' whose neighbors are both 'A'.
Now it's Bob's turn.
Bob cannot make a move on his turn since there are no 'B's whose neighbors are both 'B'.
Thus, Alice wins, so return true.
Example 2:
Input: colors = "AA"
Output: false
Explanation:
Alice has her turn first.
There are only two 'A's and both are on the edge of the line, so she cannot move on her turn.
Thus, Bob wins, so return false.
Example 3:
Input: colors = "ABBBBBBBAAA"
Output: false
Explanation:
ABBBBBBBAAA -> ABBBBBBBAA
Alice moves first.
Her only option is to remove the second to last 'A' from the right.
ABBBBBBBAA -> ABBBBBBAA
Next is Bob's turn.
He has many options for which 'B' piece to remove. He can pick any.
On Alice's second turn, she has no more pieces that she can remove.
Thus, Bob wins, so return false.
## Solution (C++)
```c=
class Solution {
public:
bool winnerOfGame(string colors) {
int count_A = 0;
int count_B = 0;
if(colors.length()<2)
return false;
for(int i=0; i<colors.length()-2; i++){
if(colors[i] == 'A' && colors[i+1] == 'A' && colors[i+2] == 'A'){
count_A++;
}
if(colors[i] == 'B' && colors[i+1] == 'B' && colors[i+2] == 'B'){
count_B++;
}
}
if(count_A == count_B){
return false;
}
return (count_A > count_B)?true:false;
}
};
```
## Notes:
* 這題看似很麻煩，但其實不用去模擬整個遊戲的過程 O(N^2)
* 你只需要3個char一組，判斷這3個char是否全都為'A' or 'B'，若滿足則代表該玩家有一回合的機會。
* 所以只需要O(N)遍歷整個string即可，統計3個char為'A'和3個char為'B'的頻率即可。
* 頻率高的就表示win GAME。
---
# 2895. Minimum Processing Time
## Question
You have n processors each having 4 cores and n * 4 tasks that need to be executed such that each core should perform only one task.
Given a 0-indexed integer array processorTime representing the time at which each processor becomes available for the first time and a 0-indexed integer array tasks representing the time it takes to execute each task, return the minimum time when all of the tasks have been executed by the processors.
Note: Each core executes the task independently of the others.
Example 1:
Input: processorTime = [8,10], tasks = [2,2,3,1,8,7,4,5]
Output: 16
Explanation:
It's optimal to assign the tasks at indexes 4, 5, 6, 7 to the first processor which becomes available at time = 8, and the tasks at indexes 0, 1, 2, 3 to the second processor which becomes available at time = 10.
Time taken by the first processor to finish execution of all tasks = max(8 + 8, 8 + 7, 8 + 4, 8 + 5) = 16.
Time taken by the second processor to finish execution of all tasks = max(10 + 2, 10 + 2, 10 + 3, 10 + 1) = 13.
Hence, it can be shown that the minimum time taken to execute all the tasks is 16.
Example 2:
Input: processorTime = [10,20], tasks = [2,3,1,2,5,8,4,3]
Output: 23
Explanation:
It's optimal to assign the tasks at indexes 1, 4, 5, 6 to the first processor which becomes available at time = 10, and the tasks at indexes 0, 2, 3, 7 to the second processor which becomes available at time = 20.
Time taken by the first processor to finish execution of all tasks = max(10 + 3, 10 + 5, 10 + 8, 10 + 4) = 18.
Time taken by the second processor to finish execution of all tasks = max(20 + 2, 20 + 1, 20 + 2, 20 + 3) = 23.
Hence, it can be shown that the minimum time taken to execute all the tasks is 23.
## Solution (C++)
```c=
class Solution {
public:
int minProcessingTime(vector<int>& processorTime, vector<int>& tasks) {
sort(processorTime.begin(), processorTime.end());
sort(tasks.begin(), tasks.end(), greater<int>());
int maxima = INT_MIN;
for(int i=0; i<processorTime.size(); i++){
maxima = max(maxima, processorTime[i] + tasks[i*4]);
}
return maxima;
}
};
```
## Notes
* 第一次參加leetcode weekly contest，記錯時間直接錯過40分鐘QQ
* 一開始還以為是dp，被minimum這個詞給騙了。
---
# 2874. Maximum Value of an Ordered Triplet II
## Question (Medium)
You are given a 0-indexed integer array nums.
Return the maximum value over all triplets of indices (i, j, k) such that i < j < k. If all such triplets have a negative value, return 0.
The value of a triplet of indices (i, j, k) is equal to (nums[i] - nums[j]) * nums[k].
Example 1:
Input: nums = [12,6,1,2,7]
Output: 77
Explanation: The value of the triplet (0, 2, 4) is (nums[0] - nums[2]) * nums[4] = 77.
It can be shown that there are no ordered triplets of indices with a value greater than 77.
Example 2:
Input: nums = [1,10,3,4,19]
Output: 133
Explanation: The value of the triplet (1, 2, 4) is (nums[1] - nums[2]) * nums[4] = 133.
It can be shown that there are no ordered triplets of indices with a value greater than 133.
Example 3:
Input: nums = [1,2,3]
Output: 0
Explanation: The only ordered triplet of indices (0, 1, 2) has a negative value of (nums[0] - nums[1]) * nums[2] = -3. Hence, the answer would be 0.
Constraints:
3 <= nums.length <= 105
1 <= nums[i] <= 106
## Solution (C++)
```c=
class Solution {
public:
long long maximumTripletValue(vector<int>& nums) {
int* left_max = new int[nums.size()]{};
int* right_max = new int[nums.size()]{};
long long int maxima = 0;
for(int i=0; i<nums.size(); i++){
left_max[i] = maxima;
if(nums[i]>maxima){
maxima = nums[i];
}
}
maxima = 0;
for(int i = nums.size()-1; i>=0; i--){
right_max[i] = maxima;
if(nums[i]>maxima)
maxima = nums[i];
}
maxima = 0;
long long int ans = 0;
for(int i=1; i<nums.size()-1; i++){
ans = (long long int)(left_max[i] - nums[i]) * right_max[i];
if(ans>maxima)
maxima = ans;
}
return (maxima<0)?0:maxima;
}
};
```
## Notes:
1. 這題比較像邏輯題，你要得到最大的triplet (i, j, k)，其實i就等於j左邊的maxima的index, k則為j右邊maxima的index。
2. 我們可以先宣告兩個1-d array來**先計算**每個index的left_maxia和right maxima，請參考line 7~18。
3. 最後用一個for loop找出最大的數值即可。
---
# 2869. Minimum Operations to Collect Elements
## Question (Leetcode Biweekly Contest 114 Q1)
You are given an array nums of positive integers and an integer k.
In one operation, you can remove the last element of the array and add it to your collection.
Return the minimum number of operations needed to collect elements 1, 2, ..., k.
Example 1:
Input: nums = [3,1,5,4,2], k = 2
Output: 4
Explanation: After 4 operations, we collect elements 2, 4, 5, and 1, in this order. Our collection contains elements 1 and 2. Hence, the answer is 4.
Example 2:
Input: nums = [3,1,5,4,2], k = 5
Output: 5
Explanation: After 5 operations, we collect elements 2, 4, 5, 1, and 3, in this order. Our collection contains elements 1 through 5. Hence, the answer is 5.
Example 3:
Input: nums = [3,2,5,3,1], k = 3
Output: 4
Explanation: After 4 operations, we collect elements 1, 3, 5, and 2, in this order. Our collection contains elements 1 through 3. Hence, the answer is 4.
## Solution (C++)
```c=
class Solution {
public:
int minOperations(vector<int>& nums, int k) {
int* record = new int[nums.size()+1]{};
int count = 0;
int flag = 0;
while(nums.size()!=0){
flag = 1;
int value = nums.back();
nums.pop_back();
record[value]++;
count++;
for(int i=1; i<=k; i++){
if(record[i]==0){
flag = 0;
break;
}
}
if(flag==1){
break;
}
}
return count;
}
};
```
## Notes:
---
# 2870. Minimum Number of Operations to Make Array Empty
## Question (Leetcode Biweekly Contest 114 Q2)
You are given a 0-indexed array nums consisting of positive integers.
There are two types of operations that you can apply on the array any number of times:
Choose two elements with equal values and delete them from the array.
Choose three elements with equal values and delete them from the array.
Return the minimum number of operations required to make the array empty, or -1 if it is not possible.
Example 1:
Input: nums = [2,3,3,2,2,4,2,3,4]
Output: 4
Explanation: We can apply the following operations to make the array empty:
- Apply the first operation on the elements at indices 0 and 3. The resulting array is nums = [3,3,2,4,2,3,4].
- Apply the first operation on the elements at indices 2 and 4. The resulting array is nums = [3,3,4,3,4].
- Apply the second operation on the elements at indices 0, 1, and 3. The resulting array is nums = [4,4].
- Apply the first operation on the elements at indices 0 and 1. The resulting array is nums = [].
It can be shown that we cannot make the array empty in less than 4 operations.
Example 2:
Input: nums = [2,1,2,2,3,3]
Output: -1
Explanation: It is impossible to empty the array.
## Solution (C++)
```c=
class Solution {
public:
int minOperations(vector<int>& nums) {
map<int, int> record;
for(int i=0; i<nums.size(); i++)
record[nums[i]]++;
int steps = 0;
for(auto it = record.begin(); it!=record.end(); it++){
cout<<it->first<<" "<<it->second<<endl;
int val = it->second;
if(val==1)
return -1;
if(val%3==0){
steps+=(val/3);
}
else if(val%3==2){
steps = steps + (val/3) + 1;
}
else if(val%3==1){
steps = steps + (val/3)-1 + 2;
}
}
return steps;
}
};
```
## Notes:
* 這題就單純考你數學邏輯
---
# 455. Assign Cookies
## Question
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.
Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
Example 1:
Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:
Input: g = [1,2], s = [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.
Constraints:
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1
## Solution (C++)
```c=
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
if(s.size()==0)
return 0;
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int count = 0, s_idx=0;
for(int i=0; i<g.size();){
if(s[s_idx]>=g[i]){
count++;
s_idx++;
i++;
}
else{
s_idx++;
}
if(s_idx>=s.size()){
break;
}
}
return count;
}
};
```
## Notes:
1. 先做sorting
3. 用一個變數紀錄s_index。對每一個child來說，size若不滿足條件，s_index++，一直找到滿足條件為止。
---
# 1291. Sequential Digits
## Question
An integer has sequential digits if and only if each digit in the number is one more than the previous digit.
Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.
Example 1:
Input: low = 100, high = 300
Output: [123,234]
Example 2:
Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]
Constraints:
10 <= low <= high <= 10^9
## Solution (C++)
```c=
class Solution {
public:
vector<int> sequentialDigits(int low, int high) {
int low_length = to_string(low).length();
int high_length = to_string(high).length();
high_length = min(9, high_length);
vector<int> ans;
string temp = "123456789";
for(int i = low_length; i<=high_length; i++){
int start = 0, end = i-1;
string t = "";
if(start==0){
for(int j=start; j<=end; j++)
t = t + temp[j];
}
if((stoi(t)<=high&&stoi(t)>=low))
ans.push_back(stoi(t));
while(end<temp.length()-1){
end++;
t.erase(t.begin(), t.begin()+1);
t = t + temp[end];
if((stoi(t)<=high&&stoi(t)>=low))
ans.push_back(stoi(t));
}
}
return ans;
}
};
```
## Notes:
1. 先判斷字串的長度界線，再用sliding window舉出所有可能
2. 不用擔先時間，因為數字最大也才10^9 (但應該能優化更好)
---
## 100. Same Tree
```c=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==nullptr && q==nullptr)
return true;
if((p==nullptr&&q!=nullptr) || (p!=nullptr&&q==nullptr))
return false;
if(p->val!=q->val)
return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};
```
### Notes:
* 兩顆樹同時比較左子樹、右子樹(用recursive寫)
---
## 2966. Divide Array Into Arrays With Max Difference
```c=
class Solution {
public:
vector<vector<int>> divideArray(vector<int>& nums, int k) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for(int i=0; i<nums.size(); i+=3){
if((nums[i+2] - nums[i]) <=k){
ans.push_back({nums[i], nums[i+1], nums[i+2]});
}
else{
ans.clear();
break;
}
}
return ans;
}
};
```
### Notes:
1. Greedy，我們需要先sort nums
2. 因為題目的要求是任意2數相差<=k，所以我們3個為一組判斷即可。
3. 只要判斷nums[i+2] - nums[i]有沒有滿足條件即可，若滿足的話，nums[i+1]也必定會滿足。
---
## 513. Find Bottom Left Tree Value
```c=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int bfs(TreeNode* root){
int retv = 0, pre_rows=0;
queue<TreeNode*> q;
queue<int> rows;
q.push(root);
rows.push(1);
while(q.size()!=0){
TreeNode* temp = q.front();
if(rows.front() > pre_rows)
retv = temp->val;
if(temp->left!=NULL){
rows.push(rows.front()+1);
q.push(temp->left);
}
if(temp->right!=NULL){
rows.push(rows.front()+1);
q.push(temp->right);
}
pre_rows = rows.front();
q.pop();
rows.pop();
}
return retv;
}
int findBottomLeftValue(TreeNode* root) {
return bfs(root);
}
};
```
### Notes:
1. 這題其實就是找最後一個level的第一個TreeNode
2. 用BFS traversal，並同時記錄每個TreeNode的level
---
## 948. Bag of Tokens
```cpp=
class Solution {
public:
int bagOfTokensScore(vector<int>& tokens, int power) {
sort(tokens.begin(), tokens.end());
int up_index = 0, down_index = tokens.size() - 1;
int score = 0, max_score = 0;
while(up_index <= down_index){
if(power >= tokens[up_index]){
score++;
power-=tokens[up_index];
up_index++;
}
else if(score >= 1){
power+=tokens[down_index];
score--;
down_index--;
}
else{
break;
}
if(score > max_score)
max_score = score;
}
return max_score;
}
};
```
### Notes:
1. face-up的情況一定挑token[i]最小的(因為score一定都統一+1)
2. face-down的情況則是挑token[i]最大的(power加的最多)
3. tokens先排序，在用two-pointer就可以解了
---
## 442. Find All Duplicates in an Array
```cpp=
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> ans;
for(int i=0; i<nums.size(); i++){
int value = abs(nums[i]);
if(nums[value-1] > 0){
nums[value-1] = -1 * nums[value-1];
}
else{
ans.push_back(value);
}
}
return ans;
}
};
```
### Notes:
1. 這題的精髓在於follow-up的部分，如何使用O(1)的space complexity。
2. 若遇到n，則把arr[n-1]乘上-1，來表示已經visit過
，因為題目的constraint有說數值介於1~n，才可以使用這個方法
---
## 179. Largest Number
```cpp=
class Solution {
public:
static bool compare(pair<string, int> s1, pair<string, int> s2){
string a = s1.first + s2.first;
string b = s2.first + s1.first;
for(int i=0; i<a.length();){
if(a[i] > b[i]){
s1.second = 1; s2.second = 0;
break;
}
else if(a[i] < b[i]){
s1.second = 0; s2.second = 1;
break;
}
else{
i++;
}
}
return s1.second > s2.second;
}
string largestNumber(vector<int>& nums) {
vector<pair<string, int>> record;
string ans = "";
for(int n: nums){
record.push_back(make_pair(to_string(n), 0));
}
sort(record.begin(), record.end(), compare);
int flag = 0;
for(int i=0; i<record.size(); i++){
if(record[i].first!="0")
flag = 1;
ans = ans + record[i].first;
}
return (flag == 0)?"0":ans;
}
};
```
### Notes:
1. 考custom sort的用法
2. 其實就把兩個字串a、b，分別比較a+b b+a哪個比較大即可決定順序
Sign in with Wallet
Connect another wallet