2020-09-09

数据结构和算法

9 分钟读完 (大约 1287 个字) 0次访问

字符串中的成对括号问题处理技巧

1. 前言

遇到成对括号问题，我相信大家第一个想到的就是栈，因为我们自从翻开严蔚敏的《数据结构》开始，就习惯于将“栈”和“成对括号”联系起来。

其实还是挺麻烦的，遍历一遍，遇到(入栈，)出栈，最后判断栈是否为空，中间还夹杂着一些其他技巧（栈底是)就直接结束之类的）。诚然，这是一个好方法，但是做题的时候讲究快速编写，研究的时候才讲究快速运行，而且通常题目不仅仅考括号匹配，括号只是题目的一部分，这时候，我们写起来就比较复杂。看我这新思路！

2. api用的越熟，写起来就越轻松！

这是我在牛客某一题看到的，叹为观止，真的对api了然于心，后来又遇见了一道题，自己试了一下，发现异常好用，因此记录下来。

先看这两个大家很熟了

int IndexOf(String str)：字符串中查找某个字符的第一次出现下标，没有则返回-1
int lastIndexOf(String str)：也是找下标，但是是最后一次出现的下标，没有则返回-1

奇妙的是，他们的重载方法，这两个参数！

int indexOf(String str, int fromIndex)：第一次，从指定位置往后找，没有则返回-1
int lastIndexOf(String str, int fromIndex)：最后一次，从指定位置开始反向搜索，没有则返回-1

认真观察，你就会发现…OHHH！！！搭配以下绝了，括号匹配思路：可以先找到第一个)，然后从这个)开始往前找(，绝了！！！匹配上了，一定是最靠近的一对

1 2	int r = str.indexOf("]"); int l = str.lastIndexOf("[", r);

无需考虑是否嵌套括号((())())！！！这两行代码一定是找到最内层最左边那个！！简直将java的api完美的使用上了，这得对api多熟练啊！！

3. 最喜欢的实战环节

3.1 腾讯2020春招后端-压缩算法

原题链接https://www.nowcoder.com/test/question/c27561e5b7e0441493adb9a54071888d?pid=21283868&tid=37272348

题目：

小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的m个相同字符串S将会压缩为m|S，例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？

输入描述:

输入第一行包含一个字符串s，代表压缩后的字符串。
S的长度<=1000;
S仅包含大写字母、[、]、|;
解压后的字符串长度不超过100000;
压缩递归层数不超过10层;

输出描述:

1	输出一个字符串，代表解压后的字符串。

输入例子1:

1	HG[3\|B[2\|CA]]F

输出例子1:

1	HGBCACABCACABCACAF

例子说明1:

1	HG[3\|B[2\|CA]]F−>HG[3\|BCACA]F−>HGBCACABCACABCACAF

题解：

为了简洁，这里除去了main部分，只给出核心函数

/**
 * 思路：直接字符串替换，但是要注意从内层开始，看你的String类api掌握程度了
 */
public static String zxvf(String str){
    //找最里面那对括号位置
    int l = 0, r = str.length() - 1;
    if (str.contains("]")){		//妙的开始
        r = str.indexOf("]");
        l = str.lastIndexOf("[", r);
    }else {
        return str;
    }
    //截取字符串并替换
    String words = str.substring(l + 1, r); //妙的结果
    String[] split = words.split("\\|");
    int time = Integer.parseInt(split[0]);
    String word = "";
    for (int i = 0; i < time; i++) {
        word += split[1];
    }
    str = str.replace("[" + words + "]", word);
    return zxvf(str);
}

你细品，注释里面标明的妙的地方，非常方便

3.2 小红书2020校招测试开发&后端笔试题卷三

原题链接https://www.nowcoder.com/question/next?pid=23567650&qid=982135&tid=37272851

题目：

薯队长写了一篇笔记草稿，请你帮忙输出最后内容。

1.输入字符包括，”(“ , “)” 和 “<”和其他字符。

2.其他字符表示笔记内容。

3.()之间表示注释内容，任何字符都无效。括号保证成对出现。

4.”<”表示退格, 删去前面一个笔记内容字符。括号不受”<”影响。

输入描述:

1	输入一行字符串。长度<=10000.

输出描述:

1	输出一行字符串，表示最终的笔记内容。

示例1：

输入

1	Corona(Trump)USA<<<Virus

输出

1	CoronaVirus

题解：

由于是acm模式，我直接贴出完整代码

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String note = sc.nextLine();
        StringBuilder sb = new StringBuilder();
        while (note.contains(")")){    //去掉注释
            int r = note.indexOf(")");
            int l = note.lastIndexOf("(", r);
            note = note.replace(note.substring(l, r + 1), "");
        }
        while (note.contains("<")){    //退格
            int idx = note.indexOf("<");
            note = note.replace(note.substring(idx - 1, idx + 1), "");
        }
        System.out.println(note);
    }
}

其实没什么原理，api摆在那，看你熟不熟练罢了，要是知道这个api搭配的话，做这题是很轻松的。那么对于括号匹配问题：while循环判断是否contains(“)”)，只要有就replace为空串，最后判断整个字符串是否为空即可，应该都有思路了吧。

# 字符串, 笔试