有人相爱,有人夜里开车看海,有人LeetCode第一题都做不出来

原创 typedef 2024-12-25 08:20

目录

  • 一、引言
  • 二、问题描述
  • 三、解决方案
    • 3.1 暴力枚举
    • 3.2 哈希表
  • 四、网友锐评
  • 五、知识点扩展
    • 5.1 哈希表
    • 5.2 UT_hash_handle
  • 六、uthash
    • 6.1 uthash 简介
    • 6.2 uthash 例程
  • 七、链接
  • 八、最后

一、引言

在日常技术探索的漫漫长路上,不经意的瞬间总能触发一段新奇旅程。就像今天,我随手点开 “LeetCode” 官网,指尖轻触 “题库”,瞬间被拉回了几年前的青涩时光 —— 我的刷题记录竟还定格在那道经典的 “两数之和”,彼时初涉力扣的青涩模样如在眼前。

心里犯起嘀咕,当年这题莫不是靠着答案才勉强通过?一股不服输的劲儿涌上心头,当下决定花两分钟重温旧题。本以为手到擒来,代码在键盘上噼里啪啦敲完,自信满满地提交,没想到换来的却是无情的 “运行错误”。

屏幕上那刺眼的提示,像极了学生时代考试失利的红灯。要是换做屏幕前的你,能一举拿下这道题吗?来吧,让我们一同深入剖析这道 “LeetCode” 必刷之 “两数之和”,看看其中暗藏哪些玄机。

二、问题描述

给定一个整数数组nums 和一个整数目标值target,请你在该数组中找出和为目标值target  的那 个整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1]

三、解决方案

3.1 暴力枚举

初涉此题,多数人脑海里蹦出的第一招便是暴力枚举。

通俗来讲,就是一股脑遍历整个数组,逐个寻觅target - x 的身影。不过这里头有个小窍门,前面已经 “验过” 的元素就没必要再跟当前元素x 配对了,毕竟题目限定每个元素只能用一次,所以目光只需聚焦在x 后面的元素群里找target - x 就行。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

inttwoSum(int* nums, int numsSize, int target, int* returnSize) {
for (int i = 0; i < numsSize; ++i) {
    for (int j = i + 1; j < numsSize; ++j) {
      if (nums[i] + nums[j] == target) {
        int* ret = malloc(sizeof(int) * 2);
        ret[0] = i, ret[1] = j;
        *returnSize = 2;
        return ret;
      }
    }
  }
  *returnSize = 0;
returnNULL;
}

时间复杂度:O(N2),其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。

空间复杂度:O(1)。

说起来,这题对基础薄弱的小伙伴不太友好,就像我,一开始愣是没瞅见注释,把结算结果错塞到returnSize 里,闹了个不大不小的笑话。

3.2 哈希表

仔细琢磨,暴力枚举之所以耗时,症结就在于找target - x 时太 “磨蹭”,时间复杂度居高不下。那有没有 “快刀斩乱麻” 的妙招呢?哈希表应运而生,它就像一把精准导航的钥匙,能闪电般定位目标元素,把找target - x 的时间复杂度从 O (N) 断崖式降至 O (1)。

struct hashTable {
  int key;
int val;
  UT_hash_handle hh;
};

struct hashTablehashtable;

struct hashTable* find(int ikey) {
struct hashTabletmp;
  HASH_FIND_INT(hashtable, &ikey, tmp);
return tmp;
}

void insert(int ikey, int ival) {
struct hashTableit = find(ikey);
if (it == NULL) {
    struct hashTabletmp = malloc(sizeof(struct hashTable));
    tmp->key = ikey, tmp->val = ival;
    HASH_ADD_INT(hashtable, key, tmp);
  } else {
    it->val = ival;
  }
}

inttwoSum(int* nums, int numsSize, int target, int* returnSize) {
  hashtable = NULL;
for (int i = 0; i < numsSize; i++) {
    struct hashTableit = find(target - nums[i]);
    if (it != NULL) {
      int* ret = malloc(sizeof(int) * 2);
      ret[0] = it->val, ret[1] = i;
      *returnSize = 2;
      return ret;
    }
    insert(nums[i], i);
  }
  *returnSize = 0;
returnNULL;
}

