算法题系列4

标签：系列 String int 算法 static new public scanner

请设计一个文件缓存系统，该文件缓存系统可以指定缓存的最大值(单位为字节)。文件缓存系统有两种操作:存储文件(put)和读取文件(get)，操作命令为put fileName fileSize或者get fileName，存储文件是把文件放入文件缓存系统中;读取文件是从文件缓存系统中访问已存在的文件，如果文件不存在，则不作任何操作。当缓存空间不足以存放新的文件时，根据规则删除文件，直到剩余空间满足新的文件大小为止，再存放新文件。
具体的删除规则为：文件访问过后，会更新文件的最近访问时间和总的访问次数，当缓存不够时，按照第一优先顺序为访问次数从少到多，第二顺序为时间从老到新的方式来删除文件。
输入描述:
第一行为缓存最大值m(整数，取值范围为0<m<=52428800);第二行为文件操作序列个数n(0 <=n<= 300000)从第三行起为文件操作序列，每个序列单独一行文件操作定义为"op file name file size"
file name是文件名，file size是文件大小
输出描述
输出当前文件缓存中的文件名列表，文件名用英文逗号分隔，按字典顺序排序如:a.c
如果文件缓存中没有文件，则输出NONE
补充说明:
1.如果新文件的文件名和文件缓存中已有的文件名相同，则不会放在缓存中
2.新的文件第一次存入到文件缓存中时，文件的总访问次数不会变化

为了解决这个文件缓存系统的问题，我们需要设计一个高效的文件缓存系统，支持存储和读取操作，并在缓存空间不足时，按照特定的删除规则来清理旧文件。下面是一个Java实现的详细设计方案：

系统设计

数据结构：
- 使用 HashMap 存储文件信息，其中键为文件名，值为 FileEntry 对象，FileEntry 记录文件的大小、访问次数和最后访问时间。
- 使用一个 PriorityQueue 来根据文件的访问次数和最后访问时间来优先删除文件。PriorityQueue 会根据文件的访问次数（从小到大）和最后访问时间（从早到晚）排序。
操作处理：
- 存储文件 (put)：
  - 如果文件已经存在，忽略存储操作。
  - 如果文件不存在且缓存空间足够，直接存储文件。
  - 如果缓存空间不足，根据删除规则删除旧文件，直到有足够的空间存储新文件。
- 读取文件 (get)：
  - 更新文件的最后访问时间和访问次数。如果文件不存在，忽略操作。
删除文件的规则：
- 优先删除访问次数少的文件。如果多个文件访问次数相同，删除最早被访问的文件。

Java 代码实现

import java.util.*;

public class FileCacheSystem {
    static class FileEntry {
        int size;
        int accessCount;
        long lastAccessTime;

        FileEntry(int size) {
            this.size = size;
            this.accessCount = 0;
            this.lastAccessTime = System.nanoTime();
        }
    }

    private final int maxSize;
    private int currentSize;
    private final Map<String, FileEntry> cache;
    private final PriorityQueue<Map.Entry<String, FileEntry>> evictionQueue;

    public FileCacheSystem(int maxSize) {
        this.maxSize = maxSize;
        this.currentSize = 0;
        this.cache = new HashMap<>();
        this.evictionQueue = new PriorityQueue<>(
                Comparator.comparingInt((Map.Entry<String, FileEntry> e) -> e.getValue().accessCount)
                          .thenComparingLong(e -> e.getValue().lastAccessTime)
        );
    }

    public void put(String fileName, int fileSize) {
        if (fileSize > maxSize) return; // Ignore files larger than cache size
        
        if (cache.containsKey(fileName)) return; // File already in cache

        while (currentSize + fileSize > maxSize) {
            if (evictionQueue.isEmpty()) break;

            Map.Entry<String, FileEntry> entry = evictionQueue.poll();
            FileEntry fileEntry = entry.getValue();
            cache.remove(entry.getKey());
            currentSize -= fileEntry.size;
        }

        if (currentSize + fileSize <= maxSize) {
            FileEntry newEntry = new FileEntry(fileSize);
            cache.put(fileName, newEntry);
            evictionQueue.offer(new AbstractMap.SimpleEntry<>(fileName, newEntry));
            currentSize += fileSize;
        }
    }

    public void get(String fileName) {
        if (!cache.containsKey(fileName)) return; // File not in cache

        FileEntry fileEntry = cache.get(fileName);
        fileEntry.accessCount++;
        fileEntry.lastAccessTime = System.nanoTime();

        evictionQueue.removeIf(entry -> entry.getKey().equals(fileName));
        evictionQueue.offer(new AbstractMap.SimpleEntry<>(fileName, fileEntry));
    }

