java解一些算法题
题目描述
某部门计划通过结队编程来进行项目开发，已知该部门有 N 名员工，每个员工有独一无二的职级，每三个员工形成一个小组进行结队编程。
结队分组规则如下： 从部门中选出序号分别为i、j、k 的 3 名员工，他们的职级分别为 level[i], level[j], level[k]
结队小组需满足 level[i] < level[j] < level[k] 或者 level[i] > level[j] > level[k] ，其中 0 ⩽ i < j < k < n 请你按上述条件计算可能组合的小组数量。
同一员工可以参加多个小组。
输入
第一行输入：员工总数 n
第二行输入：按序号依次排列的员工的职级 level，中间用空格隔开
限制：
1 ⩽ n ⩽ 6000
1 ⩽ level[i] ⩽ 10^5
输出
可能组合的小组数量
样例输入 复制
4
1 2 3 4
样例输出 复制
4
提示
可能结队成的组合 (1,2,3)、(1,2,4)、(1,3,4)、(2,3,4)。
import java.util.Scanner;
public class TripletCounter {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取员工总数
int n = scanner.nextInt();
// 读取员工的职级
int[] levels = new int[n];
for (int i = 0; i < n; i++) {
levels[i] = scanner.nextInt();
}
// 计算并输出可能组合的小组数量
int result = countTriplets(levels);
System.out.println(result);
}
private static int countTriplets(int[] levels) {
int n = levels.length;
int count = 0;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if ((levels[i] < levels[j] < levels[k]) || (levels[i] > levels[j] > levels[k])) {
count++;
}
}
}
}
return count;
}
}
题目描述
在一个机房中，服务器的位置标识在 n*m 的整数矩阵网格中，1 表示单元格上有服务器，0 表示没有。如果两台服务器位于同一行或者同一列中紧邻的位置，则认为它们之间可以组成一个局域网。
请你统计机房中最大的局域网包含的服务器个数。
输入描述
第一行输入两个正整数，n和m，0<n,m<=100
之后为n*m的二维数组，代表服务器信息
输出描述
最大局域网包含的服务器个数。
用例
输入 2 2
1 0
1 1
输出 3
说明 [0][0]、[1][0]、[1][1]三台服务器相互连接，可以组成局域网
import java.util.Scanner;
public class LargestNetwork {
private static int n, m;
private static int[][] grid;
private static boolean[][] visited;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取 n 和 m
n = scanner.nextInt();
m = scanner.nextInt();
// 初始化网格和访问标记数组
grid = new int[n][m];
visited = new boolean[n][m];
// 读取网格数据
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = scanner.nextInt();
}
}
int maxNetworkSize = 0;
// 遍历网格，查找最大的局域网
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
int networkSize = dfs(i, j);
maxNetworkSize = Math.max(maxNetworkSize, networkSize);
}
}
}
// 输出结果
System.out.println(maxNetworkSize);
}
// 深度优先搜索方法，返回局域网大小
private static int dfs(int x, int y) {
// 定义移动方向：上、下、左、右
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
visited[x][y] = true;
int size = 1;
// 遍历四个方向
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (isValid(newX, newY) && grid[newX][newY] == 1 && !visited[newX][newY]) {
size += dfs(newX, newY);
}
}
return size;
}
// 检查坐标是否有效
private static boolean isValid(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
}
题目描述
有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。
现有两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，请输出层次遍历的结果。
输入描述
输入为两个字符串，分别是二叉树的后续遍历和中序遍历结果。
输出描述
输出二叉树的层次遍历结果。
示例1
输入：
CBEFDA CBAEDF
输出：
ABDCEF
说明：
二叉树为：
A
/
B D
/ /
C E F
import java.util.*;
class TreeNode {
char val;
TreeNode left;
TreeNode right;
TreeNode(char x) {
val = x;
}
}
public class BinaryTreeTraversal {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取后序遍历和中序遍历字符串
String postorder = scanner.next();
String inorder = scanner.next();
// 构建二叉树
TreeNode root = buildTree(postorder, inorder);
// 层次遍历二叉树并输出结果
String levelOrder = levelOrderTraversal(root);
System.out.println(levelOrder);
}
// 从后序遍历和中序遍历构建二叉树
private static TreeNode buildTree(String postorder, String inorder) {
if (postorder == null || inorder == null || postorder.length() != inorder.length()) {
return null;
}
Map<Character, Integer> inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length(); i++) {
inorderMap.put(inorder.charAt(i), i);
}
return buildTreeHelper(postorder, 0, postorder.length() - 1, inorder, 0, inorder.length() - 1, inorderMap);
}
private static TreeNode buildTreeHelper(String postorder, int postStart, int postEnd,
String inorder, int inStart, int inEnd,
Map<Character, Integer> inorderMap) {
if (postStart > postEnd || inStart > inEnd) {
return null;
}
char rootVal = postorder.charAt(postEnd);
TreeNode root = new TreeNode(rootVal);
int inorderRootIndex = inorderMap.get(rootVal);
int leftTreeSize = inorderRootIndex - inStart;
root.left = buildTreeHelper(postorder, postStart, postStart + leftTreeSize - 1,
inorder, inStart, inorderRootIndex - 1, inorderMap);
root.right = buildTreeHelper(postorder, postStart + leftTreeSize, postEnd - 1,
inorder, inorderRootIndex + 1, inEnd, inorderMap);
return root;
}
// 层次遍历二叉树
private static String levelOrderTraversal(TreeNode root) {
if (root == null) {
return "";
}
StringBuilder result = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
result.append(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return result.toString();
}
}