js算法记录

> 更多请前往 https://www.passerma.com/article/86

滑动窗口

1

给定一个矩阵，包含N*M个整数，和一个包含K个整数的数组。现在要求在这个矩阵中找一个宽度最小的子矩阵，要求子矩阵包含数组中所有的整数

function minSubmatrixWidth(matrix, nums) {const row = matrix.length, col = matrix[0].length;let minWidth = Infinity;for (let i = 0; i < col; i++) {const numsCopy = [...nums];let found = 0;for (let j = i; j < col; j++) {for (let k = 0; k < row; k++) {const num = matrix[k][j];const index = numsCopy.indexOf(num);if (index !== -1) {numsCopy.splice(index, 1);found++;}}if (found === nums.length) {minWidth = Math.min(minWidth, j - i + 1);if (minWidth === 1) {return minWidth}}}}return minWidth
}
// 计算最小宽度的子矩阵
console.log(minSubmatrixWidth([[1, 2, 3],[3, 5, 6]
], [3, 6]));
console.log(minSubmatrixWidth([[1, 2, 3],[3, 5, 6]
], [1, 6]));
console.log(minSubmatrixWidth([[1, 2, 3],[3, 5, 6]
], [4]));
console.log(minSubmatrixWidth([[1, 0, 1, 4],[0, 0, 7, 8],[1, 0, 11, 12],[0, 0, 15, 16]
], [1, 0, 1, 0, 1, 0]));

输出：
在这里插入图片描述

循环

1

为了充分发挥GPU算力，需要尽可能多的将任务交给GPU执行，现在有一个任务数组，数组元素表示在这1秒内新增的任务个数且每秒都有新增任务，假设GPU最多一次执行n个任务，一次执行耗时1秒，在保证GPU不空闲情况下，最少需要多长时间执行完成

function minExecutionTime(maxExec, tasks) {let remaining = 0, time = 0for (let task of tasks) {if (task + remaining > maxExec) {remaining = task + remaining - maxExec;} else {remaining = 0;}time += 1;}while (remaining > 0) {remaining -= maxExec;time += 1;}return time
}
console.log(minExecutionTime(3, [1, 2, 3, 4, 5]));
console.log(minExecutionTime(4, [5, 4, 1, 1, 1]));