怎么做网站免费的,芜湖移动互联网开发,网站建设 互成网络,免费咨询律师不收费的平台二维前缀和
根据某个块块 的 左上角坐标#xff0c;和右下角坐标 求出 块块的累加和。 304. 二维区域和检索 - 矩阵不可变
/*** param {number[][]} matrix*/
var NumMatrix function(matrix) {let row matrix.length;let col matrix[0].length;// 初始化一个二维数组和右下角坐标 求出 块块的累加和。 304. 二维区域和检索 - 矩阵不可变
/*** param {number[][]} matrix*/
var NumMatrix function(matrix) {let row matrix.length;let col matrix[0].length;// 初始化一个二维数组用来存储每个位置的累加和。let sum new Array(row1).fill(0);for(let i 0; i sum.length; i){sum[i] new Array(col1).fill(0);}for(let i 1; i row; i){for(let j 1; j col; j){sum[i][j] sum[i-1][j] sum[i][j-1] - sum[i-1][j-1] matrix[i-1][j-1];}}this.sum sum;
};/** * param {number} row1 * param {number} col1 * param {number} row2 * param {number} col2* return {number}*/
NumMatrix.prototype.sumRegion function(row1, col1, row2, col2) {return this.sum[row21][col21] - this.sum[row1][col21] - this.sum[row21][col1] this.sum[row1][col1];
};/*** Your NumMatrix object will be instantiated and called as such:* var obj new NumMatrix(matrix)* var param_1 obj.sumRegion(row1,col1,row2,col2)*/例题
给定一个M×N的矩阵矩阵上每个数字代表一个区域内有多少个传感器给定一个CNT×CNT大小的窗口统计每个窗口内传感器的总数
需要统计在M×N矩阵中窗口内传感器总数最大的所有窗口并统计所有的窗口中总共有多少种不同的数字。
遍历一次二维数组记录二维数组的前缀和。记录为preSum遍历preSum从 i :cnt → len,j:cnt → len ,计算每个小窗口的区间和。记录为cntSum最后遍历cntSum数组找到最大的窗口并且用set记录窗口的数字总量。
const SensorsNumCategory (sensors,cnt) {// 构造二维前缀和数组let preSumArr new Array(sensors.length1);let len sensors[0].length;for(let i 0; i sensors.length1; i){preSumArr[i] new Array(len1).fill(0);}for(let i 1; i preSumArr.length; i){for(let j 1;j preSumArr[i].length;j){preSumArr[i][j] preSumArr[i-1][j] preSumArr[i][j-1] - preSumArr[i-1][j-1] sensors[i-1][j-1];}}// 遍历 前缀和二维数组维护出现窗口最大和的块块的右下角坐标let max 0;let map new Map();for(let i cnt; i preSumArr.length; i){for(let j cnt; j preSumArr[i].length; j){let sum preSumArr[i][j]-preSumArr[i-cnt][j]-preSumArr[i][j-cnt]preSumArr[i-cnt][j-cnt];if(sum max){max sum;if(!map.has(max)){map.set(max,[])}map.get(max).push([i,j])}}}let arr map.get(max);let res [];for(let i 0; i arr.length; i){[x,y] arr[i];res.push(...getElem([x-cnt,y-cnt],cnt,sensors));}// 对数组元素进行去重return Array.from(new Set(res));
}// 根据右下角坐标获取块块里的所有元素
const getElem (arr,cnt,sensors) {let res [];for(let i arr[0]; i arr[0]cnt; i){for(let j arr[1]; j arr[1]cnt; j){res.push(sensors[i][j])}}return res;
}
console.log(SensorsNumCategory([[1,3,4], [3,2,5],[1,6,1]],2))