    public void printCache() {
        if (cache.isEmpty()) {
            System.out.println("NONE");
            return;
        }

        List<String> sortedFileNames = new ArrayList<>(cache.keySet());
        Collections.sort(sortedFileNames);

        System.out.println(String.join(",", sortedFileNames));
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int maxSize = scanner.nextInt();
        int n = scanner.nextInt();
        scanner.nextLine(); // Consume newline

        FileCacheSystem fileCacheSystem = new FileCacheSystem(maxSize);

        for (int i = 0; i < n; i++) {
            String line = scanner.nextLine();
            String[] parts = line.split(" ");
            String operation = parts[0];
            String fileName = parts[1];
            int fileSize = Integer.parseInt(parts[2]);

            if ("put".equals(operation)) {
                fileCacheSystem.put(fileName, fileSize);
            } else if ("get".equals(operation)) {
                fileCacheSystem.get(fileName);
            }
        }

        fileCacheSystem.printCache();
        scanner.close();
    }
}

说明

文件缓存系统类：
- FileEntry 记录文件的大小、访问次数和最后访问时间。
- FileCacheSystem 管理缓存的最大容量、当前容量、缓存数据及其优先队列。
操作处理：
- put 操作会添加文件到缓存中，并处理缓存空间不足的情况。
- get 操作会更新文件的访问次数和最后访问时间。
- printCache 方法打印缓存中的文件名，按字典顺序排序。
性能考虑：
- PriorityQueue 的使用确保了能够在 O(log N) 时间复杂度内进行优先级排序和删除操作。
- HashMap 用于快速访问文件信息和更新缓存。
输入和输出：
- 输入通过 Scanner 读取，输出通过 System.out.println 输出缓存中文件的排序结果。

此实现有效地处理了文件缓存系统中的存储、读取和缓存清理操作，能够处理大规模的操作序列，并满足题目要求。

题目描述
评估一个网络的信号质量，其中一个做法是将网络划分为栅格，然后对每个栅格的信号质量计算，路测的时候，希望选择一条信号最好的路线（彼此相连的栅格集合）进行演示，现给出R行C列的整数数组COV，每个单元格的数值S即为该栅格的信号质量（已归一化，无单位，值越大信号越好）

要求从[0,0]到[R-1,C-1]设计一条最优路测路线。返回该路线得分。

规则:

路测路线可以上下左右四个方向，不能对角
路线的评分是以路线上信号最差的栅格为准的，例如路径8->4->5->9的值为 4，该线路评分为4。线路最优表示该条线路的评分最高。

输入
第1行表示栅格的行数R

第2行表示栅格的列数C

第3行开始，每一行表示栅格地图一行的信号值，如5 4 5

输出
最优路线的得分
样例输入
3
3
5 4 5
1 2 6
7 4 6
样例输出
4
提示
1 <= R,C <= 20

0 <= S <= 65535

要解决这个问题，我们需要找到一条从栅格左上角 (0,0) 到右下角 (R-1,C-1) 的路径，使得路径上的最小信号质量最大。这是一个典型的最优路径问题，其中路径的评分是路径上最小信号质量的最大值。

思路

我们可以使用 最大最小路径（Maximum Minimum Path） 的策略来解决这个问题。这种策略的核心思想是将所有路径分数转化为一个最大最小路径问题。具体步骤如下：

定义目标：
- 我们希望找到一条路径，使得路径上所有栅格的最小信号质量尽可能大。换句话说，找到路径中最小信号质量的最大值。
二分搜索结合 BFS：
- 二分搜索：在可能的信号质量值范围内进行二分搜索，以确定路径中最小信号质量的最大可能值。
- BFS（广度优先搜索）：对于每个候选信号质量值，使用 BFS 来检查从 (0,0) 到 (R-1,C-1) 是否存在一条路径，其中所有栅格的信号质量都大于或等于该候选值。

具体实现

输入处理：
- 读取栅格的行数和列数。
- 读取每个栅格的信号质量，并存储在二维数组中。
二分搜索：
- 定义信号质量的范围，即从最小值到最大值。
- 对于每个候选值，使用 BFS 检查是否存在一条符合条件的路径。
BFS 实现：
- 从起始栅格 (0,0) 开始，检查是否能到达终点 (R-1,C-1)。
- 在 BFS 过程中，确保路径上所有栅格的信号质量都大于或等于当前候选值。

Java 代码实现

import java.util.*;

public class NetworkSignal {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int R = scanner.nextInt();
        int C = scanner.nextInt();
        int[][] grid = new int[R][C];
        
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }
        
        System.out.println(findMaxMinPath(grid, R, C));
    }

    private static int findMaxMinPath(int[][] grid, int R, int C) {
        int left = 0, right = 65535; // Possible signal quality range
        
        // Binary search to find the maximum minimum value of the path
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (canReach(grid, R, C, mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }

    private static boolean canReach(int[][] grid, int R, int C, int minSignal) {
        boolean[][] visited = new boolean[R][C];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;
        
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // Right, Down, Left, Up
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0];
            int y = curr[1];
            
            if (x == R - 1 && y == C - 1) {
                return true; // Reached the end
            }
            
            for (int[] dir : directions) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                
                if (newX >= 0 && newX < R && newY >= 0 && newY < C && !visited[newX][newY] && grid[newX][newY] >= minSignal) {
                    visited[newX][newY] = true;
                    queue.offer(new int[]{newX, newY});
                }
            }
        }
        
        return false; // No path found
    }
}

