前言

如果你最近准备面试算法，并且没有多余时间系统复习算法，那么看这一篇文章足够了。

字符串处理

字符串处理是一个比较广的领域，有很多经典的算法可供研究，这里列举几个比较常见的算法和大家分享。

BF算法

BF 是 Brute Force 的简称，意思是“暴力”，也就是不讲究效率，而是通过蛮力来解决问题。他尤其被用在字符串匹配问题上：

BF算法的思想就是将目标串 S 的第一个字符与模式串 T 的第一个字符进行匹配，若相等，则继续比较 S 的第二个字符和 T 的第二个字符；若不相等，则比较 S 的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。

时间复杂度

该算法最坏情况下要进行 M(N-M+1) 次比较，时间复杂度为 O(MN)。

举例

S: abcdabeabcdabd
T: abcdabd

package com.kyson.chapter1.section1;

public class BF {

    public static int search(String pat, String txt) {
        int M = pat.length();
        int N = txt.length();

        for (int i = 0; i <= N - M; ++i) {
            int j;
            for (j = 0; j < M; j++) {
                if (pat.charAt(j) != txt.charAt(i + j))
                    break;
            }
            
            // pat 全都匹配了
            if(j == M) return i;
        }
        return -1;
    }
    
    public static void main(String[] args){
        String mainString = "abcdabeabcdabd";
        String subString = "abcdabd";
        int index = search(subString,mainString);
        System.out.println( "index:" + index);
    }
}

输出如下：

index:7

RK算法

RK算法（Rabin-Karp算法）是由Rabin和Karp共同提出的一个算法，他是一种基于哈希技术的字符串匹配算法，它在处理某些特定场景时具有高效性。 RK算法的核心思想是利用哈希函数将子串中的字符转换为数值，从而将字符串匹配问题转化为数值匹配问题。通过比较哈希值，可以在常数时间内判断子串是否与目标子串相等，从而大大减少了比较次数。
常用的哈希函数有MD5和SHA-1等。

使用场景

论文查重

时间复杂度

时间复杂度：O（N），最坏情况下，每个子串和模式串的哈希值都相等，则退化成BF算法，时间复杂度达到O(N*M)

举例

public static int search(String pat,String txt) {
        int M = pat.length();
        int N = txt.length();

        for (int i = 0; i <= N - M; ++i) {
            String subTxt = txt.substring(i, N - M + i);
            //防止 Hash 冲突，需要做二次确认
            if (subTxt.hashCode() == pat.hashCode() && match(pat,txt,i)) {
                return i;
            }
        }
        return -1;
    }

    private static boolean match(String p,String t,int i){

        for (int j = 0 ; j < p.length(); ++j){
            if (p.charAt(j) != t.charAt(i + j)) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        String mainString = "abcdabeabcdabd";
        String subString = "abcdabd";

        int index = search(subString,mainString);
        System.out.println( "index:" + index);
    }

输出如下：

index:7

二叉树（Binary Tree）

种类

  • 满二叉树（A full binary tree (sometimes referred to as a proper,plane, or strict binary tree)）
  • 完全二叉树 （complete binary tree）
  • 二叉查找数（又称“二叉搜索树” Binary Search Tree）
  • 平衡二叉搜索树（AVL：Adelson-Velsky and Landis）

构造代码

通过链表（Nodes and references）


public class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;
}

通过数组

大顶堆或者小顶堆就是通过这种方式。

操作

插入（Insertion）

  • Leaf nodes
  • Internal nodes

删除（Deletion）

  • Node with zero or one children
  • Node with two children

遍历（traversal visit）

Pre-order（前序遍历）

leecode第 144 题

class Solution {
    
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}

In-order（中序遍历）

// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             // 注意这一句
        inorder(root.right, list);
    }
}

Post-order（后序遍历）

// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);             // 注意这一句
    }
}

Depth-first order（深度优先）

Breadth-first order（广度优先）

动态规划

动态规划（Dynamic Programming, DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

单调栈

栈/队列是数据结构中很重要的概念，能融合这两者的双端队列更加重要。在 Java 中对应的类是 LinkedList，它既是栈，又是队列，可以说非常强大了。
单调栈能解决一些特定问题。

寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置

举例

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int lens = temperatures.length;
        int[] res = new int[lens];
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < lens; i++) {

            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                res[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }

        return res;

    }
}

时间复杂度

O(n)

空间复杂度

O(n)

算法设计与分析

  • Backtracking（回溯法）
  • Branch and bound
  • Brute-force search（暴力搜索）
  • Divide and conquer（分治法 D&C algorithms）
  • Dynamic programming（动态规划）
  • Greedy algorithm （贪心算法）
  • Recursion （递归）
  • Prune and search

公开课

算法复杂度

分治法

分治法就是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
经典的例子有

  • 二分法搜索（Binary Search）
  • 傅立叶变换
  • Karatsuba算法

挑战

分治法可能会导致占用过大的内存，因此设计时会通过一定方式减少内存使用，比如 stack, queue, 或者 priority queue。

回溯法

Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems.

使用场景

回溯是解决约束满足问题的重要工具，例如填字游戏、口头算术、数独和许多其他谜题。 对于背包问题和其他组合优化问题，它通常是最方便的解析技术。 它也是编程语言 Icon、Planner 和 Prolog 中使用的程序执行策略。

经典解决的问题：

  • 组合问题
  • 切割问题
  • 子集问题
  • 排列问题
  • 棋盘问题（八皇后问题）

贪心法

摊还分析