今天的題單：

• Majority Element

• Add Binary

169. Majority Element

找出 list 中出現次數大於一半的數字。

思路：最直覺的做法，掃一遍 list 記錄各個數字出現的次數，看誰次數超過一半。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int, int> hash_map;

        for (int& i: nums) {
            if (hash_map.find(i) == hash_map.end()) {
                hash_map[i] = 1;
            } else {
                hash_map[i]++;
            }
        }

        int ans;
        for (auto pair: hash_map) {
            if (pair.second > nums.size() / 2) {
                ans = pair.first;
                break;
            }

        }
        return ans;
    }
};

Follow-up: Could you solve the problem in linear time and in O(1) space?

這題想不出來。查了一下，大部分人是使用 多數投票算法（Boyer–Moore majority vote algorithm）。這個算法只能在 Majority Element 存在的時候使用。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int majority = 0;
        int counter = 0;

        for (int i = 0; i < nums.size(); i++) {
            if (counter == 0) {
                majority = nums[i];
                counter++;
            } else {
                nums[i] == majority ? counter++ : counter--;
            }
        }
        
        return majority;
    }
};

67. Add Binary

binary number 相加。從最低位開始加，記得要記 carry out。

class Solution {
public:
    string addBinary(string a, string b) {
        int a_idx = a.size() - 1;
        int b_idx = b.size() - 1;
        int a_value = 0;
        int b_value = 0;
        int partial_sum = 0;
        int carry_out = 0;
        string sum = "";

        while (a_idx >= 0 || b_idx >= 0 || carry_out != 0) {
            if (a_idx >= 0) {
                a_value = a[a_idx] - '0';
            }
            if (b_idx >= 0) {
                b_value = b[b_idx] - '0';
            }

            partial_sum = a_value + b_value + carry_out;

            if (partial_sum % 2 == 0) {
                sum = "0" + sum;
            } else {
                sum = "1" + sum;
            }
            if (partial_sum >= 2) {
                carry_out = 1;
            } else {
                carry_out = 0;
            }
            
            a_idx--;
            b_idx--;
            a_value = 0;
            b_value = 0;
        }
        return sum;
    }
};

一些感想

Easy 20 題了，先給自己一點掌聲。
寫到這裡，練習了一些簡單算法的實作，開始找回了一點手感，也學到了一些東西。寫到這裡發現 Easy 大概分為兩類題目：（1）純粹的實作題，把一些功能實作出來（2）需要演算法優化的題目。有一些需要小想一下，大概半小時內都能解出來，不過即使再簡單的題目，我強迫自己寫下思路步驟，除了讓思路清楚，也盡可能讓程式易讀。之後會開始注意一下 coding style。

在寫這些題目的時候，有時會想要直接想最優解，但一時之間想不出來就卡在那裡。遇到這種時候總是告訴自己，先想到可行的解法先寫出來（通常都是暴力解），再來想時間或空間上有什麼地方可以優化，使用哪些對應的資料結構和算法。可能是解出題目後壓力減小的關係吧，之後思考有哪些地方可以優化的過程我覺得蠻有趣的，想要讓程式跑得又快又好。一開始就要想出最佳解反而會讓壓力很大。