荣耀通用笔试8.25

荣耀笔试三题，分值为100 100 300

第一题：大端小端

考点：字符串相关API应用：分割、翻转、拼接
不说了，注意最后输出的是拼接后的字符串即可

第二题：会议室使用最长时间

题目大意：一个会议室早8晚23时间段内可预约会议，该时间段可以接收n个预约，预约格式为start_i, end_i，你作为秘书要保证会议室使用时间最长
输入：第一行为T，表示有T组测试用例，第二行表示有n个预约，其余表示预约start和end

输出：

解题思路：动态规划

function fn(times) {
    // 按照开始时间进行排序
    times.sort((a, b) => a[0]-b[0]);

    let dp = new Array(24).fill(0);

    for (let i = 0; i < times.length;i++) {
        let s = times[i][0], e = times[i][1];
        for (let j = 23; j >= e; j--) {
            dp[j] = Math.max(dp[s]+e-s, dp[j]);
        }
    }
    return Math.max(...dp);
}

// test
let times = [
    [15,17],
    [9,11],
    [10,16],
    [11,12],
    [13,15],
    [9,12],
];

console.log(fn(times)); // 8

这题最需要注意的就是T标明的是测试用例的组数，示例误导地给了1，所以一开始只通过了10%，实际上读取T之后，需要通过while(T--)来继续读取后面的测试用例

第三题：仓库容量

题目大意：有M个货物，重量是不一样的，要放到2个仓库里面，2个仓库的容量一样大，仓库容量至少需要多大
输入：第一行为M，表示M个货物，第二行有M个数，表示每个货物重量，货物重量没有经过排序

3
11 17 8

输出：

解释：11和8放在一个仓库，17放在一个仓库，至少需要容量大小为19
解题思路：题目思路转换一下就是求‘分割数组使两个子数组的和最为接近，且输出最大和的子数组’
我用的二分法，没有A，有空试试01背包吧

function fn(weights) {
    weights = weights.sort((a, b) => a - b);

    // left _ 最大值  right _ 容量和
    let left = Math.max(...weights),
        right = weights.reduce((a, b) => a + b);

    // 仓库容量在[left, right]之间
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (helper(mid)) {    // 大于两个仓库说明目标容量是不够的，需要扩张
            left = mid + 1;
        } else {
            right = mid;    // 小于或者等于两个仓库，收缩right边界，直至最佳
        }
    }

    return left;

    function helper(target) {
        // cur _ 记录所需仓库数量  sum _ 商品累计容量
        let cur = 1,
            sum = 0;

        for (let i = 0; i < weights.length; i++) {
            if (sum + weights[i] > target) {   // 超过目标容量，不能再继续添加了
                sum = weights[i];   // 重新计算容量总和
                cur++;   // 另起一个仓库
            } else {
                sum += weights[i]; 
            }
        }

        return cur > 2;   // 判断是否大于2个仓库
    }
}

// test
let weights = [11, 17, 8];
console.log(fn(weights));  // 19

#荣耀笔试#