Problems
LeetCode : 991. Broken Calculator
LeetCode : 1764. Form Array by Concatenating Subarrays of Another Array
[array][greedy]
LeetCode : 2086. Minimum Number of Buckets Required to Collect Rainwater from Houses
[Greedy][String][Dynamic Programming]
LeetCode : 1975. Maximum Matrix Sum
[Greedy][Array][Matrix]
LeetCode : 1054. Distant Barcodes
[Greedy][Array][Sorting][Heap ( Priority Queue )]
LeetCode : 2214. Minimum Health to Beat Game
[Greedy][Array]
LeetCode : 2007. Find Original Array From Doubled Array
[Greedy][Ordered Tree][Array][Hash Table]
LeetCode : 1253. Reconstruct a 2-Row Binary Matrix
[Greedy][Matrix]
LeetCode : 2422. Merge Operations to Turn Array Into a Palindrome
[Two Pointers][Greedy][Array]
LeetCode : 2383. Minimum Hours of Training to Win a Competition
[greedy]
LeetCode : 2498. Frog Jump II
[Greedy][Math][Medium]
LeetCode : 991. Broken Calculator
這題是三年前寫出來的，完全不知道為什麼以前的自己可以想出這種解法
題目給予的操作雖然是 startValue — 1 或是 startValue * 2，但這也可以視為 target + 1 或是 target * 2。
這樣反向思考可以更容易進行 greedy。
class Solution {
public:
int brokenCalc(int startValue, int target) {
int count = 0;
while(1) {
if(startValue >= target) {
return count + startValue - target;
}
count++;
if(target % 2 == 1) {
target++;
} else {
target /= 2;
}
}
return 0;
}
};LeetCode : 1764. Form Array by Concatenating Subarrays of Another Array
// TODO : 還能更快，印象中有算法可以避免比對失敗時，只能前進一步的情況
class Solution {
public:
bool canChoose(vector<vector<int>>& groups, vector<int>& nums) {
int nowg = 0;
int nowi = 0;
for(int i = 0;i < nums.size();i++) {
if(nums[i] == groups[nowg][nowi]) {
nowi++;
} else {
// printf("hi\n");
i -= nowi;
nowi = 0;
}
if(nowi == groups[nowg].size()) {
nowg++;
nowi = 0;
}
if(nowg == groups.size()) {
return true;
}
}
return false;
}
};LeetCode : 2086. Minimum Number of Buckets Required to Collect Rainwater from Houses
// TODO : 試試看 dynamic programming 的解法
class Solution {
public:
int minimumBuckets(string street) {
vector<int> tmp = vector<int>(street.size(), 0);
int ans = 0;
// first pass
// 假如 H 旁邊沒辦法有 '.' ， 就直接 return -1
for(int i = 0;i < street.size();i++) {
if('H' == street[i]) {
bool f = false;
if((i > 0 && '.' == street[i - 1]) ||
(i < street.size() && '.' == street[i + 1])) {
f = true;
}
if(!f) {
return -1;
}
}
}
// second pass
// 假如有 '.' 旁邊能有兩個 H ， 則把這些 H 給消耗掉
for(int i = 1;i < street.size() - 1;i++) {
if('.' == street[i]) {
if('H' == street[i - 1] &&
'H' == street[i + 1]) {
ans++;
street[i - 1] = 0;
street[i + 1] = 0;
}
}
}
// third pass
// 消耗掉剩下的 H
for(int i = 0;i < street.size();i++) {
if('.' == street[i]) {
if((i > 0 && 'H' == street[i - 1]) ||
(i != street.size() - 1 && 'H' == street[i + 1])) {
ans++;
if(i > 0 && 'H' == street[i - 1]) {
street[i - 1] = 0;
}
if(i < street.size() && 'H' == street[i + 1]) {
street[i + 1] = 0;
}
}
}
}
return ans;
}
};LeetCode : 1975. Maximum Matrix Sum
#define LL long long
class Solution {
public:
long long maxMatrixSum(vector<vector<int>>& matrix) {
// 因為可以使用無限次該指定操作
// 所以假如負數個數為偶數個的話，可以全部變為正數
// 假如負數個數為奇數個的話，選一個絕對值最小的值視為負數
LL numOfNe = 0;
LL minVal = INT_MAX;
LL sum = 0;
for(int i = 0;i < matrix.size();i++) {
for(int j = 0;j < matrix[0].size();j++) {
if(matrix[i][j] < 0) {
numOfNe++;
}
minVal = min(minVal, abs((LL)matrix[i][j]));
sum += abs((LL)matrix[i][j]);
}
}
if(0 == numOfNe % 2) {
return sum;
} else {
return sum - minVal * 2;
}
return 0;
}
};LeetCode : 1054. Distant Barcodes
// TODO : 效能太差了class Solution {
public:
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
vector<int> ans = vector<int>(barcodes.size());
// map<個數, 數字>
map<int, map<int, bool>> num2val;
// val to num
map<int, int> val2num;
// 每次都先放數量最多的那個數字
// 假如上一個是數量最多的數字，就換下一個數字來放
for(int i = 0;i < barcodes.size();i++) {
val2num[barcodes[i]]++;
}
for(auto it = val2num.begin();it != val2num.end();it++) {
num2val[it->second][it->first] = true;
}
int last = -1;
int now = 0;
int nowtimes = 0;
for(int i = 0;i < ans.size();i++) {
auto it = num2val.rbegin();
while(1) {
map<int, bool> &tmpm = it->second;
auto subit = tmpm.begin();
bool b = false;
for(;subit != tmpm.end();subit++) {
if(subit->first != last) {
now = subit->first;
nowtimes = it->first;
b = true;
break;
}
}
if(b) {
break;
}
it++;
}
num2val[nowtimes].erase(now);
if(0 == num2val[nowtimes].size()) {
num2val.erase(nowtimes);
}
if(nowtimes > 1) {
num2val[nowtimes - 1][now] = true;
}
ans[i] = now;
last = now;
}
return ans;
}
};
LeetCode : 2214. Minimum Health to Beat Game
#define LL long long
class Solution {
public:
long long minimumHealth(vector<int>& damage, int armor) {
LL ans = 0;
int maxVal = INT_MIN;
for(int i = 0;i < damage.size();i++) {
ans += damage[i];
maxVal = max(damage[i], maxVal);
}
if(maxVal > armor) {
ans -= armor;
} else {
ans -= maxVal;
}
ans++;
return ans;
}
};LeetCode : 2007. Find Original Array From Doubled Array
// "priority queue" or "map"
// 思考：最小的數，肯定是歸類在 original
// 假如最小的數歸類在 original，但卻沒有可以配合的數的話，就回傳空陣列
// TODO : 效能太差了
class Solution {
public:
vector<int> findOriginalArray(vector<int>& changed) {
if(changed.size() % 2 != 0) {
return {};
}
int size = changed.size() / 2;
map<int, int> m;
for(int i = 0;i < changed.size();i++) {
m[changed[i]]++;
}
vector<int> ans;
for(int i = 0;i < size;i++) {
int minVal = m.begin()->first;
if(minVal == 0) {
if(m[minVal] % 2 != 0) {
return {};
}
int len = m[minVal] / 2;
m.erase(minVal);
for(int j = 0;j < len;j++) {
ans.push_back(0);
}
} else {
if(m.find(minVal * 2) == m.end()) {
return {};
}
m[minVal]--;
m[minVal * 2]--;
if(m[minVal] == 0) {
m.erase(minVal);
}
if(m[minVal * 2] == 0) {
m.erase(minVal * 2);
}
ans.push_back(minVal);
}
}
return ans;
}
};LeetCode : 1253. Reconstruct a 2-Row Binary Matrix
class Solution {
public:
vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
int nowu = upper;
int nowl = lower;
vector<vector<int>> ans = vector<vector<int>>(2, vector<int>(colsum.size(), 0));
// 先遍尋 colsum[i] == 2 的情況
for(int i = 0; i < colsum.size();i++) {
if(colsum[i] == 2) {
if(nowu > 0 && nowl > 0) {
nowu--;
nowl--;
ans[0][i] = 1;
ans[1][i] = 1;
} else {
return {};
}
}
}
// 再遍尋 colsum[i] == 1 的情況
for(int i = 0;i < colsum.size();i++) {
if(colsum[i] == 1) {
if(nowu > 0) {
nowu--;
ans[0][i] = 1;
} else if (nowl > 0) {
nowl--;
ans[1][i] = 1;
} else {
return {};
}
}
}
if(nowu > 0 || nowl > 0) {
return {};
}
return ans;
}
};LeetCode : 2422. Merge Operations to Turn Array Into a Palindrome
// two pointers, greedy
#define LL long long
class Solution {
public:
int minimumOperations(vector<int>& nums) {
vector<LL> llnums = vector<LL>(nums.size(), 0);
for(int i = 0;i < nums.size();i++) {
llnums[i] = nums[i];
}
int left = 0;
int right = nums.size() - 1;
int ans = 0;
while(left < right) {
if(llnums[left] == llnums[right]) {
left++;
right--;
} else if(llnums[left] > llnums[right]) {
ans++;
llnums[right - 1] += llnums[right];
right--;
} else if(llnums[left] < llnums[right]) {
ans++;
llnums[left + 1] += llnums[left];
left++;
}
}
return ans;
}
};LeetCode : 2383. Minimum Hours of Training to Win a Competition
class Solution {
public:
int minNumberOfHours(int initialEnergy, int initialExperience, vector<int>& energy, vector<int>& experience) {
int ans = 0;
int totalE = 0;
for(int i = 0;i < energy.size();i++) {
totalE += energy[i];
}
if (totalE + 1 > initialEnergy) {
ans += (totalE - initialEnergy) + 1;
}
int nowex = initialExperience;
for (int i = 0; i < experience.size(); i++) {
if (nowex < experience[i] + 1) {
ans += (experience[i] - nowex) + 1;
nowex = experience[i] + 1;
}
nowex += experience[i];
}
return ans;
}
};LeetCode : 2498. Frog Jump II
痛苦的一題，想好久 QQ
/*
想法一：
每次的跳躍都越遠越好
當跳躍失敗時，就進行下一輪的二分搜
--> 應該是錯的，一邊看起來是挑最遠的跳，會害回程的困難度增加
--> 先從想暴力解開始吧。。。
---
想法二：dp?
---
想法三：多思考一些測資，來找找看規律
e.g. [0, 1, 2, 3, 4, 5, 6, 7]
[0, 1, 4, 5]
假如 [a, b, c]
--> 答案肯定是 |c - a|
假如 [a, b, c, d]
--> 不管怎麼選 (a->c->d, d->b->a)
(a->b->d, d->c->a)
答案肯定是 max(|a - b|, |b - d|, |a - c|, |c - d|)
假如 [a, b, c, d, e]
---
舉了一個共有七個元素的例子
[a, b, c, d, e, f, g, h]
可以看到解必定會是
[a, c, e, g, h]
[a, b, d, f, h]
挪動任何一個元素只會讓 ans 變得更大
--> 奇數個元素的解就是這樣
---
接著要討論偶數個數的解：
[a, b, c, d, e, f, g, h]
[a, c, e, g, h]
[a, b, d, f, h]
--> 可以看到挪動任何一個元素都只會讓 ans 變得更大
--> e.g. 挪動 b ， 雖然會讓 a-c 變小，但只會出現更大的 a-d
--> e.g. 挪動 c ， 雖然會讓 b-d 變小，但只會出現更大的 a-e
--> e.g. 挪動 d ， 雖然會讓 c-e 變小，但只會出現更大的 b-f
--> e.g. 挪動 e ， 雖然會讓 d-f 變小，但只會出現更大的 c-g
--> e.g. 挪動 f ， 雖然會讓 e-g 變小，但只會出現更大的 d-h
--> e.g. 挪動 g ， 雖然會讓 f-h 變小，但只會出現更大的 e-h
---
最後的總結就是，
只要給一個元素給 v1 ， 下一個元素就給 v2
只要給一個元素給 v2 ， 下一個元素就給 v1
終於成功了。。。這題花了好久的時間。。。
*/
class Solution {
public:
int maxJump(vector<int>& stones) {
vector<int> v1;
vector<int> v2;
v1.push_back(stones[0]);
v2.push_back(stones[0]);
for(int i = 1;i < stones.size() - 1;i++) {
if(i % 2 == 0) {
v1.push_back(stones[i]);
} else {
v2.push_back(stones[i]);
}
}
v1.push_back(stones.back());
v2.push_back(stones.back());
int ans = INT_MIN;
for(int i = 1;i < v1.size();i++) {
ans = max(ans, v1[i] - v1[i - 1]);
}
for(int i = 1;i < v2.size();i++) {
ans = max(ans, v2[i] - v2[i - 1]);
}
return ans;
}
};