算法之美团点评2020校招前端方向笔试题
1
考察知识点：堆内存和栈内存，以及函数传参是以值传参。
答案：
1、变量i，s，a都在栈中。new出来的对象A在堆中。
- 栈内存主要用于存储各种基本类型的变量，包括Boolean、Number、String、Undefined、Null以及对象变量的指针，堆主要存储object
- 所以字符串变量i,s以及对象指针a都存在栈中，new出来的对象开辟内存存在堆上，对应地址是指针a存的内容
2、a.i是op
- 因为创建了对象a，所以可以访问类A的i变量，但是函数传参是以值传递的，所以不改变值
- a是A类的实例，所以a.i='op'，a.func(a.i)这句执行函数，把a.i作为参数传递，该函数会复制一个变量，两个变量完全独立，所以在函数体里只是把复制的那个变量（一个新的局部变量）改变为'op9’,在函数体外的a.i并没有被改变
- 另外补充说明ECMAScript中所有函数的参数都是按值传递的——《高程3》，其实对于参数是对象的情况，实际上也是按值传递，把传参的指针复制出一个完全独立的变量，只是存的内容和传参对象地址一摸一样
2、按顺序写出打印结果
var name = 'global';
var obj = {
name: 'local',
foo: function(){
this.name = 'foo';
}.bind(window)
};
var bar = new obj.foo();
setTimeout(function() {
console.log(window.name);
}, 0);
console.log(bar.name);
var bar3 = bar2 = bar;
bar2.name = 'foo2';
console.log(bar3.name);
考察事件执行顺序event loop、this指针、引用类型的复制
打印结果为：
foo
foo2
global
原理：
1、按顺序执行，当遇见settimeout这个异步执行操作，将其放在任务队列中 ，等待执行栈执行完毕再运行。所以settimeout是最后运行的。
2、第一个foo是：/bind返回一个函数，该函数体中的this绑定到window上，然后new对该函数进行构造调用，返回一个新对象，函数体中的this指向该对象。bind是硬绑定，new绑定的优先级高于硬绑定。所以this还是绑定在bar这个新对象上。this.name='foo'就是bar.name='foo'
3、第二个foo2：因为bar3=bar2=bar指向的是同一个对象，所以复杂类型的复制是引用复制，bar2改变的时候，bar3也会改变。
3、请写出如下代码运行后产生的结果，并给出解释，说明结果是如何得出的。
setTimeout(() => console.log('a'));
Promise.resolve().then(
() => console.log('b’);
).then(
() => Promise.resolve('c').then(
(data) => {
setTimeout(() => console.log('d'));
console.log('f');
return data;
}
)
).then(data => console.log(data));考察：event-loop、宏任务、微任务
打印结果:
bfcad
原理：
1、setTimeout1为异步任务，放入任务队列中
2、遇到promise，由于是微任务，后面也没有别的宏任务的同步任务，则执行，输出b
3、在then函数中再次遇到promise，将resolve的内容给then作为参数使用。
4、在此promise中遇到settimeout，将其放入任务队列，在settimeout1的后面。
5、输出f
6、运行下一个then， data为c，输出c
7、现在开始运行异步任务，输出ad
4、请写出下面ES6代码编译后所生成的ES5代码；
class Person {
constructor (name) {
this.name = name;
}
greet () {
console.log(`Hi, my name is ${this.name}`);
}
greetDelay (time) {
setTimeout(() => {
console.log(`Hi, my name is ${this.name}`);
}, time);
}
}考察知识点：ES6语法糖理解，ES6编译到ES5过程理解，JS原型理解，this指向理解；
答案：
var Person = (function () {
function Person (name) {
//使用局部变量
this._name = name;
}
Person.prototype.greet = function () {
console.log(“Hi, my name is “ + this._name);
}
Person.prototype.greetDelay = function (time) {
var _this = this;
setTimeout(function () {
console.log(“Hi, my name is “ + _this.name);
}, time);
}
})();5、斐波那契--没啥可说的
形如1, 1, 2, 3, 5, 8, 13, 21, 34, 55的数列，后一位是前面两位相加（斐波那契数列），写出函数要求找到第 N 位是多少，如：fib(3) => 3 ， fib(5) => 8, 要求时间复杂度为O(n)。
答案：
var n=readline();
function feibonaqie(n){
if(n==0) return 1;
if(n==1) return 1;
var a=1;
var b=1;
var c=0;
for(let i=2;i<=n;i++){
c=a+b;
a=b;
b=c;
}
return c;
}
console.log(feibonaqie(n));6、代金券组合---动态规划
近期某商场由于周年庆，开启了“0元购”活动。活动中，消费者可以通过组合手中的代金券，实现0元购买指定商品。
聪明的小团想要用算法来帮助他快速计算：对于指定价格的商品，使用代金券凑出其价格即可，但所使用的代金券总面额不可超过商品价格。由于代金券数量有限，使用较少的代金券张数则可以实现价值最大化，即最佳优惠。
假设现有100元的商品，而代金券有50元、30元、20元、5元四种，则最佳优惠是两张50元面额的代金券；而如果现有65元的商品，则最佳优惠是两张30元代金券以及一张5元代金券。
请你帮助小团使用一段代码来实现代金券计算
输出是代金券的最少张数，如果不可能满足则输出impossible。
参考：代金券组合问题
答案：
通过维护一个一维数组，其中是每个每个金额所需的最少金额数
while(true){
var num = parseInt(readline())
if(num==0){
break
}
var lines =readline()
var lineArr = lines.split(" ").map(Number)
var type = lineArr[0]
var money = lineArr.slice(1)
console.log(getResult(num,type,money))
}
function getResult(num, type, money) {
var dp = []
dp[0]=0
for (var i = 1; i <=num; i++) {
var arr=[]
for(var j=0;j<money.length;j++){
if(i>=money[j]){
arr.push(dp[i-money[j]]+1)
}
}
dp[i]=Math.min(...arr)
}
return dp[num]==Infinity?"Impossible":dp[num]
}7、最短路径
链接：最短路径
给定一个包含非负整数的 M x N 迷宫，请找出一条从左上角到右下角的路径，使得路径上的数字总和最小。每次只能向下或者向右移动一步。
解题思路：
dp[i][j]代表从(0,0)走到(i,j)的最小路径和则
dp[0][i]来自第一行的累加
dp[i][0]来自第一列的累加
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grip[i]j
var firstRow=readline().split(' ');
var m=firstRow[0];
var n=firstRow[1];
var arr=[];
while(line=readline()){
var a=line.split(' ').map(Number);
arr.push(a);
}
function result(m,n,arr){
var sum=0;
var dp=[];
for(let i=0;i<m;i++){
dp[i]=[];
for(let j=0;j<n;j++){
if(i==0&&j==0){
dp[i][j]=arr[0][0];
}else if(i==0&&j!=0){
d[i][j]=d[i][j-1]+arr[i][j];
}else if(i!=0 &&j==0){
d[i][j]=d[i-1][j]+arr[i][j];
}else{
d[i][j]=Math.min(d[i-1][j],d[i][j-1])+arr[i][j];
}
}
}
return a[m-1][n-1];
}
console.log(result(m,n,arr));8、星际穿越
小团在一次星际旅行中，耗尽了飞船的能量，迷失在了空间魔方中，空间魔方中有NNN个能量粒子。美团云AI迅速帮小团分析出了空间魔方的能量分布图。
已知小团的飞船被困在能量值最高的点，能量值最高点有且只有一个。飞船每到达一个能量粒子就会吸收对应粒子的能量，该粒子会坍缩成小黑洞，飞船不可到达。小团驾驶的飞船只能从高能粒子驶向低能粒子，且每次只能从6个方向中选择一个前进。（±x,±y,±z）。
请帮助帮小团吸收最高的能量值。
#include<iostream>
(720)#include<vector>
#include<algorithm>
(831)#include<math.h>
using namespace std;
int n;int max_eng=0;
int se[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};
void dfs(vector<vector<vector<int>>> &vec,int i,int j,int z,int e)
{
e=e+vec[i][j][z];
for(int k=0;k<6;k++)
{
int a=i+se[k][0],b=j+se[k][1],c=z+se[k][2];
if(a<0||b<0||c<0||a==n||b==n||c==n||vec[a][b][c]==-1||vec[i][j][z]<=vec[a][b][c]) continue;
int temp=vec[i][j][z];vec[i][j][z]=-1;//设置访问记号，并且保留当前值
dfs(vec,a,b,c,e);
vec[i][j][z]=temp;
}
max_eng=max(max_eng,e); //跳出循环说明6个方向都没法了，即到达终点
//仅需在某条路的终点与最大值比较即可
}
int main()
{
cin>>n;if(n==0) {cout<<0;return 0;}//注意判断n为0的情况
vector<vector<vector<int>>> vec(n,vector<vector<int>>(n,vector<int>(n,0)));
int i,j,z,e;int num=pow(n,3);int m_i,m_j,m_z,m_e=0;
while(num--)
{
cin>>i>>j>>z>>e;vec[i][j][z]=e;
if(e>m_e) {m_i=i,m_j=j,m_z=z,m_e=e;}
}
dfs(vec,m_i,m_j,m_z,0);
cout<<max_eng;
system("pause");
return 0;
}
