2023年华为OD机考真题：简单的解压缩算法

算法刷题2年前 (2023)更新江南白衣

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：简单的解压缩算法
知识点栈
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
现需要实现一种算法，能将一组压缩字符串还原成原始字符串，还原规则如下：
1、字符后面加数字N，表示重复字符N次。例如：压缩内容为A3，表示原始字符串为AAA。
2、花括号中的字符串加数字N，表示花括号中的字符串重复N次。例如：压缩内容为{AB}3，表示原始字符串为ABABAB。
3、字符加N和花括号后面加N，支持任意的嵌套，包括互相嵌套。例如：压缩内容可以{A3B1{C}3}3。
输入描述：
输入一行压缩后的字符串
输出描述：
输出压缩前的字符串
补充说明：
输入保证，数字不会为0，花括号中的内容不会为空，保证输入的都是合法有效的压缩字符串
输入输出字符串区分大小写
输入的字符串长度为范围[1, 10000]
输出的字符串长度为范围[1, 100000]
数字N范围[1, 10000]
示例1
输入：
A3
输出：
AAA
说明：
A3代表A字符重复3次
示例2
输入：
{A3B1{C}3}3
输出：
AAABCCCAAABCCCAAABCCC
说明：
{A3B1{C}3}3代表A字符重复3次，B字符重复1次，花括号中的C字符重复3次，最外层花括号中的AAABCCC重复3次
解题思路：
例如：{A3B1{C}3{x2Y}2L4}3
使用双向队列deque来放置字符串，使用tempStr来放置临时字符串，isHasBrace代表是有大括号需要处理，初始化false
1、从头开始遍历，遍历到“{”，isHasBrace=false且tempStr为空，则deque=【{】；
继续遍历，直到第二个“{”，isHasBrace=false但是tempStr有值，则进行处理后放入队列中，deque=【{，AAAB，{】；
2、遍历到“}”，tempStr=“C”，因为isHasBrace=false，所以先处理完tempStr放入队列中，deque=【{，AAAB，{，C】，isHasBrace置为true；
3、遍历到“{”，因为isHasBrace=true，需要处理大括号：遍历队列，发现括号里面只有一个C，此时tempStr=3，处理完放入队列中：deque=【{，AAAB，CCC，{】，isHasBrace置为false；
4、遍历到“}”，tempStr=“x2Y”，因为isHasBrace=false，所以先处理完tempStr放入队列中，deque=【{，AAAB，CCC，{，xxY】，isHasBrace置为true；
5、遍历到“L”，因为L是字符且isHasBrace=true，需要处理大括号：遍历队列，发现括号里面是xxY，此时tempStr=2，处理完放入队列中：deque=【{，AAAB，CCC，xxYxxY】，isHasBrace置为false；
6、遍历到“}”，tempStr=“L4”，因为isHasBrace=false，所以先处理完tempStr放入队列中，deque=【{，AAAB，CCC，xxYxxY，LLLL】，isHasBrace置为true；
7、遍历到最后tempStr=3，isHasBrace=true，需要处理大括号：遍历队列，发现括号里面是AAABCCCxxYxxYLLLL，此时tempStr=3，处理完放入队列中：deque=【AAABCCCxxYxxYLLLLAAABCCCxxYxxYLLLLAAABCCCxxYxxYLLLL】。
最终从头输出队列为：AAABCCCxxYxxYLLLLAAABCCCxxYxxYLLLLAAABCCCxxYxxYLLLL

代码实现一：

package com.codernav.demo.hwod.exam;

import java.util.*;

/**
 * @title 简单的解压缩算法
 * @Description 现需要实现一种算法，能将一组压缩字符串还原成原始字符串，还原规则如下：
 * 1、字符后面加数字N，表示重复字符N次。例如：压缩内容为A3，表示原始字符串为AAA。
 * 2、花括号中的字符串加数字N，表示花括号中的字符串重复N次。例如：压缩内容为{AB}3，表示原始字符串为ABABAB。
 * 3、字符加N和花括号后面加N，支持任意的嵌套，包括互相嵌套。例如：压缩内容可以{A3B1{C}3}3。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String string = sc.nextLine();
        int len = string.length();
        Deque<String> strDeque = new ArrayDeque<>();
        String tempStr = "";    //字符串
        boolean isHasBraces = false;    //是否有大括号需要处理
        for (int i = 0; i < len; i++) {
            char c = string.charAt(i);
            if (c == '{') {       //遇到左括号
                if (isHasBraces) {    //先判断是否有大括号需要处理
                    handleBraces(tempStr, strDeque);
                    isHasBraces = false;
                } else if (!tempStr.isEmpty()) {
                    strDeque.addLast(handle(tempStr));
                }
                strDeque.addLast(String.valueOf(c));
                tempStr = "";
            } else if (c == '}') {
                strDeque.addLast(tempStr);
                if (isHasBraces) {
                    handleBraces(strDeque.pollLast(), strDeque);
                } else {
                    strDeque.addLast(handle(Objects.requireNonNull(strDeque.pollLast())));
                }
                isHasBraces = true;
                tempStr = "";
            } else {
                if (isHasBraces && Character.isLetter(c)) {
                    handleBraces(tempStr, strDeque);
                    isHasBraces = false;
                    tempStr = "";
                }
                tempStr += c;
            }
            if (i == len - 1) {   //最后一个字符
                if (isHasBraces) {
                    handleBraces(tempStr, strDeque);
                } else {
                    strDeque.addLast(handle(tempStr));
                }
            }
        }

        StringBuilder res = new StringBuilder();
        while (strDeque.size() != 0) {
            res.append(strDeque.pollFirst());
        }
        System.out.println(res);
    }

    /**
     * 获取大括号里面的字符串
     *
     * @param strDeque
     * @return
     */
    public static String getBraces(Deque<String> strDeque) {
        List<String> list = new ArrayList<>();
        while (!strDeque.peekLast().equals("{")) {   //直至碰到下一个左括号
            list.add(strDeque.pollLast());
        }
        strDeque.pollLast();    //左括号也需要删除
        Collections.reverse(list);  //因为是从尾部开始找的所以需要翻转
        String res = "";
        for (String s : list) {
            res += s;
        }
        return res;
    }

    /**
     * 处理大括号里面的内容
     *
     * @param tempStr  括号外的数字
     * @param strDeque 字符串队列
     */
    public static void handleBraces(String tempStr, Deque<String> strDeque) {
        int num = Integer.parseInt(tempStr);
        StringBuilder temp = new StringBuilder();
        String strInBraces = getBraces(strDeque);
        for (int j = 0; j < num; j++) {
            temp.append(strInBraces);
        }
        strDeque.addLast(temp.toString());
    }

    /**
     * 处理连续的字符串
     *
     * @param str
     * @return
     */
    public static String handle(String str) {
        int len = str.length();
        String res = "";
        String tempStr = "";    //字符串
        StringBuilder tempNum = new StringBuilder();    //数字字符串（处理多位数）
        for (int i = 0; i < len; i++) {
            char c = str.charAt(i);
            if (Character.isDigit(c)) {   //此时是数字
                tempNum.append(c);   //是数字直接进行拼接
            } else {     //此时是字母
                if (tempNum.length() > 0) {     //数字字符串不为空说明需要处理
                    int num = Integer.parseInt(tempNum.toString());     //字符重复的次数
                    for (int j = 0; j < num; j++) {
                        res += tempStr;     //重复多少次就拼接多少次
                    }
                    tempStr = "";   //处理完需要置空以免影响下一个字符的统计
                    tempNum = new StringBuilder();   //数字一样置空
                }
                tempStr += c;   //字符拼接
            }
            if (i == len - 1) {   //不能忘了处理最后一位
                if (tempNum.length() > 0) {     //数字字符串不为空时处理
                    int num = Integer.parseInt(tempNum.toString());
                    for (int j = 0; j < num; j++) {
                        res += tempStr;
                    }
                } else {
                    res += tempStr;     //为空时直接拼接字符串（处理单字符串的情况）
                }
            }
        }
        return res;
    }
}

代码实现二：Java代码满分实现

package com.codernav.demo.hwod.exam;

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

/**
 * @title 简单的解压缩算法
 * @Description 现需要实现一种算法，能将一组压缩字符串还原成原始字符串，还原规则如下：
 * 1、字符后面加数字N，表示重复字符N次。例如：压缩内容为A3，表示原始字符串为AAA。
 * 2、花括号中的字符串加数字N，表示花括号中的字符串重复N次。例如：压缩内容为{AB}3，表示原始字符串为ABABAB。
 * 3、字符加N和花括号后面加N，支持任意的嵌套，包括互相嵌套。例如：压缩内容可以{A3B1{C}3}3。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        System.out.println(solution(str));
    }

    public static String repeat(String str, int num) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < num; i++) {
            sb.append(str);
        }
        return sb.toString();
    }

    public static String solution(String str) {
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == '{') {
                stack.push("{");
            } else if (c == '}') {
                if (Character.isDigit(str.charAt(i + 1))) {
                    int p = i + 1;
                    while (p < str.length() && Character.isDigit(str.charAt(p))) p++;
                    int num = Integer.parseInt(str.substring(i + 1, p));
                    StringBuilder sb = new StringBuilder();
                    while (!stack.peek().equals("{")) {
                        String s = stack.pop();
                        sb.append(s);
                    }
                    stack.pop();
                    stack.push(repeat(sb.toString(), num));
                    i = p - 1;
                }
            } else if (Character.isAlphabetic(c)) {
                if (Character.isDigit(str.charAt(i + 1))) {
                    int p = i + 1;
                    while (p < str.length() && Character.isDigit(str.charAt(p))) p++;
                    int num = Integer.parseInt(str.substring(i + 1, p));
                    stack.push(repeat(c + "", num));
                    i = p - 1;
                } else {
                    stack.push(c + "");
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        String str0 = sb.toString();
        sb = new StringBuilder();
        for (int i = str0.length() - 1; i >= 0; i--) {
            sb.append(str0.charAt(i));
        }
        return sb.toString();
    }
}