20天拿下华为OD笔试之【哈希表】2025C-免单统计【Py/Java/C++/C/JS/Go六种语言OD独家2025C卷真题】【欧弟算法】全网注释最详细分类最全的华子OD真题题解

闭着眼睛学算法

1554人浏览 · 2025-09-05 06:45:00

闭着眼睛学算法 · 2025-09-05 06:45:00 发布

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

题目描述与示例

题目描述

华为商城举办了一个促销活动，如果某顾客是某一秒内最早时刻下单的顾客（可能是多个人），则可以获取免单。

请你编程计算有多少顾客可以获取免单。

输入描述

输入为 n 行数据，每一行表示一位顾客的下单时间

以（年-月-日时-分-秒.毫秒） yyyy-MM-dd HH:mm:ss.fff 形式给出。

0<n<50000
2000<yyyy<2020
0<MM<=12
0<dd<=28
0<=HH<=23
0<=mm<=59
0<=ss<=59
0<=fff<=999

所有输入保证合法。

输出描述

输出一个整数，表示有多少顾客可以获取免单。

示例一

输入

3
2019-01-01 00:00:00.001
2019-01-01 00:00:00.002
2019-01-01 00:00:00.003

输出

说明

样例 1 中，三个订单都是同一秒内下单，只有第一个订单最早下单，可以免单。

示例二

输入

3
2019-01-01 08:59:00.123
2019-01-01 08:59:00.123
2018-12-28 10:08:00.999

输出

说明

样例 2 中，前两个订单是同一秒内同一时刻（也是最早）下单，都可免单，第三个订单是当前秒内唯一一个订单（也是最早），也可免单。

示例三

输入

5
2019-01-01 00:00:00.004
2019-01-01 00:00:00.004
2019-01-01 00:00:01.006
2019-01-01 00:00:01.006
2019-01-01 00:00:01.005

输出

说明

样例 3 中，前两个订单是同一秒内同一时刻（也是最早）下单，第三第四个订单不是当前秒内最早下单，不可免单，第五个订单可以免单。

解题思路

本题难度不高，属于比较常规的使用哈希表进行模拟的题目。

首先我们需要把所有发生在同一秒的抢单信息放在一起。

由于区分是否是同一秒的信息，只需要获得毫秒之前的数据，我们对输入的每一行字符串数据进行处理的时候，可以只以"."作为分割符进行切割。即

pre, fff = input().split(".")

其中pre包含了年、月、日、时、分、秒的所有信息，fff是毫秒信息。

我们以pre作为key，同一个pre所对应的fff所构成的列表作为value，构建哈希表。即

dic = defaultdict(list)

for _ in range(n):
    pre, fff = input().split(".")
    dic[pre].append(fff)

这样发生在同一秒内的抢单信息我们都放在同一个pre对应的列表中了。

对于每一秒发生的抢单，我们需要寻找其最小值，以及最小值出现的次数。可以通过构建函数get()来完成，即

def get(lst):
    count = 0
    min_fff = min(lst)
    for fff in lst:
        if fff == min_fff:
            count += 1
    return count

最后遍历哈希表dic中的每一个value列表，传入get()函数并且更新ans即可。

for lst in dic.values():
    ans += get(lst)

代码

Python

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

# 题目：【哈希表】2024E/2025C-免单统计
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：哈希表
# 代码看不懂的地方，请直接在群上提问


from collections import defaultdict


# 对于在同一秒内发生的毫秒所构成的列表
# 计算其最小值出现的次数
def get(lst):
    # 初始化次数为0
    count = 0
    # 寻找lst中的最小值min_fff
    min_fff = min(lst)
    # 遍历lst中的毫秒值
    for fff in lst:
        # 如果fff等于min_fff，则计数+1
        if fff == min_fff:
            count += 1
    # 将计数返回出函数外
    return count


# 输入免单信息数量n
n = int(input())

# 初始化哈希表
dic = defaultdict(list)

