Algorithm
leetcode301(https://leetcode.com/problems/remove-invalid-parentheses/)，刪除最少數(shù)量字符使字符串有效，返回所有可能結(jié)果。有效判定左括號'('和右括號')'匹配。
- Input:"()())()" Output:["()()()", "(())()"]
- Input:"(a)())()" Output:["(a)()()", "(a())()"]
- Input:")(" Output: [""]
??看到這個問題第一眼想到的是棧，類似判定字符串是否回文，但是返回的結(jié)果只有一個顯然是不符合結(jié)果的。后面經(jīng)過考慮之后決定通過棧都方式返回1個結(jié)果，再做進一步計算。
??最終大致思路就是對所有對可能情況通過遞歸查找，最后排除錯誤結(jié)果。同時，為了減少遞歸分支，通過增加對最終結(jié)果無效的情況提前判斷終止遞歸。
code
public List<String> removeInvalidParentheses(String s) {
// 求出1個結(jié)果
String result = remove(s);
// 計算最小刪減無效字符數(shù)量
int strLeft = 0, strRight = 0, resultLeft = 0, resultRight = 0;
char c;
for (int i = 0; i < s.length(); i++) {
c = s.charAt(i);
if (c == '(') {
strLeft++;
} else if (c == ')') {
strRight++;
}
}
for (int i = 0; i < result.length(); i++) {
c = result.charAt(i);
if (c == '(') {
resultLeft++;
} else if (c == ')') {
resultRight++;
}
}
// 找出可能結(jié)果
List<String> list = new ArrayList<>();
recursion(list, s, "", 0, 0, 0, strLeft - resultLeft, strRight - resultRight);
// 排除結(jié)果中無效的字符串
Iterator<String> it = list.iterator();
String item;
while (it.hasNext()) {
item = it.next();
if (remove(item).length() != item.length()) {
it.remove();
}
}
return list;
}
/**
* 刪除無效的字符串(返回1個結(jié)果,明確最少刪除字符數(shù))
```java)
*/
private String remove(String s) {
if (s.length() <= 0) {
return "";
}
Stack<Character> stack = new Stack<>();
StringBuilder ret = new StringBuilder();
Character c;
for (int i = 0; i < s.length(); i++) {
c = s.charAt(i);
if (stack.size() == 0) {
if (c == '(') {
stack.push(c);
} else if (c == ')') {
} else {
ret.append(c);
}
} else {
if (c == '(') {
stack.push(c);
} else if (c == ')') {
Character temp;
StringBuilder tempS = new StringBuilder();
while (stack.size() > 0) {
temp = stack.pop();
if (temp == '(') {
tempS.insert(0, temp).append(c);
break;
} else {
tempS.insert(0, temp);
}
}
ret.append(tempS);
} else {
Character temp = stack.peek();
if (temp == ')') {
ret.append(c);
} else {
stack.push(c);
}
}
}
}
Character temp;
StringBuilder tempS = new StringBuilder();
while (stack.size() > 0) {
temp = stack.pop();
if (temp != '(' && temp != ')') {
tempS.insert(0, temp);
}
}
ret.append(tempS);
return ret.toString();
}
/**
* 可能結(jié)果
*
* @param list 結(jié)果
* @param s 原字符串
* @param result 遞歸中結(jié)果
* @param index index
* @param deleteLeft 左括號刪除數(shù)
* @param deleteRight 右括號刪除數(shù)
* @param minDeleteLeft 左括號最小刪除數(shù)
* @param minDeleteRight 右括號最小刪除數(shù)
*/
private void recursion(List<String> list, String s, String result, int index, int deleteLeft, int deleteRight, int minDeleteLeft, int minDeleteRight) {
if (deleteLeft > minDeleteLeft) return;
if (deleteRight > minDeleteRight) return;
// 剩余字符串小于刪除數(shù)
if (minDeleteLeft + minDeleteRight - deleteLeft - deleteRight > s.length() - index) return;
if (index >= s.length()) {
if (deleteLeft == minDeleteLeft && deleteRight == minDeleteRight) {
if (!list.contains(result)) {
list.add(result);
}
}
} else {
Character c;
int i;
for (i = index; i < s.length(); i++) {
c = s.charAt(i);
if (c == '(') {
recursion(list, s, result + c, i + 1, deleteLeft, deleteRight, minDeleteLeft, minDeleteRight);
deleteLeft++;
//recursion(list, s, result, i + 1, deleteLeft + 1, deleteRight, minDeleteLeft, minDeleteRight);
//break;
} else if (c == ')') {
recursion(list, s, result + c, i + 1, deleteLeft, deleteRight, minDeleteLeft, minDeleteRight);
deleteRight++;
//recursion(list, s, result, i + 1, deleteLeft, deleteRight + 1, minDeleteLeft, minDeleteRight);
//break;
} else {
result = result + c;
}
}
if (i == s.length() && deleteLeft == minDeleteLeft && deleteRight == minDeleteRight) {
if (!list.contains(result)) {
list.add(result);
}
}
}
}
代碼效率不是特別高，還能繼續(xù)優(yōu)化，優(yōu)化方向一致。
??最后個人總結(jié)，只能深度搜索所有可能才能找到結(jié)果的情況，可以通過各種方式，提前結(jié)束子搜索，類似樹分叉提前砍斷子樹，來提高效率。
Review
??作為一個java程序員，一定是用過spring，在springboot配置配置數(shù)據(jù)庫連接池默認(rèn)使用 HikariCP，HikariCP有關(guān)于數(shù)據(jù)庫連接池說明About-Pool-Sizing。
??按照我之前的想法連接池連接數(shù)越多，肯定程序越快，文中指出連接池數(shù)量在不考慮磁盤開銷、網(wǎng)絡(luò)開銷等情況，連接池數(shù)和cpu核數(shù)相同性能最好，如果連接數(shù)遠(yuǎn)大于cpu核數(shù)，cpu上下文切換會帶來額外開銷。
??在考慮磁盤開銷和網(wǎng)絡(luò)開銷情況，ssd是會減少磁盤開銷，同時帶寬更高會減少網(wǎng)絡(luò)開銷，一個系統(tǒng)數(shù)據(jù)庫連接數(shù)應(yīng)當(dāng)考慮磁盤、帶寬和cpu核數(shù)來配置適當(dāng)?shù)倪B接池連接數(shù)，不然不計后果增加連接數(shù)會適得其反。
（文中的數(shù)據(jù)庫連接池連接數(shù)提供來一個公式，沒細(xì)看，覺得只能作為參考）
再分享一篇文章java in flames，講java中結(jié)合-XX:+PreserveFramePointer參數(shù)，對java程序包括底層以及系統(tǒng)進行可視化分析。
Tip
自學(xué)docker遇到需要寫shell腳本。
linux命令 ps -ef|grep xxxxx | grep -v grep|awk '{print $2}'
ps -ef|grep用來找pid。grep -v 反向grep即排除有指定字符的結(jié)果，$2第二列就是pid。寫shell腳本找到pid，然后kill -9 pid。
java包啟動-classpath參數(shù)后jar包，linux使用:分開jar，windows使用;分開jar
分享個git常用命令忽略文件修改
git update-index --assume-unchanged FILENAME
git update-index --no-assume-unchanged FILENAME
Share
結(jié)合前段時間剛跟學(xué)的mysql對自己影響做個思考總結(jié)，對比自己一個java程序員思考
1.mysql中server層和innodb引擎之間同步，redolog先寫入處于prepare狀態(tài)，binlog再寫完之后提交講redolog改成commit，即使出現(xiàn)異常（如：binlog未寫完mysql異常重啟，binlog恢復(fù)數(shù)據(jù)沒未保存的數(shù)據(jù)；binlog寫完mysql異常重啟，binlog恢復(fù)數(shù)據(jù)后發(fā)現(xiàn)redolog處于prepare狀態(tài)后會講redolog改成commit，事物完成，兩邊一致）。在我的理解中和分布式事物很相似，保證事物完整性；
2.事物的隔離中有可重復(fù)讀，事物啟動時建立單獨視圖其他事物不可見，java中有個ThreadLocalMap中就是線程對對象對拷貝，每個線程有自己單獨對對象；
3.mysql鎖可以表鎖和全局鎖，對應(yīng)不同粒度。在java開發(fā)中，同樣可以鎖一個整個方法也可以通過不同對對象java更加細(xì)粒度鎖；
4.在mysql中有change_buffer可以對修改暫時在內(nèi)存中進行，后面再寫到磁盤中，同時寫入順序?qū)懣梢詼p少開銷。同樣，在開發(fā)中，對數(shù)據(jù)庫頻繁跟新可以加一層緩存，暫時在緩存中更新，然后通過定時任務(wù)定時將緩存寫入磁盤，為兩保證緩存不會因為程序重啟不丟失，可以使用redis來代替程序緩存；
5.mysql內(nèi)存數(shù)據(jù)頁，將數(shù)據(jù)加載在優(yōu)先隊列中，同時隊列分兩部分，前面一部分young屬于優(yōu)先隊列原則，后面一部分old在數(shù)據(jù)頁讀如內(nèi)存時放在old頭，同時在讀內(nèi)存數(shù)據(jù)時，如果old數(shù)據(jù)2次訪問間隔時間不超過1s，就將數(shù)據(jù)頁移到y(tǒng)oung頭，這樣對于訪問不頻繁對數(shù)據(jù)很容易被淘汰。這樣數(shù)據(jù)結(jié)構(gòu)在開發(fā)中目前沒有遇到過，但是很有借鑒意義。
6.mysql通過一些緩存將隨機訪問變成順序訪問就如數(shù)組這樣對數(shù)據(jù)結(jié)構(gòu)訪問比鏈表更快一樣。
目前就想到這樣，后面有還會繼續(xù)學(xué)習(xí)mysql有更深對理解會繼續(xù)思考。
最后想說，各種語言在不斷演變過程都有相互借鑒，雖然語言不同目的不同，但是思想是永遠(yuǎn)不變的。
