常见算法题型 🔥

算法的复杂度分析。
排序算法，以及他们的区别和优化。
数组中的双指针、滑动窗口思想。
利用 Map 和 Set 处理查找表问题。
链表的各种问题。
利用递归和迭代法解决二叉树问题。
栈、队列、DFS、BFS。
回溯法、贪心算法、动态规划。

滑动窗口问题

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

利用set()自动去重的特点

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if (s.length===0) return 0
    let j = 0, maxLen = 0
    let set = new Set()
    // 遍历字符串
    for (let i=0;i<s.length;i++) {
        // 每次往set里添加元素时, 都要先使用while循环从头删除set里的元素, 直到set里没有当前要添加的元素为止
        while(set.has(s[i])) {
            set.delete(s[j])
            j++ // j指针是关键
        }
        set.add(s[i])
        maxLen = Math.max(maxLen, set.size)
    }
    return maxLen
};

链表问题

反转链表

三指针：p1,p2,tmp
使用p2遍历整个链表

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function ReverseList(pHead)
{
    let p1 = null
    let p2 = pHead
    while (p2) {
        let tmp = p2.next
        p2.next = p1
        p1 = p2
        p2 = tmp
    }
    return p1
}
module.exports = {
    ReverseList : ReverseList
};

删除链表的节点

简单，画图理解即可

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param val int整型 
 * @return ListNode类
 */
function deleteNode( head ,  val ) {
    let dummy = new ListNode()
    dummy.next = head
    let cur = dummy
    while (cur.next.val!==val) {
        cur=cur.next
    }
    cur.next = cur.next.next
    return dummy.next
}
module.exports = {
    deleteNode : deleteNode
};

合并两个排序的链表

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function Merge(pHead1, pHead2) {
  let dummy = new ListNode()
  let cur = dummy
  while (pHead1 && pHead2) {
    if (pHead1.val < pHead2.val) {
      cur.next = pHead1
      pHead1 = pHead1.next
    } else {
      cur.next = pHead2
      pHead2 = pHead2.next
    }
    cur = cur.next
  }
  if (pHead1) {
    cur.next = pHead1
  }
  if (pHead2) {
    cur.next = pHead2
  }
  return dummy.next
}
module.exports = {
  Merge: Merge
};

2. 两数相加

类比拿草稿纸进行两数相加
sum先加carry，carry代表进位的数字
再更新下一轮的carry
最后再写当前位的数字，也就是创建结点
两个链表都遍历完成后，如果carry!==0，则再创建结点

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode()
    let carry = 0
    let cur = dummy // 操作cur指针, 实际上是为了改变dummy
    while (l1||l2) {
        let sum = 0
        if (l1){
            sum+=l1.val
            l1=l1.next
        }
        if (l2){
            sum+=l2.val
            l2=l2.next
        }
        sum+=carry // 1.sum先加carry
        carry = Math.floor(sum/10) // 2.再更新carry
        cur.next = new ListNode(sum%10)// 3.再创建节点
        cur=cur.next
    }
    if (carry>0) {
        cur.next = new ListNode(carry)
    }
    return dummy.next
};

24. 两两交换链表中的节点

虚拟头节点

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    let dummy = new ListNode()
    dummy.next= head
    let cur = dummy
    while (cur.next!==null && cur.next.next!==null) {
      	// 这6行可以画图理解 
        let n1 = cur.next;
        let n2 = cur.next.next;
        cur.next = n2
        n1.next = n2.next
        n2.next = n1
        cur = n1
    }
    return dummy.next
};

队列

【模板】队列

学会readline()的使用

请你实现一个队列。

操作：

push x：将 x 加入队尾，保证 x 为 int 型整数。

pop：输出队首，并让队首出队

front：输出队首：队首不出队

输入：

6
push 1
pop
front
push 2
push 3
pop

const rl = require('readline').createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  var line
  let ddyquene = [];
  while (line = await readline()) {
    let [operation,num] = line.split(' ')
    switch (operation) {
      case "push":
        ddyquene.push(num);
        break;
      case "pop":
        if (ddyquene.length) {
          console.log(ddyquene.shift());
        } else {
          console.log("error");
        }
        break;
      case "front":
        if (ddyquene.length) {
          console.log(ddyquene[0]);
        } else {
          console.log("error");
        }
        break;
    }
  }
})();

【模板】循环队列

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // Write your code here
    const line = await readline();
    const [n, q] = line.split(" ").map(Number);
    let heap = [];
    for (let i = 0; i < q; i++) {
        let newL = await readline();
        let [operate, num] = newL.split(" ");
        if (operate === "push") {
            heap.length < n ? heap.push(num) : console.log("full");
        } else if (operate === "front") {
            let msg = "empty";
            if (heap.length > 0) {
                msg = heap[0];
            }
            console.log(msg);
        } else {
            let msg = "empty";
            if (heap.length > 0) {
                msg = heap.shift();
            }
            console.log(msg);
        }
    }
})();