说明

二分搜索：在 [0, 65535] 的范围内查找，使得信号质量值最大化。
BFS：用于检查从 (0,0) 到 (R-1,C-1) 是否存在符合当前信号质量的路径。
复杂度：
- 时间复杂度：主要是二分搜索和 BFS 的复杂度，总体上是 ( O(\log M \cdot (R \cdot C)) )，其中 ( M ) 是信号质量的范围。
- 空间复杂度：主要是 BFS 使用的队列和访问标记，空间复杂度是 ( O(R \cdot C) )。

此代码实现了题目要求，能够有效地处理给定大小的信号栅格，并找到最优路径的评分。

题目

警察在侦破一个案件时，得到了线人给出的可能犯罪时间，形如 “HH:MM” 表示的时刻。根据警察和线人的约定，为了隐蔽，该时间是修改过的，解密规则为：利用当前出现过的数字，构造下一个距离当前时间最近的时刻，则该时间为可能的犯罪时间。每个出现数字都可以被无限次使用。

输入描述：形如 HH:MM 的字符串，表示原始输入

输出描述：形如 HH:MM 的字符串，表示推理出来的犯罪时间

示例 1
输入
18:52
输出
18:55
说明
利用数字1, 8, 5, 2构造出来的最近时刻是18:55，是3分钟之后。结果不是18:51因为这个时刻是18小时52分钟之后。

示例 2
输入
23:59
输出
22:22
说明
利用数字2, 3, 5, 9构造出来的最近时刻是22:22。答案一定是第二天的某一时刻，所以选择可构造的最小时刻为犯罪时间。

答案

import java.util.HashSet;
import java.util.Set;

public class NextClosestTime {
    public static void main(String[] args) {
        String input = "18:52"; // Example input; replace with actual input
        System.out.println(findNextClosestTime(input));
    }

    public static String findNextClosestTime(String time) {
        Set<Character> digits = new HashSet<>();
        for (char c : time.toCharArray()) {
            if (c != ':') {
                digits.add(c);
            }
        }
        
        String currentTime = time;
        while (true) {
            currentTime = getNextTime(currentTime);
            if (isValidTime(currentTime, digits)) {
                return currentTime;
            }
        }
    }

    private static String getNextTime(String time) {
        String[] parts = time.split(":");
        int hours = Integer.parseInt(parts[0]);
        int minutes = Integer.parseInt(parts[1]);

        minutes++;
        if (minutes == 60) {
            minutes = 0;
            hours++;
            if (hours == 24) {
                hours = 0;
            }
        }

        return String.format("%02d:%02d", hours, minutes);
    }

    private static boolean isValidTime(String time, Set<Character> digits) {
        String[] parts = time.split(":");
        String hourPart = parts[0];
        String minutePart = parts[1];

        for (char c : hourPart.toCharArray()) {
            if (!digits.contains(c)) {
                return false;
            }
        }

        for (char c : minutePart.toCharArray()) {
            if (!digits.contains(c)) {
                return false;
            }
        }

        return true;
    }
}

解释

提取数字：从给定的时间中提取出所有出现的数字，并存入一个集合 digits。
生成下一个时间：逐步生成下一个时间，直到找到一个满足条件的时间。时间递增的逻辑在 getNextTime 方法中实现。
验证时间有效性：检查生成的时间是否仅使用了之前出现的数字。通过 isValidTime 方法进行验证。
处理时间：如果找到了一个符合条件的时间，则返回；否则继续查找。

题目

给定两个字符串 A 和 B，将其映射到一个二维数组中，每个字符为一个坐标轴上的点。定义原点为 (0, 0)，终点为 (m, n)，其中 m 和 n 分别为字符串 A 和 B 的长度。每两个字符相同的坐标点之间可以作一个斜边，斜边的距离为 1。我们需要计算从 (0, 0) 到 (m, n) 的最短路径距离。路径可以是水平、垂直或斜边的组合。

输入描述

两个字符串 A 和 B，长度不超过 1000。

输出描述

输出从 (0, 0) 到 (m, n) 的最短距离。

示例

输入

ABCABBA
CBABAC

输出

解题思路

