[leetcode] 数据结构与算法思想

[noogel]

数据结构

• 数组
• 栈，先进后出
• 队列，先进先出
  • 双端队列，双端队列中的元素可以从两端弹出，插入和删除操作限定在队列的两边进行。
  • 环形队列，环形队列是一种特殊的队列结构，保证了元素也是先进先出的，但与一般队列的区别是，他们是环形的，即队列头部的上个元素是队列尾部，通常是容纳元素数固定的一个闭环。
• 堆，一种特别的树状数据结构。堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。
• 链表
  • 单向链表。
  • 双向链表。
  • 跳表，一种带多级索引的链表。
• 散列表，是根据键而直接访问在内存存储位置的数据结构。它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。
• 树
  • 二叉树，二叉树是一个连通的无环图，并且每一个顶点的度不大于3。
  • 红黑树，是一种自平衡二叉查找树。
  • 字典树（Trie） 字典树实现
• 图，图（Graph）是由顶点的有穷非空集合和顶点之间的边的集合组成。
  • https://zhuanlan.zhihu.com/p/25498681
• 布隆过滤器

算法思想

分治法

分治法是基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

例子：快排、归并排序、MapReduce

贪心算法

贪心算法就是在每一步的选择中都按照当前最优的选择，从而希望最终结果得到最优解。贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

例子：最小生成树、哈夫曼编码

动态规划（Dynamic Programming）

动态规划通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常适用于有重叠子问题和最优子结构性质的问题。
若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

递归+记忆=递推

适用情况：

1. 具有最优子结构性质。
2. 无后效性，子问题确定后不会再改变。
3. 子问题重叠的性质。

例子：背包问题

https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
https://www.zhihu.com/question/23995189/answer/613096905

回溯法（backtracking）

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

1. 找到一个可能存在的正确的答案
2. 在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

例子：八皇后问题

https://zh.wikipedia.org/wiki/%E5%9B%9E%E6%BA%AF%E6%B3%95
https://www.cnblogs.com/zuzZ/p/8178950.html

分支界限法

与贪婪算法一样，这种方法也是用来为组合优化问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，所设计出来的算法虽其时间复杂度比贪婪算法高，但它的优点是与穷举法类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过限界，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝），故它比穷举法效率更高。

例子：
N皇后问题
括号生成

概率算法

例子：
数值随机化算法
蒙特卡罗(Monte Carlo)算法
拉斯维加斯(Las Vegas)算法
舍伍德(Sherwood)算法

https://zhuanlan.zhihu.com/p/42619498

[noogel]

51. N皇后

题目

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

思路

...

解题

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SolveNQueens {
    public static void main(String[] args) {
        SolveNQueens queens = new SolveNQueens();
        System.out.println(queens.solveNQueens(5));
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> resp = new ArrayList<>();
        Set<Integer> cols = new HashSet<>();
        Set<Integer> pie = new HashSet<>();
        Set<Integer> na = new HashSet<>();
        dfs(n, 0, new ArrayList<>(), resp, cols, pie, na);
        return resp;
    }

    public void dfs(int max, int row, List<String> curState, List<List<String>> resp,
                    Set<Integer> cols, Set<Integer> pie, Set<Integer> na) {
        // 终结条件
        if (row >= max) {
            if (curState.size() == max) {
                resp.add(curState);
            }
            return;
        }
        // 循环列
        for (int col = 0; col < max; col++) {
            if (cols.contains(col) || pie.contains(row + col) || na.contains(row - col)) {
                continue;
            }
            cols.add(col);
            pie.add(row + col);
            na.add(row - col);
            curState.add(trans(col, max));
            int size = curState.size();
            List<String> newState = (max - row == 1) ? new ArrayList<String>() {{
                addAll(curState);
            }} : curState;
            // 递归层
            dfs(max, row + 1, newState, resp, cols, pie, na);
            cols.remove(col);
            pie.remove(row + col);
            na.remove(row - col);
            curState.remove(size - 1);
        }
    }

    public String trans(int point, int max) {
        char[] chars = new char[max];
        for (int i = 0; i < max; i++) {
            chars[i] = i == point ? 'Q' : '.';
        }
        return String.valueOf(chars);
    }
}

[noogel]

22. 括号生成

题目

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[---
title: 51. N皇后
date: 2019-08-20
tags: [算法, leetcode]
id: 1
---
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路

根据递归做暴力处理，同时进行剪枝操作。

解答

import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis {
    public static void main(String[] args) {
        GenerateParenthesis obj = new GenerateParenthesis();
        List<String> stringList = obj.generateParenthesis(3);
        System.out.println(stringList);
    }

    public List<String> generateParenthesis(int n) {
        List<String> collect = new ArrayList<>();
        gen(collect, "", n, n);
        return collect;
    }

    public void gen(List<String> collect, String cur, int left, int right) {
        if (left == 0 && right == 0) {
            collect.add(cur);
            return;
        }
        if (left > 0) {
            gen(collect, cur + "(", left - 1, right);
        }
        if (right > 0 && right > left) {
            gen(collect, cur + ")", left, right - 1);
        }
    }
}

[noogel]

208. 实现 Trie (前缀树)

题目

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

分析

前缀树
Trie
字典树

解答

public class Trie {
    private final int SIZE = 26;
    private Node root;

    private class Node {
        private boolean isStr;
        private int num;
        private Node[] child;

        public Node() {
            child = new Node[SIZE];
            isStr = false;
            num = 1;
        }
    }

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        if (null == word || word.isEmpty()) {
            return;
        }
        Node pNode = this.root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (pNode.child[index] == null) {
                Node tmp = new Node();
                pNode.child[index] = tmp;
            } else {
                pNode.child[index].num++;
            }
            pNode = pNode.child[index];
        }
        pNode.isStr = true;
    }

    public boolean search(String word) {
        if (null == word || word.isEmpty()) {
            return false;
        }
        Node pNode = this.root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (pNode.child[index] == null || (word.length() - i == 1 && pNode.child[index].isStr == false)) {
                return false;
            }
            pNode = pNode.child[index];
        }
        return true;
    }

    public boolean startsWith(String prefix) {
        if (null == prefix || prefix.isEmpty()) {
            return false;
        }
        Node pNode = this.root;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if (pNode.child[index] == null) {
                return false;
            }
            pNode = pNode.child[index];
        }
        return true;
    }
}