《力扣算法训练提升》图解数组篇-打卡数组统计-【661】图片平滑器
囧么肥事今日打卡题目
力扣【661.图片平滑器】
包含整数的二维矩阵 M 表示一个图片的灰度。
你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ，
平均灰度的计算是周围的8个单元和它本身的值求平均，如果周围的单元格不足八个，则尽可能多的利用它们。
具体描述
解题讨论
注意：这里解释一下，本篇内容所有的方阵（指的是矩形阵列，不一定是长宽相同的正方形"方阵"），顺手写的方阵，大致就是矩形阵列的意思，后面懒得改了，勉勉强强看吧！
讨论归纳一：轮番询问周围所有兵士
第一步：遍历数组，
每个战士轮番询问自己周围所有兵士军功
判断左方是否有人，记录军功
判断左上是否有人，记录军功
判断上方是否有人，记录军功
判断右上是否有人，记录军功
判断右方是否有人，记录军功
判断右下是否有人，记录军功
判断下方是否有人，记录军功
判断左下是否有人，记录军功
第二步：计算平均军功
动画模拟
示例一：轮番询问周围所有兵士
注：代码可左右滑动
// a[i][j] // 判断左方是否存在 // 判断左上是否存在 // 判断上方是否存在 // 判断右上是否存在 // 判断右方是否存在 // 判断右下是否存在 // 判断下方是否存在 // 判断左下是否存在public int[][] imageSmoother(int[][] img) { // 二维数组行数 int rowNums = img.length; // 二维数组列数 int colNums = img[0].length; int[][] res = new int[rowNums][colNums]; for (int i = 0; i < rowNums; i++) { for (int j = 0; j < colNums; j++) { int count = 1; int sum = img[i][j]; // a[i][j] // 判断左方是否存在 if (j - 1 >= 0) { count++; sum += img[i][j - 1]; } // 判断左上是否存在 if (i - 1 >= 0 && j - 1 >= 0) { count++; sum += img[i - 1][j - 1]; } // 判断上方是否存在 if (i - 1 >= 0) { count++; sum += img[i - 1][j]; } // 判断右上是否存在 if (i - 1 >= 0 && j + 1 < colNums) { count++; sum += img[i - 1][j + 1]; } // 判断右方是否存在 if (j + 1 < colNums) { count++; sum += img[i][j + 1]; } // 判断右下是否存在 if (i + 1 < rowNums && j + 1 < colNums) { count++; sum += img[i + 1][j + 1]; } // 判断下方是否存在 if (i + 1 < rowNums) { count++; sum += img[i + 1][j]; } // 判断左下是否存在 if (i + 1 < rowNums && j - 1 >= 0) { count++; sum += img[i + 1][j - 1]; } res[i][j] = (sum / count); } } return res; }
复杂度分析
时间复杂度：O(N)，其中 N 是图片中像素的数目。需要遍历每个像素。
空间复杂度：O(N)，如果忽略返回，空间复杂度 O(1)。
讨论归纳二：军队方阵报数
第一步：选取中心兵，开辟小型方阵
第二步：小型方阵战士依次报数
第三步：计算平均军功
动画模拟
示例二：军队方阵报数
注：代码可左右滑动
public int[][] imageSmoother(int[][] img) {
// 二维数组行数
int rowNums = img.length;
// 二维数组列数
int colNums = img[0].length;
// 结果
int[][] res = new int[rowNums][colNums];
for (int i = 0; i < rowNums; i++) {
for (int j = 0; j < colNums; j++) {
// 当前战士 a[i][j]
// 划分小型阵列，找到阵列边界
// 判断前后左右是否有队列
// 前方队列
int si = i - 1;
// 后方队列
int ei = i + 1;
// 左边队列
int sj = j - 1;
// 右边队列
int ej = j + 1;
int count = 0;
int sum = 0;
// 报数
for (int rowI = si; rowI <= ei; rowI++) {
for (int colI = sj; colI <= ej; colI++) {
// 判断小型阵列是否在大阵列内
// 只有在阵列内，才是有效阵列
if (rowI >= 0 && rowI < rowNums && colI >= 0 && colI < colNums) {
sum += img[rowI][colI];
count++;
}
}
}
res[i][j] = (sum / count);
}
}
return res;
}
复杂度分析
时间复杂度：O(N)，其中 N 是图片中像素的数目。需要遍历每个像素。
空间复杂度：O(N)，如果忽略返回，空间复杂度 O(1)。
短话长说
学算法先学什么？什么阶段该刷什么题？
关注我，日常打卡算法图解。
按照力扣题目类别结构化排序刷题，从低阶到高阶，图解算法(更新中…)，有兴趣的童鞋，欢迎一起从小白开始零基础刷力扣，共同进步！
回复：678，获取已分类好的部分刷题顺序，后续内容会持续更新，感兴趣的小伙伴自由拿取！
另外，有关分类，求小伙伴们不要再问我最后一类的起名了，奇技淫巧是个褒义词，意思是指新奇的技艺和作品。
力扣修炼体系题目，题目分类及推荐刷题顺序及题解
目前暂定划分为四个阶段：
算法低阶入门篇--武者锻体
算法中级进阶篇--武皇炼心
算法高阶强化篇--武帝粹魂
算法奇技淫巧篇--战斗秘典
以上分类原谅我有个修仙梦...
缺漏内容，正在努力整理中…
投递百度等公司10个岗位 >