定义问题: 我们需要在一个二维网格中寻找最短路径，允许水平、垂直和斜对角移动。网格的每一个点对应于字符串 A 和 B 的一个字符。如果两个字符相同，可以沿对角线移动。
使用动态规划: 我们可以使用动态规划 (DP) 来解决这个问题。定义一个 DP 表格 dp[i][j] 表示从 (0, 0) 到 (i, j) 的最短距离。初始状态为 dp[0][0] = 0，即起点的距离为 0。
状态转移:
- 从 (i-1, j) 到 (i, j) 需要加上水平边的距离。
- 从 (i, j-1) 到 (i, j) 需要加上垂直边的距离。
- 从 (i-1, j-1) 到 (i, j) 需要加上斜边的距离，前提是 A[i-1] 和 B[j-1] 相同。
边界条件: 需要处理边界条件，如初始化第一行和第一列。
最终结果: dp[m][n] 即为从 (0, 0) 到 (m, n) 的最短距离。

Java 代码实现

public class ShortestPath {
    public static void main(String[] args) {
        String A = "ABCABBA";
        String B = "CBABAC";
        System.out.println(findShortestDistance(A, B));
    }

    public static int findShortestDistance(String A, String B) {
        int m = A.length();
        int n = B.length();
        
        // Create a 2D array to store the minimum distance
        int[][] dp = new int[m + 1][n + 1];
        
        // Initialize the DP table
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        
        // Starting point
        dp[0][0] = 0;
        
        // Fill the DP table
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i > 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
                }
                if (j > 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
                }
                if (i > 0 && j > 0 && A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }
        
        // The answer is the shortest distance to (m, n)
        return dp[m][n];
    }
}

解释

初始化: dp 表格初始化为 Integer.MAX_VALUE，表示初始状态下距离为无穷大。
动态规划填表:
- 对于每个点 (i, j)，检查从 (i-1, j) 和 (i, j-1) 的水平和垂直边的距离。
- 如果 A[i-1] 和 B[j-1] 相同，还需检查斜对角的距离。
输出: dp[m][n] 是最终从 (0, 0) 到 (m, n) 的最短距离。

题目

给定一个一维整型数组，计算数组中的众数，并组成一个新的数组，然后求出这个新数组的中位数。具体步骤如下：

众数是指一组数据中出现次数最多的数。如果有多个数出现次数相同且最多，它们都算作众数。
中位数是指将数组从小到大排列后，取最中间的数。如果数组元素个数为偶数，则取中间两个数之和除以 2 的结果。

输入描述

输入一个一维整型数组，数组大小取值范围 0 < N < 1000，数组中每个元素取值范围 0 < E < 1000。

输出描述

输出众数组成的新数组的中位数。

示例

示例 1

输入

10 11 21 19 21 17 21 16 21 18 15

输出

示例 2

输入

2 1 5 4 3 3 9 2 7 4 6 2 15 4 2 4

输出

解题思路

计算众数:
- 使用哈希表统计每个数字出现的次数。
- 找到出现次数最多的数字，即为众数。如果有多个出现次数最多的数字，所有这些数字都应被记录下来。
生成新数组:
- 根据众数生成一个新数组，其中包含所有众数的值。
计算中位数:
- 将新数组进行排序。
- 根据新数组的长度，计算中位数。如果长度为奇数，取中间元素；如果长度为偶数，取中间两个元素的平均值。

Java 代码实现

import java.util.*;

public class ModeMedian {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        
        // Convert input to integer array
        int[] arr = Arrays.stream(input).mapToInt(Integer::parseInt).toArray();
        
        // Find the mode(s)
        List<Integer> modes = findModes(arr);
        
        // Calculate median of the mode array
        double median = findMedian(modes);
        
        // Print the median
        System.out.println((int) median);
    }
    
    // Function to find the mode(s) of the array
    public static List<Integer> findModes(int[] arr) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        int maxFrequency = 0;
        
        // Build frequency map and find max frequency
        for (int num : arr) {
            int frequency = frequencyMap.getOrDefault(num, 0) + 1;
            frequencyMap.put(num, frequency);
            maxFrequency = Math.max(maxFrequency, frequency);
        }
        
        // Collect all modes
        List<Integer> modes = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            if (entry.getValue() == maxFrequency) {
                modes.add(entry.getKey());
            }
        }
        
        return modes;
    }
    
    // Function to calculate median of a list of integers
    public static double findMedian(List<Integer> list) {
        Collections.sort(list);
        int size = list.size();
        if (size % 2 == 1) {
            return list.get(size / 2);
        } else {
            return (list.get(size / 2 - 1) + list.get(size / 2)) / 2.0;
        }
    }
}

解释

输入处理:
- 读取并解析输入，将字符串转换为整数数组。
计算众数:
- 使用哈希表统计每个数的出现次数。
- 找到最大出现次数的所有数，并记录下来。
计算中位数:
- 将众数列表进行排序，并根据其长度计算中位数。
输出结果:
- 打印中位数。如果输入的数组为空或不存在有效众数，则处理后的结果根据实际情况处理。

