Algorithm 一道算法题
这周算法题是Maximum Number of Events That Can Be Attended II.
一开始就知道应该先根据 endDay 排序,然后用动态规划的算法。然后用二维数组来做,但是有些 case 还是过不了。
class Solution {
public int maxValue(int[][] events, int k) {
Arrays.sort(events, Comparator.comparingInt(a -> a[1]));
int n = events.length;
int lastDay = events[n - 1][1];
int[][] dp = new int[lastDay + 1][k + 1];
int preEndDay = 0;
for (int i = 0; i < n; i++) {
int startDay = events[i][0];
int endDay = events[i][1];
int value = events[i][2];
for (int j = 1; j <= k; j++) {
for (int l = preEndDay + 1; l <= endDay - 1; l++) {
dp[l][j] = dp[preEndDay][j];
}
dp[endDay][j] = Math.max(dp[endDay - 1][j], dp[startDay - 1][j - 1] + value);
dp[endDay][j] = Math.max(dp[endDay][j], dp[endDay][j - 1]);
}
preEndDay = endDay;
}
return dp[lastDay][k];
}
}
复制代码
然后发现了 bug,就是说在更新 dp[endDay][j]的时候,应该是要取四个值的最大值,而不是两个值的最大值。
dp[endDay][j] = Math.max(dp[endDay][j], dp[endDay][j - 1]);
dp[endDay][j] = Math.max(dp[endDay][j], dp[endDay - 1][j]);
dp[endDay][j] = Math.max(dp[endDay][j], dp[startDay - 1][j - 1] + value);
复制代码
但是发现这样对于有些 case 会出现 timeout 的情况。然后想了想办法,实际上不需要那么大的空间,做了一些优化如下:
class Solution {
public int maxValue(int[][] events, int k) {
Arrays.sort(events, Comparator.comparingInt(a -> a[1]));
int n = events.length;
int[][] dp = new int[n + 1][k + 1];
for (int i = 0; i < n; i++) {
int startDay = events[i][0];
int value = events[i][2];
for (int j = 1; j <= k; j++) {
dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j]);
for (int l = i; l >= 0; l--) {
if (events[l][1] < startDay) {
dp[i+1][j] = Math.max(dp[i+1][j], dp[l + 1][j - 1] + value);
} else if (l == 0) {
dp[i+1][j] = Math.max(dp[i+1][j], value);
}
}
}
}
return dp[n][k];
}
}
复制代码
但是还是超时了,虽然多 pass 了两个 cases。然后想了想,可以在这里加个 break。
if (events[l][1] < startDay) {
dp[i+1][j] = Math.max(dp[i+1][j], dp[l + 1][j - 1] + value);
break;
}
复制代码
还剩最后一个 case 没有过。最后用了二分法,终于过了所有 cases,但是速度还是比较慢。
class Solution {
public int maxValue(int[][] events, int k) {
Arrays.sort(events, Comparator.comparingInt(a -> a[1]));
int n = events.length;
int[][] dp = new int[n + 1][k + 1];
for (int i = 0; i < n; i++) {
int startDay = events[i][0];
int value = events[i][2];
for (int j = 1; j <= k; j++) {
dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j]);
int left = 0, right = i, mid = i / 2;
while(left < right && mid != left) {
if (events[mid][1] >= startDay) {
right = mid - 1;
} else {
left = mid;
}
mid = (left + right) / 2;
}
if (events[mid][1] < startDay)
dp[i+1][j] = Math.max(dp[i+1][j], dp[mid + 1][j - 1] + value);
else
dp[i+1][j] = Math.max(dp[i+1][j], value);
if (events[right][1] < startDay)
dp[i+1][j] = Math.max(dp[i+1][j], dp[right + 1][j - 1] + value);
}
}
return dp[n][k];
}
}
复制代码
Review 一篇英文文章
这周看了一篇关于My Workflow stack with GPT的文章。主要是看怎么利用 GPT 来提高我们的工作效率。
我现在利用起来的主要有这几个,一个是 github copilot,VS Code 和 Idea 都装了对应的插件,代码的生成以及测试的生成还是挺有用的。
另一个是 Chrome 的插件,ChatGPT Summary for Chrome,主要是用来生成一些文章的 summary,可以看看是不是你想要的,再细读。
第三个是在 shell 里面调用 openai 的 api,主要是用来查询一些命令的使用。
Technique/Tips 一个技术点
在和 PM 合作完成一个新功能的时候,假如有什么不确定或者变数,一定要及时提出来,让大家都知道这件事情,确定基本需求之后可以的话最好快速给一个 demo,因为有些时候想的时候是一回事,真的做出来看到 POC 之后又是另一种感觉。
以及不能只光顾着满足 PM 的需求,还要考虑到其他的一些因素,比如说系统设计。因为某些简单的需求,可能会导致系统设计上的一些问题,比如说性能,可扩展性等等。这些都是要尽量避免的。
Share 一个观点
这周遇到一个事情,就是一个比较紧急的活,然后中间有一步,假如要用比较好的方案的话,需要考虑各种需求,不是几天时间能完成的。临时的解决方案就是直接写数据库,一开始老板不同意。然后我把要完成的这件事情所需要的具体步骤都列好,然后把用比较好的方式来做的方案也列了一下,然后把这两个方案的优缺点都列了一下,然后老板就同意了。比较好的方案先不做,先做临时的方案,然后再慢慢的把比较好的方案做出来。创建一个 work item 来追踪这个事情。
所以有时候和老板讨论问题的时候,你需要给出一个比较好的方案,然后给出一个临时的方案,然后把这两个方案的优缺点都列出来,这样的话,老板就会觉得你是在考虑问题,而不是只是想着偷懒。
评论