2 篇博文 含有标签「面试」

最近几天在学习算法方面的知识,在动态规划这块,想起了去年面试字节时二面的算法题,当时因为水平有限没有在面试中做出来,今天又重新做了一下,有所收获,在此记录.(有关这道题在CSDN上的题解简直狗屁不通,垃圾堆里果然都是垃圾,当然这道题在谷歌上也没有较为官方的题解,请读者带着思考的方式看题解,勿全信,如有不对之处,请在评论区指正)

猴子分香蕉​

题目​

动物园有猴山，每天需要给猴子们发香蕉,猴子会排队依次取食。猴子们铺张浪费,会多拿食物,但最多不会拿超过自身食量的二倍且不会超过当前还存在的香蕉的一半,最后—个猴子除外(即最后—个猴子可以拿完剩余的所有香蕉)。

最少需要准备多少香蕉,能保证所有猴子都能吃饱?

输入输出

[4,3] -> 8
[4,3,5] -> 18
[4,3,5,7] -> 28

分析​

先来理解题目意思,最少需要准备多少香蕉的隐含意思是不管前面的猴子怎么贪吃,多拿了不少香蕉,也要保证到最后一直猴子时,剩余的香蕉数量要满足猴子的食量,否则那最后一直猴子就会挨饿,不满足所有猴子都吃饱这一条件.理解这一点很重要.

从输入输出来倒推分析,以[4,3,5,7] -> 28这组数据为例. 取香蕉的策略是每只猴子都尽可能贪心多拿

1. 首先28的一半为14,并且4*2为8,取小值8,因此第1只猴子取8,剩余20
2. 20的一半为10,并且3*2为6,取小值6,因此第2只猴子取6,剩余14
3. 14的一半为7,并且5*2为10,取小值7,因此第3只猴子取7,剩余7
4. 到最后一直猴子,剩7给7,满足最后一只猴子的食量,猴子全部吃饱

假设准备的香蕉少于28,以27为例

1. 首先27的一半为13.5,并且4*2为8,取小值8,因此第1只猴子取8,剩余19
2. 19的一半为9,5,并且3*2为6,取小值6,因此第2只猴子取6,剩余13
3. 13的一半为6.5,并且5*2为10,取小值6.5,因此第3只猴子取6.5,剩余6.5
4. 到最后一直猴子,剩6.5给6.5, 6.5 < 7, 不满足最后一只猴子的食量,猴子无法全部吃饱

因此28确实是需要准备的最少香蕉数量

开始动态规划解题

1. 首先定义状态,我们可以看到,不管那种情况,最后需要满足的条件都是最后一只猴子也要吃饱,也仅仅只需要吃饱,不需要多吃,因此预期上我们给最后一只猴子准备的香蕉数就是猴子本身的食量.由此可以看出这道题肯定是要倒着递推的.因此我们把dp[i]定义为要喂[i, ..., last]猴子需要的食物
2. 根据题目给出的条件,推递推方程. dp[i]是[i, ..., last]猴子需要的食物, 那么dp[i+1]是[i+1, ..., last]猴子需要的食物 第i只猴子分的香蕉数就是dp[i] - dp[i+1], 猴子数组我们定为monkey,那么可以得到下面不等式

1. dp[i] - dp[i+1] <= 2*monkey[i] // 不会拿超过自身食量的二倍
2. dp[i] - dp[i+1] <= dp[i] / 2 // 不会超过当前还存在的香蕉的一半
3. dp[i] - dp[i+1] >= monkey[i] // 每只猴子吃饱不饿
4. 由2,3还可以推出 monkey[i]<= dp[i] / 2

整理得

dp[i] >= dp[i+1] + monkey[i]
dp[i] >= 2 * monkey[i]
dp[i] <= 2 * dp[i+1]
dp[i] <= dp[i+1] + 2 * monkey[i]

得递推公式

    dp[i] = Math.max(
      Math.min(2 * dp[i + 1], dp[i + 1] + 2 * monkey[i]),
      dp[i + 1] + monkey[i],
            monkey[i] * 2
    );

进一步分析,min当中的第二项其实已经保证了max第二项的肯定成立,因此max第二项其实是多余的,可以删去,最后得到递推公式

    dp[i] = Math.max(
      Math.min(2 * dp[i + 1], dp[i + 1] + 2 * monkey[i]),
            monkey[i] * 2
    );

3. 最终代码

function giveBanana(monkey = []) {
  if (!monkey || !monkey.length) return 0;
  let dp = new Array(monkey.length).fill(0);
  dp[dp.length - 1] = monkey[dp.length - 1];
  for (let i = dp.length - 2; i >= 0; i--) {
    dp[i] = Math.max(
      Math.min(2 * dp[i + 1], dp[i + 1] + 2 * monkey[i]),
            monkey[i] * 2
    );
  }
  return dp[0];
}

console.log(giveBanana([4, 3])); // 8
console.log(giveBanana([4, 3, 5])); // 18
console.log(giveBanana([4, 3, 5, 7])); // 28

总结​

本题的主要的三个注意点

1. 倒着推
2. 状态的定义
3. 获得递推方程较难

希望对网上搜索这道题的小伙伴有所帮助.

题目​

function Foo() {
  getName = function () {
    console.log(1);
  };
  return this;
}
Foo.getName = function () {
  console.log(2);
};
Foo.prototype.getName = function () {
  console.log(3);
};
var getName = function () {
  console.log(4);
};
function getName() {
  console.log(5);
}
Foo.getName(); // 2
Foo().getName(); // 1 
getName(); // 1
new Foo.getName(); // 2
new Foo().getName(); // 3
new new Foo().getName(); // 3

上面是字节的一道面试题，涉及到的考点很多，原型，变量提升，函数提升，this的指向，new的原理，new xx(...) vs new xx vs . 的运算优先级，是一道相当综合的面试题

解析​

1、 Foo.getName();

调用Foo的静态方法，所以，打印2

2、 Foo().getName();

Foo()就是普通函数调用，返回的this是window，后面调用window.getName()
而window下的getName在Foo()中调用getName被重新赋值,所以,打印1

3、 getName();

在执行过Foo().getName()的基础上，所以getName=function(){console.log(1)},所以,打印1，[如果getName()放在Foo().getName()上执行打印结果为4]

4、 new Foo.getName();

构造器私有属性的getName(),所以,打印2

5、 new Foo().getName();

原型上的getName()，打印3

6、 new new Foo().getName()

首先new Foo()得到一个空对象{}， 这个空对象的proto指向了Foo.prototype

第二步 Foo.prototype在上面的代码中已经挂上了打印3的一个函数

第三步 new new Foo().getName() = new {}.getName() = new ({}.proto.getName)() = new (Foo.prototype.getName)() = new (function () {console.log(3);})()

第四步 经过第三步的分析，就可以得出结果，打印3