LeetCode刷题的一天（3）

很遗憾，今天早上的周赛看了一眼就没去了。
刷别的题目去了。

简单题·最后一个单词的长度

题目

给你一个字符串 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