【Leetcode C++ 解題筆記】Greedy - part 1
===
[TOC]
本筆記僅供個人學習用途，內容斟酌參考。
## [409. Longest Palindrome](https://leetcode.com/problems/longest-palindrome/?envType=problem-list-v2&envId=greedy)
difficulty : Easy.
tags : hashtable, string, greedy.
題目敘述：
給定一個由大寫或小寫所組成的字串 s，回傳那些可以由字母所組成最長回文的長度。
字母是區分大小寫的，如 `Aa` 不被視為一種回文。
解題思路：
建立一個 hashtable (unordered_map)，計算每個字母所出現的次數。
- 如果次數是偶數：表示可以對稱放在回文的左右兩邊，可以全部使用，所以直接將次數加進去 len 裡面。
- 若次數是奇數：因為回文有對稱性，所以只能用偶數部分（次數 - 1）放在左右兩邊，剩下的字母可置於回文中間。（整個回文只能有一個這樣的字母在中間）
solution ( 0 ms )：
```cpp=
class Solution {
public:
int longestPalindrome(string s) {
unordered_map <char, int> f;
for (char c : s){
f[c]++;
}
int len = 0;
bool odd_found = false;
for (auto& p : f){
if (p.second % 2 == 0){
len += p.second;
}
else{
len += p.second - 1;
odd_found = true;
}
}
if (odd_found) len++;
return len;
}
};
```
## [2037. Minimum Number of Moves to Seat Everyone](https://leetcode.com/problems/minimum-number-of-moves-to-seat-everyone/?envType=problem-list-v2&envId=greedy)
difficulty : Easy.
tags : Array, Greedy, Sorting, Counting Sort
題目敘述：
有 n 個空座位及 n 個學生，他們都站在一個房間裡。給定一個長度為 n 的陣列 seats，`seats[i]` 為在第 i 個座位的位置；也給定一個長度為 n 的陣列 students，`students[j]` 為在第 j 個學生的位置。
然後叫你紀錄從 `seats[i]` 到 `students[j]` 的距離是多少，回傳將這些距離加起來最短的和。
解題思路：
sort 兩個 vector，迴圈跑一次算 `abs(seats[i] - students[i])`，相加後就是答案。
solution ( 0ms ) :
```cpp=
class Solution {
public:
int minMovesToSeat(vector<int>& seats, vector<int>& students) {
sort(seats.begin(), seats.end());
sort(students.begin(), students.end());
int move = 0;
for (int i = 0; i < seats.size(); i++){
move += abs(seats[i] - students[i]);
}
return move;
}
};
```
## [1221. Split a String in Balanced Strings](https://leetcode.com/problems/split-a-string-in-balanced-strings/?envType=problem-list-v2&envId=greedy)
difficulty : Easy.
tags : String, Greedy, Counting
題目敘述：
所謂平衡字串（Balanced string）就是兩字元 `'L', 'R'` 的數量相等。
給定一個字串 s，拆分成一些子字串使得：
- 每個子字串都被平衡
回傳最大可以獲得的平衡字串數量。
解題思路：
遍歷 s，看要設定成是遇到 L 就 ++，還是 R 就 ++，都可以，反正只要一增，另外一個就減。
每次遍歷要檢查 balance 是否 == 0，是的話表示平衡，count++。
solution ( 0ms ) :
```cpp=
class Solution {
public:
int balancedStringSplit(string s) {
int count = 0, balance = 0;
for (const char& c : s){
if (c == 'L'){
balance++;
}
else{
balance--;
}
if (balance == 0){
count++;
}
}
return count;
}
};
```
## [2160. Minimum Sum of Four Digit Number After Splitting Digits](https://leetcode.com/problems/minimum-sum-of-four-digit-number-after-splitting-digits/?envType=problem-list-v2&envId=greedy)
difficulty : Easy.
tags : Math, Greedy, Sorting
題目敘述：
給四位數正整數，將四位數拆分成四個一位數，求將這些一位數排列組合後，使得 new1 跟 new2 的總和最小？
new1 和 new2 最多可以是三位數，最低為一位數，兩位數與兩位數也可。
如 2932 拆成 2、9、3、2，可以組成 29、32 相加，也可以組成 22、39 相加，求得兩者相加的最小和。
解題思路：
用 while 迴圈，四位數取模（`%10`）的結果放入陣列裡面，接下來再對原四位數砍一位數（`num /= 10`），再繼續取模，直到迴圈跑完為止。
最後是 new1 跟 new2 的相加，一位數加上三位數肯定比兩位加兩位大，所以這兩個變數都是兩位加兩位。
但是在此之前可以先排序陣列，比較好操作。new1 跟 new2 的十位數一定要取最小的那兩個，之後個位數隨便怎麼排都沒差。
Solution ( 0 ms ) :
```cpp=
class Solution {
public:
int minimumSum(int num) {
int i = 4;
vector <int> nums(i);
while (i--){
nums[i] = num % 10;
num /= 10;
}
sort(nums.begin(), nums.end());
int d1 = nums[0]*10 + nums[2];
int d2 = nums[1]*10 + nums[3];
return d1 + d2;
}
};
```
## [2864. Maximum Odd Binary Number](https://leetcode.com/problems/maximum-odd-binary-number/?envType=problem-list-v2&envId=greedy)
difficulty : Easy.
tags : Math, String, Greedy
題目敘述：
給定一個必定至少含有一個 1 的字串 s。
你必須要重新排列這些位元，使其組合成一個最大的奇數二進位數字。
回傳一個字串，表示可以從給定組合中得到的最大奇數二進位數字。
解題思路：
設兩個變數，用 range-based for loop 去計算 1 跟 0 在字串 s 的次數。
因為是「二進位」，所以能不能是奇數，在最末端是致關重要的一件事，如：`0101`，最後面的 1 意即 $1 \times 2^0 = 1$ 。
因此，在算完次數後，記得要再讓紀錄 1 次數的變數 `--`，因為那一次被拿去放到最後面了。
最後用 result 字串變數儲存結果，在算完 1 後加上剩下的 0，最後再補個 1。
Solution ( 0 ms ) :
```cpp=
class Solution {
public:
string maximumOddBinaryNumber(string s) {
int count_1 = 0, count_0 = 0;
for (char c : s){
if (c == '1') count_1++;
else count_0 ++;
}
count_1--;
string result(count_1, '1');
result += string(count_0, '0');
result += '1';
return result;
}
};
```
## [1323. Maximum 69 Number](https://leetcode.com/problems/maximum-69-number/?envType=problem-list-v2&envId=greedy)
difficulty : Easy.
tags : Math, Greedy
這是一個蠻有趣的題目XD
題目敘述：
給定一個僅由 6 跟 9 所組成的正整數 num。
你只能改變一個位數的狀態，如 6 改成 9，9 改成 6，試找出改完後最大的值為何？
解題思路：
將位數存入陣列還蠻不實際的，反而轉成字串更快、更直觀。
用 `to_string()` 轉成字串後，range-based for loop 遍歷字串第一個出現 6 的字元，改成 9 後直接 break，然後再把改完的字串換成整數，結束。
Solution ( 0 ms ) :
```cpp=
class Solution {
public:
int maximum69Number (int num) {
string s = to_string(num);
for (char& c : s){
if (c == '6'){
c = '9';
break;
}
}
return stoi(s);
}
};
```
## [1827. Minimum Operations to Make the Array Increasing](https://leetcode.com/problems/minimum-operations-to-make-the-array-increasing/?envType=problem-list-v2&envId=greedy)
difficulty : Easy.
tags : Array, Greedy
題目敘述：
給定一個整數陣列（索引以 0 作為起始點），可任選一個位置的元素，使其增加 1，讓這個陣列成一個嚴格遞增的陣列。
回傳這樣的最小操作次數。
解題思路：
遍歷 vector，檢查 `nums[i] <= nums[i - 1]`，若成立，算出這兩者的增加量：`nums[i - 1] + 1 - nums[i]`，為什麼要算呢？因為這是要拿去判斷有多少操作次數的，所以之後要再把 `operations` 次數加上這個增加量。
之後就是直接做遞增的動作了。
Solution ( 10 ms ) :
```cpp=
class Solution {
public:
int minOperations(vector<int>& nums) {
int operations = 0;
for (int i = 1; i < nums.size(); i++){
if (nums[i] <= nums[i-1]){
int temp = nums[i - 1] + 1 - nums[i];
operations += temp;
nums[i] = nums[i - 1] + 1;
}
}
return operations;
}
};
```
## [561. Array Partition](https://leetcode.com/problems/array-partition/?envType=problem-list-v2&envId=greedy)
這題真的簡單到哭...害我以為真的就這樣嗎？
difficulty : Easy.
tags : Array, Greedy, Sorting, Counting Sort
題目敘述：
給定一個包含 2n 個整數的整數陣列 nums，將這些整數分組為 n 對 `(a1, b1), (a2, b2), ..., (an, bn)`，使得所有 i 的 `min(ai, bi)` 總和最大化。回傳最大化的和。
解題思路：
排序，然後 for 的遞增條件改成 `i += 2`，`sum += nums[i];` 結束。
Solution ( 15 ms )：
註：這個速度蠻讓人好奇的，我的寫法跟 0ms 完全一樣啊？？
```cpp=
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int sum = 0;
for (int i = 0; i < nums.size(); i += 2){
sum += nums[i];
}
return sum;
}
};
```
## [2656. Maximum Sum With Exactly K Elements](https://leetcode.com/problems/maximum-sum-with-exactly-k-elements/?envType=problem-list-v2&envId=greedy)
difficulty : Easy.
tags : Array, Greedy
題目敘述：
給定一個索引為 0 作為起始點的整數陣列 nums 和一個整數 k。你的任務是執行以下操作 k 次，來最大化你的分數：
1. 從 nums 選擇一個元素 m。
2. 將所選的 m 從陣列中移除。
3. 新增一個新元素到陣列裡面，其值為 m + 1。
4. 分數增加為 m。
回傳執行該操作恰好 k 次後可獲得的最高分數。
解題思路：
我不確定該題的陣列是否都排序好，保險起見可以用 `max_element(first, last)` 求最大值。
由於每次更新時都是 m + 1，所以也就成了公差為 1 的等差級數。
公式：
$$S_n = \frac{(a_1 + a_n) \times n}{2}$$
所以解題思路就是代公式，結束。
Solution ( 0ms ) :
```cpp=
class Solution {
public:
int maximizeSum(vector<int>& nums, int k) {
int m = *max_element(nums.begin(), nums.end());
return (m + m + k - 1) * k / 2; // k 是項數，記得分子那邊要減個 1。
}
};
```
## [2697. Lexicographically Smallest Palindrome](https://leetcode.com/problems/lexicographically-smallest-palindrome/description/?envType=problem-list-v2&envId=greedy)
difficulty : Easy.
tags : Two pointers, String, Greedy
題目敘述：
給定一個由小寫英文字母組成的字串 `s`，你可以多次將其中一個字元替換成另一個小寫字母。
請用最少的操作次數將 `s` 轉換成回文。若有多種解法，請回傳字典序最小的那一個回文字串。
回傳轉換後的回文字串。
解題思路：
使用雙指標 left, right，根據回文特性，若左右兩邊字元不相等，那就繼續下一個判斷條件（題目要求字典序最小）判斷字典序（`s[left] < s[right]` 或 `s[left] > s[right]`），去做相對應的字元賦值。
Solution ( 0ms ) :
```cpp=
class Solution {
public:
string makeSmallestPalindrome(string s) {
int left = 0, right = (int)s.length() - 1;
while (left < right){
if (s[left] != s[right]){
s[left] = s[right] = (s[left] < s[right]) ? s[left] : s[right];
}
left++;
right--;
}
return s;
}
};
```
Sign in with Wallet
Connect another wallet