第3周
Algorithm:
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设s 的最大长度为 1000。
解：
可以用“中心扩展法”，难点是要处理好奇数字符回文和偶数字符回文的情况。
class Solution {
public String longestPalindrome(String str) {
int n = str.length();
if (n <= 1) return str;
int lMax = 0;
int beginIdx = 0, endIdx = 0;
for (int i = 0; i < n; ++i) {
int r = 1;
int r1 = 1;
// abcba的情况
while (true) {
if ((i - r) >= 0 && (i + r) <= (n - 1) && str.charAt(i - r) == str.charAt(i + r)) {
if (r*2+1 > lMax) {
lMax = 2*r+1;
beginIdx = i - r;
endIdx = i + r;
}
++r;
} else {
break;
}
} // while(true)
//abba的情况
while (true) {
if ((i - r1 + 1) >= 0 && (i + r1) <= (n - 1) &&
str.charAt(i - r1 + 1) == str.charAt(i + r1)) {
if (r1*2 > lMax) {
lMax = r1*2;
beginIdx = i - r1 + 1;
endIdx = i + r1;
}
++r1;
} else {
break;
}
} // while(true)
}
String subStr = str.substring(beginIdx, endIdx+1); //如果没找到回文，默认返回第一个字符
return subStr;
}
}
后续：
这道题有O(n)的算法，后面要再思考、学习一下。
Review:
因为项目中发现的mysql死锁问题，在搜索引擎里挑了一篇排在前面的关于mysql锁的英文文章读了一下。
Explaining InnoDB Explicit Locking Mechanisms
文章讲解了mysql锁的基本机制，但其实太基本了，没有深入原理，内容太少。所以其实有些英文文章也不是都很好的。
Tip:
项目中发生mysql死锁。
场景：并发insert_update(insert，如果没有主键重则插入，如果主键重则update)同一条记录。
原因：insert会在记录上加上排他意向锁、update会加上排他锁，在多线程并发操作同一条记录时会相互冲突产生死锁。具体产生死锁的过程，还需要详细分析，详见下面Share部分的链接文章。
解决办法：
1、不同线程用id来区分操作的数据，避免不同事务操作同一条记录；
2、先查询是否存在记录；如果存在，则执行update；如果不存在，则执行insert。
Share:
这篇中文博文写的很相识，比上文那篇英文文章深入很多，值得细读。更深入研究的话，可以进一步学习文章引用的资料，其实mysql的官方文档中关于innodb锁机制的描述最应该认真学习。
网友评论