力扣几道括号题
使括号有效的最少添加
只有满足下面几点之一，括号字符串才是有效的：
它是一个空字符串，或者它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串 s ，移动N次，你就可以在字符串的任何位置插入一个括号。
例如，如果 s = "()))" ，你可以插入一个开始括号为 "(()))" 或结束括号为 "())))" 。
返回 为使结果字符串 s 有效而必须添加的最少括号数。
示例 1：
输入：s = "())"
输出：1
示例 2：
输入：s = "((("
输出：3
提示：
1 <= s.length <= 1000
s 只包含 '(' 和 ')' 字符。
判断当前情况
如果当前是左括号，右边可能有配对的；如果当前是右括号，判断左边有没有左括号，有就消掉，没有说明左边缺左括号，数目要加一；最后，没有消掉的左括号也要加上，表示要添加相同数目的右括号。
class Solution {
public int minAddToMakeValid(String s) {
int result = 0;
char[] chrs = s.toCharArray();
int leftCount = 0;
for(int i=0;i<chrs.length;i++) {
if(chrs[i]=='(') {
leftCount++;
} else {
if(leftCount!=0) {
leftCount--;
} else {
// leftCount==0
result++;
}
}
}
return result+leftCount;
}
}
【ATTENTION】变种：求添加括号的合规的字符串
虾皮去年的一道笔试题。（）换成了69。
这里有一个难点：就是这种添加都可以归于最左和最右的添加。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param S string字符串
* @return string字符串
*/
public String Paired69 (String S) {
// write code here
// 6696
// 69996
StringBuilder sb = new StringBuilder();
char[] chrs = S.toCharArray();
int left = 0;
for(int i=0;i<chrs.length;i++) {
if(chrs[i]=='6') left++;
else {
// 9
if(left!=0) {
left--;
} else {
sb.append("6");
}
}
}
sb.append(S);
for(int i=0;i<left;i++) {
sb.append("9");
}
return sb.toString();
}
}
合法字符串路径
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 100
grid[i][j] 要么是 '(' ，要么是 ')' 。
DFS超时
80多个测试用例第二十多个的时候就超时了，这个方法不行啊。
class Solution {
static int[][] around = new int[][]{{1,0},{0,1}};
public boolean hasValidPath(char[][] grid) {
int m = grid.length;
if(m==0) return false;
int n = grid[0].length;
// 奇数肯定不配套
if((m+n-1)%2==1||grid[0][0]==')'||grid[m-1][n-1]=='(') {
return false;
}
return dfs(grid,0,0,0);
}
private boolean dfs(char[][] grid,int i,int j,int left) {
if(left<0||i<0||j<0||i>=grid.length||j>=grid[0].length) return false;
if(i==grid.length-1&&j==grid[0].length-1&&left==1) {
return true;
}
boolean result = false;
if(grid[i][j]=='(') {
for(int k=0;k<around.length;k++) {
int nexti = i+around[k][0];
int nextj = j+around[k][1];
result |= dfs(grid,nexti,nextj,left+1);
if(result) {
break;
}
}
} else {
// )
if(left==0) return false;
for(int k=0;k<around.length;k++) {
int nexti = i+around[k][0];
int nextj = j+around[k][1];
result |= dfs(grid,nexti,nextj,left-1);
if(result) {
break;
}
}
}
return result;
}
}
动态规划
机智如我。
class Solution {
public int MAXLEN = 200;
public boolean hasValidPath(char[][] grid) {
int m = grid.length;
if(m==0) return false;
int n = grid[0].length;
// 奇数肯定不配套
if((m+n-1)%2==1||grid[0][0]==')'||grid[m-1][n-1]=='(') {
return false;
}
// 最外层的100是当前元素i,j所含有的左括号数量
boolean[][][] dp = new boolean[m+1][n+1][MAXLEN];
dp[0][1][0] = true;
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++) {
if(grid[i-1][j-1]=='(') {
for(int k=0;k<MAXLEN-1;k++) {
// i-1,j
// i,j-1 i,j
if(dp[i-1][j][k]||dp[i][j-1][k]) {
dp[i][j][k+1] = true;
}
}
} else {
// )
for(int k=1;k<=MAXLEN-1;k++) {
if(dp[i-1][j][k]||dp[i][j-1][k]) {
dp[i][j][k-1] = true;
}
}
}
}
}
return dp[m][n][0];
}
}
位图
import java.math.*;
class Solution {
public int MAXLEN = 200;
public boolean hasValidPath(char[][] grid) {
int m = grid.length;
if(m==0) return false;
int n = grid[0].length;
// 奇数肯定不配套
if((m+n-1)%2==1||grid[0][0]==')'||grid[m-1][n-1]=='(') {
return false;
}
// 最外层的100是当前元素i,j所含有的左括号数量
BigInteger[][] dp = new BigInteger[m+1][n+1];
for(int i=0;i<m+1;i++) {
dp[i][0] = new BigInteger("0");
}
for(int i=0;i<n+1;i++) {
dp[0][i] = new BigInteger("0");
}
dp[1][0] = new BigInteger("1");
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++) {
if(grid[i-1][j-1]=='(') {
dp[i][j]=(dp[i-1][j].or(dp[i][j-1])).shiftLeft(1);
} else {
dp[i][j]=(dp[i-1][j].or(dp[i][j-1])).shiftRight(1);
}
}
}
System.out.println(Arrays.deepToString(dp));
System.out.println(dp[m][n]);
return (dp[m][n].and(new BigInteger("1"))).compareTo(new BigInteger("1"))==0;
}
}
动态规划压缩
直接降维遇到了问题，就算考虑到k的前后还是后前的影响，还是有几个用例不通过。猜测可能是某些k前后影响了。用位图吧。
位图
import java.math.*;
class Solution {
public int MAXLEN = 200;
public boolean hasValidPath(char[][] grid) {
int m = grid.length;
if(m==0) return false;
int n = grid[0].length;
// 奇数肯定不配套
if((m+n-1)%2==1||grid[0][0]==')'||grid[m-1][n-1]=='(') {
return false;
}
// 最外层的100是当前元素i,j所含有的左括号数量
BigInteger[] dp = new BigInteger[n+1];
for(int i=0;i<n+1;i++) {
dp[i] = new BigInteger("0");
}
dp[1] = new BigInteger("1");
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++) {
if(grid[i-1][j-1]=='(') {
dp[j]=(dp[j].or(dp[j-1])).shiftLeft(1);
} else {
dp[j]=(dp[j].or(dp[j-1])).shiftRight(1);
}
}
}
System.out.println(Arrays.deepToString(dp));
System.out.println(dp[n]);
return (dp[n].and(new BigInteger("1"))).compareTo(new BigInteger("1"))==0;
}
}
2232. 向表达式添加括号后的最小结果
爆破
class Solution {
public String minimizeResult(String expression) {
// 直接爆破
char[] chrs = expression.toCharArray();
int plusSigIdx = 0;
while(chrs[plusSigIdx]!='+') {
plusSigIdx++;
}
int left = Integer.parseInt(expression.substring(0,plusSigIdx));
int right = Integer.parseInt(expression.substring(plusSigIdx+1,expression.length()));
int result = Integer.MAX_VALUE;
String ret = expression;
for(int i=0;i<plusSigIdx;i++) {
for(int j=0;j<expression.length()-plusSigIdx-1;j++) {
int a = left/tens(plusSigIdx-i);
if(a==0) a=1;
int b = left%tens(plusSigIdx-i);
int c = right%tens(j);
if(c==0) c=1;
int d = right/tens(j);
int tmp = a*(b+d)*c;
//System.out.printf("%d %d %d %d %d\n",a,b,d,c,tmp);
if(tmp<result) {
result = tmp;
StringBuilder sb = new StringBuilder(expression);
sb.insert(i,"(");
sb.insert(expression.length()+1-j,")");
ret = sb.toString();
}
}
}
return ret;
}
private int tens(int a) {
int ret = 1;
for(int i=0;i<a;i++) {
ret*=10;
}
return ret;
}
}
