AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

Java每日一练(20230402) 有效括号、二叉树前序遍历、全排列

2024-01-30 81
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： Java每日一练(20230402) 有效括号、二叉树前序遍历、全排列

1. 有效的括号

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

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

示例 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

true

false

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));
    }
}

输出：

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

🌟 每日一练刷题专栏 🌟

✨持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！

🌟 收藏，你的青睐是我努力的方向！

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/


文章标签：
Java
Python
算法
C++
Go
关键词：
Java遍历
Java二叉树
Java前序遍历
Java全排列
Java排列
HannYang
目录
相关文章
长梦
|
4天前
|
存储 监控 Java
《从头开始学java，一天一个知识点》之：数组入门：一维数组的定义与遍历
**你是否也经历过这些崩溃瞬间？** - 看了三天教程，连`i++`和`++i`的区别都说不清 - 面试时被追问&quot;`a==b`和`equals()`的区别&quot;，大脑突然空白 - 写出的代码总是莫名报NPE，却不知道问题出在哪个运算符 这个系列就是为你打造的Java「速效救心丸」！我们承诺：每天1分钟，地铁通勤、午休间隙即可完成学习；直击痛点，只讲高频考点和实际开发中的「坑位」；拒绝臃肿，没有冗长概念堆砌，每篇都有可运行的代码标本。明日预告：《多维数组与常见操作》。 通过实例讲解数组的核心认知、趣味场景应用、企业级开发规范及优化技巧，帮助你快速掌握Java数组的精髓。
长梦
54 23
大树营养快线
|
4月前
|
存储 Java 开发者
在 Java 中，如何遍历一个 Set 集合？
【10月更文挑战第30天】开发者可以根据具体的需求和代码风格选择合适的遍历方式。增强for循环简洁直观，适用于大多数简单的遍历场景；迭代器则更加灵活，可在遍历过程中进行更多复杂的操作；而Lambda表达式和`forEach`方法则提供了一种更简洁的函数式编程风格的遍历方式。
大树营养快线
3838 7
刘大猫.
|
4月前
|
算法 Java
JAVA 二叉树面试题
JAVA 二叉树面试题
刘大猫.
39 0
mzlogin
|
5月前
|
Java 程序员 编译器
Java｜如何正确地在遍历 List 时删除元素
从源码分析如何正确地在遍历 List 时删除元素。为什么有的写法会导致异常，而另一些不会。
mzlogin
112 3
java冯坚持
|
5月前
|
前端开发 小程序 Java
java基础：map遍历使用；java使用 Patten 和Matches 进行正则匹配；后端传到前端展示图片三种情况，并保存到手机
这篇文章介绍了Java中Map的遍历方法、使用Pattern和matches进行正则表达式匹配，以及后端向前端传输图片并保存到手机的三种情况。
java冯坚持
56 1
GuGuStudy
|
5月前
|
Java
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
GuGuStudy
50 1
GuGuStudy
|
5月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（一）
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（一）
GuGuStudy
42 1
蓝易云
|
5月前
|
存储 算法 Java
Java一分钟之-数组的创建与遍历
数组作为Java中存储和操作一组相同类型数据的基本结构，其创建和遍历是编程基础中的基础。通过不同的创建方式，可以根据实际需求灵活地初始化数组。而选择合适的遍历方法，则可以提高代码的可读性和效率。掌握这些基本技能，对于深入学习Java乃至其他编程语言的数据结构和算法都是至关重要的。
蓝易云
42 6
刘大猫.
|
6月前
|
域名解析 分布式计算 网络协议
java遍历hdfs路径信息，报错EOFException
java遍历hdfs路径信息，报错EOFException
刘大猫.
68 3
sumith
|
9月前
|
缓存 Java 测试技术
探讨Java中遍历Map集合的最快方式
探讨Java中遍历Map集合的最快方式
sumith
140 1

热门文章

最新文章

  • 1
    领略多态的魅力-对象向上转型 | 带你学《Java面向对象编程》之四十八
  • 2
    Java程序员致命的误区：“努力”
  • 3
    Java泛型方法
  • 4
    javaWeb概要介绍
  • 5
    从 java bean 的内省到 dbutils 的应用
  • 6
    《Java核心技术 卷Ⅱ　高级特性（原书第10版）》一2.5.8　ZIP文件系统
  • 7
    Java 获取类成员方法信息
  • 8
    Java并发编程：线程间协作的两种方式：wait、notify、notifyAll和Condition
  • 9
    Java 集合系列12之 TreeMap详细介绍(源码解析)和使用示例
  • 10
    监视锁——Java同步的基本思想
  • 1
    JVM实战—1.Java代码的运行原理
    14
  • 2
    《从头开始学java，一天一个知识点》之：方法定义与参数传递机制
    38
  • 3
    《从头开始学java，一天一个知识点》之：输入与输出：Scanner与System类
    30
  • 4
    Java对象创建和访问
    13
  • 5
    【YashanDB知识库】yasdb jdbc驱动集成druid连接池，业务(java)日志中有token IDENTIFIER start异常
    21
  • 6
    【YashanDB知识库】yasdb jdbc驱动集成BeetISQL中间件，业务(java)报autoAssignKey failure异常
    11
  • 7
    《从头开始学java，一天一个知识点》之：字符串处理：String类的核心API
    36
  • 8
    《从头开始学java，一天一个知识点》之：多维数组与常见操作
    27
  • 9
    【Java并发】【synchronized】适合初学者体质入门的synchronized
    45
  • 10
    怎么理解Java中的lambda表达式
    19

    • 相关课程

    更多
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计
  • Java编程入门
  • Java面向对象编程
  • Java高级编程

    • 相关电子书

    更多
  • Java单元测试实战
  • Java应用提速（速度与激情）
  • Java工程师必读手册

    • 相关实验场景

    更多
  • 基于ECS搭建Java Web开发环境
  • 使用Aliyun Java Intializr进行项目开发
  • 搭建Java Web开发环境
  • 部署基于Dragonwell的Java运行环境
  • 阿里云平台上进行Java程序的编译与运行
  • RocketMQ中使用Java客户端发送消息和消费的应用
    • 下一篇
    获取百炼API-KEY