剑指 Offer II 085. 生成匹配的括号
image.png
本题的思路不多BB，其实主要可以用回溯，主要来讲一下不同的回溯写法。相信第一种是很多人的回溯模板，把res和path声明称全局的变量，然后每次操作的时候path去回溯去掉最后一个值。然后再看写法二，他把path放在形参的位置，发现dfs后并不需要添加对应的回溯操作。其实大家可以把整个程序调试运行一遍对比一下，就拿参数里面的open来说，他作为形参，他的值可传递的时候有效的其实就是不停的函数栈加深的时候，当open=3的dfs函数栈执行完return出栈之后，open自然而然的返回地下的函数栈就是open=2的时候，是不需要你手动再把3变成2的，可以这么理解，要是把变量放在形参列表中，是不要你手动去做回溯操作的。
//写法一
package 剑指0ffer.括号题目;
import java.util.ArrayList;
import java.util.List;
public class 生成匹配的括号 {
List<String> res = new ArrayList<>();
StringBuffer path = new StringBuffer();
public List<String> generateParenthesis(int n) {
if (n <= 0) return res;
dfs(n, 0, 0);
return res;
}
private void dfs(int n, int open, int close) {
if (path.length() == 2 * n) {
res.add(path.toString());
return;
}
if (open < n) {
path.append("(");
dfs(n, open + 1, close);
path.deleteCharAt(path.length()-1);
}
if (close < open) {
path.append(")");
dfs(n, open, close + 1);
path.deleteCharAt(path.length()-1);
}
}
public static void main(String[] args) {
生成匹配的括号 so = new 生成匹配的括号();
System.out.println(so.generateParenthesis(3));
}
}
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//写法二
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
if (n <= 0) return res;
dfs(n, "", res, 0, 0);
return res;
}
private void dfs(int n, String path, List<String> res, int open, int close) {
if (open > n || close > open) return;
if (path.length() == 2 * n) {
res.add(path);
return;
}
dfs(n, path + "(", res, open + 1, close);
dfs(n, path + ")", res, open, close + 1);
}
}
1111. 有效括号的嵌套深度
image.png
本题的难点在于理解题目，其实题目要的就是尽量的让括号的深度是最浅的，可以带入平衡二叉树的理解，左右子树尽量一样长这时候的整个树的深度就是最小的。对于括号序列来说——(()),就是让连续的左括号分别分配给1和0，然后右括号的下标其实还是根据他最近的左括号来定的。所以代码可以下面这样写：
class Solution {
public int[] maxDepthAfterSplit(String seq) {
//用stack只是为了更好的模拟题目，其实是没必要的。
Stack<Character> stack = new Stack<>();
int[] res = new int[seq.length()];
char[] seqarr = seq.toCharArray();
for(int i=0;i<seqarr.length;i++){
if(seqarr[i]=='('){
res[i] = stack.size()%2;
stack.push('(');
}else {
stack.pop();
res[i] = stack.size()%2;
}
}
return res;
}
}
1021. 删除最外层的括号
image.png
思路和code都还是比较简单的，其实就是判断是不是呀），如果是，先出栈，出栈之后要是栈还是非空的，那就把之前这个）或者（算到结果中，然后最后再判断遇到左括号的时候入栈。
class Solution {
public String removeOuterParentheses(String s) {
Stack<Character> stack = new Stack<>();
String res = "";
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (c == ')') {
stack.pop();
}
if (!stack.empty()) {
res += c;
}
if (c == '(') {
stack.add('(');
}
}
return res;
}
}
921. 使括号有效的最少添加
image.png
思路：将「有效括号问题」转化为「分值有效性」的数学判定。使用 score 代指处理过程中的得分，将 ( 记为 +1，将 ) 记为 -1。一个有效的括号应当在整个过程中不出现负数，因此一旦 score 出现负数，我们需要马上增加 ( 来确保合法性；当整个 s 处理完后，还需要添加 socre 等同的 ) 来确保合法性。
class Solution {
public int minAddToMakeValid(String s) {
int score = 0;
int ans = 0;
char[] sarr= s.toCharArray();
for(int i=0;i<sarr.length;i++){
if(sarr[i]=='('){
score++;
}else if(sarr[i]==')'){
if(score==0){
ans++;
}else {
score--;
}
}
}
return ans+score;
}
}
替换字符串中的括号内容
image.png
解题思路就很简单了，首先是把list遍历一边变成一个hash表，然后遍历整个字符数组，遇到左括号的时候提取括号里面的内容进行替换，最后返回替换后的整个结果。
class Solution {
public String evaluate(String s, List<List<String>> knowledge) {
char[] sa = s.toCharArray();
Map<String,String> map = new HashMap<>();
for(List<String> lists:knowledge){
map.put(lists.get(0),lists.get(1));
}
int i=0;
StringBuffer res = new StringBuffer();
while (i<sa.length){
StringBuffer temp = new StringBuffer();
if(sa[i]=='('){
i++;
while (sa[i]!=')'){
temp.append(sa[i]);
i++;
}
i++;
res.append(map.getOrDefault(temp.toString(),"?"));
}else {
res.append(sa[i]);
i++;
}
}
return res.toString();
}
}
678. 有效的括号字符串
image.png
本题是在原有的括号匹配的基础上引入了通配符星号，思路还是围绕栈来使用，当然我们可以思考一下，以前栈在使用的时候，往栈里面加的元素是括号本身，然后从左向右遍历整个序列，要是出现左括号不够用的时候就匹配失败了。然后本题也可以先从左到右尽量先把右括号匹配全了，然后剩下的就是左括号以及星号，这时候要从右向左继续匹配，不过此时会有一个问题，就是当时入栈的时候不知道* 和（的前后关系，单纯的凭借数量关系会出现'**'（（这样失败的匹配，所以重新考虑入栈的不要是括号本身了，可以设置两个栈，一个专门记录左括号一个专门记录星号，然后入栈的是索引值。于是代码如下：
class Solution {
public boolean checkValidString(String s) {
Stack<Integer> left = new Stack<>();
Stack<Integer> stars = new Stack<>();
char[] sa = s.toCharArray();
for(int i=0;i<sa.length;i++){
if(sa[i]=='('){
left.push(i);
}else if(sa[i]=='*'){
stars.push(i);
}else {
if(left.size()>0){
left.pop();
}else {
if(stars.size()>0){
stars.pop();
}else {
return false;
}
}
}
}
if(left.size()>stars.size())
return false;
while (left.size()>0&&stars.size()>0){
if(left.pop()>stars.pop()){
return false;
}
}
return true;
}
}
2116. 判断一个括号字符串是否有效
image.png
在上一道题的基础上再做这一道题，相信就思路很清晰了，我们根据locked数组把原来的括号字符数组中0对应的括号变成星号。例如题目的序列可以变成："))"。然后继续用两个栈处理，最后得到的left和starts继续从尾部到头比较索引，最后的区别就是这边的starts他只能是括号，所以最后剩下的括号必须满足是偶数的情况。
package 剑指0ffer.括号题目;
import java.util.Stack;
public class 判断一个括号字符串是否有效 {
public boolean canBeValid(String s, String locked) {
char[] sa = s.toCharArray();
char[] la = locked.toCharArray();
for(int i=0;i<locked.length();i++){
if(la[i]=='0'){
sa[i] = '*';
}
}
Stack<Integer> left = new Stack<>();
Stack<Integer> stars = new Stack<>();
for(int i=0;i<sa.length;i++){
if(sa[i]=='('){
left.push(i);
}else if(sa[i]=='*'){
stars.push(i);
}else {
if(left.size()>0){
left.pop();
}else {
if(stars.size()>0){
stars.pop();
}else {
return false;
}
}
}
}
if(left.size()>stars.size())
return false;
while (left.size()>0&&stars.size()>0){
if(left.pop()>stars.pop()){
return false;
}
}
if(stars.size()%2!=0)
return false;
return true;
}
}
1541. 平衡括号字符串的最少插入次数
image.png
本题的思路其实就是用need记录对右括号的需求，具体看下代码就能理解
public int minInsertions(String s) {
int res = 0;
int need = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
need += 2;
if (need % 2 == 1) { //右括号数量只能为偶数，但只能添（右括号少了）
res++; //插入一个右括号
need--; //对右括号的需求-1
}
}else {
need--;
//need不可能小于-1，因为此处-1后若走上面必有+2
if (need == -1) { //右括号多了
res++; //插入一个左括号
need = 1;
}
}
}
return res + need;
}
1190. 反转每对括号间的子串
image.png
思路的话还是用栈暴力的遍历，遇到左括号的时候，不停的循环把栈的元素拿出来逆转后重新放回去。代码如下
public String reverseParentheses(String s) {
char[] sa = s.toCharArray();
Stack<Character> stack = new Stack<>();
for(int i=0;i<sa.length;i++){
if(sa[i]==')'){
StringBuffer temp = new StringBuffer();
while (stack.peek()!='('){
temp.append(stack.pop());
}
stack.pop();
for(int j=0;j<temp.length();j++){
stack.push(temp.charAt(j));
}
}else {
stack.push(sa[i]);
}
}
StringBuffer res= new StringBuffer();
while (!stack.isEmpty()){
res.append(stack.pop());
}
//因为stack是先入后出，所以从尾到头赋值后还得把string逆转。
return res.reverse().toString();
}
1963. 使字符串平衡的最小交换次数
image.png
又是一道不会做的贪心题，看的别人的答案，思路好像是说找出不匹配的括号的对数，代码如下:
class Solution {
public int minSwaps(String s) {
char[] cs = s.toCharArray();
int l = 0, r = 0;
for (int i = 0; i < cs.length; i++) {
char c = cs[i];
if (c == '[') {
l++;
} else {
if (l > 0) {
l--;
} else {
r++;
}
}
}
int sum = (l + r) >> 1;
return (sum & 1) == 1 ? (sum >> 1) + 1 : sum >> 1;
}
}
856. 括号的分数
image.png
虽然本题是一个中等题，但是做题的思路是比较巧妙的，大家可以尝试做做然后理解一下答案的思路，使用一个栈来讲记录到字符串s某一位前的分数值。比如()()((()))这样的字符串，首先在stack中放入一个0，代表当字符串指针指向-1的时候的分数是0，然后遇到左括号就加入0，遇到右括号就把栈顶的元素拿出来，判断他是否是0，如果是0则把他pop出来加1后再把此时的栈顶元素再pop出来相加，如果是非0则把他乘以2然后继续同样的相加操作。
class Solution {
public int scoreOfParentheses(String s) {
Deque<Integer> d = new ArrayDeque<>();
d.addLast(0);
for (char c : s.toCharArray()) {
if (c == '(') d.addLast(0);
else {
int cur = d.pollLast();
d.addLast(d.pollLast() + Math.max(cur * 2 , 1));
}
}
return d.peekLast();
}
}
301. 删除无效的括号
image.png
思路是暴力的回溯，首先计算出多余的左括号和右括号的个数，然后回溯，过程中根据左括号需要删除的个数进行字符串的裁剪拼接，然后把字符串通过一般的栈方法判断是否是有效的括号字符串，返回最后的结果。
package 剑指0ffer.括号题目;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class 删除无效的括号 {
List<String> res = new ArrayList<>();
public List<String> removeInvalidParentheses(String s) {
int lr = 0;
int rr = 0;
char[] sa = s.toCharArray();
for(int i=0;i<sa.length;i++){
if(sa[i]=='('){
lr++;
}else if(sa[i]==')'){
if(lr>0){
lr--;
}else {
rr++;
}
}
}
return res;
}
void bacetrack(String s,int lr,int rr,int start){
if(lr==0&&rr==0){
if(isValid(s)) res.add(s);
}
for(int i=start;i<s.length();i++){
//防止出现相同的答案，也是剪枝
if(i > start && s.charAt(i) == s.charAt(i - 1))continue;
if(s.charAt(i) == '(' && lr > 0){
//这边使用i而不是i+1其实是为了针对“)(”括号时，最后结果要""而不是null
bacetrack(s.substring(0,i)+s.substring(i+1),lr-1,rr,i);
}
if(s.charAt(i) == ')' && rr > 0){
bacetrack(s.substring(0,i)+s.substring(i+1),lr,rr-1,i);
}
}
}
boolean isValid(String s){
Stack<Character> stack = new Stack<>();
char[] sa = s.toCharArray();
for(int i=0;i<sa.length;i++){
if(sa[i]==')'){
if(stack.isEmpty()){
return false;
}else {
stack.pop();
}
}else if(sa[i]=='('){
stack.push(sa[i]);
}
}
return stack.isEmpty();
}
}
