本文主要是介绍前端典例算法集合,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
前言
刷算法顺序:1、熟悉本文章第1点的内容;2、刷力扣算法,可以参考这本书的顺序与思想:代码随想录完整版PDF下载 | 合集下载 | 百度云 | | 代码随想录 (programmercarl.com)
3、刷牛客的高频考题
1、熟悉数组Array,字符串String、对象Object、字典Map、集合Set的方法、Math对象、Date对象、正则对象RegExp等基础
1.1、数组Array的方法:
-
添加和删除元素:
push(element1, ..., elementN)
: 在数组末尾添加一个或多个元素,并返回数组的新长度。pop()
: 移除并返回数组的最后一个元素。unshift(element1, ..., elementN)
: 在数组开头添加一个或多个元素,并返回数组的新长度。shift()
: 移除并返回数组的第一个元素。
-
拼接和分割:
concat(array1, array2, ..., arrayN)
: 返回一个由当前数组和其他数组或值拼接而成的新数组。join(separator)
: 将数组的所有元素连接成一个字符串,使用指定的分隔符。
-
切片和连接:
slice(start, end)
: 返回一个从起始索引到结束索引(不包括结束索引)的新数组。splice(start, deleteCount, item1, item2, ...)
: 从指定位置开始删除元素,并可选地插入新元素。
-
查找和过滤:
indexOf(searchElement[, fromIndex])
: 返回指定元素在数组中第一次出现的索引,如果不存在则返回 -1。lastIndexOf(searchElement[, fromIndex])
: 返回指定元素在数组中最后一次出现的索引,如果不存在则返回 -1。find(callback(element, index, array))
: 返回数组中第一个满足条件的元素,否则返回undefined
。filter(callback(element, index, array))
: 返回一个包含所有满足条件的元素的新数组。
-
映射和遍历:
map(callback(element, index, array))
: 返回一个新数组,包含对每个元素进行指定操作后的结果。forEach(callback(element, index, array))
: 对数组中的每个元素执行一次提供的函数。
-
排序和反转:
sort([compareFunction])
: 将数组中的元素排序。如果未提供比较函数,则元素按照字符串 Unicode 码点升序排序。reverse()
: 将数组中的元素颠倒。
-
其他:
indexOf()
,lastIndexOf()
,findIndex()
: 查找元素或满足条件的元素的索引。includes(element[, fromIndex])
: 判断数组是否包含某个元素。every(callback(element, index, array))
: 判断数组中的所有元素是否都满足条件。some(callback(element, index, array))
: 判断数组中是否至少有一个元素满足条件。reduce(callback(accumulator, currentValue, index, array)[, initialValue])
: 对数组中的每个元素执行一个累加器函数,返回累积的结果。
1.2、字符串String方法
-
字符串拼接和分割:
concat(str1, str2, ..., strN)
: 将多个字符串拼接成一个新字符串。+
操作符: 也可以用于字符串拼接。split(separator[, limit])
: 将字符串分割为子字符串数组,根据指定的分隔符进行分割。
-
字符串查找:
indexOf(searchValue[, fromIndex])
: 返回指定值在字符串中首次出现的位置,如果没有找到则返回 -1。lastIndexOf(searchValue[, fromIndex])
: 返回指定值在字符串中最后一次出现的位置,如果没有找到则返回 -1。startsWith(searchString[, position])
: 判断字符串是否以指定的字符开始。endsWith(searchString[, length])
: 判断字符串是否以指定的字符结尾。includes(searchString[, position])
: 判断字符串是否包含指定的字符。
-
字符串截取和提取:
slice(start[, end])
: 提取字符串的一部分,返回一个新字符串。substring(start[, end])
: 类似于slice
,但不允许负数作为参数。substr(start[, length])
: 从指定位置开始,返回指定长度的字符串。
-
字符串转换:
toLowerCase()
: 将字符串转换为小写。toUpperCase()
: 将字符串转换为大写。toString()
: 返回字符串的原始值的字符串表示。
-
字符串替换:
replace(searchValue, replaceValue)
: 替换字符串中的指定值,返回一个新字符串。可以使用正则表达式进行全局替换。replaceAll(searchValue, replaceValue)
: 替换字符串中的所有匹配项。
-
去除空格:
trim()
: 移除字符串两端的空格。
-
其他:
charAt(index)
: 返回指定索引位置的字符。charCodeAt(index)
: 返回指定索引位置的字符的 Unicode 值。length
: 返回字符串的长度。
1.3、对象Object的方法
在 JavaScript 中,对象是键值对的集合,可以包含各种类型的数据。对象类型提供了一些内置的方法,用于执行各种操作。以下是一些常见的对象方法:
-
对象属性操作:
Object.keys(obj)
: 返回一个包含对象自身所有可枚举属性的数组。Object.values(obj)
: 返回一个包含对象自身所有可枚举属性值的数组。Object.entries(obj)
: 返回一个包含对象自身所有可枚举属性的[key, value]
数组的数组。Object.hasOwnProperty(prop)
: 检查对象是否具有指定属性,不包括原型链上的属性。Object.getOwnPropertyNames(obj)
: 返回一个包含对象自身所有属性(不仅仅是可枚举属性)的数组。Object.getOwnPropertyDescriptor(obj, prop)
: 返回指定属性的属性描述符。
-
对象合并和克隆:
Object.assign(target, source1, source2, ...sourceN)
: 将源对象的所有可枚举属性复制到目标对象,返回目标对象。Object.create(proto[, propertiesObject])
: 创建一个新对象,使用现有对象作为新创建对象的原型。Object.freeze(obj)
: 冻结对象,阻止修改现有属性和添加新属性。
-
对象遍历:
Object.keys(obj).forEach(key => ...)
: 遍历对象的所有可枚举属性的键。Object.values(obj).forEach(value => ...)
: 遍历对象的所有可枚举属性的值。Object.entries(obj).forEach(([key, value]) => ...)
: 遍历对象的所有可枚举属性的[key, value]
数组。
-
对象删除属性:
delete obj.property
: 通过属性名删除对象的属性。
-
对象比较:
Object.is(value1, value2)
: 比较两个值是否相同,类似于===
,但处理 NaN 和 +0/-0 的不同。
-
其他:
Object.getPrototypeOf(obj)
: 返回指定对象的原型。Object.setPrototypeOf(obj, proto)
: 设置指定对象的原型。Object.entries(obj).length
: 获取对象中可枚举属性的数量
1.4、字典Map的方法
-
基本操作:
set(key, value)
: 向 Map 中添加或更新键值对。get(key)
: 获取指定键对应的值,如果键不存在则返回undefined
。has(key)
: 判断 Map 中是否包含指定键,返回布尔值。delete(key)
: 删除 Map 中指定键对应的键值对。clear()
: 清空 Map 中的所有键值对。
-
遍历方法:
keys()
: 返回一个包含 Map 中所有键的迭代器。values()
: 返回一个包含 Map 中所有值的迭代器。entries()
: 返回一个包含 Map 中所有键值对的迭代器。forEach(callbackFn [, thisArg])
: 遍历 Map 中的键值对,并对每个键值对执行回调函数。
-
属性:
size
: 返回 Map 中键值对的数量。
-
初始化:
new Map(iterable)
: 创建一个新的 Map 对象,可传入可迭代对象(如数组)来初始化 Map。
1.5、集合Set的方法
-
基本操作:
add(value)
: 向 Set 中添加一个值,如果值已经存在则不会重复添加。delete(value)
: 删除 Set 中指定的值。has(value)
: 判断 Set 中是否包含指定的值,返回布尔值。clear()
: 清空 Set 中的所有值。
-
遍历方法:
values()
: 返回一个包含 Set 中所有值的迭代器。也可以用for...of
遍历。keys()
: 与values()
方法相同,返回一个包含 Set 中所有值的迭代器。entries()
: 返回一个包含 Set 中所有值的[value, value]
数组的迭代器。forEach(callbackFn [, thisArg])
: 遍历 Set 中的每个值,并对每个值执行回调函数。
-
属性:
size
: 返回 Set 中值的数量。
-
初始化:
new Set(iterable)
: 创建一个新的 Set 对象,可传入可迭代对象(如数组)来初始化 Set。
1.6、Math对象的方法
-
基本数学运算:
Math.abs(x)
: 返回 x 的绝对值。Math.ceil(x)
: 返回大于或等于 x 的最小整数。Math.floor(x)
: 返回小于或等于 x 的最大整数。Math.round(x)
: 返回 x 的四舍五入值。Math.max(x, y, ..., n)
: 返回一组数中的最大值。Math.min(x, y, ..., n)
: 返回一组数中的最小值.
-
指数和对数运算:
Math.pow(x, y)
: 返回 x 的 y 次幂。Math.sqrt(x)
: 返回 x 的平方根。Math.exp(x)
: 返回自然数 e 的 x 次幂。Math.log(x)
: 返回 x 的自然对数。
-
三角函数:
Math.sin(x)
: 返回 x 弧度的正弦值。Math.cos(x)
: 返回 x 弧度的余弦值。Math.tan(x)
: 返回 x 弧度的正切值。Math.asin(x)
: 返回 x 的反正弦值。Math.acos(x)
: 返回 x 的反余弦值。Math.atan(x)
: 返回 x 的反正切值。
-
随机数生成:
Math.random()
: 返回一个 0(包括)到 1(不包括)之间的随机数。Math.floor(Math.random() * (max - min + 1)) + min
: 返回一个指定范围内的随机整数。
-
常数:
Math.PI
: 圆周率 π。Math.E
: 自然对数的底数 e。
-
其他:
Math.abs(x)
: 返回 x 的绝对值。Math.sign(x)
: 返回 x 的符号,1 表示正数,-1 表示负数,0 表示零。Math.trunc(x)
: 返回 x 的整数部分。
1.7、Date对象的方法
-
获取日期和时间信息:
new Date()
: 创建一个表示当前时间的Date
对象。Date.now()
: 返回当前时间的时间戳(毫秒)。getDate()
: 返回日期中的天(1-31)。getMonth()
: 返回日期中的月份(0-11)。getFullYear()
: 返回日期中的年份(四位数)。getHours()
: 返回时间中的小时(0-23)。getMinutes()
: 返回时间中的分钟(0-59)。getSeconds()
: 返回时间中的秒(0-59)。getMilliseconds()
: 返回时间中的毫秒(0-999)。getDay()
: 返回日期中的星期几(0-6,0 表示星期日)。
-
设置日期和时间信息:
setDate(day)
: 设置日期中的天。setMonth(month)
: 设置日期中的月份。setFullYear(year)
: 设置日期中的年份。setHours(hours)
: 设置时间中的小时。setMinutes(minutes)
: 设置时间中的分钟。setSeconds(seconds)
: 设置时间中的秒。setMilliseconds(milliseconds)
: 设置时间中的毫秒。setTime(time)
: 设置日期对象的时间值。
-
格式化输出:
toDateString()
: 返回日期部分的字符串。toTimeString()
: 返回时间部分的字符串。toLocaleDateString()
: 返回本地化的日期字符串。toLocaleTimeString()
: 返回本地化的时间字符串。toString()
: 返回日期和时间的字符串表示。
-
比较和计算:
getTime()
: 返回日期对象的时间戳(毫秒)。getTimezoneOffset()
: 返回当前时区与 UTC 时区之间的分钟差。Date.parse(dateString)
: 解析日期字符串,返回对应的时间戳。
1.8、正则对象的方法
-
创建正则对象:
new RegExp(pattern [, flags])
: 创建一个新的正则表达式对象,其中pattern
是正则表达式的模式字符串,flags
是标志字符串(可选),用于设置匹配规则。
-
正则表达式的常用模式:
/pattern/flags
: 直接使用字面量表示法创建正则表达式,其中pattern
是正则表达式的模式,flags
是标志(可选)。-
// 示例 let regex = /\d+/g; // 匹配一个或多个数字,全局匹配// 使用正则对象进行匹配测试 let result = regex.test("12345"); console.log(result); // 输出: true
-
匹配规则和标志:
^
: 匹配字符串的开头。$
: 匹配字符串的结尾。.
: 匹配任意单个字符。*
: 匹配前一个字符零次或多次。+
: 匹配前一个字符一次或多次。?
: 匹配前一个字符零次或一次。[]
: 匹配字符集中的任意一个字符。|
: 或运算,匹配两者之一。\
: 转义字符,用于匹配特殊字符。()
: 分组,用于将多个模式组合在一起。
-
字符类别:
\d
: 匹配数字字符(相当于[0-9]
)。\D
: 匹配非数字字符。\w
: 匹配单词字符(字母、数字、下划线,相当于[a-zA-Z0-9_]
)。\W
: 匹配非单词字符。\s
: 匹配空白字符(空格、制表符、换行符等)。\S
: 匹配非空白字符。
-
量词:
{n}
: 匹配前一个字符恰好 n 次。{n,}
: 匹配前一个字符至少 n 次。{n,m}
: 匹配前一个字符至少 n 次,最多 m 次。
-
贪婪和非贪婪:
*?
: 非贪婪匹配,匹配前一个字符零次或多次,尽量匹配少的字符。+?
: 非贪婪匹配,匹配前一个字符一次或多次,尽量匹配少的字符。??
: 非贪婪匹配,匹配前一个字符零次或一次,尽量匹配少的字符。{n,}?
: 非贪婪匹配,匹配前一个字符至少 n 次,尽量匹配少的字符。{n,m}?
: 非贪婪匹配,匹配前一个字符至少 n 次,最多 m 次,尽量匹配少的字符。
-
匹配结果的方法:
test(str)
: 测试字符串是否匹配正则表达式,返回布尔值。exec(str)
: 在字符串中执行正则表达式匹配,返回匹配结果的数组,如果没有匹配则返回null
。
2、数组算法
2.1、螺旋数组
螺旋矩阵 II
/*** @param {number} n* @return {number[][]}*/
var generateMatrix = function(n) {let startX = startY = 0; // 起始位置let loop = Math.floor(n/2); // 旋转圈数let mid = Math.floor(n/2); // 中间位置let offset = 1; // 控制每一层填充元素个数let count = 1; // 更新填充数字let res = Array(n).fill(Array(n).fill(0));while (loop--) {let row = startX, col = startY;// 上行从左到右(左闭右开)for (; col < n - offset; col++) {res[row][col] = count++;}// 右列从上到下(左闭右开)for (; row < n - offset; row++) {res[row][col] = count++;}// 下行从右到左(左闭右开)for (; col > startY; col--) {res[row][col] = count++;}// 左列做下到上(左闭右开)for (; row > startX; row--) {res[row][col] = count++;}// 更新起始位置startX++;startY++;// 更新offsetoffset += 1;}// 如果n为奇数的话,需要单独给矩阵最中间的位置赋值if (n % 2 === 1) {res[mid][mid] = count;}return res;
};
3、链表
3.1、反转链表
反转链表
function ListNode(x){ return {val :x,next :null}var reverseList =function ( head ) {// write code herevar phead=ListNode(null)var p=head;while(head){p=p.next;head.next=phead.nextphead.next=head;head=p}console.log(phead.next)return phead.next
}
3.2、 链表内指定区间反转
/** function ListNode(x){* this.val = x;* this.next = null;* }*/
/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** */
function reverse(head) {let pre = null;let cur = head;let next;while (cur) {next = cur.next;cur.next = pre;pre = cur;cur = next;}return [pre,head];
}
function reverseBetween(head, m, n) {// 增加一个origin方便返回最终结果 origin.next// 因为head也有可能被翻转了const origin = new ListNode(0)origin.next=headhead = origin;let left, right;let i = 0;for (; i < m - 1; i++) {head = head.next;}left = head;for (; i < n; i++) {head = head.next;}right = head.next;head.next = null;const [start, end] = reverse(left.next);left.next = start;end.next = right;return origin.next;
}
module.exports = {reverseBetween: reverseBetween,
};
4、利用Map进行记录
4.1、求两数的和、前 K 个高频元素
两数之和
/*** @param {number[]} nums* @param {number} target* @return {number[]}*/
var twoSum = function (nums, target) {let hash = {};for (let i = 0; i < nums.length; i++) { // 遍历当前元素,并在map中寻找是否有匹配的keyif (hash[target - nums[i]] !== undefined) {return [i, hash[target - nums[i]]];}hash[nums[i]] = i; // 如果没找到匹配对,就把访问过的元素和下标加入到map中}return [];
};
5、字符串
5.1、字符串匹配
(匹配规则) 输出括号里面的内容??
var str = "2[2[ab7[d]]3[c]]4[e]";
const decode = (str) => {if (!/\d+\[[a-zA-Z]+\]/g.test(str)) return str;// var test = str;// console.log(test.replace(/\d+\[[a-zA-Z]+\]/g, "啊"));str = str.replace(/\d+\[[a-zA-Z]+\]/g, function (item, index) {//item是指7[d] 3[c] 4[e],index时item的起始下标// console.log("测试", index, item);// 匹配符合规制的字符串// var arrtest = item.match(/\d+\[[a-zA-Z]+\]/);// console.log("arrtest", arrtest);// 匹配符合规制的字符串并保留括号里面的内容// var arr = item.match(/(\d+)\[([a-zA-Z]+)\]/);// console.log("arr", arr);var arr = item.match(/(\d+)\[(.+?)\]/).slice(1);var s = arr[1].repeat(arr[0]);return s;});// console.log("str", str);str = decode(str);return str;
};
decode(str);var matchStr = "{a}2{b{{c}d}2}3";
const matchCode = (matchStr) => {if (!/\{[a-zA-Z]+\}\d*/g.test(matchStr)) return matchStr;matchStr = matchStr.replace(/\{[a-zA-Z]+\}\d*/g, function (item, index) {console.log(item, index);var flagarr = item.match(/\{([a-zA-Z]+)\}(\d*)/).slice(1);var s2 = flagarr[1] == "" ? flagarr[0] : flagarr[0].repeat(flagarr[1]);console.log("s2", s2);return s2;// console.log("flagarr", flagarr);});matchStr = matchCode(matchStr);console.log("matchStr", matchStr);return matchStr;
};
matchCode(matchStr);
6、排列与组合
6.1、组合
给定数组 [1, 2, 3, 4, 5] 中的所有可能的三个数组合。
function findCombinations(arr) {let combinations = [];for (let i = 0; i < arr.length - 2; i++) {for (let j = i + 1; j < arr.length - 1; j++) {for (let k = j + 1; k < arr.length; k++) {combinations.push([arr[i], arr[j], arr[k]]);}}}return combinations;
}let inputArray = [1, 2, 3, 4, 5];
let result = findCombinations(inputArray);console.log(result);
6.2、排列
function permute( num ) {// write code herelet res=[]let len=num.lengthlet arrange=(leftarr,rightarr)=>{if(leftarr.length===len){res.push(leftarr)}else{rightarr.forEach((item,index)=>{let temp=[].concat(rightarr)temp.splice(index,1)arrange(leftarr.concat(item),temp)}) }}arrange([],num)return res
}
7、树
7.1、层次遍历
var levelOrder = function(root) {if(!root) return [];const q = [[root, 0]];const res = [];while(q.length){const [n, level] = q.shift();if(!res[level]) {res.push([n.val]);} else{res[level].push(n.val);}if(n.left) q.push([n.left, level + 1]);if(n.right) q.push([n.right, level + 1]);}return res;
};
7.2、二叉树的先序遍历
//递归
function preorderTraversal( root ) {// write code hereconst res = [];preorder(root,res);return res;}
function preorder(root,res){if(!root){return;}res.push(root.val);preorder(root.left,res);preorder(root.right,res);
}
module.exports = {preorderTraversal : preorderTraversal
};//非递归
function preorderTraversal( root ) {let res = [];if(!root) return res;let stk = [root];while(stk.length){let top = stk.pop();res.push(top.val);if(top.right) stk.push(top.right);if(top.left) stk.push(top.left);}return res;}
7.3、中序遍历的递归和非递归解法
function inorderTraversal( root ) {// write code hereconst res = [];inorder(root,res);return res;
}
function inorder(root,res){if(!root) return;inorder(root.left,res);res.push(root.val);inorder(root.right,res);
}
module.exports = {inorderTraversal : inorderTraversal
};
function inorderTraversal( root ) {// write code herelet res = [];if(!root) return res;let p = root;let q = [];while(q.length || p ){while(p){q.push(p);p = p.left;}//console.log(q)let qHead = q.pop();res.push(qHead.val);p = qHead.right;}return res;
}
7.4、后序遍历的递归和非递归解法
function postorderTraversal( root ) {// write code hereconst res = [];postOrder(root,res);return res;
}
function postOrder(root,res){if(!root) return;postOrder(root.left,res);postOrder(root.right,res);res.push(root.val);
}
module.exports = {postorderTraversal : postorderTraversal
};
function postorderTraversal(root) {// write code herelet res = [];if (!root) return res;let stk1 = [root];let stk2 = [];while (stk1.length) {const n = stk1.pop();stk2.push(n.val);//此处与先序顺序相反if (n.left) stk1.push(n.left);if (n.right) stk1.push(n.right);}//console.log(stk2)while (stk2.length) {res.push(stk2.pop());}return res;
}
module.exports = {postorderTraversal: postorderTraversal,
};
8、动态规划
一般以压轴题出现,分值最高,也是最难(我时常自己被自己搞晕,嘤嘤嘤)
8.1、背包不放回策略
每件物品都只有一个(也就是只能拿一次)
function testWeightBagProblem(weight, value, size) {// 定义 dp 数组const len = weight.length,dp = Array(len).fill(Array(size + 1).fill(0));// 初始化 size=6for (let j = weight[0]; j <= size; j++) {dp[0][j] = value[0];}// weight 数组的长度len 就是物品个数for (let i = 1; i < len; i++) {// 遍历物品for (let j = 0; j <= size; j++) {// 遍历背包容量if (j < weight[i]) dp[i][j] = dp[i - 1][j];elsedp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}console.table(dp);console.log(dp[len - 1][size]);return dp[len - 1][size];
}
testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6);
8.2、背包有放回策略
每件物品都有无限个(也就是可以放入背包多次)
// 先遍历物品,再遍历背包容量
function test_completePack1() {let weight = [5, 3, 1];let value = [30, 20, 6];let bagWeight = 4;let dp = new Array(bagWeight + 1).fill(0);for (let i = 0; i <= weight.length; i++) {// j表示容量for (let j = weight[i]; j <= bagWeight; j++) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}console.log(dp);
}
test_completePack1();
8.3、最长公共子序列
const longestCommonSubsequence = (text1, text2) => {let dp = Array.from(Array(text1.length+1), () => Array(text2.length+1).fill(0));for(let i = 1; i <= text1.length; i++) {for(let j = 1; j <= text2.length; j++) {if(text1[i-1] === text2[j-1]) {dp[i][j] = dp[i-1][j-1] +1;;} else {dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])}}}return dp[text1.length][text2.length];
};
8.4、最长公共子串
/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** longest common substring* @param str1 string字符串 the string* @param str2 string字符串 the string* @return string字符串*/
function LCS(str1, str2) {// write code herelet res = [];if (str1.length == 0 || str2.length == 0) return -1;let dp = [];for (let i = 0; i < str1.length; i++) dp.push([]);//dp[i][j]表示s1的i 和 s2的j的最长公共子序列for (let i = 0; i < str1.length; i++){for(let j=0;j<str2.length;j++){if(i==0||j==0){dp[i][j]=str1[i]==str2[j]?1:0}else{dp[i][j]=str1[i]==str2[j]?(dp[i-1][j-1]+1):0}}}let max=0let indexi=-1let indexj=-1dp.forEach((item,index)=>{item.forEach((key,id)=>{if(key>max){max=key;indexi=indexindexj=id}})})console.log("res", indexi,indexj);for (let i = indexi, j = indexj;i >= 0 && j >= 0 && dp[i][j] >= 1;){res.push(str1[i]);i--;j--;}// console.log("res", res.reverse());return res.reverse().join("")
}
module.exports = {LCS: LCS,
};
9、图深度遍历
9.1、飞地的数量
/*** @param {number[][]} grid* @return {number}*/
var numEnclaves = function(grid) {let m=grid.length,n=grid[0].length,max=0;const dfs=(grid, i, j,m,n)=>{if(i<0||j<0||i>=m||j>=n) return 0if(grid[i][j]==0) return 0grid[i][j]=0return 1+dfs(grid, i+1, j,m,n)+dfs(grid, i-1, j,m,n)+dfs(grid, i, j+1,m,n)+dfs(grid, i, j-1,m,n);}for(let i=0;i<m;i++){dfs(grid, i, 0,m,n)dfs(grid, i, n-1,m,n)}for(let i=0;i<n;i++){dfs(grid, 0, i,m,n)dfs(grid, m-1, i,m,n)}for (let i = 0; i < grid.length; i++) {for (let j = 0; j < grid[i].length; j++) {if ( grid[i][j] === 1) {max+=dfs(grid, i, j,m,n);}}
}
return max
};
9.2、岛屿的数量
广度优先
var numIslands = function (grid) {let dir = [[0, 1], [1, 0], [-1, 0], [0, -1]]; // 四个方向let bfs = (grid, visited, x, y) => {let queue = [];queue.push([x, y]);visited[x][y] = true;while (queue.length) {let top = queue.shift();//取出队列头部元素console.log(top)for (let i = 0; i < 4; i++) {let nextX = top[0] + dir[i][0]let nextY = top[1] + dir[i][1]if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length)continue;if (!visited[nextX][nextY] && grid[nextX][nextY] === "1") {queue.push([nextX, nextY])visited[nextX][nextY] = true}}}}let visited = new Array(grid.length).fill().map(() => Array(grid[0].length).fill(false))let res = 0for (let i = 0; i < grid.length; i++) {for (let j = 0; j < grid[i].length; j++) {if (!visited[i][j] && grid[i][j] === "1") {++res;bfs(grid, visited, i, j);}}}return res
};
深度优先
/*** @param {character[][]} grid* @return {number}*/
var numIslands = function (grid) {let dir = [[0, 1], [1, 0], [-1, 0], [0, -1]]; // 四个方向let dfs = (grid, visited, x, y) => {for (let i = 0; i < 4; i++) {let nextX = x + dir[i][0]let nextY = y + dir[i][1]if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length)continue;if (!visited[nextX][nextY] && grid[nextX][nextY] === "1") {visited[nextX][nextY] = truedfs(grid,visited,nextX,nextY)}}}let visited = new Array(grid.length).fill().map(() => Array(grid[0].length).fill(false))let res = 0for (let i = 0; i < grid.length; i++) {for (let j = 0; j < grid[i].length; j++) {if (!visited[i][j] && grid[i][j] === "1") {++res;visited[i][j] = true;dfs(grid, visited, i, j);}}}return res
};
这篇关于前端典例算法集合的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!