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 来追踪这个事情。
所以有时候和老板讨论问题的时候，你需要给出一个比较好的方案，然后给出一个临时的方案，然后把这两个方案的优缺点都列出来，这样的话，老板就会觉得你是在考虑问题，而不是只是想着偷懒。
评论