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

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

2024-01-30 52
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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
目录
相关文章
GuGuStudy
|
3月前
|
Java
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
GuGuStudy
34 1
GuGuStudy
|
3月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（一）
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（一）
GuGuStudy
30 1
刘大猫.
|
2月前
|
算法 Java
JAVA 二叉树面试题
JAVA 二叉树面试题
刘大猫.
22 0
yinying293
|
5月前
|
存储 算法 Java
LeetCode经典算法题：二叉树遍历（递归遍历+迭代遍历+层序遍历）以及线索二叉树java详解
LeetCode经典算法题：二叉树遍历（递归遍历+迭代遍历+层序遍历）以及线索二叉树java详解
yinying293
85 0
好奇的菜鸟
|
7月前
|
Java
二叉树简单遍历、查找、删除(java)
二叉树简单遍历、查找、删除(java)
好奇的菜鸟
30 0
好奇的菜鸟
|
7月前
|
存储 Java
顺序存储二叉树(java)
顺序存储二叉树(java)
好奇的菜鸟
26 0
好奇的菜鸟
|
7月前
|
Java
二叉树线索化(java)
二叉树线索化(java)
好奇的菜鸟
28 0
大数据文摘
|
10天前
|
Java
Java—多线程实现生产消费者
本文介绍了多线程实现生产消费者模式的三个版本。Version1包含四个类：`Producer`（生产者）、`Consumer`（消费者）、`Resource`（公共资源）和`TestMain`（测试类）。通过`synchronized`和`wait/notify`机制控制线程同步，但存在多个生产者或消费者时可能出现多次生产和消费的问题。 Version2将`if`改为`while`，解决了多次生产和消费的问题，但仍可能因`notify()`随机唤醒线程而导致死锁。因此，引入了`notifyAll()`来唤醒所有等待线程，但这会带来性能问题。
大数据文摘
40 1
Java—多线程实现生产消费者
2G冲浪词条
|
12天前
|
安全 Java Kotlin
Java多线程——synchronized、volatile 保障可见性
Java多线程中，`synchronized` 和 `volatile` 关键字用于保障可见性。`synchronized` 保证原子性、可见性和有序性，通过锁机制确保线程安全；`volatile` 仅保证可见性和有序性，不保证原子性。代码示例展示了如何使用 `synchronized` 和 `volatile` 解决主线程无法感知子线程修改共享变量的问题。总结：`volatile` 确保不同线程对共享变量操作的可见性，使一个线程修改后，其他线程能立即看到最新值。
2G冲浪词条
32 7
大数据文摘
|
12天前
|
消息中间件 缓存 安全
Java多线程是什么
Java多线程简介：本文介绍了Java中常见的线程池类型，包括`newCachedThreadPool`（适用于短期异步任务）、`newFixedThreadPool`（适用于固定数量的长期任务）、`newScheduledThreadPool`（支持定时和周期性任务）以及`newSingleThreadExecutor`（保证任务顺序执行）。同时，文章还讲解了Java中的锁机制，如`synchronized`关键字、CAS操作及其实现方式，并详细描述了可重入锁`ReentrantLock`和读写锁`ReadWriteLock`的工作原理与应用场景。
大数据文摘
32 7

热门文章

最新文章

  • 1
    Java volatile关键字：你真的懂了吗？
  • 2
    java小工具util系列2：字符串工具
  • 3
    Java爬虫：数据采集的强大工具
  • 4
    Java多线程并发编程：同步机制与实践应用
  • 5
    Java中的异常处理：从基础到高级
  • 6
    深入理解Java异常处理机制
  • 7
    Liunx部署java项目Tomcat、Redis、Mysql教程
  • 8
    Java爬虫：深入解析商品详情的利器
  • 9
    java实现从HDFS上下载文件及文件夹的功能，以流形式输出，便于用户自定义保存任何路径下
  • 10
    Java 异常处理：机制、策略与最佳实践
  • 1
    【Java开发指南 | 第三十一篇】Java 包(package)
    88
  • 2
    【Java开发指南 | 第二十九篇】Java接口
    52
  • 3
    【Java开发指南 | 第二十八篇】Java封装
    62
  • 4
    【Java开发指南 | 第二十六篇】Java多态
    42
  • 5
    【Java开发指南 | 第二十四篇】Java继承
    62
  • 6
    【Java开发指南 | 第九篇】访问实例变量和方法、继承、接口
    61
  • 7
    【Java开发指南 | 第八篇】Java变量、构造方法、创建对象
    95
  • 8
    Java Stream API详解与使用
    102
  • 9
    Java医院绩效考核系统源码B/S+avue+MySQL助力医院实现精细化管理
    85
  • 10
    《手把手教你》系列技巧篇（四十三）-java+ selenium自动化测试-处理https 安全问题或者非信任站点-上篇（详解教程）
    141

    • 相关课程

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

    • 相关电子书

    更多
  • Spring Cloud Alibaba - 重新定义 Java Cloud-Native
  • The Reactive Cloud Native Arch
  • JAVA开发手册1.5.0

    • 相关实验场景

    更多
  • 阿里云平台上进行Java程序的编译与运行
  • 使用Java面向对象编写网络通信程序应用
  • 手动部署Java Web环境（Alibaba Cloud Linux 2）
  • 搭建Java Web开发环境（Anolis OS）
  • RocketMQ中使用Java客户端发送消息和消费的应用
  • 部署基于Dragonwell的Java运行环境
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月