在第一层循环里面,先去哈希表中查找是否有 key 为target - nums[i]的值,如果查到了就分配一片空间并将计算结果返回,反之就将键值对nums[i], i插入哈希表中。

为了让大伙理解更透彻,特意奉上一张官方视频讲解中的配图(见下图),图文并茂,一目了然。

哈希表求解过程

顺带提一嘴,后面章节会详细拆解 UT_hash_handle 以及 HASH 函数,这里先卖个小关子。

时间复杂度:O(N),其中 N 是数组中的元素数量。对于每一个元素 x,我们可以 O(1) 地寻找 target - x。

空间复杂度:O(N),其中 N 是数组中的元素数量。主要为哈希表的开销。

值得留意的是,官方解法也并非十全十美,像struct hashTable* hashtable 定义哈希表时忘了初始化指针,这可是个暗藏隐患的 “雷区”。uthash 作者再三强调,此处务必初始化为 NULL。

Declare the hash

大伙日常写代码可得长点心,野指针这玩意儿,一旦冒头,那就是程序崩溃的 “定时炸弹”。

四、网友锐评

这道题一抛出,网友们的吐槽那叫一个热闹非凡,让我们来看一下吧。

有人相爱,有人夜里开车看海,有人leetcode第一题都做不出来。

哈希表是什么、我连两个for都想了很久,你给我说哈希表。

别跟我谈什么空间复杂度,时间复杂度,我解题就是一手暴力枚举,自信提交,运行错误。

是谁力扣第一题都做的磕磕巴巴,原来是我。

看题之前我是心高气傲,看题之后我是生死难料。

单纯c语言角度看,这题用c 比用其他语言要麻烦,因为一上来就涉及到了最麻烦的指针。

五、知识点扩展

哈希表,你太让我陌生了。

我开发到现在也没用到哈希算法。

今天咱就抱着学习的态度来学习一下哈希表。

5.1 哈希表

哈希表是一种高效的数据结构,它通过哈希函数将键(Key)映射到表中的位置,从而实现快速查找、插入和删除操作。

哈希函数将键转换为数组索引,使得每个元素都能直接定位到其存储位置,理想情况下,这种映射关系使得查找、插入和删除操作的时间复杂度接近 O(1)。

5.2 UT_hash_handle

在使用哈希表求解时,结构体中使用了一个UT_hash_handle类型,这个类型是什么?在哪里?

C语言的标准库中没有哈希表的函数可以使用,需要包含第三方头文件uthash.h,第三方库链接放到最后了。

UT_hash_handle类型在uthash.h头文件定义如下,通过其中的成员看出是通过双向链表实现哈希表的。

typedef struct UT_hash_handle {
struct UT_hash_table *tbl;
void *prev;                       /* prev element in app order      */
void *next;                       /* next element in app order      */
struct UT_hash_handle *hh_prev;   /* previous hh in bucket order    */
struct UT_hash_handle *hh_next;   /* next hh in bucket order        */
constvoid *key;                  /* ptr to enclosing struct's key  */
unsigned keylen;                  /* enclosing struct's key len     */
unsigned hashv;                   /* result of hash-fcn(key)        */
} UT_hash_handle;

六、uthash

6.1 uthash 简介

uthash 是一款极为精巧的工具,代码量仅约 1000 行 C 代码。它借助宏的形式巧妙实现,进而天然具备内联特性。它对哈希表项目的操作提供了完备支持,在功能层面,支持如下操作。

  1. add/replace
  2. find
  3. delete
  4. count
  5. iterate
  6. sort

6.2 uthash 例程

#include    /* printf */
#include   /* atoi, malloc */
#include   /* strcpy */
#include "uthash.h"

struct my_struct {
int id;                    /* key */
char name[21];
  UT_hash_handle hh;         /* makes this structure hashable */
};

