Algorithm：旋转字符串
本月主要学习【字符串】这个系列，这是这个系列第一个算法题。
LeetCode 题目链接见796 Rotate String，这道题是 Easy 类型的题目，比较简单，个人的解法是：将 A 左边第一个字符移到右边（假设此时是 ），然后判断与 B 是否相等，再对
做前面的操作，直到把 A 的所有字符都处理了一遍。这种解法的时间复杂度是
跟 A 的长度成正比，具体代码如下：
public boolean rotateString(String A, String B) {
if ((A == null && B == null) || (A.length() == 0 && B.length() == 0)) {
return true;
}
boolean ans = false;
String rotateA = A;
for (int i = 0; i < A.length(); i++) {
char c = A.charAt(i);
rotateA = rotateA.substring(1) + c;
if (rotateA.equals(B)) {
ans = true;
}
}
return ans;
}
那么来思考一下有没有更好的解法（上面的代码，可以加了对字符串长度的判断，如果长度不同，直接返回 false，这样如果输入的字符串长度不一致，在最开始就能发现），在看别人的代码，发现一个比较牛逼的 solution，自己并没有想到这个解法，这种解法只用了一行代码就搞定了，时间复杂度完全变成了 ，这个优化跟特定的场景有关系（还是有一定的技巧性的）。
public boolean rotateString2(String A, String B) {
return (A == null && B == null) || (A.length() == B.length() && (A + A).contains(B));
}
Review
第一次 ARTS 准备得还是有些仓促，本来 Review 是打算阅读论文或者《Streaming System》这本书的内容，这周 ARTS 开始得有些晚，最后还是选了 medium 上的一篇关于 Calcite 的文章 Query Planning with Apache Calcite: Part 1，因为对这块比较熟悉，所以文章大概看了不到10min 就看完了，下周还是打算按原来的计划进行，但是需要做的改进是一定要提前开始，这几个其实在工作日之余就可以提前准备好（像 Review、Tip、Share 最好与工作相关，这样收益也比较明显），在周末的时候只是把已经准备好的东西梳理一下，这样会好很多。
Query Planning with Apache Calcite: Part 1 这篇文章，并没有太多干货，只是简单了介绍了一下 Calcite 的处理流程，然后就是介绍了一下自己的 测试代码 各个模块，主要面对的读者是 Calcite 入门的同学。
Tip：开源项目可以使用 IDEA 的 DEBUG 模式学习
这里分享一个近段看源码的心得，之前看代码的时候都是顺着代码逻辑一点一点看，因为对系统比较了解，所以看起来也不是那么费劲。后来转了一个新方向的时候，由于对这块不是很了解，对着代码流程去看，有时候其实看得云里雾里、比较费时间，看源码时，其实有一个技巧的 —— 测试 case，用 debug 模式一步步调试看详细的处理逻辑，这个方法之前别人也给说过，但是并真正去使用，近段在 Apache Calcite 源码（这个项目对于没有接触过的人来说，入门的门槛有些高，需要有编译原理、关系代数相关的知识）时，在看主要处理逻辑时，遇到一些不太懂、或则拿不准的地方就会使用 Debug 模式调试那些测试 case，这个方法非常好用，大家可以尝试一下。
Share：技术总结文章分享
Share 计划还是技术总结文章为主，这里分享一篇近段看 Apache Calcite 代码总结的一篇文章 Apache Calcite 优化器详解（二），文章是上周日写的初稿，这周做的修改，下周计划再写一篇 Calcite 的技术总结文章。
网友评论