今天的题目是 365. Water and Jug Problem 。 我们可以执行的操作有三种: 给一个杯子装满 倒掉一个杯子中的所有水 将一个杯子中的水转移到另一个杯子中直到没水或者另一个杯子装满 三种操作会分别让两个杯子总水量产生三种: 增加 x 或 y 减少 x 或 y…

今天的题目是 274. H-Index 。 这道题要求出最大的一个 h 满足总共有 h 篇文章引用了至少 h 次。给定的输入时每一篇文章引用数。 这种问题,一般来说都是先排个序来做加速的。如果现在 citations 数组是有序的,我们可以从后往前搜索,找到最大的 j 使得倒数第 j 个元素的引用数( citations[j] )大于等于 j 。因此,代码如下:

今天的题目是 116. Populating Next Right Pointers in Each Node 。 不算难的题目,因为题目中给出的树是特定的树,即所谓的完美二叉树,因此我们可以简单的用一个指针去获取左子树最右边的节点,右子树最左边的节点,然后直接对应相连。完成这一步后左子树和右子树之间已经通过 next 指针连接起来了,现在只需要递归地去连接左,右子树各自的 next…

今天的题目是 1227. Airplane Seat Assignment Probability 。 比较简单的题目,我的思路大概是这样的。 先假设 f(n) 为有 n 个人时,第 n 个人坐到自己位置的概率。 首先,第 1 个人随机选位置的时候,可能有三种情况: 选到了自己的位置,那么后面就不会有人发现自己座位被做了,此时第 n 个人一定会坐到自己的位置。 选到了第 n 个人的位置,这时第 n…

今天的题目是 375. Guess Number Higher or Lower II 。 一道动态规划问题,一开始以为是通过二分查找的方式来计算就好了,但是后面发现这样算出来答案不是最优的。 思路大概是这样的,把问题先泛化为,给定从 i 到 j 的数字,猜数字的最大代价,为了得到最大代价,我们不妨假设每次都猜错,直到只有一个元素时。 第一次猜的时候,我们可以猜从 i 到 j 的任意一个数字 k…

本站总访问量次 本站访客数人次

Design by wuxiaobai24. Power by Gatsby.js. The website content is licensed CC BY NC SA 4.0.

You can find the source code in Github.