可上 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1441了解算法冲刺训练（备注【CSDN】否则不通过）

文章目录

相关推荐阅读

题目练习网址：【哈希表】双机位A-恢复数字序列

题目描述与示例

题目描述

对于一个连续正整数组成的序列，可以将其拼接成一个字符串，再将字符串里的部分字符打乱顺序。如序列8 9 10 11 12，拼接成的字符串为89101112，打乱一部分字符后得到90811211，原来的正整数10就被拆成了0和1。 现给定一个按如上规则得到的打乱字符的字符串，请将其还原成连续正整数序列，并输出序列中最小的数字。

输入描述

输入一行，为打乱字符的字符串和正整数序列的长度，两者间用空格分隔，字符串长度不超过200，正整数不超过1000，保证输入可以还原成唯一序列。

输出描述

输出一个数字，为序列中最小的数字。

示例一

输入

19801211 5

输出

8

说明

还原出的序列为 8 9 10 11 12，故输出 8

示例二

输入

432111111111 4

输出

111

说明

还原出的序列为 111 112 113 114，故输出 111

解题思路

直接从序列s中进行判断，较难完成。

考虑到数据量不大，可以通过穷举的方式来完成。

对于1到1000的数字num，考虑长度为n的序列

num num+1 num+2 ... num+n-2 num+n-1

将该序列中的每一个数字转化为字符串，再统计每一个数字字符出现的个数，用哈希表cnt_new来记录。

原序列s中的数字字符，用另外一个哈希表cnt来记录。即

for num in range(1, 1001):
    cnt_new = Counter()
    for i in range(num, num+n):
        for ch in str(i):
            cnt_new[ch] += 1

或者更加简洁的写法

for num in range(1, 1001):
    cnt_new = Counter("".join(str(i) for i in range(num, num+n)))

若发现存在cnt_new == cnt，说明此时num是所寻找的序列的第一个数字。

这是一种相对而言比较暴力的解法，但也足以通过所有用例。

如果想要进一步优化，可以使用固定滑窗的做法。

固定长度为序列长度n的窗口，对正整数序列1 2 3 ... 1000进行滑动，构建一个win_cnt表示窗口中各个数字出现的次数。

左边的数字离开，则在win_cnt中减去对应的频次；右边的数字加入，则在win_cnt中加入对应的频次。

感兴趣的同学可以自行完成上述代码。

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 题目：【哈希表】2024E/2025B/双机位A-恢复数字序列
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：哈希表
# 代码看不懂的地方，请直接在群上提问


from collections import Counter

# 属于打乱的字符串s和数字序列长度n
s, n = input().split()
# 将n转换为数字
n = int(n)

# 将序列s中的每一个字符进行统计
cnt = Counter(s)

# 序列最大不会超过1000，故遍历1-1000的所有元素
for num in range(1, 1001):
    # 考虑长度为n的序列
    # 起始位置为num，终止位置为num+n-1
    # 将每一个int转为str后再进行字符串合并
    # 合并完再使用Counter进行元素频率统计
    cnt_new = Counter("".join(str(i) for i in range(num, num+n)))
    # 如果cnt_new等于cnt，直接输出num，并且退出循环
    if cnt_new == cnt:
        print(num)
        break

Java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        int n = scanner.nextInt();
        scanner.close();

        Map<Character, Integer> cnt = new HashMap<>();
        for (char c : s.toCharArray()) {
            cnt.put(c, cnt.getOrDefault(c, 0) + 1);
        }

        for (int num = 1; num <= 1000; num++) {
            Map<Character, Integer> cntNew = new HashMap<>();
            for (int i = num; i < num + n; i++) {
                String iStr = Integer.toString(i);
                for (char c : iStr.toCharArray()) {
                    cntNew.put(c, cntNew.getOrDefault(c, 0) + 1);
                }
            }
            if (cntNew.equals(cnt)) {
                System.out.println(num);
                break;
            }
        }
    }
}

C++

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::string s;
    int n;
    std::cin >> s >> n;

    std::unordered_map<char, int> cnt;
    for (char c : s) {
        cnt[c]++;
    }

    for (int num = 1; num <= 1000; num++) {
        std::unordered_map<char, int> cntNew;
        for (int i = num; i < num+n; i++){
            std::string iStr = std::to_string(i);
            for (char c : iStr) {
                cntNew[c]++;
            }
        }
        if (cntNew == cnt) {
            std::cout << num << std::endl;
            break;
            }
    }

    return 0;
}

