Technology is open source and knowledge is shared.

preface

Data structures and algorithms are the internal discipline of programmers. Some developers have even come up with programs = data structures + algorithms. Shaoxia, when I participated in the school recruitment, I was also praised by the interviewer for my excellent algorithm solution in the section of hand-tearing code, and defeated many competitors and finally got offers from bytedance and other big factories. In order to keep the algorithm heart classics day by day proficiency, I secretly decided to start to write Internet data structure and algorithm related articles, I hope to help you readers in the future tore code skillfully, 360 degrees of the interviewer counterattack, let the interview colleagues stunned, crazy reaper Internet big factory offer! In spite of the exaggerated rhetoric used in the article, we should always keep a humble heart. I hope to learn and progress together with you with an open mind.

Problem description

Problem analysis

The problem is clear and intuitive. The double layer for loop is iterated one by one. See? Well, it’s time to say goodbye to you all.



The idea is intuitive, but the time complexity is impressive! isO(n2)We are interviewing and developingAvoid the time complexity of square as much as possible“, which can be scary and even lead to server downtime.

So are there any good ideas? Of course there is. Let me explain.

The solution

Train of thought

Think this problem is actually thinking is not difficult, because it is easy to know the stack to solve, but the detail place there will be a lot of a lot of places to pay attention to and dig in, the first is the use of the stack, a lot of people will use two stack, stack a number, a string of stack, I am only a stack solution here, because only a stack, so not character stack, but the string stack stack

While (), use a while loop to read the string between (and). I’m using a StringBuffer to improve string concatenation, and then delete (pop) and start reading num. Note that numbers can be many digits. I’m just going to use parseInt to convert the string to a number, and then I’m going to copy the string as num times, and then I’m going to put the string back on the stack. Otherwise, I’m just going to convert it to a string and I’m going to push it on the stack. Use insert concatenation instead of append

code

class Solution {
    public String decodeString(String s) {
        StringBuffer sb = new StringBuffer();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i ! = s.length(); i++) {char c = s.charAt(i);
            stack.push(c);
            if (c == '] ') {
                char n;
                String repeated = "";
                stack.pop();
                while((n = stack.pop()) ! ='[') {
                    repeated = n + repeated;
                }
                int repeatedNum = Integer.valueOf(repeated);
                stack.pop();
                String repeatedStr = "";
                while((n = stack.pop()) ! ='(') {
                    repeatedStr = n + repeatedStr;
                }

                for (int j = 0; j ! = repeatedNum; j++) {char[] chars = repeatedStr.toCharArray();
                    for (charc1 : chars) { stack.push(c1); }}}}while(! stack.isEmpty()) { sb.insert(0, stack.pop());
        }

        returnsb.toString(); }}Copy the code

Algorithm execution efficiency

Doesn’t it feel better to look at the running time and memory footprint of the algorithm?

summary