struct my_struct *users = NULL;/* important! initialize to NULL */

void add_user(int user_id, const char *name) {
struct my_struct *s;

  HASH_FIND_INT(users, &user_id, s);  /* id already in the hash? */
if (s == NULL) {
    s = (struct my_struct*)malloc(sizeof *s);
    s->id = user_id;
    HASH_ADD_INT(users, id, s);  /* id is the key field */
  }
strcpy(s->name, name);
}

struct my_struct *find_user(int user_id) {
struct my_struct *s;

  HASH_FIND_INT(users, &user_id, s);  /* s: output pointer */
return s;
}

void delete_user(struct my_struct *user) {
  HASH_DEL(users, user);  /* user: pointer to deletee */
free(user);
}

void delete_all() {
struct my_struct *current_user;
struct my_struct *tmp;

  HASH_ITER(hh, users, current_user, tmp) {
    HASH_DEL(users, current_user);  /* delete it (users advances to next) */
    free(current_user);             /* free it */
  }
}

void print_users() {
struct my_struct *s;

for (s = users; s != NULL; s = (struct my_struct*)(s->hh.next)) {
    printf("user id %d: name %s\n", s->id, s->name);
  }
}

int by_name(const struct my_struct *a, const struct my_struct *b) {
returnstrcmp(a->name, b->name);
}

int by_id(const struct my_struct *a, const struct my_struct *b) {
return (a->id - b->id);
}

const char *getl(const char *prompt) {
staticchar buf[21];
char *p;
printf("%s? ", prompt); fflush(stdout);
  p = fgets(buf, sizeof(buf), stdin);
if (p == NULL || (p = strchr(buf, '\n')) == NULL) {
    puts("Invalid input!");
    exit(EXIT_FAILURE);
  }
  *p = '\0';
return buf;
}

int main() {
int id = 1;
int running = 1;
struct my_struct *s;
int temp;

while (running) {
    printf(" 1. add user\n");
    printf(" 2. add or rename user by id\n");
    printf(" 3. find user\n");
    printf(" 4. delete user\n");
    printf(" 5. delete all users\n");
    printf(" 6. sort items by name\n");
    printf(" 7. sort items by id\n");
    printf(" 8. print users\n");
    printf(" 9. count users\n");
    printf("10. quit\n");
    switch (atoi(getl("Command"))) {
      case1:
        add_user(id++, getl("Name (20 char max)"));
        break;
      case2:
        temp = atoi(getl("ID"));
        add_user(temp, getl("Name (20 char max)"));
        break;
      case3:
        s = find_user(atoi(getl("ID to find")));
        printf("user: %s\n", s ? s->name : "unknown");
        break;
      case4:
        s = find_user(atoi(getl("ID to delete")));
        if (s) {
          delete_user(s);
        } else {
          printf("id unknown\n");
        }
        break;
      case5:
        delete_all();
        break;
      case6:
        HASH_SORT(users, by_name);
        break;
      case7:
        HASH_SORT(users, by_id);
        break;
      case8:
        print_users();
        break;
      case9:
        temp = HASH_COUNT(users);
        printf("there are %d users\n", temp);
        break;
      case10:
        running = 0;
        break;
    }
  }

  delete_all();  /* free any structures */
return0;
}

七、链接

  • https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/
  • https://github.com/troydhanson/uthash
  • https://troydhanson.github.io/uthash/userguide.html

八、最后

在日常的开发工作里,大家有没有像我这般,基本就靠着if、switch、for 这些基础语句结构一路“闯荡江湖”,很少主动去调用那些精妙复杂的算法呢?

真挺好奇的,评论区留下你的答案。

END

点赞、转发加关注,一键三连,好运年年

关注公众号后台回复数字688或668可获取嵌入式相关资料

往期推荐

为什么推荐大家去考软考高级,因为政府补贴已到账

程序员必看:浮点数精度问题全解析

C语言编程新手:如何判断结构体(struct)相等?

加个变量,程序崩了

