零 题目:算法(leetcode,附思维导图 + 全副解法)300 题之(240)搜寻二维矩阵 II
一 题目形容
二 解法总览(思维导图)
三 全副解法
面试官:题目看得差不多了吧,怎么样、有无思路呀?
狂徒张三:波及“映射、数量、重复性(即去重)、唯一性(即次数)等”,我可能会优先思考 hash(JS 里对应的是 map 数据结构)。
面试官:那你先讲讲大抵思路吧
狂徒张三:
1)遍历二维数组里的每个元素,将它们放在哈希表里。2)最初判断 target 值,是否在哈希表里即可~
面试官:嗯嗯,整体思路是 ok 的,那么开始写吧
狂徒张三:过了 2 分 52 秒后,张三就写完了程序
1 计划 1
1)代码:
// 计划 1“本人。哈希法”。// 注:通过 124 / 129,会超时。// 用时:15:14 - 15:16。// 技巧:波及“映射、数量、重复性(即去重)、唯一性(即次数)等”可优先思考 hash(JS 里对应的是 map 数据结构)。// 思路:// 1)状态初始化:m = matrix.length, n = matrix[0].length;
// resMap = new Map();
// 2)遍历二维数组,将每个元素放入 resMap 中。// 3)返回后果:resMap.has(target)。var searchMatrix = function(matrix, target) {// 1)状态初始化:m = matrix.length, n = matrix[0].length;
// resMap = new Map();
const m = matrix.length,
n = matrix[0].length;
let resMap = new Map();
// 2)遍历二维数组,将每个元素放入 resMap 中。for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {const tempVal = matrix[i][j];
resMap.set(tempVal, 1);
}
}
// 3)返回后果:resMap.has(target)。return resMap.has(target);
};
旁边:代码在后盾运行中,过了 3 秒,屏幕忽然【闪现】出【通过 124 / 129,超出工夫限度】。
面试官(面带一丝轻蔑):小伙子,写代码要讲武德、要长于利用题干的条件
狂徒张三(定睛细看题干 60 秒后):嗯嗯,有序,emmmm —> 是否能够应用二分查找呢?
面试官:你认真想想哈
狂徒张三(脑离回忆二分查找的各种思路、模板后):整体思路如下:
1)遍历二维数组的每一行,对每一行(即有序数组)应用二分查找 —— 判断 target 是否在外面。2)若 每一行都不存在 target 值,则 返回 false,否则返回 true。
面试官:
旁白:几分钟不到,张三就写完了“二分查找”法 的代码并通过了所有的 case。
2 计划 2
1)代码:
// 计划 2“本人。二分查找”。// 用时:15:37 - 15:43。// 技巧:在有序的数组里进行元素的查找,可优先思考“二分查找”。// 思路:// 1)状态初始化:m = matrix.length, n = matrix[0].length;
// resFlag = false;。// 2)外围:遍历二维数组的每一行,对每一行(即有序数组)应用二分查找 —— 判断 target 是否在外面。// 2.1)若 target 在以后行 —— isFindTarget(matrix[i], target),// 则 resFlag = true 并退出搜寻。// 3)返回后果:resFlag。var searchMatrix = function(matrix, target) {const isFindTarget = (list = [], target = 0) => {
const l = list.length;
let left = 0,
right = l - 1,
resFlag = false;
while (left <= right) {const mid = left + Math.floor((right - left) / 2),
midVal = list[mid];
if (midVal === target) {
resFlag = true;
break;
}
else if (midVal > target) {right = mid - 1;}
else {left = mid + 1;}
}
return resFlag;
};
// 1)状态初始化:m = matrix.length, n = matrix[0].length;
// resFlag = false;。const m = matrix.length,
n = matrix[0].length;
let resFlag = false;
// 2)外围:遍历二维数组的每一行,对每一行(即有序数组)应用二分查找 —— 判断 target 是否在外面。for (let i = 0; i < m; i++) {// 2.1)若 target 在以后行 —— isFindTarget(matrix[i], target),// 则 resFlag = true 并退出搜寻。if (isFindTarget(matrix[i], target)) {
resFlag = true;
break;
}
}
// 3)返回后果:resFlag。return resFlag;
}
面试官:认真看题干 ——“每行的元素从左到右升序排列。每列的元素从上到下升序排列。”,那么咱们是否从一些非凡的地位开始搜寻呢?
狂徒张三(认真看了看):嗯嗯,看起来左下角、右上角是比拟靠两头的元素,咱们能够从它们开始搜寻。
面试官:
狂徒张三:
比方,1)咱们从左下角开始一直【向上、向右】搜寻。1.1)若 以后值 tempVal === target,则 退出搜寻。1.2)若 以后值 tempVal < target,则 向右搜寻。1.3)若 以后值 tempVal > target,则 向上搜寻。
面试官:
3 计划 3
1)代码:
// 计划 3“本人。Z 字形查找”。// 用时:15:22 - 15:27。// 想法:// 1)题干中,“每行的元素从左到右升序排列。每列的元素从上到下升序排列。”。// 2)那么咱们开始抉择较为两头的地位开始搜寻,若以后值偏小就向右搜寻、偏大就向上搜寻、相等就退出搜寻。// 思路:// 1)状态初始化:m = matrix.length, n = matrix[0].length;
// i = m - 1, j = 0【从左下角开始搜寻】, resFlag = true;
// 2)外围:从左下角开始一直【向上、向右】搜寻。// 2.1)若 以后值 tempVal === target,则 退出搜寻。// 2.2)若 以后值 tempVal < target,则 向右搜寻。// 2.2)若 以后值 tempVal > target,则 向上搜寻。// 3)返回后果 resFlag。var searchMatrix = function(matrix, target) {// 1)状态初始化:m = matrix.length, n = matrix[0].length;
// i = m - 1, j = 0【从左下角开始搜寻】, resFlag = true;
const m = matrix.length,
n = matrix[0].length;
let i = m - 1,
j = 0,
resFlag = true;
// 2)外围:从左下角开始一直【向上、向右】搜寻。while (true) {if (i < 0 || i >= m || j < 0 || j >= n) {
resFlag = false;
break;
}
const tempVal = matrix[i][j];
// 2.1)若 以后值 tempVal === target,则 退出搜寻。if (tempVal === target) {break;}
// 2.2)若 以后值 tempVal < target,则 向右搜寻。else if (tempVal < target) {j++;}
// 2.2)若 以后值 tempVal > target,则 向上搜寻。else {i--;}
}
// 3)返回后果 resFlag。return resFlag;
};
旁白:张三写完了如上代码,急忙问面试官。
狂徒张三:通过面试了吧?
面试官:
狂徒张三:
又 1 个 offer,而后马上就要出任 CEO 了,我早晨应该是去吃 沙县小吃 呢?还是 兰州拉面 呢?哎,抉择太多也是一种懊恼!
四 资源分享 & 更多
1 历史文章 – 总览
2 博主简介
码农三少,一个致力于编写 极简、但齐全题解(算法 )的博主。
专一于 一题多解、结构化思维,欢送一起刷穿 LeetCode ~