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 = 0
  for (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]));