前言

较为简单的一场，第一题考察最大最小值，第二题是输出字符串及其出现次数，，第三题直接动态规划即可。

第一题

小欧有一个数组，他可以将任意两个元素删除，并将这两个元素之和放进数组。

小欧最多可以进行一次操作，他想让数组的极值 《数组的最大值减最小值)尽可能小，求最小的极值。

输入描述

第一行输入一个整数 n(2<=n<=10^5) 表示数组长度.

第二行输入n个整数表示数组a(1<=ai<=10^9)

输出描述

输出一个整数表示答案.

示例1

输入

7
1 4 3 3 2 2 3

输出

2

说明

可以将一个1和一个3加起来变成4。
此时数组为:443223。
极值为4-2 =2。

思路与代码

根据输入的整数数组，通过一系列操作生成一个新数组，然后找到新数组中最大值和最小值之间的差的最小值，最终将其输出。这个过程涉及了排序、列表操作和数学运算等基本概念。

import java.util.*;
public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        if (n == 2) {
            System.out.println(0);
            return;
        }
        Arrays.sort(arr);
        int res = arr[n-1] - arr[0];
        List<Integer> list = new ArrayList<>();
        if (arr[0] >= 0){
            for (int i=2; i<n; i++) list.add(arr[i]);
            list.add(arr[0] + arr[1]);
        }else if (arr[n-1] <= 0){
            for (int i=0; i<n-2; i++) list.add(arr[i]);
            list.add(arr[n-1] + arr[n-2]);
        }else if(arr[n-1] > 0) {
            for (int i=1; i<n-1; i++){
                list.add(arr[i]);
            }
            list.add(arr[n-1] + arr[0]);
        }
        Collections.sort(list);
        res = Math.min(res, list.get(list.size() - 1) - list.get(0));
        System.out.println(res);
    }
}

第二题

小欧在创建文件夹，需要输入文件决的名字，比如先创建名字为“abc”的文件夹，那么此时就有一个文件夹名字为“abc”。如果存在相同名字的文件夹，则在名字后面加上一个正整数，比如“abc”已经存在，那么此时创建的文件夹名字为“abc(1)”。如果“abc(1)”也存在，那么此时创建的文件夹名字为“abc(2)”。以此类推。请你帮助小欧创建文件夹。

输入描述

第一行输入一个正整数n，表示创建文件夹的数量。
接下来 n 行，每行输入一个仅包含小写字母的字符串，表示要创建的文件夹名字，字符串长度不超过 10。
1<=n<=10^4

输出描述

输出 n 行，每行输出一个字符串，表示创建的文件夹名字。

示例1

输入

5
abc
abc
vfd
dsf

输出

abc
abc(1)
abc(2)
vfd
dsf

思路与代码

根据不同情况输出字符串及其出现次数。如果某个字符串是第一次出现，只输出字符串本身；如果某个字符串不是第一次出现，输出字符串和它之前的出现次数。

public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String cur = in.next();
            map.put(cur, map.getOrDefault(cur, 0) + 1);
            int count = map.get(cur);
            if (count == 1){
                System.out.println(cur);
            }else{
                int temp = count-1;
                System.out.println(cur + "(" + temp + ")");
            }
        }
    }
}

第三题

小欧有一个仅由小写字母组成的字符串，小欧每次可以修改一个字母，求使得字符串中至少有k个子串是“oppo”的最小修改次数。

输入描述

第一行输入两个整数 n,k(1<=n<=10^4,1<=k<=200)

第二行输入一个长度为 n 的仅由小写字母组成的字符串。

输出描述

输出一个整数表示答案。

若是无解则输出 -1。

示例1

输入

4 1
opop

输出

2

说明

可以将字符串 后两个字母改成”po”，此时字符串变成了"oppo"，有1个子串是"oppo”

思路与代码

使用动态规划的方法，计算了在给定操作次数下，通过替换字符'o'为'p'，使得字符串中的字符'p'连续出现的最小次数。如果无法进行足够的替换操作，则输出-1。

 public class Solution {
    static int kk = 0x3f3f3f3f;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        String s = in.next();
        if (n < k * 3 + 1){
            System.out.println(-1);
            return;
        }
        int[][] dp = new int[n + 1][k + 1];
        int[][] min = new int[n + 1][k + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], kk);
            Arrays.fill(min[i], kk);
        }
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
            min[i][0] = 0;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                if (i < 3 * j + 1){
                    dp[i][j] = kk;
                    continue;
                }
                int tt = 0;
                if (j == 1){
                    if (s.charAt(i - 1) != 'o') tt++;
                    if (s.charAt(i - 2) != 'p') tt++;
                    if (s.charAt(i - 3) != 'p') tt++;
                    if (s.charAt(i - 4) != 'o') tt++;
                    dp[i][j] = dp[i-4][j-1] + tt;
                    min[i][j] = Math.min(min[i-1][j], dp[i][j]);
                }else{
                    if (s.charAt(i - 1) != 'o') tt++;
                    if (s.charAt(i - 2) != 'p') tt++;
                    if (s.charAt(i - 3) != 'p') tt++;
                    dp[i][j] = dp[i-3][j-1] + tt;
                    if (s.charAt(i - 4) != 'o') tt++;
                    dp[i][j] = Math.min(min[i-4][j-1] + tt, dp[i][j]);
                    min[i][j] = Math.min(min[i-1][j], dp[i][j]);
                }
            }
        }
        int res = kk;
        for (int i = 3 * k + 1; i <= n; i++) {
            res = Math.min(res, dp[i][k]);
        }
        System.out.println(res);
    }
}