打开脑洞，一道字节跳动面试真题的优雅解法！

以你之姓@ 2023-10-11 11:15 33阅读 0赞

公众号后台回复“**学习**”，获取作者独家秘制精品资料

![640?wx\_fmt=png][640_wx_fmt_png]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

扫描下方海报二维码，试听课程：

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

![640?wx\_fmt=png][640_wx_fmt_png]

原题：给你一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶

请想个优雅的办法，使得其中一个水壶恰好装 4 升水，每一步的操作只能是倒空或倒满。

![640?wx\_fmt=png][640_wx_fmt_png 1]

理解了这个题目的意思之后，我们的第一个方法肯定就是使用强大的脑力来进行暴力破解法

瓶子里的水在我们的脑子里颠三倒四，但是脑子有可能没那么清晰，想了几步之后就开始出现记忆错乱，然后就开始慢慢重播。甚至到最后好不容易搞定了，但是怎么走过来的步骤又给忘记的一干二净。

这道题其实有一道非常科学的解决方法 —— 广度遍历，我们将三个瓶子的状态标示为一个数。

**8 0 0**

然后开始拓展这个数的所有可能的状态，第一步这个数可以变为，括号里的数是上一步的数字

**3 5 0（8 0 0） 、 5 0 3（8 0 0）**

然后继续拓展第二步所有可能的状态，**并且不得和之前的状态出现重复（这叫剪枝）**

**0 5 3（3 5 0）、3 2 3（3 5 0）、5 3 0（5 0 3）**

继续第三步

**6 2 0（3 2 3）、2 3 3（5 3 0）**

我们发现状态变少了，这是怎么回事呢？这是因为剪枝约束 —— 不得出现和之前重复的状态，就好比下象棋，如果我不动我还能活，但是必须动就会被将死的感觉一样。

继续第四步

**6 0 2（6 2 0）、2 5 1（2 3 3）**

继续第五步，怎么还没出现 4 这个数字呢，好着急啊！

**1 5 2（6 0 2）、7 0 1（2 5 1）**

继续第六步

**1 4 3（1 5 2）**

总算搞定了，这就是算法的**停止条件**，出现第一个数字 4。所以最终的路径就是

**1 4 3** <-- **1 5 2** <-- **6 0 2** <-- **6 2 0** <-- **3 2 3** <-- **3 5 0** <-- **8 0 0**

一脸懵逼的读者们，如果这是一道字节跳动的 LeetCode 题，你们能使用代码来解决上面这个问题么？

**END**

**如有收获，请划至底部，点击“在看”，谢****谢****！**

![640?wx\_fmt=png][640_wx_fmt_png]

欢迎长按下图关注公众号**石杉的架构笔记**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

**BAT架构经验倾囊相授**

[640_wx_fmt_png]: https://img-blog.csdnimg.cn/img_convert/4a615593d528e23acfe693977ced0fd4.png
[640_wx_fmt_jpeg]: https://img-blog.csdnimg.cn/img_convert/0af129915634b031fc5b4a9fab67719b.png
[640_wx_fmt_jpeg 1]: https://img-blog.csdnimg.cn/img_convert/1ae22d9de2a48486145a62b082fdb3a9.png
[640_wx_fmt_png 1]: https://img-blog.csdnimg.cn/img_convert/1ea70c33977f9a2f98f5b46232534351.png
[640_wx_fmt_jpeg 2]: https://img-blog.csdnimg.cn/img_convert/cbb2e2e6a877e8b2b9c2b77889110c74.png

发表评论取消回复

表情：

评论列表（有 0 条评论，33人围观）

还没有评论，来说两句吧...

相关阅读

相关记一道字节跳动的算法面试题

击蓝色“五分钟学算法”关注我哟加个“星标”，天天中午 12:15，一起学算法 ![640?wx\_fmt=jpeg][640_wx_fmt_jpeg] 作者 | ...

雨点打透心脏的1/2处/ 2024年04月17日 19:53/ 0 赞/ 70 阅读

相关打开脑洞，一道字节跳动面试真题的优雅解法！

公众号后台回复“学习”，获取作者独家秘制精品资料 ![640?wx\_fmt=png][640_wx_fmt_png] ![640?wx\_fmt=jpeg][640_wx

以你之姓@/ 2023年10月11日 11:15/ 0 赞/ 34 阅读

相关记一道字节跳动的算法面试题

前几天有个朋友去面试字节跳动，面试官问了他一道链表相关的算法题，不过他一时之间没做出来，就来问了我一下，感觉这道题还不错，拿来讲一讲。题目这其实是一道变形的链表反转

太过爱你忘了你带给我的痛/ 2023年08月17日 17:28/ 0 赞/ 145 阅读

相关字节跳动面试

一面：线程和进程的区别 sort（）用到的排序算法求一个数组中的第K大个元素, 并说明算法复杂度？ \[3,2,4,7,10,23\] k=3 ret=7 数

野性酷女/ 2023年08月17日 15:48/ 0 赞/ 146 阅读

相关字节跳动面试

一面：线程和进程的区别 1. 进程是资源分配的基本单位，也是调度运行的基本单位。 2. 线程是进程中的每一个执行单元，当一个java程序启动时，就会产生一个进程，该进

客官°小女子只卖身不卖艺/ 2023年06月02日 09:20/ 0 赞/ 49 阅读

相关一道简简单单的字节跳动算法面试题

点击上方“图解面试算法”，选择“星标”公众号重磅干货，第一时间送达![format_png][] 今天分享的题目来源于 LeetCode 上的剑指 Offer 系列面试

亦凉/ 2023年02月17日 11:28/ 0 赞/ 225 阅读

相关字节跳动面试题

字节跳动三面面经字节跳动一面面试题：自我介绍聊聊项目，时间大概15种左右，面试官会根据项目的一些设计点来提问，提前做好准备，别自己坑了自己分布式锁是锁住

爱被打了一巴掌/ 2023年01月02日 13:22/ 0 赞/ 202 阅读

相关大厂面试题整理-字节跳动

字节跳动一面一道算法题聊项目，你们的广告检索引擎是如何设计的？为什么你们的广告检索不使用 ElasticSearch 这样的搜索组件？

喜欢ヅ旅行/ 2022年11月14日 10:18/ 0 赞/ 274 阅读

相关 tableau一道烧脑的表计算面试题

文章目录前言 tableau 描述怎么做？（1）用表计算法（2）方法，用min\[细分\]

男娘i/ 2022年10月07日 13:00/ 0 赞/ 229 阅读

相关 spring-boot @ConfigurationProperties脑洞真大

搞了一阵子C++，以前感觉C++很牛，现在怎么觉得这东西这么落后了，很多理念完全跟不上时代，关键兼容性让人抓狂了。。。只能说一切为了效率。。。

绝地灬酷狼/ 2022年06月17日 14:00/ 0 赞/ 190 阅读