二叉树

实现二叉树先序，中序和后序遍历

递归 + 根左右/左根右/左右根

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 *
 * @param root TreeNode类 the root of binary tree
 * @return int整型二维数组
 */
let preArr = []; // preOrder
let headArr = [];// inOrder
let proArr = []; // postOrder
function preOrders(root) {
    if (!root) {
        return null;
    }
    preArr.push(root.val);
    preOrders(root.left);
    preOrders(root.right);
}
function headOrders(root) {
    if (!root) {
        return null;
    }
    headOrders(root.left);
    headArr.push(root.val);
    headOrders(root.right);
}
function proOrders(root) {
    if (!root) {
        return null;
    }
    proOrders(root.left);
    proOrders(root.right);
    proArr.push(root.val);
}
function threeOrders(root) {
    // write code here
    preOrders(root);
    headOrders(root);
    proOrders(root);
    let res = [];
    res.push(preArr, headArr, proArr);
    return res;
}
module.exports = {
    threeOrders: threeOrders,
};

105. 从前序与中序遍历序列构造二叉树 - 力扣（Leetcode）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if (preorder.length===0||inorder.length===0) return null
    var root = preorder[0]
    let idx = inorder.indexOf(root) // 根节点在中序遍历中的下标
    let node = new TreeNode(root)
    node.left = buildTree(preorder.slice(1,idx+1), inorder.slice(0, idx))
    node.right = buildTree(preorder.slice(idx+1), inorder.slice(idx+1))
    return node
};

106. 从中序与后序遍历序列构造二叉树 - 力扣（Leetcode）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    if (inorder.length===0||postorder.length===0) return null
    var root = postorder[postorder.length-1]
    let node = new TreeNode(root)
    let idx = inorder.indexOf(root)
    node.left = buildTree(inorder.slice(0, idx), postorder.slice(0, idx))
    node.right = buildTree(inorder.slice(idx+1), postorder.slice(idx,postorder.length-1))
    return node
};

bfs

dfs

200. 岛屿数量

下沉扩散 + 深度优先搜索

遍历表格, 若检测到取值为"1"的点, 就将count++, 并将当前点的值设为"0", 也即下沉当前点
使用深度优先搜索, 将当前点周围取值为"1"的点也设置为"0"
继续遍历表格, 最后返回count

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {

  let count = 0

  // 下沉函数
  function dfs (row, col) {
    // 边界判断
    if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] === '0') {
      return
    }
    // 下沉当前点
    grid[row][col] = '0'
    // 并使用深度优先搜索进行下沉扩散
    dfs(row - 1, col)
    dfs(row + 1, col)
    dfs(row, col - 1)
    dfs(row, col + 1)
  }
  // 遍历表格
  for (let row = 0; row < grid.length; row++) {
    for (let col = 0; col < grid[0].length; col++) {
      if (grid[row][col] === '1') {
        count++
        dfs(row, col)
      }
    }
  }
  return count
}

257. 二叉树的所有路径

用当前节点的值去拼接左右子树递归调用当前函数获得的所有路径。

也就是根节点拼上以左子树为根节点得到的路径，加上根节点拼上以右子树为根节点得到的所有路径。

直到叶子节点，仅仅返回包含当前节点的值的数组。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
let binaryTreePaths = function (root) {
  let res = []
  if (!root) {
    return res
  }

  if (!root.left && !root.right) {
    return [`${root.val}`]
  }

  let leftPaths = binaryTreePaths(root.left)
  let rightPaths = binaryTreePaths(root.right)

  leftPaths.forEach((leftPath) => {
    res.push(`${root.val}->${leftPath}`)
  })
  rightPaths.forEach((rightPath) => {
    res.push(`${root.val}->${rightPath}`)
  })

  return res
}

查找表问题

350. 两个数组的交集 II

为两个数组分别建立 map，用来存储 num -> count 的键值对，统计每个数字出现的数量。

然后对其中一个 map 进行遍历，查看这个数字在两个数组中分别出现的数量，取出现的最小的那个数量（比如数组 1 中出现了 1 次，数组 2 中出现了 2 次，那么交集应该取 1 次），push 到结果数组中即可。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function (nums1, nums2) {
  let map1 = new Map()
  let map2 = new Map()
  let res = []
  // 获得map
  for (let i = 0; i < nums1.length; i++) {
    if (map1.get(nums1[i])) {
      map1.set(nums1[i], map1.get(nums1[i]) + 1)
    } else {
      map1.set(nums1[i], 1)
    }
  }
  for (let i = 0; i < nums2.length; i++) {
    if (map2.get(nums2[i])) {
      map2.set(nums2[i], map2.get(nums2[i]) + 1)
    } else {
      map2.set(nums2[i], 1)
    }
  }
	// 遍历map1
  for (let item of map1.keys()) {
    let count1 = map1.get(item)
    let count2 = map2.get(item)
    if (count2) {
      let countPush = Math.min(count1, count2)
      for (let j = 0; j < countPush; j++) {
        res.push(item)
      }
    }
  }
  return res
};