typedef 主要用于记录个人学习、总结、分享的一个平台。 教学相长,共同进步。同时并建立技术交流群,欢迎加入。期待您的关注。
评论
  • 百佳泰特为您整理2024年12月各大Logo的最新规格信息。——————————USB▶ 百佳泰获授权进行 USB Active Cable 认证。▶ 所有符合 USB PD 3.2 标准的产品都有资格获得USB-IF 认证——————————Bluetooth®▶ Remote UPF Testing针对所有低功耗音频(LE Audio)和网格(Mesh)规范的远程互操作性测试已开放,蓝牙会员可使用该测试,这是随时测试产品的又一绝佳途径。——————————PCI Express▶ 2025年
    百佳泰测试实验室 2024-12-20 10:33 196浏览
  • //```c #include "..\..\comm\AI8051U.h"  // 包含头文件,定义了硬件寄存器和常量 #include "stdio.h"              // 标准输入输出库 #include "intrins.h"         &n
    丙丁先生 2024-12-20 10:18 134浏览
  • Supernode与艾迈斯欧司朗携手,通过Belago红外LED实现精准扫地机器人避障;得益于Belago出色的红外补光功能,使扫地机器人能够大大提升其识别物体的能力,实现精准避障;Belago点阵照明器采用迷你封装,兼容标准无铅回流工艺,适用于各种3D传感平台,包括移动设备、物联网设备和机器人。全球领先的光学解决方案供应商艾迈斯欧司朗(瑞士证券交易所股票代码:AMS)近日宣布,与国内领先的多行业三维视觉方案提供商超节点创新科技(Supernode)双方联合推出采用艾迈斯欧司朗先进Belago红
    艾迈斯欧司朗 2024-12-20 18:55 202浏览
  •                                                窗        外       年底将近,空气变得格外寒冷,估计这会儿北方已经是千里
    广州铁金刚 2024-12-23 11:49 169浏览
  • ALINX 正式发布 AMD Virtex UltraScale+ 系列 FPGA PCIe 3.0 综合开发平台 AXVU13P!这款搭载 AMD 16nm 工艺 XCVU13P 芯片的高性能开发验证平台,凭借卓越的计算能力和灵活的扩展性,专为应对复杂应用场景和高带宽需求而设计,助力技术开发者加速产品创新与部署。随着 5G、人工智能和高性能计算等领域的迅猛发展,各行业对计算能力、灵活性和高速数据传输的需求持续攀升。FPGA 凭借其高度可编程性和实时并行处理能力,已成为解决行业痛点的关
    ALINX 2024-12-20 17:44 211浏览
  • 光耦合器,也称为光隔离器,是用于电气隔离和信号传输的多功能组件。其应用之一是测量电路中的电压。本文介绍了如何利用光耦合器进行电压测量,阐明了其操作和实际用途。使用光耦合器进行电压测量的工作原理使用光耦合器进行电压测量依赖于其在通过光传输信号的同时隔离输入和输出电路的能力。该过程包括:连接到电压源光耦合器连接在电压源上。输入电压施加到光耦合器的LED,LED发出的光与施加的电压成比例。光电二极管响应LED发出的光由输出侧的光电二极管或光电晶体管检测。随着LED亮度的变化,光电二极管的电阻相应减小,
    腾恩科技-彭工 2024-12-20 16:31 214浏览
  • 汽车行业的变革正愈演愈烈,由交通工具到“第三生活空间”。业内逐渐凝聚共识:汽车的下半场在于智能化。而智能化的核心在于集成先进的传感器,以实现高等级的智能驾驶乃至自动驾驶,以及更个性、舒适、交互体验更优的智能座舱。毕马威中国《聚焦电动化下半场 智能座舱白皮书》数据指出,2026年中国智能座舱市场规模将达到2127亿元,5年复合增长率超过17%。2022年到2026年,智能座舱渗透率将从59%上升至82%。近日,在SENSOR CHINA与琻捷电子联合举办的“汽车传感系列交流会-智能传感专场”上,艾
    艾迈斯欧司朗 2024-12-20 19:45 304浏览
  • 汽车驾驶员监控系统又称DMS,是一种集中在车辆中的技术,用于实时跟踪和评估驾驶员状态及驾驶行为。随着汽车产业智能化转型,整合AI技术的DMS逐渐成为主流,AI模型通过大量数据进行持续训练,使得驾驶监控更加高效和精准。 驾驶员监测系统主要通过传感器、摄像头收集驾驶员的面部图像,定位头部姿势、人脸特征及行为特征,并通过各种异常驾驶行为检测模型运算来识别驾驶员的当前状态。如果出现任何异常驾驶行为(如疲劳,分心,抽烟,接打电话,无安全带等),将发出声音及视觉警报。此外,驾驶员的行为数据会被记录
    启扬ARM嵌入式 2024-12-20 09:14 119浏览
  • 国产数字隔离器已成为现代电子产品中的关键部件,以增强的性能和可靠性取代了传统的光耦合器。这些隔离器广泛应用于医疗设备、汽车电子、工业自动化和其他需要强大信号隔离的领域。准确测试这些设备是确保其质量和性能的基本步骤。如何测试数字隔离器测试数字隔离器需要精度和正确的工具集来评估其在各种条件下的功能和性能。以下设备对于这项任务至关重要:示波器:用于可视化信号波形并测量时序特性,如传播延迟、上升时间和下降时间。允许验证输入输出信号的完整性。频谱分析仪:测量电磁干扰(EMI)和其他频域特性。有助于识别信号
    克里雅半导体科技 2024-12-20 16:35 191浏览
  • 光耦固态继电器(SSR)作为现代电子控制系统中不可或缺的关键组件,正逐步取代传统机械继电器。通过利用光耦合技术,SSR不仅能够提供更高的可靠性,还能适应更加复杂和严苛的应用环境。在本文中,我们将深入探讨光耦固态继电器的工作原理、优势、挑战以及未来发展趋势。光耦固态继电器:如何工作并打破传统继电器的局限?光耦固态继电器通过光电隔离技术,实现输入信号与负载之间的电气隔离。其工作原理包括三个关键步骤:光激活:LED接收输入电流并发出与其成比例的光信号。光传输:光电传感器(如光电二极管或光电晶体管)接收
    腾恩科技-彭工 2024-12-20 16:30 159浏览
  • 随着工业自动化和智能化的发展,电机控制系统正向更高精度、更快响应和更高稳定性的方向发展。高速光耦作为一种电气隔离与信号传输的核心器件,在现代电机控制中扮演着至关重要的角色。本文将详细介绍高速光耦在电机控制中的应用优势及其在实际工控系统中的重要性。高速光耦的基本原理及优势高速光耦是一种光电耦合器件,通过光信号传递电信号,实现输入输出端的电气隔离。这种隔离可以有效保护电路免受高压、电流浪涌等干扰。相比传统的光耦,高速光耦具备更快的响应速度,通常可以达到几百纳秒到几微秒级别的传输延迟。电气隔离:高速光
    晶台光耦 2024-12-20 10:18 223浏览
  • 耳机虽看似一个简单的设备,但不仅只是听音乐功能,它已经成为日常生活和专业领域中不可或缺的一部分。从个人娱乐到专业录音,再到公共和私人通讯,耳机的使用无处不在。使用高质量的耳机不仅可以提供优良的声音体验,还能在长时间使用中保护使用者听力健康。耳机产品的质量,除了验证产品是否符合法规标准,也能透过全面性的测试和认证过程,确保耳机在各方面:从音质到耐用性,再到用户舒适度,都能达到或超越行业标准。这不仅保护了消费者的投资,也提升了该公司在整个行业的产品质量和信誉!客户面临到的各种困难一家耳机制造商想要透
    百佳泰测试实验室 2024-12-20 10:37 274浏览
我要评论
0
点击右上角,分享到朋友圈 我知道啦
请使用浏览器分享功能 我知道啦