1. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([)]"

输出：false

示例 5：

输入：s = "{[]}"

输出：true

提示：

1 <= s.length <= 10^4

s 仅由括号 '()[]{}' 组成

出处：

https://edu.csdn.net/practice/24500359

代码1：原题中的代码

class Solution {
    public boolean isValid(String s) {
        char[] parentheses = { '(', '[', '{', ')', ']', '}' };
        int i = 0;
        char c;
        int[] sum = { 0, 0, 0 };
        Stack<Integer> top = new Stack<Integer>();
        while (i < s.length()) {
            c = s.charAt(i);
            for (int j = 0; j <= 2; j++) {
                if (c == parentheses[j]) {
                    top.push(j);
                    sum[j]++;
                } else if (c == parentheses[j + 3]) {
                    if (top.size() == 0 || top.peek() != j) {
                        return false;
                    }
                    top.pop();
                    sum[j]--;
                } else {
                }
            }
            i++;
        }
        for (int j = 0; j <= 2; j++) {
            if (sum[j] != 0) {
                return false;
            }
        }
        return true;
    }
}

代码2：

import java.util.*;
public class isValid {
    public static class Solution {
        public boolean isValid(String s) {
            Stack<Character> stack = new Stack<>();
            for (char c : s.toCharArray()) {
                if (c == '(' || c == '{' || c == '[') {
                    stack.push(c);
                } else {
                    if (stack.isEmpty()) {
                        return false;
                    }
                    char top = stack.pop();
                    if (c == ')' && top != '(') {
                        return false;
                    }
                    if (c == '}' && top != '{') {
                        return false;
                    }
                    if (c == ']' && top != '[') {
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        String[] parentheses = {"()","()[]{}","(]","([)]","{[]}"};
        for (String parenthis : parentheses) {
            System.out.println(s.isValid(parenthis));
        }
    }
}

代码3：

import java.util.*;
public class isValid {
    public static class Solution {
        public boolean isValid(String s) {
            char[] stack = new char[s.length()];
            int top = -1;
            for (char c : s.toCharArray()) {
                if (c == '(' || c == '{' || c == '[') {
                    stack[++top] = c;
                } else {
                    if (top == -1) {
                        return false;
                    }
                    char topChar = stack[top--];
                    if (c == ')' && topChar != '(') {
                        return false;
                    }
                    if (c == '}' && topChar != '{') {
                        return false;
                    }
                    if (c == ']' && topChar != '[') {
                        return false;
                    }
                }
            }
            return top == -1;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        String[] parentheses = {"()","()[]{}","(]","([)]","{[]}"};
        for (String parenthis : parentheses) {
            System.out.println(s.isValid(parenthis));
        }
    }
}

代码4：

import java.util.*;
public class isValid {
    public static class Solution {
        public boolean isValid(String s) {
            Map<Character, Character> map = new HashMap<>();
            map.put(')', '(');
            map.put('}', '{');
            map.put(']', '[');
            Stack<Character> stack = new Stack<>();
            for (char c : s.toCharArray()) {
                if (map.containsKey(c)) {
                    if (stack.isEmpty() || stack.pop() != map.get(c)) {
                        return false;
                    }
                } else {
                    stack.push(c);
                }
            }
            return stack.isEmpty();
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        String[] parentheses = {"()","()[]{}","(]","([)]","{[]}"};
        for (String parenthis : parentheses) {
            System.out.println(s.isValid(parenthis));
        }
    }
}

输出：

true

false

true

2. 二叉树的前序遍历

给你00 二叉树的根节点 root ，返回它节点值的前序遍历。

示例 1：

输入：root = [1,null,2,3]

输出：[1,2,3]

示例 2：

输入：root = []

输出：[]

示例 3：

输入：root = [1]

输出：[1]

示例 4：

输入：root = [1,2]

输出：[1,2]

示例 5：

输入：root = [1,null,2]

输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

出处：

https://edu.csdn.net/practice/24500360

代码1：递归法

import java.util.*;
import java.util.LinkedList;
public class preorderTraversal {
    public final static int NULL = Integer.MIN_VALUE; //用NULL来表示空节点
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
    public static class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> resultList = new ArrayList<>();
            if (root == null) {
                return resultList;
            }
            helper(resultList, root);
            return resultList;
        }
        public void helper(List<Integer> resultList, TreeNode root) {
            if (root == null)
                return;
            resultList.add(root.val);
            helper(resultList, root.left);
            helper(resultList, root.right);
        }
    }
    public static TreeNode createBinaryTree(Integer[] arr) {
        Vector<Integer> vec = new Vector<Integer>(Arrays.asList(arr));
        if (vec == null || vec.size() == 0) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(vec.get(0));
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                TreeNode node = queue.poll();
                if (i < vec.size() && vec.get(i) != NULL) {
                    node.left = new TreeNode(vec.get(i));
                    queue.offer(node.left);
                }
                i++;
                if (i < vec.size() && vec.get(i) != NULL) {
                    node.right = new TreeNode(vec.get(i));
                    queue.offer(node.right);
                }
                i++;
            }
        }
        return root;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        Integer[] arr = {1,NULL,2,3}; 
        TreeNode root = createBinaryTree(arr);
        System.out.println(s.preorderTraversal(root));
        Integer[] arr2 = {1,NULL,2}; 
        TreeNode root2 = createBinaryTree(arr2);
        System.out.println(s.preorderTraversal(root2));
    }
}

代码2：迭代法

用栈来模拟递归过程：从根节点开始，首先将根节点压入栈中，然后进入循环，如果栈不为空，取出栈顶元素，将其值加入到结果列表中。注意到栈的后进先出的特性：先将右子节点压入栈中，后压入左子节点，保证左子节点先于右子节点被遍历。

import java.util.*;
import java.util.LinkedList;
public class preorderTraversal {
    public final static int NULL = Integer.MIN_VALUE; //用NULL来表示空节点
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
    public static class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> resultList = new ArrayList<>();
            if (root == null) {
                return resultList;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.empty()) {
                TreeNode node = stack.pop();
                resultList.add(node.val);
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
            return resultList;
        }
    }
    public static TreeNode createBinaryTree(Integer[] arr) {
        Vector<Integer> vec = new Vector<Integer>(Arrays.asList(arr));
        if (vec == null || vec.size() == 0) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(vec.get(0));
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                TreeNode node = queue.poll();
                if (i < vec.size() && vec.get(i) != NULL) {
                    node.left = new TreeNode(vec.get(i));
                    queue.offer(node.left);
                }
                i++;
                if (i < vec.size() && vec.get(i) != NULL) {
                    node.right = new TreeNode(vec.get(i));
                    queue.offer(node.right);
                }
                i++;
            }
        }
        return root;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        Integer[] arr = {1,NULL,2,3}; 
        TreeNode root = createBinaryTree(arr);
        System.out.println(s.preorderTraversal(root));
        Integer[] arr2 = {1,NULL,2}; 
        TreeNode root2 = createBinaryTree(arr2);
        System.out.println(s.preorderTraversal(root2));
    }
}

