字数

1613 字

阅读时间

9 分钟

字符串

[[待办事项 | 各种字符串的算法]]

回文子串

使用动态规划来做，dp[i][j] 表示从i到j的索引位置的子串是否是回文子串
1. 初始化dp数组，首先索引相同的一个元素的子串肯定是回文子串
2. 确定递推顺序，dp[i][j] = dp[i + 1][j - 1]
3. 遍历递推顺序，从小到大
var longestPalindrome = function(s) {
    let len = s.length;
    if (len < 2) return s;

    let maxLen = 1;
    let begin = 0;
    let dp = new Array(len).fill(0).map(item => new Array(len).fill(false));

    for (let i = 0; i < len; i++) {
        dp[i][i] = true;
    }

    let charArr = s.split("");
    for (let j = 1; j < len; j++) {
        for (let i = 0; i < j; i++) {
            if (charArr[i] != charArr[j]) {
                dp[i][j] = false;
            } else {
                if (j - i < 3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }

                if (dp[i][j] && j - i + 1 > maxLen) {
                    begin = i;
                    maxLen = j - i + 1;
                }
            }
        }
    }
    return s.substring(begin, begin + maxLen);
};

kmp 算法

一般字符串匹配可以用两个 for 循环暴力破解， 然后 kmp 是对二次遍历的起始顺序的一个优化，能够让重新遍历的起始位置根据模式串的特性进行动态改变

这个动态改变的方式就是通过维护一个 dp 数组，这个数组的元素表示重新起始位置的迭代顺序，这个 dp 数组又称为部分匹配表

const getNext = function (str) {
    let k = -1, j = 0;
    let next = new Array(str.length);
    next[0] = -1;
    while (j < str.length - 1) {
        if (k === -1 || next[j] ==== next[k]) {
            // P[0 ~ k] == P[j-k ~ j]
            next[++j] = ++k;
        } else {
            k = next[k];
        }
    }
    return next;
}

