【算法题】消消乐游戏

共计 2377 个字符，预计需要花费 6 分钟才能阅读完成。

2022年6月9日23点14分 更新

import java.util.Scanner;
import java.util.Stack;

/**
 * 标题：消消乐游戏 | 时间限制：1秒 | 内存限制：65536K | 语言限制：不限
 * 游戏规则：输入一个只包含英文字母的字符串，字符串中的两个字母如果相邻且相同，就可以消除。
 * <p>
 * 在字符串上反复执行消除的动作，直到无法继续消除为止，此时游戏结束。
 * 输出最终得到的字符串长度。
 * <p>
 * 大小写敏感， str 长度不超过100。
 * <p>
 * 输出描述:
 * 输出游戏结束后，最终得到的字符串长度
 * <p>
 * 示例1
 * 输入
 * gg
 * 输出
 * 0
 * 说明
 * gg 可以直接消除，得到空串，长度为0
 * 示例2
 * 输入
 * mMbccbc
 * 输出
 * 3
 * 说明
 * 在 mMbccbc 中，可以先消除 cc ；此时字符串变成 mMbbc ，可以再消除 bb ；此时字符串变成 mMc ，此时没有相邻且相同的字符，无法继续消除。最终得到的字符串为 mMc ，长度为3
 * 备注:
 * 输入中包含 非大小写英文字母 时，均为异常输入，直接返回 0
 * <p>
 * aaccbbdcskiuhgvsdffdsvcj 10
 * scdxcckkjjnhbbvvfgv 9
 *
 * @since 2022年6月9日
 */
public class M_N_T_16 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();

        char[] chars = line.toCharArray();

        extracted_2(chars);

    }

    private static void extracted_2(char[] chars) {
        Stack<Character> stack = new Stack<>(); // 利用栈特性
        for (char aChar : chars) {
            if (!Character.isLetter(aChar)) { // 遇到非字母字符直接返回0
                System.out.println(0);
                return;
            }

            if (stack.size() == 0) { // 注意第一个字符或者栈中已有字符被消除完了情况，要先插入
                stack.push(aChar);
                continue;
            }

            if (aChar == stack.peek()) { // 相同就会弹栈，反之入栈 peek()获取最近一个入栈的字符而先不弹出
                stack.pop();
            } else {
                stack.push(aChar);
            }

        }

        System.out.println(stack.size()); // 判断最后留下的
    }
}

原解法

import java.util.Scanner;

/**
 * 标题：消消乐游戏 | 时间限制：1秒 | 内存限制：65536K | 语言限制：不限
 * 游戏规则：输入一个只包含英文字母的字符串，字符串中的两个字母如果相邻且相同，就可以消除。
 * <p>
 * 在字符串上反复执行消除的动作，直到无法继续消除为止，此时游戏结束。
 * 输出最终得到的字符串长度。
 * <p>
 * 大小写敏感， str 长度不超过100。
 * <p>
 * 输出描述:
 * 输出游戏结束后，最终得到的字符串长度
 * <p>
 * 示例1
 * 输入
 * gg
 * 输出
 * 0
 * 说明
 * gg 可以直接消除，得到空串，长度为0
 * 示例2
 * 输入
 * mMbccbc
 * 输出
 * 3
 * 说明
 * 在 mMbccbc 中，可以先消除 cc ；此时字符串变成 mMbbc ，可以再消除 bb ；此时字符串变成 mMc ，此时没有相邻且相同的字符，无法继续消除。最终得到的字符串为 mMc ，长度为3
 * 备注:
 * 输入中包含 非大小写英文字母 时，均为异常输入，直接返回 0
 * <p>
 * aaccbbdcskiuhgvsdffdsvcj 10
 * scdxcckkjjnhbbvvfgv 9
 *
 * @since 2022年4月30日
 */
public class M_N_T_16 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();

        char[] chars = line.toCharArray();

        StringBuilder sb = new StringBuilder();
        merge(chars,0, 0, 0, 1, sb);

        System.out.println(sb.length());
    }

    private static void merge(char[] chars, int start, int preIndex, int le, int ri, StringBuilder sb) {
        if (le > chars.length || ri > chars.length) {
            return;
        }

        if (ri == chars.length) {
            sb.append(chars[ri - 1]);
            return;
        }

        if (!(((chars[le] >= 65 && chars[le] <= 90) || (chars[le] >= 97 && chars[le] <= 122)) &&
                ((chars[ri] >= 65 && chars[ri] <= 90) || (chars[ri] >= 97 && chars[ri] <= 122)))) {
            sb.setLength(0);
            return;
        }

        if (chars[le] == chars[ri]) {
            start = le == start ? ri + 1 : start;
            le--;
            if (le < start) {
                le = ri + 1;
                ri++;
            } else {
                le = Math.min(le, preIndex);
                sb.deleteCharAt(sb.length() - 1);
            }
        } else {
            sb.append(chars[le]);
            preIndex = le;
            le = ri;
        }
        ri++;

        merge(chars, start, preIndex, le, ri, sb);
    }
}