这个解决方案高效地处理了数组众数和中位数的计算，适用于给定的输入范围。

题目

设计一个简易的重复内容识别系统。系统需要处理两个字符串，并通过给定的相似字符对来判断这两个字符串是否相似。如果相似，则返回 True 和相似的字符对；如果不相似，则返回第一个内容的“不相似”信息。

输入描述

两个字符串 str1 和 str2 需要比较相似性。
一些相似字符对，如 (顿号, 逗号) 表示顿号和逗号相似。
匹配相似字符对时，字符对可以有任意长度的内容匹配。

输出描述

如果两个字符串相似，输出 True 和相似的字符对。
如果不相似，返回第一个内容的不相似信息。多处不相似的字符串用空格分隔。

示例

示例 1

输入

异世邪君（人气玄幻作家）
异世邪君
(异世邪君, 异世邪君)

输出

True (异世邪君, 异世邪君)

示例 2

输入

hello world
hello, world
(hello, hello) (world, world)

输出

hello world

解题思路

建立相似字符对的映射关系:
- 使用一个字典来存储所有的相似字符对。
- 利用传递性关系将所有相关字符对连接在一起。
替换字符串中的字符:
- 使用上述映射关系将字符串中的字符替换为它们的相似字符。
- 例如，如果 顿号 和 逗号 是相似的，那么所有的 顿号 可以替换为 逗号，进行比较时将其替换为相似字符集合的标准字符。
比较字符串:
- 将两个字符串转换为标准形式后进行比较。
- 如果两者相等，则返回相似结果和相似字符对。
- 如果不相等，返回不相似的内容。

Java 代码实现

import java.util.*;

public class ContentSimilarity {

    private static Map<String, Set<String>> similarityMap = new HashMap<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Read input
        String str1 = scanner.nextLine().trim();
        String str2 = scanner.nextLine().trim();
        String[] pairs = scanner.nextLine().trim().split(" ");
        
        // Initialize similarity map
        initializeSimilarityMap(pairs);
        
        // Check similarity
        if (areSimilar(str1, str2)) {
            System.out.println("True " + getSimilarPairs());
        } else {
            System.out.println(getDissimilarParts(str1));
        }
        
        scanner.close();
    }
    
    // Initialize similarity map
    private static void initializeSimilarityMap(String[] pairs) {
        for (String pair : pairs) {
            String[] parts = pair.replace("(", "").replace(")", "").split(",");
            if (parts.length == 2) {
                String a = parts[0].trim();
                String b = parts[1].trim();
                
                similarityMap.computeIfAbsent(a, k -> new HashSet<>()).add(b);
                similarityMap.computeIfAbsent(b, k -> new HashSet<>()).add(a);
                
                // Adding transitive relations
                addTransitiveRelations(a, b);
            }
        }
    }
    
    // Add transitive relations to the map
    private static void addTransitiveRelations(String a, String b) {
        Set<String> aSet = similarityMap.get(a);
        Set<String> bSet = similarityMap.get(b);
        
        if (aSet != null && bSet != null) {
            for (String item : bSet) {
                aSet.add(item);
                similarityMap.get(item).add(a);
            }
            for (String item : aSet) {
                bSet.add(item);
                similarityMap.get(item).add(b);
            }
        }
    }
    
    // Check if two strings are similar
    private static boolean areSimilar(String str1, String str2) {
        return transform(str1).equals(transform(str2));
    }
    
    // Transform string based on similarity map
    private static String transform(String str) {
        StringBuilder transformed = new StringBuilder();
        for (char ch : str.toCharArray()) {
            String chStr = String.valueOf(ch);
            if (similarityMap.containsKey(chStr)) {
                transformed.append(getRepresentative(chStr));
            } else {
                transformed.append(ch);
            }
        }
        return transformed.toString();
    }
    
    // Get representative for a character or string
    private static String getRepresentative(String str) {
        Set<String> set = similarityMap.get(str);
        return set != null ? set.iterator().next() : str;
    }
    
    // Get similar pairs
    private static String getSimilarPairs() {
        StringBuilder result = new StringBuilder();
        for (Map.Entry<String, Set<String>> entry : similarityMap.entrySet()) {
            for (String similar : entry.getValue()) {
                result.append("(").append(entry.getKey()).append(", ").append(similar).append(") ");
            }
        }
        return result.toString().trim();
    }
    
    // Get dissimilar parts
    private static String getDissimilarParts(String str) {
        return str;
    }
}

解释

建立相似字符对的映射关系:
- 利用哈希表存储每个字符的相似字符对，并建立传递关系。
字符串转换:
- 将字符串中所有字符根据映射关系转换为标准字符。
比较和输出:
- 比较转换后的两个字符串是否相同，如果相同则输出相似的字符对；否则输出第一个内容的不相似信息。

