《Dubbo 实现原理与源码解析 —— 精品合集》 《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》 《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》 《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》 《Java 面试题 + Java 学习指南》

摘要: 原创出处 码洞 「码洞」欢迎转载,保留摘要,谢谢!


🙂🙂🙂关注**微信公众号:【芋道源码】**有福利:

  1. RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表
  2. RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址
  3. 您对于源码的疑问每条留言将得到认真回复。甚至不知道如何读源码也可以请教噢
  4. 新的源码解析文章实时收到通知。每周更新一篇左右
  5. 认真的源码交流微信群。

原题:给你一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶,请想个优雅的办法,使得其中一个水壶恰好装 4 升水,每一步的操作只能是倒空或倒满。

理解了这个题目的意思之后,我们的第一个方法肯定就是使用强大的脑力来进行暴力破解法,瓶子里的水在我们的脑子里颠三倒四,但是脑子有可能没那么清晰,想了几步之后就开始出现记忆错乱,然后就开始慢慢重播。甚至到最后好不容易搞定了,但是怎么走过来的步骤又给忘记的一干二净。

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

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 题,你们能使用代码来解决上面这个问题么?

文章目录