# 遍历n次，输入免单信息
for _ in range(n):
    # 根据"."进行分割，pre是年、月、日、时、分、秒的信息，fff是毫秒信息
    pre, fff = input().split(".")
    # 将同一个pre的毫秒储存在同一个哈希表中
    dic[pre].append(fff)

ans = 0

# 遍历dic的values中的每一个列表lst
# 将lst传入get，更新ans
for lst in dic.values():
    ans += get(lst)

print(ans)

Java

import java.util.*;

public class Main {
    // 函数get：计算在同一秒内发生的毫秒最小值出现的次数
    private static int get(List<Integer> lst) {
        // 初始化计数
        int count = 0;
        // 寻找列表中的最小值
        int minValue = Collections.min(lst);
        // 遍历列表中的每个值
        for (int value : lst) {
            // 如果当前值等于最小值，则计数增加
            if (value == minValue) {
                count++;
            }
        }
        // 返回计数结果
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 输入免单信息数量
        int n = scanner.nextInt();
        scanner.nextLine(); // 消费换行符
        
        // 初始化哈希表，key为日期时间字符串，value为该秒内的毫秒列表
        Map<String, List<Integer>> dic = new HashMap<>();
        
        for (int i = 0; i < n; i++) {
            // 输入免单信息，以“.”为分隔符
            String[] parts = scanner.nextLine().split("\\.");
            String pre = parts[0];
            int fff = Integer.parseInt(parts[1]);
            
            // 如果该秒还没有任何数据，先初始化一个新的列表
            dic.putIfAbsent(pre, new ArrayList<>());
            // 将毫秒值加入到对应的列表中
            dic.get(pre).add(fff);
        }
        
        int ans = 0;
        
        // 遍历哈希表的所有值列表
        for (List<Integer> lst : dic.values()) {
            // 计算每个列表中最小毫秒值的出现次数，并累计到ans
            ans += get(lst);
        }
        
        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 函数get：计算在同一秒内发生的毫秒最小值出现的次数
int get(const vector<int>& lst) {
    // 初始化计数
    int count = 0;
    // 找到列表中的最小值
    int minValue = *min_element(lst.begin(), lst.end());
    // 遍历列表中的每个值
    for (int value : lst) {
        // 如果当前值等于最小值，则计数增加
        if (value == minValue) {
            count++;
        }
    }
    // 返回计数结果
    return count;
}

int main() {
    int n;
    cin >> n;
    cin.ignore();  // 消费换行符

    // 初始化哈希表，key为日期时间字符串，value为该秒内的毫秒列表
    unordered_map<string, vector<int>> dic;

    for (int i = 0; i < n; ++i) {
        string line;
        getline(cin, line);
        
        // 使用“.”进行分割
        size_t pos = line.find('.');
        string pre = line.substr(0, pos);
        int fff = stoi(line.substr(pos + 1));

        // 将毫秒值加入到对应的列表中
        dic[pre].push_back(fff);
    }

    int ans = 0;

    // 遍历哈希表的所有值列表
    for (const auto& pair : dic) {
        // 计算每个列表中最小毫秒值的出现次数，并累计到ans
        ans += get(pair.second);
    }

    cout << ans << endl;
    return 0;
}

C

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

/* -------- 安全工具函数 -------- */
static char* xstrdup(const char* s) {
    if (!s) return NULL;
    size_t len = strlen(s);
    char* p = (char*)malloc(len + 1);
    if (!p) { fprintf(stderr, "malloc fail\n"); exit(1); }
    memcpy(p, s, len + 1);
    return p;
}

/* 去掉行尾 '\n' / '\r' */
static void chomp(char* s) {
    if (!s) return;
    size_t L = strlen(s);
    while (L && (s[L-1] == '\n' || s[L-1] == '\r')) s[--L] = '\0';
}

/* -------- 题目逻辑：哈希表（链地址） -------- */
typedef struct Node {
    char *key;       /* 秒字符串 */
    int  *values;    /* 该秒内所有毫秒 */
    int   size;      /* 已用个数 */
    int   cap;       /* 容量 */
    struct Node *next;
} Node;

#define TABLE_SIZE 10007  /* 简单素数桶数 */
static Node* table[TABLE_SIZE];  /* 全局静态区 => 自动置零 */

/* djb2 哈希 */
static unsigned long hash_str(const char* s) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
    return h % TABLE_SIZE;
}

/* 确保节点的 values 容量足够 */
static void ensure_cap(Node* node) {
    if (node->size < node->cap) return;
    int newCap = node->cap ? node->cap * 2 : 4;
    int* np = (int*)realloc(node->values, (size_t)newCap * sizeof(int));
    if (!np) { fprintf(stderr, "realloc fail\n"); exit(1); }
    node->values = np;
    node->cap = newCap;
}

/* 插入一条记录（key: 秒字符串；value: 毫秒） */
static void ht_insert(const char* key, int value) {
    unsigned long idx = hash_str(key);
    Node* cur = table[idx];
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            ensure_cap(cur);
            cur->values[cur->size++] = value;
            return;
        }
        cur = cur->next;
    }
    /* 新建节点 */
    Node* node = (Node*)malloc(sizeof(Node));
    if (!node) { fprintf(stderr, "malloc fail\n"); exit(1); }
    node->key = xstrdup(key);
    node->values = NULL;
    node->size = 0;
    node->cap = 0;
    node->next = table[idx];
    table[idx] = node;

    ensure_cap(node);
    node->values[node->size++] = value;
}

