前言

2024-3-24 17:41:54

私密发布于
2024-03-24 23:25:39

公开发布于
2024-5-23 11:13:53

以下内容源自《【笔试真题】》
仅供学习交流使用

版权

禁止其他平台发布时删除以下此话
本文首次发布于CSDN平台
作者是CSDN@日星月云
博客主页是https://jsss-1.blog.csdn.net
禁止其他平台发布时删除以上此话

小米 2024/3/12

偏爱字符串

小李天生偏爱一些字符，对于一个字符串，他总是想把字符串中的字符变成他偏爱的那些字符。
如果字符串中某个字符不是他所偏爱的字符，称为非偏爱字符，那么他会将该非偏爱字符替换为字符串中距离该字符最近的一个偏爱的字符。
这里的距离定义即为字符在字符串中的对应下标之差的绝对值。如果有不止一个偏爱的字符距离非偏爱字符最近，
那么小李会选择最左边的那个偏爱字符来营换该非偏爱字符，这样就保证了替换后的字符用是唯一的。
小李的所有替换操作是同时进行的。

假定小李有m个偏爱的字符，依次为c1，c2…，cm当小李看到一个长度为n的字符串s时，请你输出小李在进行全部替换操作后形成的字符串。

输入描述
第一行输入两个正整数n，m。
接下来一行输入m个字符c1,c2.…cm，每两个字符之间用空格隔开，表示小李偏爱的字符。
接下来一行输入一个字符围s。
1<=n<=100000，1<=m≤26，保证题目中所有的字符均为大写字符，小偏爱的字符互不相同，且偏爱字符至少出现一次。

样例输入
12 4
Z G B A
ZQWEGRTBYAAI
样例输出
ZZZGGGBBBAAA

说明
字符Q为非偏爱字符，且偏爱字符Z距离它最近，所以替换成Z;同理E距离G最近，替换成G
对于字符W，偏爱字符Z和G与其距离相同，所以替换为左边的Z
…
对于字符I，右边没有偏爱字符，左边第一个偏爱字符是A，所以替换成字符2。
同一个偏爱字符可能会在字符串中出现多次

package xiaomi20240312;

import java.util.*;


/**
 *
 * <h1>偏爱字符串</h1>
 * 小李天生偏爱一些字符，对于一个字符串，他总是想把字符串中的字符变成他偏爱的那些字符。
 * 如果字符串中某个字符不是他所偏爱的字符，称为非偏爱字符，那么他会将该非偏爱字符替换为字符串中距离该字符最近的一个偏爱的字符。
 * 这里的距离定义即为字符在字符串中的对应下标之差的绝对值。如果有不止一个偏爱的字符距离非偏爱字符最近，
 * 那么小李会选择最左边的那个偏爱字符来营换该非偏爱字符，这样就保证了替换后的字符用是唯一的。
 * 小李的所有替换操作是同时进行的。
 *
 * 假定小李有m个偏爱的字符，依次为c1，c2..，cm当小李看到一个长度为n的字符串s时，请你输出小李在进行全部替换操作后形成的字符串。
 *
 * 输入描述
 * 第一行输入两个正整数n，m。
 * 接下来一行输入m个字符c1,c2.…cm，每两个字符之间用空格隔开，表示小李偏爱的字符。
 * 接下来一行输入一个字符围s。
 * 1<=n<=100000，1<=m≤26，保证题目中所有的字符均为大写字符，小偏爱的字符互不相同，且偏爱字符至少出现一次。
 *
 * 样例输入
 * 12 4
 * Z G B A
 * ZQWEGRTBYAAI
 * 样例输出
 * ZZZGGGBBBAAA
 *
 * 说明
 * 字符Q为非偏爱字符，且偏爱字符Z距离它最近，所以替换成Z;同理E距离G最近，替换成G
 * 对于字符W，偏爱字符Z和G与其距离相同，所以替换为左边的Z
 * ....
 * 对于字符I，右边没有偏爱字符，左边第一个偏爱字符是A，所以替换成字符2。
 * 同一个偏爱字符可能会在字符串中出现多次
 */
public class Main1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine();

        Set<Character> favorites = new HashSet<>();
        for (int i = 0; i < m; i++) {
            favorites.add(scanner.next().charAt(0));
        }

        scanner.nextLine();
        String s = scanner.nextLine();

        char[] chars = s.toCharArray();

        String res = solve(favorites, chars);
        System.out.println(res);
    }

    private static String solve(Set<Character> favorites, char[] chars) {
        int n = chars.length;

        //记录下标
        int[] flag = new int[n];
        Arrays.fill(flag, -1);
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (favorites.contains(chars[i])) {
                flag[i] = i;
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
//            System.out.println(Arrays.toString(queue.toArray()));
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                Integer poll = queue.poll();

                if (poll > 0) {
                    if (flag[poll - 1] == -1) {
                        flag[poll - 1] = flag[poll];
                        chars[poll - 1] = chars[poll];
                        queue.add(poll - 1);
                    }
                }

                if (poll + 1 < n) {
                    if (flag[poll + 1] == -1) {
                        flag[poll + 1] = flag[poll];
                        chars[poll + 1] = chars[poll];
                        queue.add(poll + 1);
                    }
                }


            }
        }

        return String.valueOf(chars);

    }


}

消除游戏

小明在玩一个消除游戏。这个消除游戏有点特别。游戏中，你会得到n个一维排列的有各自颜色的砖块。
消除的时候，你有三种消除方案。你可以单消一个砖块，这样你可以得到a的得分，如果两个颜
色一样的砖块在一起，你可以将这两个砖块一起消除获得b的得分，如果三个颜色一样的砖块在
一期，你可以将这三个砖块一起消除获得c的得分。

消除后，被消除的砖块自动消失，被消除砖块的左右两端的砖块将在消除之后挨在一起.
小明想知道在最优策略下他能得到多少得分
输入描述
第一行4个整数n，a，b，c，表示砖块数盘，和一消/二消/三消的得分。
接下来一行n个整数，第i个整数si 表示第i个砖块的颜色

输出须述
输出最高得分
样例输入
8 1 3 7
3 1 3 1 3 2 2 3

样例输出
14

1<si< n<300 0<=a,b,c<=10000

package xiaomi20240312;

/**
 *
 * <h1>消除游戏</h1>
 * 小明在玩一个消除游戏。这个消除游戏有点特别。游戏中，你会得到n个一维排列的有各自颜色的砖块。
 * 消除的时候，你有三种消除方案。你可以单消一个砖块，这样你可以得到a的得分，如果两个颜
 * 色一样的砖块在一起，你可以将这两个砖块一起消除获得b的得分，如果三个颜色一样的砖块在
 * 一期，你可以将这三个砖块一起消除获得c的得分。
 *
 * 消除后，被消除的砖块自动消失，被消除砖块的左右两端的砖块将在消除之后挨在一起.
 * 小明想知道在最优策略下他能得到多少得分
 * 输入描述
 * 第一行4个整数n，a，b，c，表示砖块数盘，和一消/二消/三消的得分。
 * 接下来一行n个整数，第i个整数si 表示第i个砖块的颜色
 *
 * 输出须述
 * 输出最高得分
 * 样例输入
 * 8 1 3 7
 * 3 1 3 1 3 2 2 3
 *
 * 样例输出
 * 14
 *
 * 1<si< n<300 0<=a,b,c<=10000
 */
public class Main2 {

   
}

最后

2024-3-24 17:41:57

迎着日光月光星光，直面风霜雨霜雪霜。