题目

给定一张地图上有 n 个城市和道路，城市间的道路构成了一棵树。要求找到一个城市，使得切断通往该城市的所有道路后，地图上最大的城市群（连通分量）的城市数目最小。具体来说，求解每个城市的聚集度（Degree of Polymerization，DP），DP 定义为：切断该城市后，形成的多个连通子图中最大的城市数目。我们需要找出所有使得 DP 最小的城市，并按升序输出。

输入描述

第一行是一个整数 N，表示城市的数量，1 <= N <= 1000。
接下来的 N-1 行，每行包含两个整数 x 和 y，表示城市 x 和城市 y 之间有一条道路。

输出描述

输出所有使得 DP 最小的城市编号。如果有多个，按编号升序输出。

示例

示例 1

输入

输出

示例 2

输入

输出

2 3

解题思路

建图:
- 使用邻接表来存储城市之间的连接关系。由于城市构成树状结构，所以每个节点的连接关系只有一个。
DFS 计算子树大小:
- 使用深度优先搜索 (DFS) 计算每个节点的子树大小。
计算 DP 值:
- 对于每个城市 i，假设移除 i，计算所有生成的子图的大小，并得到 DP 值。
- 计算 DP 值时，对于每个节点，移除该节点后，可以得到多个子图。DP 值为这些子图中最大的子图的大小。
寻找最小 DP 值的城市:
- 遍历所有城市，找到 DP 值最小的城市，并输出这些城市编号。

Java 实现

import java.util.*;

public class MinDegreeOfPolymerization {

    private static List<List<Integer>> graph;
    private static int[] subtreeSize;
    private static int n;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        graph = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            graph.get(x).add(y);
            graph.get(y).add(x);
        }

        subtreeSize = new int[n + 1];
        boolean[] visited = new boolean[n + 1];
        calculateSubtreeSizes(1, visited);

        int minDp = Integer.MAX_VALUE;
        List<Integer> result = new ArrayList<>();
        
        for (int i = 1; i <= n; i++) {
            int dp = calculateDP(i);
            if (dp < minDp) {
                minDp = dp;
                result.clear();
                result.add(i);
            } else if (dp == minDp) {
                result.add(i);
            }
        }

        Collections.sort(result);
        System.out.println(result.stream().map(String::valueOf).collect(Collectors.joining(" ")));
    }

    private static void calculateSubtreeSizes(int node, boolean[] visited) {
        visited[node] = true;
        subtreeSize[node] = 1;
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                calculateSubtreeSizes(neighbor, visited);
                subtreeSize[node] += subtreeSize[neighbor];
            }
        }
    }

    private static int calculateDP(int root) {
        boolean[] visited = new boolean[n + 1];
        visited[root] = true;
        int maxSize = 0;

        for (int neighbor : graph.get(root)) {
            if (!visited[neighbor]) {
                maxSize = Math.max(maxSize, dfsSize(neighbor, visited));
            }
        }

        return maxSize;
    }

    private static int dfsSize(int node, boolean[] visited) {
        visited[node] = true;
        int size = 1;
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                size += dfsSize(neighbor, visited);
            }
        }
        return size;
    }
}

解释

图的构建:
- 用邻接表表示城市之间的连接关系。
DFS 计算子树大小:
- 从一个节点开始，使用 DFS 计算每个节点的子树大小。
计算 DP 值:
- 对于每个城市，计算切断它后生成的各个子图的大小，确定最大值作为 DP 值。
找出最小 DP 值的城市:
- 遍历所有城市，找到 DP 值最小的城市，并输出这些城市编号。

题目

某公司部门需要派遣员工去国外做项目。代号为 x 的国家和代号为 y 的国家分别需要 cntx 名和 cnty 名员工。每个员工有一个员工号（1, 2, 3, ...），工号连续，从1开始。

部长派遣员工的规则：

从 [1, k] 中选择员工派遣出去。
编号为 x 的倍数的员工不能去 x 国，编号为 y 的倍数的员工不能去 y 国。

问题：

找到最小的 k，使得可以将编号在 [1, k] 中的员工分配给 x 国和 y 国，且满足 x 国和 y 国的需求。

输入描述

四个整数 x, y, cntx, cnty。

条件：

2 ≤ x < y ≤ 30000
x 和 y 一定是质数
1 ≤ cntx, cnty < 10^9
cntx + cnty ≤ 10^9

输出描述

输出满足条件的最小的 k。

解题思路

确定有效员工总数:
- 需要排除 x 和 y 的倍数。对于每个 k，总员工数是 k，但我们需要排除掉不能派遣的员工。即不能派遣的员工数包括 k / x 和 k / y，但需要加上 k / lcm(x, y)，因为那些是 x 和 y 的倍数的员工被计算了两次。
计算公式:
- 使用以下公式来确定有效员工总数：
  [
  \text{有效员工总数} = k - \left(\frac{k}{x} + \frac{k}{y} - \frac{k}{\text{lcm}(x, y)}\right)
  ]