/* 计算同一秒内“最小毫秒值”的出现次数 */
static int count_min_occurs(const int* a, int n) {
    if (n <= 0) return 0;
    int mn = a[0];
    for (int i = 1; i < n; ++i) if (a[i] < mn) mn = a[i];
    int cnt = 0;
    for (int i = 0; i < n; ++i) if (a[i] == mn) ++cnt;
    return cnt;
}

int main(void) {
    /* 输入条数 */
    int n;
    if (scanf("%d", &n) != 1) { puts("0"); return 0; }
    /* 吃掉换行 */
    int ch;
    while ((ch = getchar()) != '\n' && ch != EOF) {}

    char line[512];  /* 行缓冲：足够容纳典型的 "YYYY-MM-DD HH:MM:SS.mmm" */
    for (int i = 0; i < n; ++i) {
        if (!fgets(line, sizeof(line), stdin)) break;
        chomp(line);
        if (!line[0]) { /* 空行则跳过本次，不减少 i，因为题目通常给定 n 行合法输入 */
            continue;
        }

        /* 按 '.' 分割成 秒字符串 与 毫秒 */
        char* dot = strchr(line, '.');
        if (!dot) {
            /* 没有毫秒部分，视为非法行，跳过 */
            continue;
        }
        *dot = '\0';
        const char* secStr = line;
        const char* msStr  = dot + 1;

        /* 将毫秒转换为整数；允许前后有空格 */
        while (*msStr == ' ' || *msStr == '\t') ++msStr;
        int ms = (int)strtol(msStr, NULL, 10);

        /* 插入哈希表 */
        ht_insert(secStr, ms);
    }

    /* 汇总答案 */
    long long ans = 0;
    for (int b = 0; b < TABLE_SIZE; ++b) {
        for (Node* cur = table[b]; cur; cur = cur->next) {
            ans += count_min_occurs(cur->values, cur->size);
        }
    }

    printf("%lld\n", ans);

    /* 释放内存 */
    for (int b = 0; b < TABLE_SIZE; ++b) {
        Node* cur = table[b];
        while (cur) {
            Node* nxt = cur->next;
            free(cur->key);
            free(cur->values);
            free(cur);
            cur = nxt;
        }
        table[b] = NULL;
    }

    return 0;
}

Node JavaScript

const readline = require("readline");

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

