写点什么

ATRS Week 3

作者:Geek_c25301
  • 2023-09-04
    日本
  • 本文字数:2581 字

    阅读完需:约 8 分钟

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 来追踪这个事情。


所以有时候和老板讨论问题的时候,你需要给出一个比较好的方案,然后给出一个临时的方案,然后把这两个方案的优缺点都列出来,这样的话,老板就会觉得你是在考虑问题,而不是只是想着偷懒。

发布于: 刚刚阅读数: 2
用户头像

Geek_c25301

关注

还未添加个人签名 2022-03-19 加入

还未添加个人简介

评论

发布
暂无评论
ATRS Week 3_Geek_c25301_InfoQ写作社区