function KMP(strT, strP) {
    let i = 0, j = 0;
    let next = getNext(strP);
    while (i < strT.length && j < strT.length) {
        if (j === -1 || strT[i] === strP[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j === strP.length) {
        return i - j;
    } else {
        return -1;
    }
}

bf 算法

Brute Force

function bf(strT, strP) {
    let i = 0, j = 0;
    while (i < strT.length && j < strP.length) {
        if (strP[i] === strT[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (i === strP.length) {
        return i - j;
    }
    return -1;
}

排序

快速排序

快速排序的空间复杂度取决于递归的深度，所以最好的时候为 O(logn)，最坏的时候为 O(n)。

快速排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(n²) ，空间复杂度为 O(logn) ，不是稳定排序

function quickSort(array, start, end) {
  let len = array.length;
  if (!Array.isArray(array) || len <= 1 || start > end) return;

  // 将数组划为两个部分
  let index = partion(array, start, end);

  quickSort(array, start, index - 1);
  quickSort(array, index + 1, end);
}

function partion(array, start, end) {
  let pivot = array[start];

  // 左边的值小于pivot，右边的大于pivot
  while (start < end) {
    while (array[end] >= pivot && start < end) {
      end--;
    }
    array[start] = array[end];
    while (array[start] <= pivot && start < end) {
      start++;
    }
    array[end] = array[start];
  }
  array[start] = pivot;
  return start;
}

const _quickSort = array => {
  if(array.length === 1) return array
  let mid = array[0]
  let leftArray = array.filter(item => item < mid)
  // 注意 如果我们取下标 0 为基准值的话，分割后取等的一边，下标智不能为 0
  let rightArray = array.filter((item,index) => item >= mid && index !== 0)
  return [...leftArray,mid,...rightArray]
}

二叉树

使用栈的 先入后出 来做 DFS，使用队列的 先入先出 来做 BFS

深度遍历 -- 迭代遍历

// 前序遍历：中左右

var preorderTraversal = function(root, res = []) {
    const stack = [];
    if (root) stack.push(root);
    while(stack.length) {
        const node = stack.pop();
        if(!node) {
            res.push(stack.pop().val);
            continue;
        }
        if (node.right) stack.push(node.right); // 右
        if (node.left) stack.push(node.left); // 左
        stack.push(node); // 中
        stack.push(null);
    };
    return res;
};

广度遍历 -- 迭代遍历

应用场景

• 求二叉树的最大深度
• 求二叉树的最小深度
• 二叉树的右视图
  • int size = que.size();
  • if (i == (size - 1)) result.push_back(node->val); // 将每一层的最后元素放入 result 数组中
• N 叉树的层序遍历
  • for (int i = 0; i < node->children.size(); i++) { // 将节点孩子加入队列 if (node->children[i]) que.push(node->children[i]); }

function levelOrder(root) {
    let res = [], queue = [];
    if (root) queue.push(root);
    while (queue.length) {
        let len = queue.length;
        let curLevel = [];
        for (let i = 0; i < len; i++) {
            let node = queue.shift();
            curLevel.push(node.val);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        res.push(curLevel);
    }
    return res;
}

回溯

组合问题

let path = [], res = [];
function backTracking (n, k, startIndex) {
    if (path.length === k) {
        res.push([...path]); // 注意点
        return;
    }
    // 优化点
    // i <= n 优化到 i <= n - (k - path.length) + 1
    // 举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2
    // 至多要从 xxx 开始遍历
    for (let i = startIndex; i <= n - (k - path.length) + 1; i++) {
        let path = [];
        path.push(str[i]);
        backTracking(n, k, i+1);
        path.pop();
    }
}
backTracking(n, k, 1);
return res;

电话号码

var letterCombinations = function(digits) {
    const k = digits.length;
    const map = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"];
    if(!k) return [];
    // 处理边界
    if(k === 1) return map[digits].split("");

    const res = [], path = [];
    backtracking(digits, k, 0);
    return res;

    function backtracking(n, k, a) {
        if(path.length === k) {
            // 注意是path.join("")
            res.push(path.join(""));
            return;
        }
        for(const v of map[n[a]]) {
            path.push(v);
            backtracking(n, k, a + 1);
            path.pop();
        }

    }
};

组合问题（重复元素，组合去重

利用 used 数组 去重，同一树层为 false，同一树枝为 true

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明： 所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。

示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

示例 2: 输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [   [1,2,2],   [5] ]

let len = candidate.length;
let used = new Array(len).fill(false);
let path = [], res = [];
candidate.sort((a, b) => a - b);
function backtracking (candidate, target, sum, startIndex, used) {
    if (target > sum) {
        return;
    }
    if (target === sum) {
        res.push([...path]);
        return;
    }
    for (let i = startIndex; i < candidate.length && sum + candidate[i] <= target; i++) {
        if (i > 0 && candidate[i] === candidate[i - 1] && !used[i - 1]) {
            continue;
        }
        sum += candidate[i];
        path.push(candidate[i]);
        used[i] = true;
        backtracking(candidate, target, sum, startIndex + 1, used);
        used[i] = false;
        path.pop(candidate[i]);
        sum -= candidate[i];
    }
}
backtracking(candidate, target, 0, 0, used);
return res;

分割回文串

isPalindrome

循环终止的判断条件为 startIndex >= str.length

子集问题

对比组合问题和切割问题求的是树的 叶子节点，子集问题求的是树的 所有节点，

var subsets = function(nums) {
    let result = []
    let path = []
    function backtracking(startIndex) {
        result.push([...path]) // 注意
        for(let i = startIndex; i < nums.length; i++) {
            path.push(nums[i])
            backtracking(i + 1)
            path.pop()
        }
    }
    backtracking(0)
    return result
};

全排列问题

利用 used 数组去重，跳过循环的条件为 used[i]

var permute = function(nums) {
    const res = [], path = [];
    backtracking(nums, nums.length, []);
    return res;

    function backtracking(n, k, used) {
        if(path.length === k) { // 注意
            res.push(Array.from(path));
            return;
        }
        for (let i = 0; i < k; i++ ) {
            if(used[i]) continue; // 注意
            path.push(n[i]);
            used[i] = true; // 同支
            backtracking(n, k, used);
            path.pop();
            used[i] = false;
        }
    }
};

N 皇后

贡献者

jiechen

页面历史

最后编辑于 22 天前

查看完整历史

645939d-refactor: bump version

452cb6a-chore: remove useless files

4852296-style: use the Obsidian Lint plugin to unify the style

1bb046d-chore: remove useless files

c69a0b7-chore: organize file directories

bda0b7c-init

eef598d-init