- 这里，lcm(x, y) 是 x 和 y 的最小公倍数，可以通过公式计算：
  [
  \text{lcm}(x, y) = \frac{x \times y}{\text{gcd}(x, y)}
  ]
- 用二分查找来找到最小的 k，使得有效员工总数至少满足 cntx + cnty。
二分查找:
- 二分查找从 1 到一个合理的上界（例如 cntx + cnty + max(x, y)），在每一步中计算有效员工数，并判断是否能满足需求。

Java 实现

import java.util.Scanner;

public class EmployeeDispatch {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int x = scanner.nextInt();
        int y = scanner.nextInt();
        long cntx = scanner.nextLong();
        long cnty = scanner.nextLong();

        long left = 1;
        long right = cntx + cnty;
        long result = right;

        while (left <= right) {
            long mid = left + (right - left) / 2;
            long validEmployees = mid - (mid / x + mid / y - mid / lcm(x, y));

            if (validEmployees >= cntx + cnty) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(result);
    }

    private static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    private static long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }
}

解释

计算有效员工总数:
- 使用 k - (k / x + k / y - k / lcm(x, y)) 公式来计算有效员工数量。
二分查找:
- 在 [1, cntx + cnty] 范围内进行二分查找来找到满足条件的最小 k。
辅助函数:
- gcd 和 lcm 用于计算最小公倍数。

结果

通过上述实现，可以找到满足条件的最小 `k`。使用二分查找的方法保证了效率，即使 `cntx` 和 `cnty` 很大，代码仍然可以在合理的时间内完成计算。

题目描述

项目组有 N 名开发人员，项目经理接到了 M 个独立需求，每个需求的工作量不同，且每个需求只能由一个开发人员独立完成，不能多人合作。任务是帮助项目经理安排工作，使得整个项目用最少的时间交付。

输入描述

第一行输入为 M 个需求的工作量，单位为天，用逗号隔开。例如：6 2 7 7 9 3 2 1 3 11 4。
第二行输入为项目组人员数量 N。例如：2。

输出描述

输出最快完成所有工作的天数。

示例

输入

6 2 7 7 9 3 2 1 3 11 4
2

输出

说明

共有两位员工，分配需求 6 2 7 7 3 2 1 共需要 28 天完成，另一位分配需求 9 3 11 4 共需要 27 天完成，因此整个项目的最短完成时间是 28 天。

解题思路

这个问题可以转化为一个 “工作分配问题”，它类似于一个 “最小最大负载” 问题。目标是将任务分配给 N 个开发人员，使得所有开发人员的工作量的最大值尽可能地小。

具体步骤：

定义问题:
- 将任务分配给 N 个开发人员，最小化完成所有工作的最大天数。
- 这是一个典型的分配问题，可以用二分查找配合贪心算法解决。
二分查找:
- 设定搜索范围：
  - 最小值是最大工作量（因为至少一个开发人员要处理最大任务）。
  - 最大值是所有工作量之和（即所有工作都由一个人完成的情况）。
检查函数:
- 设计一个函数来判断某个时间 T 是否能够将所有任务分配给 N 个开发人员，使得每个开发人员的工作时间不超过 T。
二分查找算法:
- 在上述范围内进行二分查找，根据检查函数的结果来调整搜索范围，最终确定最小的 T。

Java 实现

import java.util.Scanner;

public class ProjectManager {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取需求的工作量
        String[] input = scanner.nextLine().split(" ");
        int[] workloads = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            workloads[i] = Integer.parseInt(input[i]);
        }
        
        // 读取项目组人员数量
        int N = scanner.nextInt();
        
        // 二分查找范围的设定
        int low = 0;
        int high = 0;
        for (int workload : workloads) {
            low = Math.max(low, workload);
            high += workload;
        }
        
        // 二分查找最小的最大工作时间
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (canDistributeWork(workloads, N, mid)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        
        // 输出结果
        System.out.println(low);
    }

    // 检查是否可以将工作分配给 N 个开发人员，且最大工作时间不超过 maxTime
    private static boolean canDistributeWork(int[] workloads, int N, int maxTime) {
        int count = 1;
        int currentTime = 0;
        
        for (int workload : workloads) {
            if (currentTime + workload > maxTime) {
                count++;
                currentTime = workload;
                if (count > N) {
                    return false;
                }
            } else {
                currentTime += workload;
            }
        }
        return true;
    }
}

解释

输入解析:
- 读取并解析工作量数组以及员工数量。
二分查找:
- 使用二分查找确定最小的最大工作时间。
检查函数:
- canDistributeWork 函数判断给定最大工作时间下，是否可以在 N 名开发人员之间合理分配工作。
输出结果:
- 输出满足条件的最小最大工作时间。

