深度优先搜索和广度优先搜索广泛运用于树和图中，但是它们的应用远远不止如此。

BFS

广度优先搜索一层一层地进行遍历，每层遍历都以上一层遍历的结果作为起点，遍历一个距离能访问到的所有节点。需要注意的是，遍历过的节点不能再次被遍历。

第一层：

• 0 -> {6,2,1,5}

第二层：

• 6 -> {4}
• 2 -> {}
• 1 -> {}
• 5 -> {3}

第三

1. 给表达式加括号

241. Different Ways to Add Parentheses (Medium)

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output : [0, 2]

public List<Integer> diffWaysToCompute(String input) {
    List<Intege

正常实现

Input : [1,2,3,4,5]
key : 3
return the index : 2

public int binarySearch(int[] nums, int key) {
    int l = 0, h = nums.length - 1;
    while (l <= h) {
        int m = l + (h - l) / 2;
   

保证每次操作都是局部最优的，并且最后得到的结果是全局最优的。

1. 分配饼干

455. Assign Cookies (Easy)

Input: [1,2], [1,2,3]
Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.

快速选择

用于求解 Kth Element 问题，也就是第 K 个元素的问题。

可以使用快速排序的 partition() 进行实现。需要先打乱数组，否则最坏情况下时间复杂度为 O(N²)。

堆

用于求解 TopK Elements 问题，也就是 K 个最小元素的问题。可以维护一个大小为 K 的最小堆，最小堆中的元素就是最小元素。最小堆需要使用大顶堆来实现，大顶堆表

双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。

1. 有序数组的 Two Sum

Leetcode ：167. Two Sum II - Input array is sorted (Easy)

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

题目描述：在有序数组中找出两个

60. n 个骰子的点数

Lintcode

题目描述

把 n 个骰子仍在地上，求点数和为 s 的概率。

解题思路

动态规划

使用一个二维数组 dp 存储点数出现的次数，其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。

空间复杂度：O(N²)

public List<Map.Entry<Integer, Double>> dic

50. 第一个只出现一次的字符位置

NowCoder

题目描述

在一个字符串中找到第一个只出现一次的字符，并返回它的位置。

Input: abacc
Output: b

解题思路

最直观的解法是使用 HashMap 对出现次数进行统计，但是考虑到要统计的字符范围有限，因此可以使用整型数组代替 HashMap，从而将空间复杂度由 O(N) 降低为 O(1)。

pub

40. 最小的 K 个数

NowCoder

解题思路

快速选择

• 复杂度：O(N) + O(1)
• 只有当允许修改数组元素时才可以使用

快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。可以利用这个特性找出数组的第 K 个元

30. 包含 min 函数的栈

NowCoder

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的 min 函数。

解题思路

private Stack<Integer> dataStack = new Stack<>();
private Stack<Integer> minStack = new Stack<>();

public void