很遗憾，今天早上的周赛看了一眼就没去了。
刷别的题目去了。
简单题·最后一个单词的长度
题目
给你一个字符串 s，由若干单词组成，单词之间用空格隔开。返回字符串中最后一个单词的长度。如果不存在最后一个单词，请返回0。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
示例 1：
输入：s = "Hello World"
输出：5
- 1
- 2
示例 2：
输入：s = " "
输出：0
- 1
- 2
提示：
1 <= s.length <= 104
s 仅有英文字母和空格 ' ' 组成
- 1
- 2
来源：力扣（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
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
中等题·插入区间
给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
- 1
- 2
示例 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] 重叠。
- 1
- 2
- 3
示例 3：
输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]
- 1
- 2
示例 4：
输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]
- 1
- 2
示例 5：
输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]
- 1
- 2
提示：
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
- 1
- 2
- 3
- 4
- 5
- 6
来源：力扣（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; }
- 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
- 29
困难题·分发糖果
题目
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
- 1
- 2
那么这样下来，老师至少需要准备多少颗糖果呢？
示例 1：
输入：[1,0,2]
输出：5
解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。
- 1
- 2
- 3
示例 2：
输入：[1,2,2]
输出：4
解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
- 1
- 2
- 3
- 4
来源：力扣（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; }
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/candy/solution/fen-fa-tang-guo-by-leetcode-solution-f01p/
来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。
原文链接：lion-wu.blog.csdn.net/article/details/114484892