paint-brush
Leetcode:二和的直观方法 经过@carolisabino
797 讀數
797 讀數

Leetcode:二和的直观方法

经过 Caroline Sabino
Caroline Sabino HackerNoon profile picture

Caroline Sabino

@carolisabino

Software engineer.

4 分钟 read2024/04/23
Read on Terminal Reader
Read this story in a terminal
Print this story

太長; 讀書

建立解决问题的直觉,以便您可以将其应用到自己的案例场景中。
featured image - Leetcode:二和的直观方法
Caroline Sabino HackerNoon profile picture
Caroline Sabino

Caroline Sabino

@carolisabino

Software engineer.

0-item
1-item

STORY’S CREDIBILITY

Code License

Code License

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

Guide

Guide

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.


想象一下,您是 Spot-On Change 酒店内一家纪念品商店的骄傲老板。当您关闭收银机时,您发现多出了 8 欧元。似乎一位客人没有收到正确的零钱。这可能会损害酒店的声誉。为了避免这种情况,您决定解决错误零钱的谜团。打开商店的现金系统后,您发现错误发生在两个不同的账户上!


你制定了一个计划:走访每个房间,询问客人在商店里收到了多少零钱,直到找到两个拿错钱的人。到达一楼后,一位客人说收到了 4 欧元的零钱。你计算出需要找到一个数字,将其与 4 欧元相加,结果是 8。移至二楼,客人的零钱是 5 欧元。4 + 5 结果是 9,所以不可能是这个……五楼、六楼……十楼,不,不,不!


由于第一次尝试没有找到值,你下到二楼,再次开始询问所有客人的零钱,以便将其与下一层起始楼层的值进行比较,这很累人,不是吗?在计算机科学中,这种搜索方法称为蛮力搜索,这是一种非常慢的搜索方法,通过将一个项目与数组中的后续项目进行比较来工作。


图片来自 interviewing.io

图片来自 interviewing.io




这浪费了大量的时间,而且效率不高,想象一下在 Spot-On Change Hotel 的所有楼层上下好几次!这对您来说不切实际,对计算机来说也不切实际。


如果你好奇在软件程序中这种上下移动是如何实现的,那么在 JavaScript 中它看起来应该是这样的:


 twoSum(nums, target) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] === target) { return [i, j]; } } } }


冷静评估情况后,您意识到有更有效的方法来找到两位拿错零钱的客人。


你完善了最初的数学直觉,即 9 欧元等于 x + y。通过一些算术运算,你意识到:x + y = 9 与 y = 9 — x 相同,这对提高搜索效率大有裨益。


你的策略中另一个改变是,现在你会拿一个记事本记下客人告诉你的数值,这样你就不用为客人问两次同样的数值,也不用花一整天的时间上下楼梯了。(电梯坏了那该有多可怕啊!)。


有了新工具后,您前往一楼,一位客人告诉您,他们有 5 欧元的零钱。您将其记录为 {5: 0},表示位置 0 的值为 5。在等式中用 5 代替 x,计算出 y = 8–5,结果为 y = 3。由于您的记事本仍为空,因此您没有记录数字 3,而 3 是 5 的补数,可得出结果 8。然后,您将数字 5 写在记事本上(请记住,始终写下当前验证的数字,而不是其补数;您只会使用补数将其与您写下的目标数字进行比较)。您继续与第二位客人交谈,他提到收到 2 欧元的零钱。再次应用公式:y = 8–2 => y = 6,您检查记录,没有找到任何数字 6。因此,您将 2 添加到记录中,现在记录为 {5: 0, 2: 1}。继续搜索,下一位客人报告收到 3 欧元的零钱。您再次计算:y = 8–3 => y = 5。Bingo!您的记事本上记录了 5!来自 0 楼的客人与来自 2 楼的客人互补!这种方法称为哈希表,对您和计算机来说,它都更快、更高效。在 JavaScript 中,这将按如下方式实现:


 twoSum(nums, target) { const myTable = {}; for (let i = 0; i < nums.length; i++) { const complementaryNumber = target - nums[i]; if (complementaryNumber in myTable) { return [i, myTable[complementaryNumber]]; } myTable[nums[i]] = i; } }


这是一道Leetcode上的简单问题,只有在理解了背后的概念后才会变得简单。我建议您尝试自己解决这个问题,花一些时间尝试建立背后的直觉,创建自己的类比,复习,并尝试编写伪代码,然后再继续解决问题。


我希望我的类比能帮助您更好地理解二和挑战背后的概念。


下次再见!