前端典例算法集合

2023-12-13 07:24:40

前言

刷算法顺序:1、熟悉本文章第1点的内容;2、刷力扣算法,可以参考这本书的顺序与思想:代码随想录完整版PDF下载 | 合集下载 | 百度云 | | 代码随想录 (programmercarl.com)

3、刷牛客的高频考题

1、熟悉数组Array,字符串String、对象Object、字典Map、集合Set的方法、Math对象、Date对象、正则对象RegExp等基础

1.1、数组Array的方法:

  1. 添加和删除元素:

    • push(element1, ..., elementN): 在数组末尾添加一个或多个元素,并返回数组的新长度。
    • pop(): 移除并返回数组的最后一个元素。
    • unshift(element1, ..., elementN): 在数组开头添加一个或多个元素,并返回数组的新长度。
    • shift(): 移除并返回数组的第一个元素。
  2. 拼接和分割:

    • concat(array1, array2, ..., arrayN): 返回一个由当前数组和其他数组或值拼接而成的新数组。
    • join(separator): 将数组的所有元素连接成一个字符串,使用指定的分隔符。
  3. 切片和连接:

    • slice(start, end): 返回一个从起始索引到结束索引(不包括结束索引)的新数组。
    • splice(start, deleteCount, item1, item2, ...): 从指定位置开始删除元素,并可选地插入新元素。
  4. 查找和过滤:

    • indexOf(searchElement[, fromIndex]): 返回指定元素在数组中第一次出现的索引,如果不存在则返回 -1。
    • lastIndexOf(searchElement[, fromIndex]): 返回指定元素在数组中最后一次出现的索引,如果不存在则返回 -1。
    • find(callback(element, index, array)): 返回数组中第一个满足条件的元素,否则返回 undefined
    • filter(callback(element, index, array)): 返回一个包含所有满足条件的元素的新数组。
  5. 映射和遍历:

    • map(callback(element, index, array)): 返回一个新数组,包含对每个元素进行指定操作后的结果。
    • forEach(callback(element, index, array)): 对数组中的每个元素执行一次提供的函数。
  6. 排序和反转:

    • sort([compareFunction]): 将数组中的元素排序。如果未提供比较函数,则元素按照字符串 Unicode 码点升序排序。
    • reverse(): 将数组中的元素颠倒。
  7. 其他:

    • 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方法

  1. 字符串拼接和分割:

    • concat(str1, str2, ..., strN): 将多个字符串拼接成一个新字符串。
    • + 操作符: 也可以用于字符串拼接。
    • split(separator[, limit]): 将字符串分割为子字符串数组,根据指定的分隔符进行分割。
  2. 字符串查找:

    • indexOf(searchValue[, fromIndex]): 返回指定值在字符串中首次出现的位置,如果没有找到则返回 -1。
    • lastIndexOf(searchValue[, fromIndex]): 返回指定值在字符串中最后一次出现的位置,如果没有找到则返回 -1。
    • startsWith(searchString[, position]): 判断字符串是否以指定的字符开始。
    • endsWith(searchString[, length]): 判断字符串是否以指定的字符结尾。
    • includes(searchString[, position]): 判断字符串是否包含指定的字符。
  3. 字符串截取和提取:

    • slice(start[, end]): 提取字符串的一部分,返回一个新字符串。
    • substring(start[, end]): 类似于 slice,但不允许负数作为参数。
    • substr(start[, length]): 从指定位置开始,返回指定长度的字符串。
  4. 字符串转换:

    • toLowerCase(): 将字符串转换为小写。
    • toUpperCase(): 将字符串转换为大写。
    • toString(): 返回字符串的原始值的字符串表示。
  5. 字符串替换:

    • replace(searchValue, replaceValue): 替换字符串中的指定值,返回一个新字符串。可以使用正则表达式进行全局替换。
    • replaceAll(searchValue, replaceValue): 替换字符串中的所有匹配项。
  6. 去除空格:

    • trim(): 移除字符串两端的空格。
  7. 其他:

    • charAt(index): 返回指定索引位置的字符。
    • charCodeAt(index): 返回指定索引位置的字符的 Unicode 值。
    • length: 返回字符串的长度。

1.3、对象Object的方法

