LeetCode刷題的一天（3）

很遺憾，今天早上的周賽看了一眼就沒去了，
刷別的題目去了，

簡單題·最后一個單詞的長度

題目

給你一個字串 s，由若干單詞組成，單詞之間用空格隔開，回傳字串中最后一個單詞的長度，如果不存在最后一個單詞，請回傳0，

單詞 是指僅由字母組成、不包含任何空格字符的最大子字串，

示例 1：

輸入：s = "Hello World"
輸出：5

示例 2：

輸入：s = " "
輸出：0

提示：

1 <= s.length <= 104
s 僅有英文字母和空格 ' ' 組成

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/length-of-last-word
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

思路

思路其實沒什么難的，就找空格嘛，不過要注意可能最后幾個字符會全是空格，需要仔細甄別就好了，

代碼實作

int lengthOfLastWord(string s) {
        int sz = s.size();

        if (sz == 0) {
            return NULL;
        }

        int flag = 0, keep_flag = 0;

        for (int i = 0; i < sz; i++) {
            if (s[i] == ' ') {
                if(flag > 0 )
                    keep_flag = flag;
                flag = 0;
                continue;
            }
            flag++;
        }

        if (flag == 0)
            return keep_flag;
        return flag;
    }

中等題·插入區間

給你一個 無重疊的 ，按照區間起始端點排序的區間串列，

在串列中插入一個新的區間，你需要確保串列中的區間仍然有序且不重疊（如果有必要的話，可以合并區間），

示例 1：

輸入：intervals = [[1,3],[6,9]], newInterval = [2,5]
輸出：[[1,5],[6,9]]

示例 2：

輸入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
輸出：[[1,2],[3,10],[12,16]]
解釋：這是因為新的區間 [4,8] 與 [3,5],[6,7],[8,10] 重疊，

示例 3：

輸入：intervals = [], newInterval = [5,7]
輸出：[[5,7]]

示例 4：

輸入：intervals = [[1,5]], newInterval = [2,3]
輸出：[[1,5]]

示例 5：

輸入：intervals = [[1,5]], newInterval = [2,7]
輸出：[[1,7]]

提示：

0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 10^5
intervals 根據 intervals[i][0] 按 升序 排列
newInterval.length == 2
0 <= newInterval[0] <= newInterval[1] <= 10^5

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/insert-interval
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

思路

那這不也很直接嗎？并沒有什么彎彎繞的，

代碼實作

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        bool placed = false;
        vector<vector<int>> ans;
        for (const auto& interval: intervals) {
            if (interval[0] > right) {
                // 在插入區間的右側且無交集
                if (!placed) {
                    ans.push_back({left, right});
                    placed = true;                    
                }
                ans.push_back(interval);
            }
            else if (interval[1] < left) {
                // 在插入區間的左側且無交集
                ans.push_back(interval);
            }
            else {
                // 與插入區間有交集，計算它們的并集
                left = min(left, interval[0]);
                right = max(right, interval[1]);
            }
        }
        if (!placed) {
            ans.push_back({left, right});
        }
        return ans;
    }

困難題·分發糖果

題目

老師想給孩子們分發糖果，有 N 個孩子站成了一條直線，老師會根據每個孩子的表現，預先給他們評分，

你需要按照以下要求，幫助老師給這些孩子分發糖果：

每個孩子至少分配到 1 個糖果，
評分更高的孩子必須比他兩側的鄰位孩子獲得更多的糖果，

那么這樣下來，老師至少需要準備多少顆糖果呢？

示例 1：

輸入：[1,0,2]
輸出：5
解釋：你可以分別給這三個孩子分發 2、1、2 顆糖果，

示例 2：

輸入：[1,2,2]
輸出：4
解釋：你可以分別給這三個孩子分發 1、2、1 顆糖果，
     第三個孩子只得到 1 顆糖果，這已滿足上述兩個條件，

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/candy
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

思路

這個題啊，就沒有那么好想了，
剛開始我的想法是類似于“接雨水”那倒題的思維，層序遞減，算了一下時間復雜度，不合算，

休息了一會兒，還是畫了畫草圖，發現可以從頭遍歷，記住每個轉折點，對比轉折點前后的高度，進行比對，
但是實作起來還是比較繁瑣的，

突然，靈機一動，這不就是在一個序列中不斷尋找上升序列和下降序列的程序嘛，但是因為有“持平”序列的干擾，導致計數并沒有那么好計，
那好辦吶，那頭尾先不計嘛，等著一上一下解決之后，在計算上下之間夾著的波峰/波谷的值不就好了嘛，

草圖就不放啦，用LeetCode上的圖吧，看的比較容易懂，我那兒就畫了一條波浪線，比較，，

如果光看這張圖，容易以偏概全，還是要在紙上自己畫條波浪線，把細節部分敲定清楚了，

代碼實作

我的代碼太冗余，還是用LeetCode的輕裝代碼吧，

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        int ret = 1;
        int inc = 1, dec = 0, pre = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] >= ratings[i - 1]) {
                dec = 0;
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                ret += pre;
                inc = pre;
            } else {
                dec++;
                if (dec == inc) {
                    dec++;
                }
                ret += dec;
                pre = 1;
            }
        }
        return ret;
    }
};

作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/candy/solution/fen-fa-tang-guo-by-leetcode-solution-f01p/
來源：力扣（LeetCode） 著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，