Java教程

【注释详细,思路清晰】【打卡第18天】leetcode热题HOT100之Java实现:394. 字符串解码【栈】

本文主要是介绍【注释详细,思路清晰】【打卡第18天】leetcode热题HOT100之Java实现:394. 字符串解码【栈】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1、题目描述

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

2、算法分析

首先最后结果是一个字符串,[]里面是字母,[]前面的数字是[]内字母重复的次数,2[s2[aa]],[]的嵌套结果也会迭代。

可以用栈存储解决:

① 获取遍历字符串中的第一个‘】’之前的所有字符

② 获取其中一层的2[aa]的计算信息,分为2步骤,获取字符串和获取‘[’前的数字

③ 根据数字倍数将字母push到stack

④ 将所有结果从栈中取出,并返回

知识点补充:

① 字符串拆分成字符数组存储:s.toCharArray()

② 判断字符是否为字母:Character.isLetter(stack.peek())

③ 只获取栈顶信息,不取值:stack.peek(),stack.pop()是取值的

④ 判断字符是否为数字:Character.isDigit(stack.peek())

代码注释详细,直接看代码!

3、代码实现

class Solution {
    public String decodeString(String s) {
        // 使用栈存储
        
        Stack<Character> stack = new Stack<>();
        // 遍历字符串数组
        for(char c:s.toCharArray()){
            //所有字符全部存储到栈中,除了 ]
            if(c != ']'){
                stack.push(c);
            }else{
                /**
                    1、获取字符串
                 */
                //去除[]中的字符串, 使用StringBuilder存储字符
                StringBuilder sb = new StringBuilder();
                while(!stack.isEmpty() && Character.isLetter(stack.peek())){
                    sb.insert(0,stack.pop());
                }
                // 取出[]中的字符串
                String sub = sb.toString();
                //[]中的字符串取完后,去除内层的[
                stack.pop();

                /**
                    2、获取[]前的数字
                 */
                StringBuilder dight = new StringBuilder();
                while(!stack.isEmpty() && Character.isDigit(stack.peek())){
                    dight.insert(0,stack.pop());
                }
                int count = Integer.valueOf(dight.toString());

                /**
                    3、根据数字倍数将字母push到stack
                 */
                 while(count > 0){
                    for(char ch : sub.toCharArray()){
                        stack.push(ch);
                    }
                    count--;
                 }
                
            }
           
        }
         /**
             4、把所有的字母取出来
                  */
                StringBuilder result = new StringBuilder();
                while(!stack.isEmpty()){
                    result.insert(0,stack.pop());
                }  
                 return result.toString(); 

    }
}

 OK,你学肥么有~

这篇关于【注释详细,思路清晰】【打卡第18天】leetcode热题HOT100之Java实现:394. 字符串解码【栈】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!