My code:
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() <= 1)
return 0;
int len = s.length();
int max = 0;
int[] dp = new int[len];
for (int i = len - 2; i >= 0; i--) {
int j = i + dp[i + 1] + 1;
if (j < len && s.charAt(i) == '(' && s.charAt(j) == ')')
dp[i] = dp[i + 1] + 2;
else
continue;
j = i + dp[i];
if (j < len && dp[j] != 0) {
dp[i] += dp[j];
}
max = Math.max(max, dp[i]);
}
return max;
}
}
這道題目我沒(méi)有做出來(lái)。應(yīng)該說(shuō)，我做出來(lái)了，但是超時(shí)了。
我也想到了用dp，但是用的是二維數(shù)組。后來(lái)看了提示，想到用一維數(shù)組，但是一個(gè)關(guān)鍵我忘記了。
當(dāng)dp[i] 成功賦值后，即dp[i] == '(' && dp[j] == ')', 需要觀察觀察，dp[i + dp[i]] 是否為0，如果不是，需要合并。
還有個(gè)做法是stack的。不是很難。具體就不寫了。
一個(gè)早上，洗了個(gè)澡，洗了衣服。投了兩個(gè)實(shí)習(xí)。馬上要上課了。
太忙了，但感覺(jué)什么都沒(méi)收獲。
參考網(wǎng)頁(yè)：
DP:
http://blog.csdn.net/abcbc/article/details/8826782
Stack:
http://www.programcreek.com/2014/06/leetcode-longest-valid-parentheses-java/
Anyway, Good luck, Richardo!
Stack 做法：
My code:
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0)
return 0;
Stack<int[]> ss = new Stack<int[]>();
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
if (curr == '(') {
int[] temp = {i, 0};
ss.push(temp);
}
else {
if (ss.isEmpty() || ss.peek()[1] == 1) {
int[] temp = {i, 1};
ss.push(temp);
}
else {
ss.pop();
if (ss.isEmpty()) {
maxLen = Math.max(maxLen, i + 1);
}
else {
maxLen = Math.max(maxLen, i - ss.peek()[0]);
}
}
}
}
return maxLen;
}
}
Anyway, Good luck, Richardo!
首先寫一個(gè)超時(shí)的二維DP算法。
My code:
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int len = s.length();
int[][] dp = new int[len][len];
int max = 0;
for (int i = 0; i < len; i++) {
for (int j = i; j < len; j++) {
char curr = s.charAt(j);
int end = i;
if (curr == ')') {
if (j > 0 && dp[i][j - 1] > 0) {
dp[i][j] = dp[i][j - 1] - 1;
}
else {
dp[i][j] = -1;
}
}
else {
if (j > 0 && dp[i][j - 1] < 0) {
dp[i][j] = -1;
}
else if (j > i) {
dp[i][j] = dp[i][j - 1] + 1;
}
else {
dp[i][j] = 1;
}
}
if (dp[i][j] == 0) {
end = Math.max(end, j);
max = Math.max(max, end - i + 1);
}
}
}
return max;
}
}
這么做的原因，在于。
我先用brute force進(jìn)行解答，然后發(fā)現(xiàn)，重復(fù)操作的地方，然后再用DP cache
從 O(n ^ 3) -> O(n ^ 2)
但是仍然超時(shí), 仍需要優(yōu)化。
DP solution:
My code:
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int len = s.length();
int[] dp = new int[len];
int max = 0;
for (int i = dp.length - 2; i >= 0; i--) {
char curr = s.charAt(i);
if (curr == ')') {
dp[i] = 0;
}
else {
int j = i + 1 + dp[i + 1];
if (j < dp.length) {
if (s.charAt(j) == ')') {
dp[i] = j - i + 1;
}
else {
continue;
}
}
j = i + dp[i];
if (j < dp.length) {
dp[i] = dp[i] + dp[j];
}
max = Math.max(max, dp[i]);
}
}
return max;
}
}
還是看的以前的思路。
兩個(gè)注意點(diǎn)；
- 從倒數(shù)第二位開(kāi)始后退遍歷就行了。
- 跳躍時(shí)，不用一直跳到最后。跳一次。然后如果是 ')'
就更新d[[i]
然后如果 dp[j + 1] > 0,
再次更新 dp[i]
測(cè)試程序有時(shí)候可以過(guò)，有時(shí)候時(shí)間超了。我想本身的代碼應(yīng)該問(wèn)題不大，就是 O(n)的復(fù)雜度。
下面開(kāi)始想一下 Stack 的做法：
My code:
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) {
return 0;
}
Stack<Integer> st = new Stack<Integer>();
int left = -1;
int max = 0;
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
if (curr == '(') {
st.push(i);
}
else {
if (st.isEmpty()) {
left = i;
}
else {
st.pop();
if (st.isEmpty()) {
max = Math.max(max, i - left);
}
else {
max = Math.max(max, i - st.peek());
}
}
}
}
return max;
}
}
reference:
https://discuss.leetcode.com/topic/7234/simple-java-solution-o-n-time-one-stack
只是不知道為什么，最后一個(gè)case，總是 time limited。我這個(gè)明明是 O(n) 啊。
不管了。
具體思想就是，
stack 里面只存 ' ( '
棧里面存的都是 index
當(dāng)碰到 ( 時(shí)，就直接push
當(dāng)碰到 ) 時(shí)，
如果此時(shí)棧為空了，就代表上一層的valid parenthesis 已經(jīng)結(jié)束了，那么移動(dòng)left指針，只想當(dāng)前 ) index
如果未空，那么上一層的 valid parenthesis 并沒(méi)有結(jié)束，先將這個(gè)匹配的 ( 彈出。然后計(jì)算下該段 valid parenthesis 的有效長(zhǎng)度
此時(shí)又有兩種情況。
如果?？樟耍硎具@一層的valid parenthesis 結(jié)束了。那么
[left, i]
如果棧未空，那么該層還沒(méi)有徹底結(jié)束。那么起始位置應(yīng)該是 s.peek()
[s.peek(), i]
因?yàn)樵?[s.pop(), i] 之前可能還存在其他并且的有效字段，只不過(guò)已經(jīng)提前彈出去了，所以算最大長(zhǎng)度時(shí)，要一起考慮進(jìn)去。
差不多就這樣了。
Anyway, Good luck, Richardo! -- 08/18/2016
發(fā)現(xiàn)之前的理解還是膚淺了，只記得有跳躍的過(guò)程，忘記了還有合并的過(guò)程。
1 . 跳躍，將自己的有限范圍找出來(lái)
2 . merge, 將其他和自己相鄰的有限部分merge
求最大值。
同樣的思路并不適用于 longest palindrome.
因?yàn)閜anlindrome一個(gè)字母也可以是一個(gè)panlidrome
Stack 的做法也是只理解了意思，自己敲還是沒(méi)寫出來(lái)。
最大的特點(diǎn)是，棧里面只放 '('
好處是，當(dāng)我碰到 ')'時(shí)，
我不用判斷棧頂元素是什么，因?yàn)樗欢ㄊ?'('
我將它彈出來(lái)，看棧是否為空。
所以這里，我需要一個(gè)變量來(lái)暫存每一塊valid區(qū)域的最左邊界的再左邊一個(gè)點(diǎn)。
當(dāng)?？盏臅r(shí)候，len = i - left;
否則， len = i - st.peek();
max = Math.max(max, len);
Anyway, Good luck, Richardo! -- 09/18/2016
