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

一、

题目描述：

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

输入描述：

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

1<= n <=$10^5$

1<= k <=$10^9$

输出描述：

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

示例输入

5 2
01010

输出

00101

题解

双指针模拟，将第一个出现在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);}}
}

二、

讨厌鬼有一个长度为 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

输出：

10

解释：

符合要求的子序列有：{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);}
}