在 JavaScript 中,对象是键值对的集合,可以包含各种类型的数据。对象类型提供了一些内置的方法,用于执行各种操作。以下是一些常见的对象方法:

  1. 对象属性操作:

    • Object.keys(obj): 返回一个包含对象自身所有可枚举属性的数组。
    • Object.values(obj): 返回一个包含对象自身所有可枚举属性值的数组。
    • Object.entries(obj): 返回一个包含对象自身所有可枚举属性的 [key, value] 数组的数组。
    • Object.hasOwnProperty(prop): 检查对象是否具有指定属性,不包括原型链上的属性。
    • Object.getOwnPropertyNames(obj): 返回一个包含对象自身所有属性(不仅仅是可枚举属性)的数组。
    • Object.getOwnPropertyDescriptor(obj, prop): 返回指定属性的属性描述符。
  2. 对象合并和克隆:

    • Object.assign(target, source1, source2, ...sourceN): 将源对象的所有可枚举属性复制到目标对象,返回目标对象。
    • Object.create(proto[, propertiesObject]): 创建一个新对象,使用现有对象作为新创建对象的原型。
    • Object.freeze(obj): 冻结对象,阻止修改现有属性和添加新属性。
  3. 对象遍历:

    • Object.keys(obj).forEach(key => ...): 遍历对象的所有可枚举属性的键。
    • Object.values(obj).forEach(value => ...): 遍历对象的所有可枚举属性的值。
    • Object.entries(obj).forEach(([key, value]) => ...): 遍历对象的所有可枚举属性的 [key, value] 数组。
  4. 对象删除属性:

    • delete obj.property: 通过属性名删除对象的属性。
  5. 对象比较:

    • Object.is(value1, value2): 比较两个值是否相同,类似于 ===,但处理 NaN 和 +0/-0 的不同。
  6. 其他:

    • Object.getPrototypeOf(obj): 返回指定对象的原型。
    • Object.setPrototypeOf(obj, proto): 设置指定对象的原型。
    • Object.entries(obj).length: 获取对象中可枚举属性的数量

1.4、字典Map的方法

  1. 基本操作:

    • set(key, value): 向 Map 中添加或更新键值对。
    • get(key): 获取指定键对应的值,如果键不存在则返回 undefined
    • has(key): 判断 Map 中是否包含指定键,返回布尔值。
    • delete(key): 删除 Map 中指定键对应的键值对。
    • clear(): 清空 Map 中的所有键值对。
  2. 遍历方法:

    • keys(): 返回一个包含 Map 中所有键的迭代器。
    • values(): 返回一个包含 Map 中所有值的迭代器。
    • entries(): 返回一个包含 Map 中所有键值对的迭代器。
    • forEach(callbackFn [, thisArg]): 遍历 Map 中的键值对,并对每个键值对执行回调函数。
  3. 属性:

    • size: 返回 Map 中键值对的数量。
  4. 初始化:

    • new Map(iterable): 创建一个新的 Map 对象,可传入可迭代对象(如数组)来初始化 Map。

1.5、集合Set的方法

  1. 基本操作:

    • add(value): 向 Set 中添加一个值,如果值已经存在则不会重复添加。
    • delete(value): 删除 Set 中指定的值。
    • has(value): 判断 Set 中是否包含指定的值,返回布尔值。
    • clear(): 清空 Set 中的所有值。
  2. 遍历方法:

    • values(): 返回一个包含 Set 中所有值的迭代器。也可以用 for...of 遍历。
    • keys(): 与 values() 方法相同,返回一个包含 Set 中所有值的迭代器。
    • entries(): 返回一个包含 Set 中所有值的 [value, value] 数组的迭代器。
    • forEach(callbackFn [, thisArg]): 遍历 Set 中的每个值,并对每个值执行回调函数。
  3. 属性:

    • size: 返回 Set 中值的数量。
  4. 初始化:

    • new Set(iterable): 创建一个新的 Set 对象,可传入可迭代对象(如数组)来初始化 Set。

1.6、Math对象的方法

  1. 基本数学运算:

    • 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): 返回一组数中的最小值.
  2. 指数和对数运算:

    • Math.pow(x, y): 返回 x 的 y 次幂。
    • Math.sqrt(x): 返回 x 的平方根。
    • Math.exp(x): 返回自然数 e 的 x 次幂。
    • Math.log(x): 返回 x 的自然对数。
  3. 三角函数:

    • Math.sin(x): 返回 x 弧度的正弦值。
    • Math.cos(x): 返回 x 弧度的余弦值。
    • Math.tan(x): 返回 x 弧度的正切值。
    • Math.asin(x): 返回 x 的反正弦值。
    • Math.acos(x): 返回 x 的反余弦值。
    • Math.atan(x): 返回 x 的反正切值。
  4. 随机数生成:

    • Math.random(): 返回一个 0(包括)到 1(不包括)之间的随机数。
    • Math.floor(Math.random() * (max - min + 1)) + min: 返回一个指定范围内的随机整数。
  5. 常数:

    • Math.PI: 圆周率 π。
    • Math.E: 自然对数的底数 e。
  6. 其他:

    • Math.abs(x): 返回 x 的绝对值。
    • Math.sign(x): 返回 x 的符号,1 表示正数,-1 表示负数,0 表示零。
    • Math.trunc(x): 返回 x 的整数部分。

