第3周
Algorithm:?
給定一個字符串?s疑枯，找到?s?中最長的回文子串椭更。你可以假設(shè)s?的最大長度為 1000抄罕。
解：
可以用“中心擴(kuò)展法”屁药，難點是要處理好奇數(shù)字符回文和偶數(shù)字符回文的情況。
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); //如果沒找到回文情屹，默認(rèn)返回第一個字符
????????return subStr;? ? ? ?
? ? }
}
后續(xù)：
這道題有O(n)的算法坪仇，后面要再思考、學(xué)習(xí)一下垃你。
Review: ?
?因為項目中發(fā)現(xiàn)的mysql死鎖問題椅文，在搜索引擎里挑了一篇排在前面的關(guān)于mysql鎖的英文文章讀了一下。
Explaining InnoDB Explicit Locking Mechanisms
文章講解了mysql鎖的基本機(jī)制惜颇，但其實太基本了皆刺，沒有深入原理，內(nèi)容太少凌摄。所以其實有些英文文章也不是都很好的羡蛾。
Tip:
項目中發(fā)生mysql死鎖。
場景：并發(fā)insert_update(insert锨亏，如果沒有主鍵重則插入痴怨，如果主鍵重則update)同一條記錄。
原因：insert會在記錄上加上排他意向鎖器予、update會加上排他鎖浪藻，在多線程并發(fā)操作同一條記錄時會相互沖突產(chǎn)生死鎖。具體產(chǎn)生死鎖的過程乾翔，還需要詳細(xì)分析爱葵，詳見下面Share部分的鏈接文章。
解決辦法：
1末融、不同線程用id來區(qū)分操作的數(shù)據(jù)钧惧，避免不同事務(wù)操作同一條記錄；
2勾习、先查詢是否存在記錄浓瞪；如果存在，則執(zhí)行update巧婶；如果不存在乾颁，則執(zhí)行insert。
Share:
這篇中文博文寫的很相識艺栈，比上文那篇英文文章深入很多英岭，值得細(xì)讀。更深入研究的話湿右，可以進(jìn)一步學(xué)習(xí)文章引用的資料诅妹，其實mysql的官方文檔中關(guān)于innodb鎖機(jī)制的描述最應(yīng)該認(rèn)真學(xué)習(xí)。