1. 两数之和

map知识点：

has(key)方法判断map中是否存在key，返回boolen值
get(key)方法返回map中的value值
set(key, value)方法设置map中的键值对

解题过程：

用map来存放{数组元素值，索引}这样的键值对
运用逆向解法，即用target减去数组中的某个元素，然后来判断map中是否有相同的值，若有则存在满足条件的答案，返回两个坐标即可；若没有，则保存{数组中某个元素值，对应的坐标}到map对象中。依次遍历即可判断是否有满足条件的两个元素。
- 如果map里能找不到key = target-nums[i]的, 就将当前值作为key, 当前索引作为value存入map中
- 如map里能找到键为target-nums[i]则返回[map.get(temp), i]

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = new Map()
    for (let i=0;i<nums.length;i++) {
        let temp = target-nums[i]
        if (!map.has(temp)) {
            map.set(nums[i], i)
        }else {
            return [map.get(temp), i]
        }
    }
};

栈与队列

20. 有效的括号 - 力扣（Leetcode）

利用一个map和一个stack，由于js里没有stack，所以使用数组的push和pop来模拟栈的操作

遍历字符串，如果当前字符包含在map的key里，就将对应的value入栈
否则就出栈，判断出栈元素是否等于当前字符，如果不相等就返回false，说明括号无效
最后判断栈的长度，如果为0说明括号有效，否则无效

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let map = new Map();
    map.set('(', ')');
    map.set('[', ']');
    map.set('{', '}');
    let stack = [];
    for (let i=0; i<s.length; i++) {
        if (map.has(s[i])) {
            stack.push(map.get(s[i]));
        } else {
            if (stack.pop()!==s[i]) return false
        }
    }
    return stack.length===0
};

排序算法

4. 寻找两个正序数组的中位数🫣

暴力解法: 快排+找中位数

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    // 快排
    function quickSort(arr=[]) {
        if (arr.length<2) return arr
        let privot = arr[0]
        let smallerList = arr.slice(1).filter(item=>item<=privot)
        let largerList = arr.slice(1).filter(item=>item>privot)
        return [...quickSort(smallerList), privot, ...quickSort(largerList)]
    }
    let arr = quickSort([...nums1, ...nums2])
    // 找中位数
    let len = arr.length
    if (len % 2 === 0) { // 长度偶数
        return (arr[len / 2] + arr[len / 2 - 1]) / 2;
    }
    else { // 长度奇数
        return arr[(len - 1) / 2];
    }
};

题目要求时间复杂度为O(log (m + n)),一般带有log就要想到二分法

...

中心扩散算法

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (s.length<2) return s;
    let start = 0;
    let maxLen = 1;
    function expandAroundCenter(l, r){
        while (l>=0&&r<s.length&&s[l]===s[r]) {
            if (r-l+1>maxLen) {
                maxLen = r-l+1;
                start = l;
            }
            l--;
            r++;
        }
    }
    for (let i=0; i<s.length;i++) {
        expandAroundCenter(i-1, i+1);
        expandAroundCenter(i, i+1);
    }
    return s.substring(start, start+maxLen);
};

二分查找

二分查找-I

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @param target int整型
 * @return int整型
 */
function search(nums, target) {
    // write code here
    let len = nums.length;
    if (!len) {
        return -1;
    }
    let [left, right] = [0, len - 1];
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        const num = nums[mid];
        if (num > target) {
            right = mid - 1;
        } else if (num < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}
module.exports = {
    search: search,
};

递归

汉诺塔问题

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return string字符串一维数组
 */
function move(m, n, arr) {
  arr.push("move from " + m + " to " + n)
}
function hanoi(n, left, mid, right, arr) {
  if (n === 1) {
    move(left, right, arr)
  } else {
    hanoi(n - 1, left, right, mid, arr) //递归，把left上编号1~n-1的圆盘移到mid上，以right为辅助塔
    move(left, right, arr)//把left塔上的圆盘移到right上
    hanoi(n - 1, mid, left, right, arr)//递归，把mid塔上编号1~n-1的圆盘移到righ上，以left为辅助塔
  }
}
function getSolution(n) {
    let arr =[]
  hanoi(n, "left", "mid", "right", arr)
  return arr
}
module.exports = {
  getSolution: getSolution
};

常见算法题型 🔥 ​

滑动窗口问题 ​

链表问题 ​

队列 ​

二叉树 ​

bfs ​

dfs ​

200. 岛屿数量 ​

查找表问题 ​

栈与队列 ​

排序算法 ​

4. 寻找两个正序数组的中位数🫣 ​

中心扩散算法 ​

二分查找 ​

递归 ​