我的日程安排表1
题目:实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排，则可以存储这个新的日程安排。MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生重复预订。每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。请按照以下步骤调用 MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
示例 1:
MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
解释:
第一个日程安排可以添加到日历中. 第二个日程安排不能添加到日历中，因为时间 15 已经被第一个日程安排预定了。
第三个日程安排可以添加到日历中，因为第一个日程安排并不包含时间 20 。
说明:
每个测试用例，调用 MyCalendar.book 函数最多不超过 100次。
调用函数 MyCalendar.book(start, end)时， start 和 end 的取值范围为 [0, 10^9]。
思路：简单来说这个题首先是开放式的题目。是我最喜欢又最不喜欢的。喜欢是因为实现方式多种多样比较好做，不喜欢是同样是实现，人家的赏心悦目，自己的一言难尽。回到这个题：因为时间范围太大了，所以也不是很好用数组存储不能用的时间。而且还涉及到一个起始都没用的，但是中间不能用的情况。。有点复杂。。大概率是用list来存储，判断新插入是是不是单独一个区间吧
第一版ac代码实现了，先贴代码：
class MyCalendar {
List<Integer> list;
public MyCalendar() {
list = new ArrayList<Integer>();
}
public boolean book(int start, int end) {
//第一条无论如何都能插入
if(list.size() == 0) {
list.add(start);
list.add(end-1);
return true;
}
//结束时间比现有的最小开始时间小，直接插到头部
if(end-1<list.get(0)) {
list.add(0, start);
list.add(1,end-1);
return true;
}
//开始时间比现有的最大时间大，直接插到尾部
if(start>list.get(list.size()-1)) {
list.add(start);
list.add(end-1);
return true;
}
int idx = -1;//开始插入的下标
for(int i = 0;i<list.size()-1;i++) {
if(list.get(i)<start && list.get(i+1)>end-1) {
idx = i+1;//新的开始下标插入到i后面
break;
}
}
// 一对一对从0开始，如果插入的是单数，说明插入一对中间了，所以直接false
if(idx == -1 || idx%2 == 1) return false;
list.add(idx,start);
list.add(idx+1,end-1);
return true;
}
}
/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar obj = new MyCalendar();
* boolean param_1 = obj.book(start,end);
*/
虽然性能有点问题，但是起码ac了，简单来说这个思路就是所有的开闭区间都存储到一个list中，根绝下标的位置判断对（0-1.2-3,4-5.确定偶数-下一个奇数是一对的数据。）然后看新的区间是不是中间没别的元素。不是的话则false，否则true。当然了其中优化点也很多，比如这个首末区间可以统一整理一下。不过我就不调试了，直接看看性能第一的代码吧：
class MyCalendar {
class Node {
int start;
int end;
Node right;
Node left;
Node(int start, int end) {
this.start = start;
this.end = end;
this.left = null;
this.right = null;
}
}
private Node root = null;
public MyCalendar() {
}
public boolean book(int start, int end) {
if (root == null) {
root = new Node(start, end);
return true;
}
Node insert = new Node(start, end);
Node curr = root;
while (true) {
if (curr.start >= end) {
if (curr.left == null) {
curr.left = insert;
return true;
}
curr = curr.left;
} else if (curr.end <= start) {
if (curr.right == null) {
curr.right = insert;
return true;
}
curr = curr.right;
} else {
return false;
}
}
}
}
/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar obj = new MyCalendar();
* boolean param_1 = obj.book(start,end);
*/
我实现了，人家也实现了。然后我是低空掠过，人家是性能为主。这里用了线段树的思路，主要有几点：
- 构造线段树节点。
- 新添加的线段树节点，要么只能全在node.start往左，要么只能全在node.end往右。
- 左右子树如果不存在，这表示该区间不存在，可以插入，如果存在，则往其左右子树递推即可。
- 不满足条件的则表示与当前节点的区间发生了重叠，不能插入。
这个线段树的概念我也是才接触，之前还专门看了这方面的解析。总觉得照着代码反推是理解了，但是自己写有点问题。
挺精巧的代码，而且我看了这道题解法还是比较多的，这个题看着挺有意思的，我再去找找别的方法 ：
class MyCalendar {
// key->start ; value->end
private TreeMap<Integer,Integer> tm;
public MyCalendar() {
tm = new TreeMap<>();
}
public boolean book(int start, int end) {
if (start >= end){
return false;
}
Integer low = tm.floorKey(start);
if(low != null && tm.get(low) > start){
return false;// 前节点考虑
}
Integer high = tm.ceilingKey(start);
if (high != null && high < end){
return false;// 后节点考虑
}
tm.put(start,end);
return true;
}
}
二叉树的实现，大概思路就是找到比start小的值，看其value是不是比start大，如果大于start，则表示重复，不能插入
再找到比start大的值，看其本身是不是比end小，如果小于end，则表示重复，不能插入
如果两者都可以插入，说明是可以插进去的。
反正这个题我感觉我实现出来一点都没开心的，和人家的思路完全是两个东西。就好像1+2+3...100一样，感觉自己好蠢。。哎，下一题下一题。
我的日程安排表2
题目：实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
示例：
MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns true
解释：
前两个日程安排可以添加至日历中。 第三个日程安排会导致双重预订，但可以添加至日历中。
第四个日程安排活动（5,15）不能添加至日历中，因为它会导致三重预订。
第五个日程安排（5,10）可以添加至日历中，因为它未使用已经双重预订的时间10。
第六个日程安排（25,55）可以添加至日历中，因为时间 [25,40] 将和第三个日程安排双重预订；
时间 [40,50] 将单独预订，时间 [50,55）将和第二个日程安排双重预订。
提示：
每个测试用例，调用 MyCalendar.book 函数最多不超过 1000次。
调用函数 MyCalendar.book(start, end)时， start 和 end 的取值范围为 [0, 10^9]。
思路：安排完又要安排，这个题和1的区别就是日程可以安排两次。然后日程安排两次的概念就是同一个时间段，可以有两个时间区间的叠加。如果遇到已有两层还想要往上叠加才会返回false。我觉得这个题可以和上一个题差不多思路。只不过这个题要有判断是不是三重叠加，所以存储一下二层叠加。有个大体的思路，我去试试代码实现。
第一版ac代码：
public class MyCalendarTwo {
List<int[]> calendar;
List<int[]> overlaps;
MyCalendarTwo() {
calendar = new ArrayList();
overlaps = new ArrayList();
}
public boolean book(int start, int end) {
for (int[] iv: overlaps) {
//start或者end在一个区间中，那么这段肯定有重叠区间
//当前已经是双层重叠，所以三层重叠直接false
if (iv[0] < end && start < iv[1]) return false;
}
for (int[] iv: calendar) {
//判断是不是有二层重叠，并且二层重叠的区间入overlaps
if (iv[0] < end && start < iv[1]){
overlaps.add(new int[]{Math.max(start, iv[0]), Math.min(end, iv[1])});
}
}
calendar.add(new int[]{start, end});
return true;
}
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo obj = new MyCalendarTwo();
* boolean param_1 = obj.book(start,end);
*/
这个其实就是暴力法，也是上一道题结果的变种，加了一个二层重叠区间的概念。然后注释我也写的挺清楚了，所以不多说什么了。其实我觉得这个题也可以用map来实现，只不过要引入一个二层重叠的概念，我再去实现下试试。
这个思路有毒。。因为在判断二层重叠的时候，只能找到首尾两条线。如果出现中间还有重叠区根本找不到，所以这个思路pass了。我还是老老实实去看题解吧：
看了题解，豁然开朗，就连第一个题都可以用的一种很精巧的思路：每个区间起始点+1.结束点-1。这样当累计数目达到3的时候，说明一定是有三层重叠了，其实上一道题也是类似的，到累计达到2说明2层重叠。因为这个数据要全遍历。所以可能每次最多遍历1000个kv。但是不得不否则这种思路很神奇啊。我去写代码：
public class MyCalendarTwo {
private TreeMap<Integer,Integer> tm;
MyCalendarTwo() {
tm = new TreeMap<>();
}
public boolean book(int start, int end) {
tm.put(start, tm.getOrDefault(start, 0)+1);
tm.put(end, tm.getOrDefault(end, 0)-1);
int count = 0;
for(Integer i:tm.values()) {
count += i;
if(count>2) {//说明遇到三层重叠了
//这个区间回滚。
tm.put(start, tm.getOrDefault(start, 0)-1);
tm.put(end, tm.getOrDefault(end, 0)+1);
return false;
}
}
return true;
}
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo obj = new MyCalendarTwo();
* boolean param_1 = obj.book(start,end);
*/
这个代码虽然性能不是那么好，但是我真的觉得思路很精巧，最后再去看看性能第一的代码：
果不其然线段树，这个真的是我只是盲区，每次顺着人家的代码捋没哈问题，自己一写就懵：
class MyCalendarTwo {
SegmentTreeNode root;
public MyCalendarTwo() {
root = null;
}
public boolean book(int start, int end) {
if (!canBook(start, end, root)) {
return false;
}
root = book(start, end, root);
return true;
}
private SegmentTreeNode book(int start, int end, SegmentTreeNode node) {
if (start >= end) {
return node;
}
if (node == null) {
return new SegmentTreeNode(start, end);
}
if (start >= node.end) {
node.right = book(start, end, node.right);
return node;
}
if (end <= node.start) {
node.left = book(start, end, node.left);
return node;
}
node.overlap = true;
int a = Math.min(node.start, start);
int b = Math.max(node.start, start);
int c = Math.min(node.end, end);
int d = Math.max(node.end, end);
node.left = book(a, b, node.left);
node.right = book(c, d, node.right);
node.start = b;
node.end = c;
return node;
}
private boolean canBook(int start, int end, SegmentTreeNode node) {
if (start >= end || node == null) {
return true;
}
if (start >= node.end) {
return canBook(start, end, node.right);
}
if (end <= node.start) {
return canBook(start, end, node.left);
}
if (node.overlap) {
return false;
}
if (node.start <= start && end <= node.end) {
return true;
}
return canBook(start, node.start, node.left) && canBook(node.end, end, node.right);
}
private static class SegmentTreeNode {
int start;
int end;
boolean overlap;
SegmentTreeNode left;
SegmentTreeNode right;
SegmentTreeNode(int start, int end) {
this.start = start;
this.end = end;
overlap = false;
left = null;
right = null;
}
}
}
这是我知识盲区，还是上一道题才知道这个概念，之前做题就想到了上一题可以用线段树这一题也可以，但是我莫得勇气自己去写。。。也就是分析分析别人的代码仰望下了。至于这个线段树，看得多了自然就会了，不浪费时间了，下一题。
行星碰撞
题目：给定一个整数数组 asteroids，表示在同一行的行星。对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
示例 1:
输入:
asteroids = [5, 10, -5]
输出: [5, 10]
解释:
10 和 -5 碰撞后只剩下 10。 5 和 10 永远不会发生碰撞。
示例 2:
输入:
asteroids = [8, -8]
输出: []
解释:
8 和 -8 碰撞后，两者都发生爆炸。
示例 3:
输入:
asteroids = [10, 2, -5]
输出: [10]
解释:
2 和 -5 发生碰撞后剩下 -5。10 和 -5 发生碰撞后剩下 10。
示例 4:
输入:
asteroids = [-2, -1, 1, 2]
输出: [-2, -1, 1, 2]
解释:
-2 和 -1 向左移动，而 1 和 2 向右移动。
由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。
说明:
数组 asteroids 的长度不超过 10000。
每一颗行星的大小都是非零整数，范围是 [-1000, 1000] 。
思路：审题半天我都没明白示例4，后来还是问了群里的人才明白：-是往左，前面的也是往左。如果是左边的往左，右边的往右则碰不上。所以说如果前面的是往左，可以直接往后遍历了，这个往左的肯定撞不了了。感觉题目应该不难，我想想去怎么实现。
我先贴第一版本ac代码：
class Solution {
public int[] asteroidCollision(int[] asteroids) {
List<Integer> list = new ArrayList<Integer>();
List<Integer> res = new ArrayList<Integer>();
for(int i = 0;i<asteroids.length;i++) {
if(asteroids[i]>0) {
list.add(asteroids[i]);
}else {
int size = list.size();
boolean flag = true;
for(int j = size-1;j>=0;j--) {
if(-asteroids[i]<list.get(j)) {//i小，碰没了
flag = false;
break;
}else if(-asteroids[i]== list.get(j)) {//相等。俩都碰没了
list.remove(j);
flag = false;
break;
}else {//说明当前的大，碰没之前的
list.remove(j);
}
}
if(flag) res.add(asteroids[i]);
}
}
//到这剩下的list都是可以作为res的结尾的
int[] ans = new int[list.size()+res.size()];
int idx = 0;
for(int i:res) ans[idx++] = i;
for(int i:list) ans[idx++] = i;
return ans;
}
}
这个题其实不难，就是分两种情况：最前面的负数和最后面的正数不用管，中间正负的会互相抵消。抵消机制就是正-负。一样大俩都消失，正大负消失，负大正消失。唯一算是稍微复杂点的就是这个比较是个两个阵营的比较，因为我是从前往后遍历。也就是正正正负的话，如果负不消失，是要和前面所有的正比较。大概就是这个意思。我这个代码的性能也还行。我去看看性能第一的代码：
class Solution {
public int[] asteroidCollision(int[] asteroids) {
int[] nums = new int[asteroids.length];
int idx = 0;
for (int i = 0; i < nums.length; i++) {
if (asteroids[i] < 0 && idx > 0 && nums[idx - 1] > 0) {
if (asteroids[i] + nums[idx - 1] < 0) {
i--;
idx--;
} else if (asteroids[i] + nums[idx - 1] == 0) {
idx--;
}
} else {
nums[idx++] = asteroids[i];
}
}
return Arrays.copyOf(nums, idx);
}
}
这个代码处理起来更优雅，但是思路上也没啥特别的地方。这个题就这么过了，下一题。
每日温度
题目：请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
思路：这个题整体来说就是下一个更高温度。最简单的就是暴力法：从当前温度开始往下找。而且照着这个数据量来说应该也不会超时。。如果说优化的话有点模糊的想法：比如从后往前遍历，然后就不知道了，我先去试试暴力法再说吧。
果不其然，暴力法ac了，虽然性能一言难尽。先贴代码：
class Solution {
public int[] dailyTemperatures(int[] T) {
int[] ans = new int[T.length];
for(int i = 0;i<T.length;i++) {
for(int j = i+1;j<T.length;j++) {
if(T[i]<T[j]){
ans[i] = j-i;
break;
}
}
}
return ans;
}
}
然后说说优化，想来想去依然觉得优化点在从后往前遍历上。毕竟我感觉顺序遍历最大的性能损耗应该就是30000个数字，从大到小顺序排列。那样就要每次第二层循环都要i走到结尾。所以我去想象从后往前遍历的实现吧。
倒叙确实性能好点，但是好的有限，我先贴代码：
class Solution {
public int[] dailyTemperatures(int[] T) {
int[] ans = new int[T.length];
ans[T.length-1] = 0;//最后一天不可能有更好的温度了
for(int i = T.length-2;i>=0;i--) {
for(int j = i+1;j<T.length;j++) {
if(T[i]<T[j]){
ans[i] = j-i;
break;
}else if(ans[j] == 0){
ans[i] = 0;
break;
}
}
}
return ans;
}
}
随着做，我发现这个题应该可以用dp来做了。因为当前面的大于后面的，后面的已经是0.则前面是0.那么能不能换个角度，前面的大于后面的，直接去找比后面的数大的，其余比后面的还要小的就没必要浪费时间比对了？我再好好琢磨琢磨。
果然这个思路是对的，性能飞升上来了，直接贴代码：
class Solution {
public int[] dailyTemperatures(int[] T) {
int[] ans = new int[T.length];
ans[T.length-1] = 0;//最后一天不可能有更好的温度了
for(int i = T.length-2;i>=0;i--) {
for(int j = i+1;j<T.length;j++) {
if(T[i]<T[j]){
ans[i] = j-i;
break;
}else if(ans[j] == 0){
ans[i] = 0;
break;
}else {//因为这层循环完j还会+1，所以这里-1
j = j + ans[j]-1;
}
}
}
return ans;
}
}
然后这个代码性能超过百分之九十七的人了。所以就不多说，直接下一题。
删除与获得点数
题目：给定一个整数数组 nums ，你可以对它进行一些操作。每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1:
输入: nums = [3, 4, 2]
输出: 6
解释:
删除 4 来获得 4 个点数，因此 3 也被删除。
之后，删除 2 来获得 2 个点数。总共获得 6 个点数。
示例 2:
输入: nums = [2, 2, 3, 3, 3, 4]
输出: 9
解释:
删除 3 来获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。
注意:
nums的长度最大为20000。
每个整数nums[i]的大小都在[1, 10000]范围内。
思路：这个题的思路简单来说从整体看当前值+1和当前值-1是商品的损耗价值。应该是损耗越小得到的数值越大。有点类似之前做过的一道石子游戏5。不仅仅看字面值计算。我觉得我思路是挺清晰的，我去试试代码。
怎么说呢，稀里哗啦写了一堆代码，然後测试错误，结果越看这个题越觉得可以往dp上靠，先附上我错误了的代码:
错误代码
因为这个已经错了所以用截图方式示意：
错误的原因就是哪怕从删除最小的开始算，但是往后延申：比如1，2，3，4这四个1只需要删除2，但是2要删除1，3.所以我之前的方式是把1留下，2删除，3留下，但是问题来了。3需要删除2，4.所以删2留1，3是不合算的，因为后面有四。
看这个分析：因为后面有4，所以前面的结果受影响了，典型的dp递推公式出来了啊！所以说，这个题是我想复杂了，应该是一个简单的dp就能实现了的，下面是实现代码:
class Solution {
public int deleteAndEarn(int[] nums) {
if(nums.length==0) return 0;
if(nums.length==1) return nums[0];
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i:nums) map.put(i, map.getOrDefault(i, 0)+1);
int ans = 0;
Arrays.sort(nums);
int[] dp = new int[nums.length+1];
dp[0] = 0;
dp[1] = nums[0]*map.get(nums[0]);
int idx = 2;
for(int i = 1;i<nums.length;i++) {
if(nums[i] == nums[i-1]) continue;
//说明是连续的，那么只能二选一
if(nums[i]-nums[i-1] == 1) {
dp[idx] = Math.max(dp[idx-1],dp[idx-2]+nums[i]*map.get(nums[i]));
}else {//不是连续的，可以都要
dp[idx] = dp[idx-1]+nums[i]*map.get(nums[i]);
}
idx++;
}
return dp[idx-1];
}
}
这个代码虽然也是dp，虽然也ac了，但是我也不知道为啥性能贼差。。感觉思路没问题啊，估计就是细节处理上的东西了。其实感觉这里用treeMap实现应该也比较好，直接key存数值，value存这个数值对应的总和。我再去换种写法试试:
class Solution {
public int deleteAndEarn(int[] nums) {
if(nums.length==0) return 0;
if(nums.length==1) return nums[0];
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
for(int i:nums) map.put(i, map.getOrDefault(i, 0)+i);
int[] dp = new int[map.size()+1];
int idx = 1;
int pre = -1;
for(Integer key:map.keySet()) {
//说明连续了
if(key == pre+1) {
dp[idx] = Math.max(dp[idx-1], dp[idx-2]+map.get(key));
}else {
dp[idx] = dp[idx-1]+map.get(key);
}
idx++;
pre = key;
}
return dp[dp.length-1];
}
}
关于这个越优化性能越差，我也是服了。直接去看性能排第一的代码了：
class Solution {
public int deleteAndEarn(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
} else if (nums.length == 1) {
return nums[0];
}
int len = nums.length;
int max = nums[0];
for (int i = 0; i < len; ++i) {
max = Math.max(max, nums[i]);
}
// 构造一个新的数组all
int[] all = new int[max + 1];
for (int item : nums) {
all[item] ++;
}
int[] dp = new int[max + 1];
dp[1] = all[1] * 1;
dp[2] = Math.max(dp[1], all[2] * 2);
// 动态规划求解
for (int i = 2; i <= max; ++i) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * all[i]);
}
return dp[max];
}
}
理解不了为啥我的性能这么差，思路都是dp。也没觉得特别精巧。哎。就这样吧。
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！
网友评论