【阿里淘天】淘天20230824真题一、二 ＜模拟、双指针＞_淘天算法题

一、

题目描述：

小红有一个01字符串，她可以进行最多k次提作，每次操作可以交换相邻的两个字符，问可以得到的字典序最小的字符串是什么

输入描述：

一行两个整数 n 和 k，表示字符串的长度和可以进行的操作次数。
接下来一行一个长度为 n 的 01 字符串。

1<= n <=$10^5$

1<= k <=$10^9$

输出描述：

输出一个长度为 n 的字符串，表示字典序最小的字符串。

示例输入

5 2
01010
1
2

输出

00101
1

题解

双指针模拟，将第一个出现在1后面的0与最前面的1交换
判断需要交换次数大于或者小于 k，后移指向 1 的指针，满足交换次数

import java.util.Scanner;

public class A {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        in.nextLine();
        char[] input = in.nextLine().toCharArray();

        int indexOne = 0, indexZero = -1;
        while (k > 0) {
            // 找第一个是1的
            for (int i = indexOne; i < input.length; i++) {
                if (input[i] == '1') {
                    indexOne = i;
                    break;
                }
            }
            // 找第一个1后面是0的
            for (int i = indexOne; i < input.length; i++) {
                if (input[i] == '0') {
                    indexZero = i;
                    break;
                }
            }

            int index = indexZero - indexOne;

            if (k >= index) {
                k = k - index;
                char c = input[indexZero];
                input[indexZero] = input[indexOne];
                input[indexOne] = c;
            }
            else {
                indexOne = indexZero - k;
                char c = input[indexZero];
                input[indexZero] = input[indexOne];
                input[indexOne] = c;
                break;
            }
        }
        for (char c:input) {
            System.out.print(c);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

二、

讨厌鬼有一个长度为 n 的数组，他想知道这个数组有多少个子序列是一个排列?
子序列的定义：数组删除若干个元素(也可以不删)后得到的新数组。
排列的定义：长度为 m 的数组，1 到 m 每个元素都出现过，且恰好出现1次。

输入描述：

第一行输入一个整数 n (1<=n<=$10^5$)

第二行输入 n 个整数$a_i$ (1<=$a_i$<=$10^9$)

输出描述：

一行一个整数，表示有多少个子序列是一个排列。由于答案过大，请将答案对$10^9$+ 7 取模后输出

示例输入：

6
1 1 5 2 3 4
1
2

输出：

10
1

解释：

符合要求的子序列有：{1}，{1}，{1，2}，{1，2}，{1，2，3}，{1，2，3}，{1，2，3，4}，{1，2，3，4}，{1，5，2，3，4}，{1，5，2，3，4}共10个

题解

记录每个数字出现的次数
根据乘法原理，当前数字可以组合成的合法子序列个数为 cur * cnt[i]，累加

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        int[] cnt = new int[(int)1e5+10];
        int mod = (int)1e9 + 7;

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();

            cnt[nums[i]]++;//出现的次数 cnt[1]=2
        }

        // 根据乘法原理，当前数字可以组合成的合法子序列个数为cur * cnt[i]，累加即可
        int cur = 1;
        int res = 0;

        for (int i = 1; i < cnt.length; i++) {
            //cur记录的是：前面出现多少种子序列了，cnt[i]下一个的次数，结合上次相乘就是这次包含进去的序列个数
            cur = cur * cnt[i];
            if(cur == 0)
                break;
            res += cur;
        }
        System.out.println(res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30