输出：

[1, 2, 3]

[1, 2]

3. 全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出:[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

出处：

https://edu.csdn.net/practice/24500361

代码： 原题中的代码

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        List<Integer> first = new ArrayList<Integer>();
        for (int r = 0; r < nums.length; r++) {
            first.add(nums[r]);
        }
        result.add(first);
        int i = nums.length - 2;
        while (i >= 0) {
            if (nums[i] < nums[i + 1]) {
                int temp = nums[i];
                for (int j = nums.length - 1; j > i; j--) {
                    if (nums[j] > temp) {
                        nums[i] = nums[j];
                        nums[j] = temp;
                        break;
                    }
                }
                nums = quick_sort(nums, i + 1, nums.length - 1);
                List<Integer> sub = new ArrayList<Integer>();
                for (int t = 0; t < nums.length; t++) {
                    sub.add(nums[t]);
                }
                result.add(sub);
                i = nums.length - 2;
            } else {
                i--;
            }
        }
        return result;
    }
    public int[] quick_sort(int[] a, int left, int right) {
        if (left < right) {
            int l = left;
            int r = right;
            int temp = a[l];
            while (l != r) {
                while (l < r && a[r] > temp) {
                    r--;
                }
                if (l < r) {
                    a[l] = a[r];
                    l++;
                }
                while (l < r && a[l] < temp) {
                    l++;
                }
                if (l < r) {
                    a[r] = a[l];
                    r--;
                }
            }
            a[l] = temp;
            quick_sort(a, left, l - 1);
            quick_sort(a, l + 1, right);
        }
        return a;
    }
}

代码2：回溯法

import java.util.*;
public class permute {
    public static class Solution {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> path = new ArrayList<>();
            boolean[] used = new boolean[nums.length];
            backtrack(nums, path, used, res);
            return res;
        }
        private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> res) {
            if (path.size() == nums.length) {
                res.add(new ArrayList<>(path));
                return;
            }
            for (int i = 0; i < nums.length; i++) {
                if (!used[i]) {
                    path.add(nums[i]);
                    used[i] = true;
                    backtrack(nums, path, used, res);
                    used[i] = false;
                    path.remove(path.size() - 1);
                }
            }
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1,2,3};
        System.out.println(s.permute(nums));
    }
}