ARTS：Algorithm、Review、Tip、Share
- Algorithm 算法题
- Review 英文文章
- Tip 回想一下本周工作中学到的一个小技巧
- Share思考一个技术观点、社会热点、一个产品或是一个困惑
Algorithm
练习：最长回文子串
manacher算法是解决最长回文子串的经典算法，如果使用暴力算法求解，时间复杂度为O(n^2)，而manacher算法能够将时间复杂度优化为O(n)。
首先，为了解决奇偶数不同情况下回文字符串的识别，通过在每个字符前后添加特殊符号来分隔实现统一处理。其次准备一个pArray数组来保存每个字符对应的最长回文子串的大小，最小也就是为1。额外两个有用的变量
- 用R标记当前达到的最大右边界；
- 最大右边界对应的回文字符串重点位置C；
遍历参数字符串中每个字符，分情况处理：
- i在R外（只可能是右侧）：暴力去识别回文结构，识别完后，更新R、C
- i在R内，此时又分为3种情况：
- i 根据C在其左侧对应的 i’ 已经求结果，对应的回文结构完全在L…R内（L是对应R左侧的位置），i 的最长回文子串大小此时直接为pArray(i’)；
- i’ 的回文子串左侧在L外，此时i的最长回文子串大小为R-i；
- i’ 的回文子串左侧正好在L处，此时i的最长回文子串大小至少为R-i，还需要再继续右扩继续识别。
编码实现
public static int manacher(String s) {
if (s == null || s.isEmpty()) {
return 0;
}
char[] str = manacherString(s);
int[] pArr = new int[str.length];
int C = -1;
int R = -1;
int max = Integer.MIN_VALUE;
for (int i = 0; i < str.length; i++) {
pArr[i] = i < R ? Math.min(pArr[2 * C - i], R - i) : 1;
while (i + pArr[i] < str.length && i - pArr[i] > -1) {
if (str[i + pArr[i]] == str[i - pArr[i]]) {
pArr[i]++;
} else {
break;
}
}
if (i + pArr[i] > R) {
R = i + pArr[i];
C = i;
}
max = Math.max(pArr[i], max);
}
return max - 1;
}
public static char[] manacherString(String str) {
char[] charArr = str.toCharArray();
char[] res = new char[str.length() * 2 + 1];
int index = 0;
for (int i = 0; i != res.length; i++) {
res[i] = (i & 1) == 0 ? '#' : charArr[index++];
}
return res;
}
复杂度分析
R的处理不断向右，时间复杂度为O(n)。
Review
DecimalFormat Is Not Thread Safe
Tip
最近在看项目中的代码，计算金额的部分用到了BigDecimal、DecimalFormat 类，并且直接定义DecimalFormat为了类的静态成员变量类型，在多个线程之间公用，看了下DecimalFormat的注释，明确说明了这个类并不是线程安全的，那能不能这么直接使用呢？翻看了一些资料，介绍一般都是避免在线程间共享使用的，如果为了复用对象，最好是使用ThreadLocal包一层。
也没翻到一些具体怎么复现出问题的情况，由于我们只用到了format方法，自己模拟了一下并发的情况，并没有什么问题，但对于这种情况JDK是并不能保证未来的版本不会出问题的，所以我认为还是应该在多线程共享的情况下小心使用。
最近感触：做好工作，但不能只局限于工作的琐碎，在工作中成长、提高，善于发现问题，更善于解决问题；
Share
看了几篇吴军老师的文章，对生活中的无常、无奈有了些感受，也更多的思考自己生活的节奏，过去总是过的那么匆忙，却总是忘了让自己经常停下来放慢一些节奏。工作上可能要求我们快速处理，但生活上、个人的思考上，我想更适合慢一些的节奏吧。
|