Java每日一练(20230406)
目录
1. 翻转二叉树 🌟
2. 接雨水 🌟🌟
1. 翻转二叉树
翻转一棵二叉树。
示例:
输入:
4 / \ 2 7 / \ / \ 1 3 6 9
输出:
4 / \ 7 2 / \ / \ 9 6 3 1
出处:
https://edu.csdn.net/practice/24851844
代码:
import java.util.Arrays;
import java.util.Vector;
import java.util.Queue;
import java.util.LinkedList;
public class invertTree {
public final static int NULL = Integer.MIN_VALUE; //用NULL来表示空节点
public static void main(String[] args) {
Integer[] arr = {4,2,7,1,NULL,6,9};
Vector<Integer> vec = new Vector<Integer>(Arrays.asList(arr));
TreeNode root = createBinaryTree(vec);
printTree(root);
Solution s = new Solution();
s.invertTree(root);
printTree(root);
}
public static class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null)
return null;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode rightTree = node.right;
node.right = node.left;
node.left = rightTree;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return root;
}
}
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public static TreeNode createBinaryTree(Vector<Integer> vec) {
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 printTree(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node != null) {
System.out.print(node.val + " ");
if (node.left != null || node.right != null) {
queue.offer(node.left);
queue.offer(node.right);
}
} else {
System.out.print("null ");
}
}
System.out.println();
}
}
}
输出:
4
2 7
1 null 6 9
4
7 2
9 6 null 1
2. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5] 输出:9
提示:
n == height.length
0 <= n <= 3 * 10^4
0 <= height[i] <= 10^5
以下程序实现了这一功能,请你填补空白处内容:
```Java
public int trap(int[] height) {
if (height == null)
return 0;
int len = height.length;
if (len == 0)
return 0;
int res = 0;
int[] left_max = new int[len];
int[] right_max = new int[len];
left_max[0] = height[0];
for (int i = 1; i < len; i++) {
left_max[i] = Math.max(height[i], left_max[i - 1]);
}
right_max[len - 1] = height[len - 1];
__________________;
for (int i = 1; i < len - 1; i++) {
res += Math.min(left_max[i], right_max[i]) - height[i];
}
return res;
}
```
出处:
https://edu.csdn.net/practice/24851845
代码:
public class trap {
public static class Solution {
public int trap(int[] height) {
if (height == null)
return 0;
int len = height.length;
if (len == 0)
return 0;
int res = 0;
int[] left_max = new int[len];
int[] right_max = new int[len];
left_max[0] = height[0];
for (int i = 1; i < len; i++) {
left_max[i] = Math.max(height[i], left_max[i - 1]);
}
right_max[len - 1] = height[len - 1];
for (int i = len - 2; i >= 0; i--) {
right_max[i] = Math.max(height[i], right_max[i + 1]);
}
for (int i = 1; i < len - 1; i++) {
res += Math.min(left_max[i], right_max[i]) - height[i];
}
return res;
}
}
public static void main(String[] args) {
Solution s = new Solution();
int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
System.out.println(s.trap(height));
int[] height2 = {4,2,0,3,2,5};
System.out.println(s.trap(height2));
}
}
输出:
6
9
代码2:
单调栈:遍历每个位置时,将该位置的高度和下标入栈,如果当前位置的高度小于栈顶位置的高度,则将当前位置入栈,否则弹出栈顶位置,计算出当前位置和栈顶位置之间的水的高度,然后继续比较栈顶位置和当前位置的高度,直到栈为空或当前位置的高度小于栈顶位置的高度。
import java.util.Stack;
public class trap {
public static class Solution {
public int trap(int[] height) {
if (height == null)
return 0;
int len = height.length;
if (len == 0)
return 0;
int res = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < len; i++) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop();
if (stack.isEmpty())
break;
int left = stack.peek();
int width = i - left - 1;
int h = Math.min(height[left], height[i]) - height[top];
res += width * h;
}
stack.push(i);
}
return res;
}
}
public static void main(String[] args) {
Solution s = new Solution();
int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
System.out.println(s.trap(height));
int[] height2 = {4,2,0,3,2,5};
System.out.println(s.trap(height2));
}
}
3. 求平均值、最大值
输入若干个数,设输入的第一个数n为后面要输入的数的个数,求平均值及最大值,并在屏幕输出来
出处:
https://edu.csdn.net/practice/24851846
代码:
import java.util.Scanner;
public class Test{
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
System.out.println("输入n:");
int n=in.nextInt();
int temp,max=0,sum=0;
for(int i=0;i<n;i++){
temp=in.nextInt();
if (temp>max){
max=temp;
}
sum+=temp;
}
System.out.println("最大值为:"+max+",平均值为:"+sum*1.0/n);
}
}
输出:
略
🌟 每日一练刷题专栏 🌟
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页:https://hannyang.blog.csdn.net/
![]() | Golang每日一练 专栏 |
![]() | Python每日一练 专栏 |
![]() | C/C++每日一练 专栏 |
![]() | Java每日一练 专栏 |
相关文章
- java volatile关键字的作用_Java并发编程彻底搞懂volatile关键字「建议收藏」
- IDEA设置java 编译级别
- java.lang.IllegalArgumentException 如何解决这个异常
- Java List 随机取值的多种方法
- Java递归详解_java难不难学
- java和vue+springboot开发的电子书系统
- Java设计模式之观察者模式
- 为了避免内存攻击,美国国家安全局提倡Rust、C#、Go、Java、Ruby 和 Swift,但将 C 和 C++ 置于一边
- Java 的 Optional.ofNullable()方法,防止空指针异常
- 【Java】Best coding practices every java developer should
- Oracle下的Java分页功能_动力节点Java学院整理
- Java中CountDownLatch用法详解编程语言
- java堆排序算法代码详解编程语言
- 数据库解锁Java,优雅连接Oracle数据库(java使用oracle)
- Linux环境下编译Java程序的指南(linux编译java)
- 机制探究Redis与Java实现过期机制的科学性(redisjava过期)
- 失效Java缓存Redis实现过期失效机制(redisjava过期)
- 使用 Java 持久化 API
- 使用Java去连接MySQL数据库(java jdbc mysql)
- Java数据库之MySQL学习使用教程(mysql中java教程)
- Java锁表与Oracle数据库协调实现数据安全(java锁表oracle)
- 通往成功的道路通过Java考证Oracle获取更高的成就(java考证oracle)
- 堆栈探索Java构建Oracle堆栈的可能性(java建oracle)
- Java和Oracle技术融合,汇聚智能新大陆(java oracle包)
- java多线程编程之捕获子线程异常示例