剑指 Offer（专项突击版）第13|14题

前言

• 现在前端要求变高了,找工作的时可能会碰上算法题,每天刷几道算法题做足准备,今天是《剑指 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]]])

提示：
● 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 方法

---

知识点： 设计[1] 数组[2] 矩阵[3] 前缀和[4]

方法一：前缀和

如果不考虑时间复杂度，则采用蛮力法用两个嵌套的循环总是可以求出一个二维矩阵的数字之和。如果矩阵的行数和列数分别是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. 字符串中的变位词

给定两个字符串 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 仅包含小写字母

知识点： 哈希表[5] 双指针[6] 字符串[7] 滑动窗口[8]

方法一：双指针

分析：变位词指组成各个单词的字母及每个字母出现的次数完全相同，只是字母排列的顺序不同。由变位词的定义可知，变位词具有以下几个特点。首先，一组变位词的长度一定相同；其次，组成变位词的字母集合一定相同，并且每个字母出现的次数也相同。

这个题目如果不考虑时间复杂度，用暴力法就可以解决。实际上，一个字符串的变位词是字符串的排列。可以先求出字符串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

• 结尾依旧：长风破浪会有时，直挂云帆济沧海！

• 在线整理的确实很好，对文章进行了一个汇总整理，在线备战面试、刷题指南，拿走不谢，要学会站在别人的肩膀上提升自己点击这里-->

最后:

如果你现在正在找工作，可以私信“web”或者直接添加小助理进群领取前端面试小册、简历优化修改、大厂内推以及更多阿里、字节大厂面试真题合集，和p8大佬一起交流。