# 第三屆特雷維歡樂賽題解

[Q1](http://git.trevi.cc/RanceJen/trevi-competition/blob/master/20190614-3/Q1.md)

LeetCode 387. [First Unique Character in a String](https://leetcode.com/problems/first-unique-character-in-a-string/)

Time O(n) n = string size
Space O(k) k = 26

第一次把整個字串掃過，用一個 hash map 紀錄每個字母出現次數
接著從前面再往後掃一次，比對遇到的字母總出現次數，發現是 1 的話就回傳 index ，若是掃到底都沒有比對成功則回傳 -1

int firstUniqChar(string s) {
    map<char, int> recorder{};
    for (const auto& v : s) {
        recorder[v]++;
    }

    int i = 0;
    for (; i < s.size(); ++i) {
        if (recorder[s[i]] == 1) {
            return i;
        }
    }

    return -1;
}

---

[Q2](http://git.trevi.cc/RanceJen/trevi-competition/blob/master/20190614-3/Q2.md)
LeetCode 860. [Lemonade Change](https://leetcode.com/problems/lemonade-change/)

因為小的硬幣能組成大的，大的不能拆分成小的，所以找錢先用大的硬幣準沒錯。
用一個 map 紀錄現有各零錢數量，每次找零時先看大的能不能找，扣掉能找的部份，再看小的。把能找的都找完之後還有剩就代表沒得找了。

Time O(n) n = bills size
Space O(k) k = 3

bool lemonadeChange(vector<int>& bills) {
    map<int, int> coins{};
    for (const auto& v : bills) {
        coins[v]++;
        auto less = v - 5;
        if (less >= 20) {
            auto need = min(less / 20, coins[20]);
            coins[20] -= need;
            less -= need * 20;
        }
        if (less >= 10) {
            auto need = min(less / 10, coins[10]);
            coins[10] -= need;
            less -= need * 10;
        }
        if (less >= 5) {
            auto need = min(less / 5, coins[5]);
            coins[5] -= need;
            less -= need * 5;
        }
        if (less != 0) {
            return false;
        }
    }
    return true;
}

---

[Q3](http://git.trevi.cc/RanceJen/trevi-competition/blob/master/20190614-3/Q3.md)

LeetCode 121. [Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)

因為股票只能先買後賣，所以我們只需要看賣出前的最低點。
手上先拿好第一次的價格，開始一路往後看，每次都計算賣出的差額，紀錄最大差額，如果有當下價格比手上拿的還便宜的，就替換掉手上拿股票，因為這樣後續賣出差額會更大，然後繼續往後算下去。

Time O(n) n = prices size
Space O(1)

int maxProfit(vector<int>& prices) {
    if (prices.empty()) {
        return 0;
    }
    int diff = 0;
    int cur = prices[0];
    for (const auto & v : prices) {
        if (v < cur) {
            cur = v;
        }
        else {
            diff = max(diff, v - cur);
        }
    }
    return diff;
}