多少人去字节跳动面试挂在了这道题上...

Android高级架构 · · 315 次点击 · · 开始浏览    

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

image

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

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

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

下面是字节跳动的内推入口,找出自己心意的职位后,请勇于投递你的个人简历,内部系统的数据安全性做得非常到位,我是看不到你们的简历内容的,所以不必太担心个人隐私问题。北京、上海、深圳、杭州、成都、广州等城市的职位都有,Python、Java、Golang、算法、数据、分布式计算和存储的岗位也都有,个人发挥自己的搜商,进去自行寻找吧。

黄金招聘季,点击获取字节跳动内推机会!​job.toutiao.com
图标

结尾

最后我想说:不论以后选择什么方向发展,目前重要的是把Android方面的技术学好,毕竟其实对于程序员来说,要学习的知识内容、技术有太多太多,要想不被环境淘汰就只有不断提升自己,从来都是我们去适应环境,而不是环境来适应我们! 当程序员容易,当一个优秀的程序员是需要不断学习的,从初级程序员到高级程序员,从初级架构师到资深架构师,或者走向管理,从技术经理到技术总监,每个阶段都需要掌握不同的能力。早早确定自己的职业方向,才能在工作和能力提升中甩开同龄人

原文作者:老钱

原文链接:https://zhuanlan.zhihu.com/p/79938638


欢迎关注我们的微信公众号,每天学习Go知识

本文来自:简书

感谢作者:Android高级架构

查看原文:多少人去字节跳动面试挂在了这道题上...

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:muxilin131420 备注:入群;或加QQ群:815126783

315 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传