网站建设与网页设计课程设计,西安网站建设推广服务,成都景观设计公司,广州app网站建设一、
题目描述#xff1a;
小红有一个01字符串#xff0c;她可以进行最多k次提作#xff0c;每次操作可以交换相邻的两个字符#xff0c;问可以得到的字典序最小的字符串是什么
输入描述#xff1a;
一行两个整数 n 和 k#xff0c;表示字符串的长度和可以进行的操作…一、
题目描述
小红有一个01字符串她可以进行最多k次提作每次操作可以交换相邻的两个字符问可以得到的字典序最小的字符串是什么
输入描述
一行两个整数 n 和 k表示字符串的长度和可以进行的操作次数。 接下来一行一个长度为 n 的 01 字符串。
1 n 1 0 5 10^5 105
1 k 1 0 9 10^9 109
输出描述
输出一个长度为 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 (1n 1 0 5 10^5 105)
第二行输入 n 个整数 a i a_i ai (1 a i a_i ai 1 0 9 10^9 109)
输出描述
一行一个整数表示有多少个子序列是一个排列。由于答案过大请将答案对 1 0 9 10^9 109 7 取模后输出
示例输入
6
1 1 5 2 3 4输出
10解释
符合要求的子序列有{1}{1}{12}{12}{123}{123}{1234}{1234}{15234}{15234}共10个
题解
记录每个数字出现的次数 根据乘法原理当前数字可以组合成的合法子序列个数为 cur * cnt[i]累加
import java.util.*;public class Solution {public static void main(String[] args) {int[] cnt new int[(int)1e510];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);}
}
