32. 最长有效括号

public class Solution { public int longestValidParentheses(String s) { int maxans = 0; int dp[] = new int[s.length()]; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == ')') { if (s.charAt(i - 1) == '(') { dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') { dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2; } maxans = Math.max(maxans, dp[i]); } } return maxans; } } class Solution { public int longestValidParentheses(String s) { int max = 0; Stack<Integer> stack = new Stack<>(); stack.push(-1); for(int i = 0;i <s.length();i++){ char c = s.charAt(i); if(c == '('){ stack.push(i); }else{ stack.pop(); if(stack.isEmpty()){ stack.push(i); }else{ max = Math.max(max,i-stack.peek()); } } } return max; } } class Solution { public int longestValidParentheses(String s) { int left = 0, right = 0, max = 0; //从前往后右括号大于左括号，left和right都归0 for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { left++; } else { right++; } //left大于right先不管 if (left == right) { max = Math.max(max, 2 * right); } else if (right > left) { //right大于left重新记 left = right = 0; } } left = right = 0; //从后往前左括号大于右括号，left和right都归0 for (int i = s.length() - 1; i >= 0; i--) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { max = Math.max(max, 2 * left); } else if (left > right) { left = right = 0; } } return max; } }

96. 不同的二叉搜索树

public class Solution { public int numTrees(int n) { int[] G = new int[n + 1]; G[0] = 1; G[1] = 1; for (int i = 2; i <= n; ++i) { for (int j = 1; j <= i; ++j) { G[i] += G[j - 1] * G[i - j]; } } return G[n]; } }

557. 反转字符串中的单词 III

class Solution { public String reverseWords(String s) { String[] strs = s.split(" "); StringBuilder sb = new StringBuilder(); for(int i = 0;i < strs.length;i++){ sb.append(new StringBuilder(strs[i]).reverse().toString()); sb.append(" "); } return sb.toString().trim(); } } class Solution { public String reverseWords(String s) { char[] sentence = s.toCharArray(); int i = 0, j = 0; while(j < sentence.length) { while(i < sentence.length && sentence[i] == ' ') ++i; while(j < sentence.length && sentence[j] != ' ') ++j; reverse(sentence, i, j - 1); i = j; ++j; } s = String.valueOf(sentence); return s; } private void reverse(char[] arr, int start, int end) { if (arr.length == 0) return; while (start < end) { char temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; ++start; --end; } } } class Solution { public String reverseWords(String s) { char[] a = s.toCharArray(); int n = a.length; int left = 0; int right = 0; char temp; for (int i = 0; i < n; i++) { if (a[i] == ' ') { right = i - 1; while (left < right) { temp = a[left]; a[left++] = a[right]; a[right--] = temp; } left = i + 1; } } right = n - 1; while (left < right) { temp= a[left]; a[left++] = a[right]; a[right--] = temp; } return new String(a); } }

你知道的越多，你不知道的越多。