序言
- 如今前面规定变变高,找工作时可能遇上算法题,每日刷几个算法题做好充足的准备,今天《剑指 Offer（专项突击版）》第13|14题。
挥剑 Offer II 013. 二维子矩阵总和
给出一个二维矩阵 matrix，下列类别的好几个要求：
- 测算他的儿子方形范围之内元素总数，该子矩阵的左上方为 (row1, col1) ，右下方为 (row2, col2) 。
完成 NumMatrix 类：
- NumMatrix(int[][] matrix) 给出整数金额引流矩阵 matrix 开展复位
- int sumRegion(int row1, int col1, int row2, int col2) 回到左上方 (row1, col1) 、右下方 (row2, col2) 的子矩阵元素总数。
难度系数：中等水平
实例 1：
键入: ["NumMatrix","sumRegion","sumRegion","sumRegion"] [[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]] 导出: [null, 8, 11, 12] 表述: NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]]); numMatrix.sumRegion(2, 1, 4, 3); // return 8 (鲜红色矩形元素总数) numMatrix.sumRegion(1, 1, 2, 2); // return 11 (翠绿色矩形元素总数) numMatrix.sumRegion(1, 2, 2, 4); // return 12 (深蓝色矩形元素总数)
提醒：
● m == matrix.length
● n == matrix[i].length
● 1 <= m, n <= 200
● -105 <= matrix[i][j] <= 105
● 0 <= row1 <= row2 < m
● 0 <= col1 <= col2 < n
● 较多启用 104 次 sumRegion 方式
知识要点： 设计方案 二维数组 引流矩阵 作为前缀和
方法一：作为前缀和
假如不考虑到算法复杂度，则采用了蛮干法用两个嵌入能量循环一直能够算出一个二维矩阵的数字之和。假如引流矩阵的行数与行数分别为m和n，那么这样的蛮干方法的算法复杂度是O（mn）。仅仅这道题提及，对于一个二维矩阵，可能因为键入不同类型的座标而不断求不一样子矩阵的数字之和，这表明应当提升求合的一个过程，要尽量快地完成子矩阵的数字求和。
具体分析，发觉左上方座标为（r1，c1）、右下方座标为（r2，c2）的子矩阵的数字之和可以使用4个左上方座标为（0，0）的子矩阵的数字之和求取。
最先创建一个和输入矩阵尺寸同样辅助引流矩阵sums，该引流矩阵里的座标（i，j）的值为输入矩阵中从左上方座标（0，0）到右下方座标（i，j）的子矩阵的数字之和。有了这样的协助引流矩阵sums，再求左上方座标为（r1，c1）、右下方座标为（r2，c2）的子矩阵的数字之和就会变得很容易。
图中引流矩阵的数字之和相当于sums[r2][c2]-sums[r1-1][c2]-sums[r2][c1-1] sums[r1-1][c1-1]。
/**
* @param {number[][]} matrix
*/
var NumMatrix = function(matrix) {
const m = matrix.length;
if (m > 0) {
const n = matrix[0].length;
this.sums = new Array(m 1).fill(0).map(()=> new Array(n 1).fill(0));
for (let i = 0; i < m; i ) { for (let j = 0; j < n; j ) {
this.sums[i 1][j 1] = this.sums[i][j 1] this.sums[i 1][j] - this.sums[i][j] matrix[i][j];
}
}
}
};
/**
* @param {number} row1
* @param {number} col1
* @param {number} row2
* @param {number} col2
* @return {number}
*/
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
return this.sums[row2 1][col2 1] - this.sums[row1][col2 1] - this.sums[row2 1][col1] this.sums[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)
*/
复杂度分析
- 算法复杂度：复位 O(mn)，每一次查找 O(1)，在其中 m 和 n 分别为引流矩阵 matrix 的行数与行数。 复位必须赋值引流矩阵 matrix 测算二维作为前缀和，算法复杂度是 O(mn)。 每一次查找的算法复杂度是 O(1)。
- 空间复杂度：O(mn)，在其中 m 和 n 分别为引流矩阵 matrix 的行数与行数。必须创建一个 m 1 行 n 1列二维作为前缀和二维数组 sums。
挥剑 Offer II 014. 字符串数组里的变位词
给出2个字符串数组 s1 和 s2，写一个函数公式来判定 s2 是否含有 s1 ****某个变位词。
也就是说，第一个字符串数组的排序之一是第二个字符串数组的 签串的 。
难度系数：中等水平
实例 1：
键入: s1 = "ab" s2 = "eidbaooo" 导出: True 表述: s2 包括 s1 的排序之一 ("ba").
实例 2：
键入: s1= "ab" s2 = "eidboaoo" 导出: False
提醒：
● 1 <= s1.length, s2.length <= 104
● s1 和 s2 仅包括小写
知识要点： 哈希表 双指针 字符串数组 滑动窗口
方法一：双指针
剖析：变位词指构成每个词汇的英文字母及每一个英文字母发生次数完全一致，仅仅字母排列顺序不一样。由变位词的定义得知，变位词具备以下几种特性。最先，一组变位词汇的长短一定同样；次之，构成变位词汇的英文字母结合一定同样，而且每一个英文字母发生次数也相同。
这道题假如不考虑到算法复杂度，用暴力行为法就能解决。事实上，一个字符串数组的变位名词是字符串数组的排序。可以直接算出字符串数组s1中的所有排序，随后分辨每一个排序是否字符串数组s2的子字符串。如果一个字符串数组有n字符，那它一共有n！（n的阶乘）个排序，所以这种打法的算法复杂度不容易小于O（n！）。
下边探寻更有效的优化算法。
最先扫描仪字符串数组s1。保存在哈希表中。
随后考虑如何判断字符串s2中是否含有字符串数组s1的变位词。
假定字符串数组s2中有一个子字符串是字符串数组s1的变位词，逐一扫描仪这一变位词里的英文字母，然后把英文字母在哈希表中相匹配数值减1。因为字符串数组s1的变位词和字符串数组s1包括同样的英文字母，而且每一个英文字母发生次数也相同，因而扫描仪完字符串数组s1的变位词以后，哈希表中每一个值全是0。字符串数组s1的变位词和字符串数组s1长度一样。假定字符串数组s1长度是n，下边逐一判断字符串s2中长度n的子字符串是否字符串数组s1的变位词。分辨的方法就是扫描仪子字符串中的每一个英文字母，把要英文字母在哈希表中相匹配数值减1。假如哈希表中所有值是0，那么这个子字符串便是字符串数组s1的一个变位词。
/**
* @param {string} s1
* @param {string} s2
* @return {boolean}
*/
var checkInclusion = function(s1, s2) {
const n = s1.length;
const m = s2.length;
if(n > m) {
return false; }
const cnt = new Array(26).fill(0);
for(let i = 0; i < n; i ) {
cnt[s1[i].charCodeAt() - 'a'.charCodeAt()]--;
}
let left = 0;
for (let right = 0; right < m; right ) {
const x = s2[right].charCodeAt() - 'a'.charCodeAt();
cnt[x] ;
while (cnt[x] > 0) {
cnt[s2[left].charCodeAt() - 'a'.charCodeAt()]--;
left ;
}
if (right - left 1 === n) {
return true;
}
}
return false;
};
复杂度分析
- 算法复杂度：O(n m ∣Σ∣)。 建立 cnt 必须 O(∣Σ∣) 的时间也。 赋值 s1必须 O(n) 的时间也。 双指针赋值 s2时，因为 left 和 right 都会往右边挪动，故这一部分必须 O(m) 的时间也。
- 空间复杂度：O(∣Σ∣)。
so
- 末尾依然：长风破浪会有时，直挂云帆济沧海！
- 线上搜集的确实很好，对AdminJS的帖子进行了一个归纳梳理，在线刷题手册，拿走不谢，要懂得站在他人的肩上提高自己点击这里--> 前面升阶手册
