.net做网站用什么框架,阅读网站源码,织梦网站首页是哪个文件,集团网站建设哪个好题目 对于一个连续正整数组成的序列#xff0c;可以将其拼接成一个字符串#xff0c;再将字符串里的部分字符打乱顺序。如序列89101112, 拼接成的字符串19810112,打乱部分字符后得908112111。原来的正整数10就被拆成了0和1.现给定一个按如上规则得到的打乱字符的字符串#…题目 对于一个连续正整数组成的序列可以将其拼接成一个字符串再将字符串里的部分字符打乱顺序。如序列89101112, 拼接成的字符串19810112,打乱部分字符后得908112111。原来的正整数10就被拆成了0和1.现给定一个按如上规则得到的打乱字符的字符串请将其还原成连续正整数序列并输出序列中最小的数字 输入描述 输入行为打乱字符的字符串和正整数序列的长度两者间用空格分隔字符审长度不超过200,正整数不超过10000 保证输入可以还原成唯一序列。 输出描述 输出一个数字为序列中最小的数字 示例1: 输入 19801211 5 输出 8 说明: 正常的数字序列为8 9 10 11 12这5个数字最小数宇为8 思路
暴力法 最小值设为start1根据输入的序列长度n得到start开始长度为n的字符串tempstr判断tempStr通过打乱顺序后是否能和输入的字符串相等。如果相等则返回start否则继续遍历。 关键在于第2步如果字符串a打乱后能够得到字符串b那么字符串a和b通过排序后得到的字符串一定是相等的。 滑动窗口 判断字符串a打乱后是否能够得到字符串b字符的范围为[0-9]可以用一个int[10]的数组记录每个字符串出现的次数如下 在字符串a中各字符出现的次数得到int[] freqa; 在字符串b中各字符出现的次数得到int[] freqb; 如果freqa和freqb中每个字符出现的次数相等那么就a打乱顺序后可以得到b 滑动窗口法的代码步骤如下 用一个int[10]的数组target_freqs记录输入字符串每个字符串出现的次数初始化窗口[1,2,3,4,n-1]。使用cur_freqs记录当前窗口每个字符串出现的次数如果cur_freqs和target_freqs每个字符出现的次数均相等那么返回此窗口最左侧的值否则开始右移窗口加入一个n删除一个1并且维护cur_freqs的值 题解
滑动窗口
package hwod;import java.util.*;public class RecoveryNumQueue {private static int[] target_freqs new int[10];private static int[] cur_freqs new int[10];public static void main(String[] args) {Scanner sc new Scanner(System.in);final String[] inputs sc.nextLine().split( );String s inputs[0];int n Integer.parseInt(inputs[1]);System.out.println(recoveryNumQueue(s, n));}//滑动窗口private static int recoveryNumQueue(String s, int n) {//统计输入的字符串每个字符出现的次数for (int i 0; i s.length(); i) {target_freqs[s.charAt(i) - 0] 1;}//初始化滑动窗口LinkedListInteger queue new LinkedList();for (int i 0; i n; i) {queue.addLast(i 1);for (char c : String.valueOf(i 1).toCharArray()) {cur_freqs[c - 0] 1;}}//移动窗口while (!check(cur_freqs, target_freqs)) {int addNum queue.peekLast() 1;for (char c : String.valueOf(addNum).toCharArray()) {cur_freqs[c - 0] 1;}queue.addLast(addNum);int removeNum queue.peekFirst();for (char c : String.valueOf(removeNum).toCharArray()) {cur_freqs[c - 0] - 1;}queue.removeFirst();}return queue.peekFirst();}private static boolean check(int[] cur_freqs, int[] target_freqs) {for (int i 0; i 10; i) {if (cur_freqs[i] ! target_freqs[i]) return false;}return true;}
}
暴力破解
package hwod;import java.util.*;public class RecoveryNumQueue {private static int[] target_freqs new int[10];private static int[] cur_freqs new int[10];public static void main(String[] args) {Scanner sc new Scanner(System.in);final String[] inputs sc.nextLine().split( );String s inputs[0];int n Integer.parseInt(inputs[1]);System.out.println(recoveryNumQueue(s, n));}//暴力查找private static int recoveryNumQueue(String s, int n) {int ans 0;while (true) {if (check(ans, n, s)) return ans;ans;}}private static String sort(String string) {char[] chars string.toCharArray();Arrays.sort(chars);return String.valueOf(chars);}private static boolean check(int start, int n, String s) {StringBuilder sb new StringBuilder();for (int i start; i start n; i) {sb.append(i);}return sort(sb.toString()).equals(s);}
}
推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
