单纯做网站的公司,多站点网站群的建设与管理系统,建筑行业信息查询平台,安阳建设网站题目
对于一个连续正整数组成的序列#xff0c;可以将其拼接成一个字符串#xff0c;再将字符串里的部分字符打乱顺序。如序列8 9 10 11 12,拼接成的字符串为89101112,打乱一部分字符后得到90811211,原来的正整数10就被拆成了0和1。
现给定一个按如上规则得到的打乱字符的字…题目
对于一个连续正整数组成的序列可以将其拼接成一个字符串再将字符串里的部分字符打乱顺序。如序列8 9 10 11 12,拼接成的字符串为89101112,打乱一部分字符后得到90811211,原来的正整数10就被拆成了0和1。
现给定一个按如上规则得到的打乱字符的字符串请将其还原成连续正整数序列并输出序列中最小的数字。
输入描述
输入一行为打乱字符的字符串和正整数序列的长度两者间用空格分隔字符串长度不超过200,正整数不超过1000保证输入可以还原成唯一序列。
输出描述
输出一个数字为序列中最小的数字。
用例
输入输出19801211 58 思考
给出了有序序列的长度因此可从整数 1 开始选取连续的给定长度的数字序列和打乱序列进行匹配如果是组成成分完全相同的序列就终止选取序列循环返回枚举序列的起点数字即序列中最小数字。这个在循环中枚举起点选取固定长度序列操作就是滑动窗口思想的应用窗口的大小就是给定的序列长度。问题是怎么比较选取有序序列和打乱的目标序列我开始想到的做法竟然是把序列拆分成单个数字字符数组再转成单个数字组成的数组从小到大排序后再连接成字符串和同样这样处理的目标字符串进行比较完全相同就找到目标序列。如[9, 10, 11]-[9,1,0,1,1]-[0,1,1,1,9]-01119。这样反复拆分字符串又排序做法肯定不好。实际上比较两个字符串的成分是否相同应该统计组成它们的0-9数字频率是否相同如果相同则它们的有序序列一定相同。定义一个数组索引 0~9 对应的值为索引表示的数字出现的频率预先计算目标字符串的频率数组 matchFreqs每次移动窗口左边界时开始更新选取的数字序列频率数组 freqs并比较 matchFreqs 和 freqs 频率是否完全匹配匹配则找到结果然后返回窗口左边界值。 算法过程
统计目标字符串数字频率用长度为 10 的数组记录 0-9 各数字出现次数。确定起始数字范围最大起始值设为1000-n受题目条件限制。遍历检查可能起始值对每个起始数i生成i到in-1的数字串统计频率并与目标对比。输出匹配结果找到频率完全一致的起始值i输出即为最小数字。
时间复杂度O (m k×n)m 为字符串长度k 为遍历次数最多 1000。 参考代码
function solution() {const arr readline().split( );const n parseInt(arr[1]);const matchStr arr[0];const matchFreqs Array(10).fill(0);for (let num of matchStr) {matchFreqs[Number(num)];}const check function(i, j) {let s ;for (let k i; k j; k) {s k;}s s.toString();const freqs Array(10).fill(0);for (let c of s) {freqs[Number(c)];}for (let i 0; i 9; i) {if (freqs[i] ! matchFreqs[i]) {return false;}}return true;};for (let i 1; i 1000-n; i) {let j i n;if (check(i, j)) {console.log(i);return;}}}const cases [19801211 5,
];let caseIndex 0;
let lineIndex 0;const readline (function () {let lines [];return function () {if (lineIndex 0) {lines cases[caseIndex].trim().split(\n).map((line) line.trim());}return lines[lineIndex];};
})();cases.forEach((_, i) {caseIndex i;lineIndex 0;solution();
});
