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