C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 辅助函数：统计某个字符串中每个数字字符的出现次数
void countDigits(const char* s, int freq[10]) {
    for (int i = 0; s[i]; i++) {
        freq[s[i] - '0']++;
    }
}

// 辅助函数：比较两个频率数组是否完全相等
int isSameFreq(int a[10], int b[10]) {
    for (int i = 0; i < 10; i++) {
        if (a[i] != b[i]) return 0;
    }
    return 1;
}

int main() {
    char s[10000];
    int n;
    scanf("%s %d", s, &n);

    int targetFreq[10] = {0};
    countDigits(s, targetFreq); // 统计目标字符串中每个数字字符的频率

    for (int num = 1; num <= 1000; num++) {
        int currentFreq[10] = {0};
        for (int i = num; i < num + n; i++) {
            char buf[20];
            sprintf(buf, "%d", i);
            countDigits(buf, currentFreq);
        }

        if (isSameFreq(targetFreq, currentFreq)) {
            printf("%d\n", num);
            break;
        }
    }

    return 0;
}

Node JavaScript

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

rl.on('line', (line) => {
  // 读取一行输入：例如 "19801211 5"
  const [s, nStr] = line.trim().split(' ');
  const n = parseInt(nStr);

  // 构建目标字符串 s 的字符频率统计
  const targetFreq = {};
  for (const c of s) {
    targetFreq[c] = (targetFreq[c] || 0) + 1;
  }

  // 在1到1000之间寻找符合要求的起始数字
  for (let start = 1; start <= 1000; start++) {
    const freq = {};

    for (let i = start; i < start + n; i++) {
      const str = i.toString();
      for (const c of str) {
        freq[c] = (freq[c] || 0) + 1;
      }
    }

    if (isSameFreq(freq, targetFreq)) {
      console.log(start);
      break;
    }
  }

  rl.close();
});

// 判断两个字符频率字典是否相同
function isSameFreq(a, b) {
  const keysA = Object.keys(a);
  const keysB = Object.keys(b);
  if (keysA.length !== keysB.length) return false;

  for (const key of keysA) {
    if (a[key] !== b[key]) return false;
  }
  return true;
}

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "strconv"
        "strings"
)

// 辅助函数：将字符串中每个字符的频率统计为 map
func getFreqMap(s string) map[rune]int {
        freq := make(map[rune]int)
        for _, c := range s {
                freq[c]++
        }
        return freq
}

// 辅助函数：判断两个 map 是否完全相同
func isSameFreq(a, b map[rune]int) bool {
        if len(a) != len(b) {
                return false
        }
        for k, v := range a {
                if b[k] != v {
                        return false
                }
        }
        return true
}

func main() {
        scanner := bufio.NewScanner(os.Stdin)
        if scanner.Scan() {
                // 读取一整行，例如 "19801211 5"
                parts := strings.Fields(scanner.Text())
                if len(parts) != 2 {
                        fmt.Println("Invalid input")
                        return
                }

                s := parts[0]
                n, err := strconv.Atoi(parts[1])
                if err != nil {
                        fmt.Println("Invalid number")
                        return
                }

                // 计算目标频率 map
                targetFreq := getFreqMap(s)

                // 枚举从 num = 1 到 1000 的所有起点
                for num := 1; num <= 1000; num++ {
                        currentFreq := make(map[rune]int)
                        for i := num; i < num+n; i++ {
                                for _, c := range strconv.Itoa(i) {
                                        currentFreq[c]++
                                }
                        }

                        if isSameFreq(currentFreq, targetFreq) {
                                fmt.Println(num)
                                break
                        }
                }
        }
}

时空复杂度

时间复杂度：O(``KM``)。其中M为字符串长度最大值为200，K为序列的最大值为1000。

空间复杂度：O(``1``)。哈希表的长度最多为10，可以认为是常数时间复杂度。

华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务1000+同学成功上岸！

  • 课程讲师为全网200w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 90+天陪伴式学习，100+直播课时，300+动画图解视频，500+LeetCode经典题，500+华为OD真题/大厂真题，还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1441或了解更多

# 散列表 # java # javascript # c++ # c语言 # python
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

WRB1205S-1WR2 与钡特电源 VB1-12S05S 参数规格解析｜ 1W 宽压输入隔离 DC-DC 工业电源模块性能拆解

avatar 亚马逊云科技技术品牌专区
cover

人工智能如何改变学习方式

avatar 亚马逊云科技技术品牌专区
cover

AI技术正在改变

avatar 亚马逊云科技技术品牌专区