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); } }
输出：
略
