【Leetcode C++ 解題筆記】Greedy - part 1

本筆記僅供個人學習用途，內容斟酌參考。

409. Longest Palindrome

difficulty : Easy.

tags : hashtable, string, greedy.

題目敘述：

給定一個由大寫或小寫所組成的字串 s，回傳那些可以由字母所組成最長回文的長度。

字母是區分大小寫的，如 Aa 不被視為一種回文。

解題思路：

建立一個 hashtable (unordered_map)，計算每個字母所出現的次數。

  • 如果次數是偶數：表示可以對稱放在回文的左右兩邊，可以全部使用，所以直接將次數加進去 len 裡面。
  • 若次數是奇數：因為回文有對稱性，所以只能用偶數部分（次數 - 1）放在左右兩邊，剩下的字母可置於回文中間。（整個回文只能有一個這樣的字母在中間）

solution ( 0 ms )：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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

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 ) :

1
2
3
4
5
6
7
8
9
10
11
12
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

difficulty : Easy.

tags : String, Greedy, Counting

題目敘述：

所謂平衡字串（Balanced string）就是兩字元 'L', 'R' 的數量相等。

給定一個字串 s，拆分成一些子字串使得：

  • 每個子字串都被平衡

回傳最大可以獲得的平衡字串數量。

解題思路：

遍歷 s，看要設定成是遇到 L 就 ++，還是 R 就 ++，都可以，反正只要一增，另外一個就減。

每次遍歷要檢查 balance 是否 == 0，是的話表示平衡，count++。

solution ( 0ms ) :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

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 ) :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

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 ) :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

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 ) :

1
2
3
4
5
6
7
8
9
10
11
12
13
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

difficulty : Easy.

tags : Array, Greedy

題目敘述：

給定一個整數陣列（索引以 0 作為起始點），可任選一個位置的元素，使其增加 1，讓這個陣列成一個嚴格遞增的陣列。

回傳這樣的最小操作次數。

解題思路：

遍歷 vector，檢查 nums[i] <= nums[i - 1]，若成立，算出這兩者的增加量：nums[i - 1] + 1 - nums[i]，為什麼要算呢？因為這是要拿去判斷有多少操作次數的，所以之後要再把 operations 次數加上這個增加量。

之後就是直接做遞增的動作了。

Solution ( 10 ms ) :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

這題真的簡單到哭…害我以為真的就這樣嗎？

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 完全一樣啊？？

1
2
3
4
5
6
7
8
9
10
11
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

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 的等差級數。

公式：

所以解題思路就是代公式，結束。

Solution ( 0ms ) :

1
2
3
4
5
6
7
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

difficulty : Easy.

tags : Two pointers, String, Greedy

題目敘述：

給定一個由小寫英文字母組成的字串 s，你可以多次將其中一個字元替換成另一個小寫字母。

請用最少的操作次數將 s 轉換成回文。若有多種解法，請回傳字典序最小的那一個回文字串。

回傳轉換後的回文字串。

解題思路：

使用雙指標 left, right，根據回文特性，若左右兩邊字元不相等，那就繼續下一個判斷條件（題目要求字典序最小）判斷字典序（s[left] < s[right] 或 s[left] > s[right]），去做相對應的字元賦值。

Solution ( 0ms ) :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
    }
};