算法-堆栈

发表于 | 分类于 ，

二叉树遍历

模拟操作系统中堆栈，创建一个Command类，封装了一个string和treenode，string指定command执行的操作，treenode保存数据，则前中后遍历只需要调整很少的顺序就可以了。

中序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package leetcode.stack;
import java.awt.event.ComponentAdapter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class BinaryTreeInOrderTraversal_94 {
    List<Integer> res = new ArrayList<>();
    //递归方法
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            res.add(root.val);
            inorderTraversal(root.right);
        }
        return res;
    }
    //非递归方法
    public List<Integer> inorderTraversal1(TreeNode root) {
        if (root == null)
            return res;
        Stack<Command> stack = new Stack<>();
        stack.push(new Command("go", root));
        while (!stack.isEmpty()) {
            Command command = stack.pop();
            if (command.s.equals("print"))
                res.add(command.node.val);
            else {
                if (command.node.right != null)
                    stack.push(new Command("go", command.node.right));
                stack.push(new Command("print", command.node));
                if (command.node.left != null)
                    stack.push(new Command("go", command.node.left));
            }
        }
        return res;
    }
    class Command{
        String s;  //print,go
        TreeNode node;
        public Command(String s, TreeNode node) {
            this.s = s;
            this.node = node;
        }
    }
}

前序–这个没有改，用的经典算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package leetcode.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class BinaryTreePrecoderTraversal_144 {
    List<Integer> res = new ArrayList<>();
    //递归方法
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root != null) {
            res.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
        return res;
    }
    //非递归方法
    public List<Integer> preorderTraversal1(TreeNode root) {
        if (root == null)
            return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.right != null)
                stack.push(node.right);
            if (node.left != null)
                stack.push(node.left);
        }
        return res;
    }
}

后序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package leetcode.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class BinaryTreePostorderTraversal_145 {
    List<Integer> res = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null)
            return res;
        Stack<Command> stack = new Stack<>();
        stack.push(new Command("go", root));
        while (!stack.isEmpty()) {
            Command command = stack.pop();
            if (command.s.equals("print"))
                res.add(command.node.val);
            else {
                stack.push(new Command("print", command.node));
                if (command.node.right != null)
                    stack.push(new Command("go", command.node.right));
                if (command.node.left != null)
                    stack.push(new Command("go", command.node.left));
            }
        }
        return res;
    }
    class Command {
        String s;//print, go
        TreeNode node;
        public Command(String s, TreeNode node) {
            this.s = s;
            this.node = node;
        }
    }
}

逆波兰表达式计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package leetcode.stack;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class EvaluateReversePolishNotation_150 {
    public int evalRPN(String[] tokens) {
        Stack<Integer> number = new Stack<>();
        Stack<Character> operators = new Stack<>();
        for (String s : tokens) {
            switch (s) {
                case "*":
                    number.push(number.pop() * number.pop());
                    break;
                case "+":
                    number.push(number.pop() + number.pop());
                    break;
                case "-":
                    number.push(-(number.pop() - number.pop()));
                    break;
                case "/":
                    int tmp1 = number.pop();
                    int tmp2 = number.pop();
                    number.push(tmp2 / tmp1);
                    break;
                default:
                    number.push(Integer.valueOf(s));
                    break;
            }
        }
        return number.pop();
    }
}

地址简化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package leetcode.stack;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class SimplifyPath_71 {
    public String simplifyPath(String path) {
        Stack<String> stack = new Stack<>();
        String[] strings = path.split("/");
        for (String s : strings) {
            switch (s) {
                case "." :
                    break;
                case "..":
                    if (!stack.isEmpty())
                        stack.pop();
                    break;
                default:
                    if (!s.equals(""))
                        stack.push(s);
                    break;
            }
        }
        StringBuilder sb = new StringBuilder();
        if (stack.isEmpty())
            return "/";
        while (!stack.isEmpty()) {
            sb.insert(0,  "/" + stack.pop());
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        SimplifyPath_71 simplifyPath_71 = new SimplifyPath_71();
        String s = "/...";
        System.out.println(simplifyPath_71.simplifyPath(s));
    }
}

FlattenNestedListIterator_341

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package leetcode.stack;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class FlattenNestedListIterator_341 implements Iterator<Integer>{
    Stack<NestedInteger> stack = new Stack<>();
    Stack<Integer> integers = new Stack<>();
    public FlattenNestedListIterator_341(List<NestedInteger> nestedList) {
        for (NestedInteger i : nestedList) {
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            NestedInteger nestedInteger = stack.pop();
            if (nestedInteger.isInteger()) {
                integers.push(nestedInteger.getInteger());
            } else {
                for (NestedInteger j : nestedInteger.getList()){
                    stack.push(j);
                }
            }
        }
    }
    @Override
    public boolean hasNext() {
        return !integers.isEmpty();
    }
    @Override
    public Integer next() {
        return integers.pop();
    }
}

符号匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package leetcode.stack;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class ValidParentheses_20 {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch =='{' || ch == '[')
                stack.push(ch);
            else {
                if (stack.isEmpty())
                    return false;
                char cha = stack.pop();
                char match;
                switch (ch) {
                    case '(' :
                        match = ')';
                        break;
                    case '[':
                        match=']';
                        break;
                    default:
                        match='}';
                        break;
                }
                if (cha != match)
                    return false;
            }
        }
        return stack.isEmpty();
    }
}
Donate comment here