美团点评前端在线笔试题总结

由于太久没有复习算法知识，导致基本没写出来，但是都是以前学过的知识，编程题主要有两道：

1.求矩阵最小路径

给定一个矩阵m
从左上角开始
每次只能往下或者往右走
最后到达右下角的位置
路径上所有数字之和就是路径和
求最小路径和
用c++写的：

#include <iostream>
using namespace std;

int main() {
    int m;
    scanf("%d",&m);//输入矩阵大小
    int i,j,input[m][m],output[m][m];
    for (i = 0 ; i<m; i++) {//输入矩阵值
        for (j = 0; j<m; j++) {
            cin>>input[i][j];
            output[i][j] = input[i][j];
        }
    }
    for (i=1; i<m; i++) {
        output[0][i] += output[0][i-1];//处理第一行
        output[i][0] += output[i-1][0];//处理第一列
        for (j=1; j<m; j++) {
            output[i][j] += output[i][j-1]<output[i-1][j]?output[i][j-1]:output[i-1][j];//比较上方元素和左方元素值大小，取小
        }
    }
    cout<<output[m-1][m-1]<<endl;//输出答案
    return 0;
}

2.求最少优惠券使用数量

自行输入用例：
商品价格，若干种面值的优惠券（第一个数是种类数量）
65
4 30 20 10 5
输出使用优惠券最少的最优方案
（需要先排序）从大到小，这里省略

function dikou(total, youhui) {
    function _dikou(t, q, tmp) {
        // console.log(tmp, q, q.length - 1)
        if (t < q[q.length - 1] || tmp.length >= 5) return tmp

        if (t - q[0] >= 0) {
            tmp.push(q[0])
            return _dikou(t - q[0], q, tmp)
        } else {
            return _dikou(t, q.slice(1), tmp)
        }
    }

    let result = []
    return _dikou(total, youhui, result)
}

console.log(dikou(65, [30, 20, 10, 5]))