1.7、Date对象的方法

  1. 获取日期和时间信息:

    • 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 表示星期日)。
  2. 设置日期和时间信息:

    • setDate(day): 设置日期中的天。
    • setMonth(month): 设置日期中的月份。
    • setFullYear(year): 设置日期中的年份。
    • setHours(hours): 设置时间中的小时。
    • setMinutes(minutes): 设置时间中的分钟。
    • setSeconds(seconds): 设置时间中的秒。
    • setMilliseconds(milliseconds): 设置时间中的毫秒。
    • setTime(time): 设置日期对象的时间值。
  3. 格式化输出:

    • toDateString(): 返回日期部分的字符串。
    • toTimeString(): 返回时间部分的字符串。
    • toLocaleDateString(): 返回本地化的日期字符串。
    • toLocaleTimeString(): 返回本地化的时间字符串。
    • toString(): 返回日期和时间的字符串表示。
  4. 比较和计算:

    • getTime(): 返回日期对象的时间戳(毫秒)。
    • getTimezoneOffset(): 返回当前时区与 UTC 时区之间的分钟差。
    • Date.parse(dateString): 解析日期字符串,返回对应的时间戳。

1.8、正则对象的方法

  1. 创建正则对象:

    • new RegExp(pattern [, flags]): 创建一个新的正则表达式对象,其中 pattern 是正则表达式的模式字符串,flags 是标志字符串(可选),用于设置匹配规则。
  2. 正则表达式的常用模式:

    • /pattern/flags: 直接使用字面量表示法创建正则表达式,其中 pattern 是正则表达式的模式,flags 是标志(可选)。
    • // 示例
      let regex = /\d+/g; // 匹配一个或多个数字,全局匹配
      
      // 使用正则对象进行匹配测试
      let result = regex.test("12345");
      console.log(result); // 输出: true
  3. 匹配规则和标志:

    • ^: 匹配字符串的开头。
    • $: 匹配字符串的结尾。
    • .: 匹配任意单个字符。
    • *: 匹配前一个字符零次或多次。
    • +: 匹配前一个字符一次或多次。
    • ?: 匹配前一个字符零次或一次。
    • []: 匹配字符集中的任意一个字符。
    • |: 或运算,匹配两者之一。
    • \: 转义字符,用于匹配特殊字符。
    • (): 分组,用于将多个模式组合在一起。
  4. 字符类别:

    • \d: 匹配数字字符(相当于 [0-9])。
    • \D: 匹配非数字字符。
    • \w: 匹配单词字符(字母、数字、下划线,相当于 [a-zA-Z0-9_])。
    • \W: 匹配非单词字符。
    • \s: 匹配空白字符(空格、制表符、换行符等)。
    • \S: 匹配非空白字符。
  5. 量词:

    • {n}: 匹配前一个字符恰好 n 次。
    • {n,}: 匹配前一个字符至少 n 次。
    • {n,m}: 匹配前一个字符至少 n 次,最多 m 次。
  6. 贪婪和非贪婪:

    • *?: 非贪婪匹配,匹配前一个字符零次或多次,尽量匹配少的字符。
    • +?: 非贪婪匹配,匹配前一个字符一次或多次,尽量匹配少的字符。
    • ??: 非贪婪匹配,匹配前一个字符零次或一次,尽量匹配少的字符。
    • {n,}?: 非贪婪匹配,匹配前一个字符至少 n 次,尽量匹配少的字符。
    • {n,m}?: 非贪婪匹配,匹配前一个字符至少 n 次,最多 m 次,尽量匹配少的字符。
  7. 匹配结果的方法:

    • 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++;

        // 更新offset
        offset += 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 here
    var phead=ListNode(null)
    var p=head;
    while(head){
        p=p.next;
        head.next=phead.next
        phead.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=head
    head = 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中寻找是否有匹配的key
    if (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 here
    let res=[]
    let len=num.length
   
    let 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 here
    const 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 here
    const 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 here
    let 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 here
    const 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 here
    let 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=6
  for (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];
      else
        dp[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 here
    let 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=0
    let indexi=-1
    let indexj=-1
    dp.forEach((item,index)=>{
        item.forEach((key,id)=>{
            if(key>max){
                max=key;
                indexi=index
                indexj=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 0
        if(grid[i][j]==0) return 0
        grid[i][j]=0
        return 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 = 0
    for (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] = true
                dfs(grid,visited,nextX,nextY)
            }
        }
    }
    let visited = new Array(grid.length).fill().map(() => Array(grid[0].length).fill(false))


    let res = 0
    for (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
};

文章来源:https://blog.csdn.net/m0_56770663/article/details/134850605
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。