题目描述

给定一个包含 0 和 1 的二维矩阵，物体从给定的初始位置开始移动，以给定的速度进行运动。在碰到矩阵边缘时，物体会发生镜面反射。你需要计算在经过 t 时间单位后，物体经过的 1 的点的次数。

输入描述

矩阵：一个二维矩阵，只包含 0 和 1。
初始位置：物体的初始位置 (x, y)。
速度：物体的速度 (vx, vy)，表示物体每个时间单位在 x 和 y 方向上的移动距离。
时间 t：模拟的时间单位。

输出描述

输出在经过 t 时间单位后，物体经过的 1 的点的次数。

示例

输入

输出

解释

在给定的初始位置 (2, 2) 和速度 (1, 1) 下，物体在 3 个时间单位后经过的点如下：

时间 0: (2, 2)，值为 1。
时间 1: (3, 3)，值为 0。
时间 2: (4, 4)，值为 1。
时间 3: (0, 0)，值为 1（经过边界反射）。

在这些时间点中，物体总共经过了 7 个 1。

解题思路

矩阵反射处理:
- 对于物体的每次移动，检查是否超出了矩阵的边界。若超出，则调整方向进行反射。
位置计算:
- 使用模运算和反射逻辑来计算物体的位置。例如，x 轴的反射可以通过 (x + t * vx) % (2 * (cols - 1)) 计算，然后调整方向。
遍历每个时间单位:
- 从时间 0 到时间 t，计算物体的位置并检查其值是否为 1，并统计经过 1 的次数。

Java 实现

import java.util.Scanner;

public class MatrixReflection {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取矩阵的行和列
        int rows = scanner.nextInt();
        int cols = scanner.nextInt();
        
        // 读取矩阵
        int[][] matrix = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }
        
        // 读取初始位置和速度
        int startX = scanner.nextInt();
        int startY = scanner.nextInt();
        int vx = scanner.nextInt();
        int vy = scanner.nextInt();
        
        // 读取时间 t
        int t = scanner.nextInt();
        
        // 计算经过的1的点的次数
        int count = 0;
        
        for (int time = 0; time <= t; time++) {
            int x = startX + time * vx;
            int y = startY + time * vy;
            
            // 处理 x 方向反射
            int horizontalPeriod = 2 * (cols - 1);
            if (x < 0) {
                x = -x;
                x = (x / horizontalPeriod) % 2 == 0 ? x % horizontalPeriod : horizontalPeriod - x % horizontalPeriod;
            } else {
                x = x % horizontalPeriod;
                if (x >= cols) {
                    x = horizontalPeriod - x;
                }
            }
            
            // 处理 y 方向反射
            int verticalPeriod = 2 * (rows - 1);
            if (y < 0) {
                y = -y;
                y = (y / verticalPeriod) % 2 == 0 ? y % verticalPeriod : verticalPeriod - y % verticalPeriod;
            } else {
                y = y % verticalPeriod;
                if (y >= rows) {
                    y = verticalPeriod - y;
                }
            }
            
            // 检查当前位置是否是1
            if (matrix[y][x] == 1) {
                count++;
            }
        }
        
        // 输出结果
        System.out.println(count);
    }
}

说明

矩阵处理:
- 读取矩阵并初始化。
位置计算:
- 使用反射逻辑计算当前位置，并处理边界情况。
统计:
- 遍历每个时间单位，检查当前位置并统计经过 1 的次数。

标签：系列,String,int,算法,static,new,public,scanner
From： https://www.cnblogs.com/mingyu15/p/18353104

系统设计

Java 代码实现

说明

思路

具体实现

Java 代码实现

说明

题目

答案

解释

题目

输入描述

输出描述

示例

解题思路

Java 代码实现

解释

题目

输入描述

输出描述

示例

解题思路

Java 代码实现

解释

这个解决方案高效地处理了数组众数和中位数的计算，适用于给定的输入范围。

题目

输入描述

输出描述

示例

解题思路

Java 代码实现

解释

题目

输入描述

输出描述

示例

解题思路

Java 实现

解释

题目

输入描述

输出描述

解题思路

Java 实现

解释

结果

通过上述实现，可以找到满足条件的最小 k。使用二分查找的方法保证了效率，即使 cntx 和 cnty 很大，代码仍然可以在合理的时间内完成计算。

题目描述

输入描述

输出描述

示例

解题思路

Java 实现

解释

题目描述

输入描述

输出描述

示例

解题思路

Java 实现

说明

相关文章

赞助商

阅读排行

通过上述实现，可以找到满足条件的最小 `k`。使用二分查找的方法保证了效率，即使 `cntx` 和 `cnty` 很大，代码仍然可以在合理的时间内完成计算。