let input = [];
rl.on("line", line => {
  input.push(line.trim());
});

rl.on("close", () => {
  // 输入免单信息数量
  let n = parseInt(input[0]);

  // 初始化哈希表，key 为日期时间字符串，value 为该秒内的毫秒列表
  let dic = new Map();

  for (let i = 1; i <= n; i++) {
    let parts = input[i].split(".");
    let pre = parts[0];
    let fff = parseInt(parts[1]);

    if (!dic.has(pre)) {
      dic.set(pre, []);
    }
    dic.get(pre).push(fff);
  }

  let ans = 0;

  // 遍历哈希表的所有值列表
  for (let lst of dic.values()) {
    // 找到该秒内的最小毫秒值
    let minValue = Math.min(...lst);
    // 统计最小值出现次数
    let count = lst.filter(v => v === minValue).length;
    ans += count;
  }

  console.log(ans);
});

Go

package main

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

func main() {
        in := bufio.NewReader(os.Stdin)

        // 输入免单信息数量
        line, _ := in.ReadString('\n')
        n, _ := strconv.Atoi(strings.TrimSpace(line))

        // 初始化哈希表，key 为日期时间字符串，value 为该秒内的毫秒列表
        dic := make(map[string][]int)

        for i := 0; i < n; i++ {
                line, _ = in.ReadString('\n')
                line = strings.TrimSpace(line)
                parts := strings.Split(line, ".")
                pre := parts[0]
                fff, _ := strconv.Atoi(parts[1])

                dic[pre] = append(dic[pre], fff)
        }

        ans := 0

        // 遍历哈希表的所有值列表
        for _, lst := range dic {
                // 找到该秒内的最小毫秒值
                minValue := lst[0]
                for _, v := range lst {
                        if v < minValue {
                                minValue = v
                        }
                }
                // 统计最小值出现次数
                count := 0
                for _, v := range lst {
                        if v == minValue {
                                count++
                        }
                }
                ans += count
        }

        fmt.Println(ans)
}

时空复杂度

时间复杂度：O(N)。每个元素会被考虑3次，构建哈希表dic一次，计算min_fff一次，计算count一次，故O(3N) = O(N)。

空间复杂度：O(N)。哈希表所占空间。

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

华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务1000+同学成功上岸！
课程讲师为全网200w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
90+天陪伴式学习，100+直播课时，300+动画图解视频，500+LeetCode经典题，500+华为OD真题/大厂真题，还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
可查看链接OD真题汇总(持续更新)
绿色聊天软件戳 od1441或了解更多

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

更多推荐

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

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

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

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

AI技术正在改变

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

所有评论(0)

查看更多评论

闭着眼睛学算法

@weixin_48157259

已为社区贡献14条内容

20天拿下华为OD笔试之【哈希表】2025C-免单统计【Py/Java/C++/C/JS/Go六种语言OD独家2025C卷真题】【欧弟算法】全网注释最详细分类最全的华子OD真题题解

闭着眼睛学算法

文章目录

相关推荐阅读

题目描述与示例

题目描述

输入描述

输出描述

示例一

输入

输出

说明

示例二

输入

输出

说明

示例三

输入

输出

说明

解题思路

代码

Python

Java

C++

C

Node JavaScript

Go

时空复杂度

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

所有评论(0)

闭着眼睛学算法

20天拿下华为OD笔试之【哈希表】2025C-免单统计【Py/Java/C++/C/JS/Go六种语言OD独家2025C卷真题】【欧弟算法】全网注释最详细分类最全的华子OD真题题解

闭着眼睛学算法

文章目录

相关推荐阅读

题目描述与示例

题目描述

输入描述

输出描述

示例一

输入

输出

说明

示例二

输入

输出

说明

示例三

输入

输出

说明

解题思路

代码

Python

Java

C++

C

Node JavaScript

Go

时空复杂度

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

所有评论(0)

温馨提示：您尚未绑定手机号

闭着眼睛学算法