LeetCode 394: DecodeString (Java)

ccj659 发布于2019-08-14 15:50 / 2065人阅读

摘要：思路非常清晰，但是实现起来并不简单。得注意细节及其处理方式，比如数字可能出现两位及以上并列关系和包含关系如何巧妙区分。另外发现大循环用而不是可能更方便一些。

解码题。
编码规则直接看例子(编码后字符串->原字符串)：
2[b] -> bb
3[a2[c]] -> 3[acc] -> accaccacc
2[a2[b]ef]xy ->2[abbef]xy->abbefabbefxy

根据上面的结构我们很容易想到用深搜算法：

先将"]" 之前的信息（要重复的部分及重复次数）压到stack里，等到了"]"再一个一个推出还原。思路非常清晰，但是实现起来并不简单。得注意细节及其处理方式，比如数字可能出现两位及以上; 并列关系［］,［］和包含关系［［］］如何巧妙区分。另外发现大循环用while而不是for可能更方便一些。

下面是我在leetcode论坛上找到的比较好看的代码（44%）：

public static String decodeString(String s) {
    Stack count = new Stack<>();
    Stack result = new Stack<>();//用Stack处理包含关系

    result.push("");
    int i = 0;

    while(i= "0" && a <= "9"){
            int p1 = i;
            while(Character.isDigit(s.charAt(i+1))) i++;
            count.push(Integer.parseInt(s.substring(p1,i+1)));
        } else if (a == "[") {
            result.push("");//用初始化空字符串处理并列关系
        } else if(a == "]") {
            String temp = new String(result.pop());
            StringBuilder sb = new StringBuilder();
            int nloop = count.pop();
            for(int j = 0; j < nloop;j++)
                sb.append(temp);
            result.push(result.pop()+sb.toString());
        } else {
            result.push(result.pop()+a);
        }
        i++;
    }
    return result.pop();
}

当然也可以用递归算法，但我感觉比较难想，这种算法比较直接，面试的时候想到比较实际。

Ref：Java short and easy-understanding solution using stack

海外云主机 GPU服务器 DecodeString LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66056.html

LeetCode 394：字符串解码 Decode String

摘要：用栈暂存的逻辑与递归基本一致，可以理解为用递归实现栈。没有栈这种数据结构，可以用数组或双端队列可以只用一个栈以元组的形式重复次数和字符串，如利用栈初始化数据结构递归字符串入栈刷新计算重复次数可直接操作字符串真的很方便。题目：给定一个经过编码的字符串，返回它解码后的字符串。Given an encoded string, return its decoded string. 编码规则...

邹强 2019-08-19 10:30 评论0 收藏0
leetcode-394-Decode String

摘要：原题核心是理解题意，总结规律，属于哪一类题目。完成从内往外层层解决，需要保持字符串的记忆。再加上列表操作和字符串追加的小技巧。应用栈的操作，保持一个字符串的状态，并可以从后往前进行处理。动态规划也可以。正则解法栈队列解法原题： Given an encoded string, return its decoded string. The encoding rule is: k[enc...

snifes 2019-07-30 17:38 评论0 收藏0
leetcode394. Decode String

摘要：利用栈我们可以存储外围层已持有的字符串以及应当展开的次数。用栈的思路来写要求思路更加严谨，以免出现逻辑错误。这里需要额外注意的是，如果当前该括号外围存在父元素，则我们应当将父元素的计数和已有字符串压入栈中。题目要求 Given an encoded string, return its decoded string. The encoding rule is: k[encoded_...

Ilikewhite 2019-08-16 15:04 评论0 收藏0
Decode String

摘要：题目链接的题，感觉还是分析下什么时候，什么时候，思路会比较快。里面不加循环的写法。 Decode String 题目链接：https://leetcode.com/problems... stack的题，感觉还是分析下stack什么时候pop，什么时候push，思路会比较快。loop里面不加while循环的写法。 public class Solution { public S...

ysl_unh 2019-08-14 17:22 评论0 收藏0
GoJS 绘图 (五) ：定位面板与垂直面板（Panel）

摘要：虽然只有一个面板，也有许多不同类型的面板，每个都有其自己的目的是如何安排的元素。这些都是存在的各种面板组成位置面板最简单的一种面板是。每个元素获得其正常大小，无论其默认大小或指定或等价的和。垂直面板面板的所有面板元件的排列垂直从上到下。 Panel是负责任的大小和位置的所有元素。每个面板建立自己的坐标系。一个面板的元件的绘制顺序表示建立这些元素的Z轴排序。虽然只有一个面板，也有许多不同...

PrototypeZ 2019-08-19 18:26 评论0 收藏0