## LEETCODE常见算法之二分查找超详细白话讲解

1. 基础版本：查找数组中某个数值的下标。
2. 查找第一个大于等于（小于等于）某个数的下标
3. 查找第一个大于（小于）某个数的下标

```public int binarySearch(int[] a, int target) {
int low = 0;
int high = a.length - 1;
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
if (target == a[mid]) {
return mid;
} else if (target < a[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
```

```public int firstGreatOrEqual(int[] a, int target) {
int low = 0;
int high = a.length - 1;
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
// 这里大于和等于属于同一种情况
if (a[mid] >= target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
// 返回值要做越界判断
return low < a.length ? low : -1;
}
```

```public int firstSmallOrEqual(int[] a, int target) {
int low = 0;
int high = a.length - 1;
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid] <= target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return high >=0 ? high : -1;
}
```

```public int firstGreat(int[] a, int target) {
int low = 0;
int high = a.length - 1;
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return low < a.length ? low : -1;
}
```

```public int firstSmall(int[] a, int target) {
int low = 0;
int high = a.length - 1;
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return high >=0 ? high : -1;
}
```

1. 无论什么情况下，二分查找的循环条件都是low<=high
2. 当mid指向的值大于或者大于等于target时，我们需要减小mid，二分区间应变为low到mid-1，反之，二分区间变为mid+1到high。
3. 当求某个特定值target的位置时，判断条件存在大于，等于，小于三个分支。若求大于等于某个target，或者小于某个target时，大于和等于属于一个分支，小于属于另一个分支。若求小于等于某个target，或者大于某个target时，小于和等于属于一个分支，而大于属于另一个分支。
4. 当求某个特定值target的位置时，mid是最终解。当求大于或者大于等于target时，low是最终解，求小于或者小于等于target时，high是最终解。另外注意high与low超出数组边界时，代表没有找到符合条件的元素。

LEETCODE 69. Sqrt(x)

x 的平方根

```public int mySqrt(int x) {
if(x<=1) return x;
long low=1,high=x;
while(low<=high){
long mid=(low+high)/2;
long n=mid*mid;
if(n<=x){
low=mid+1;
}else{
high=mid-1;
}
}
return high>=0?(int)high:-1;
}
```

1. 首先我们使用第一类二分方法，返回数组中等于target值的任意下标，如果返回值为-1，说明数组中不存该值。否则数组中存在target。
2. 找到第一个大于等于target的下标start。
3. 找到第一个小于等于target的下标end。
4. start到end区间即是target所在的范围。

## LEETCODE 1352. Product of the Last K Numbers 解题思路分析

• 将数字 `num` 添加到当前数字列表的最后面。

getProduct(int k)

• 返回当前数字列表中，最后 `k` 个数字的乘积。
• 你可以假设当前列表中始终 至少 包含 `k` 个数字。

## LEETCODE 1354. Construct Target Array With Multiple Sums 解题思路分析

• 令 x 为你数组里所有元素的和
• 选择满足 0 <= i < target.size 的任意下标 i ，并让 A 数组里下标为 i 处的值为 x 。
• 你可以重复该过程任意次

## LEETCODE常见算法之广度优先搜索BFS超详细白话讲解

• 遍历树结构
• 遍历图结构
• 遍历二维数组

`输入：root = [1,2,3,4,5,null,6,7,null,null,null,null,8]输出：15`

```public int bfs(TreeNode root) {
// 定义bfs用的Queue
// 初始化bfs，将起始节点根节点加入Queue
q.offer(root);
// 如果Queue不为空，一直循环
while(q.size()>0){
// 取得当前Queue中元素个数
int size=q.size();
// 当前行的元素和
int sum = 0;
// 遍历当前行的所有元素（循环size次）
while(size>0){
// 从Queue中取出一个节点元素
TreeNode n =q.poll();
// 当前行元素个数减一
size--;
// 当前元素的值累加至sum
sum+=n.val;
// 如果左子节点不为空，添加至Queue
if(n.left!=null) q.offer(n.left);
// 如果右子节点不为空，添加至Queue
if(n.right!=null) q.offer(n.right);
}
// 如果Queue为空，说明已到最深层，终止bfs，返回当前层的sum
if(q.size()==0) return sum;
}
return 0;
}
```

```public int bfs(TreeNode root) {
q.offer(root);
int deep=0; // 二叉树层数
while(q.size()>0){
int size=q.size();
// bfs循环当前层
while(size>0){
TreeNode n =q.poll();
size--;
if(n.left!=null) q.offer(n.left);
if(n.right!=null) q.offer(n.right);
} // bfs当前层结束
deep++; // 层数加一
}
return deep;
}
```

1. bfs最擅长解决哪一类问题？
2. bfs与dfs的效率哪个更好？

bfs相关题目讲解： https://leetcode.jp/tag/bfs/

## LEETCODE 386. Lexicographical Numbers 解题思路分析

ls： 以字符串的格式输入一个路径。如果它是一个文件的路径，那么函数返回一个列表，仅包含这个文件的名字。如果它是一个文件夹的的路径，那么返回该 文件夹内 的所有文件和子文件夹的名字。你的返回结果（包括文件和子文件夹）应该按字典序排列。

mkdir：输入一个当前不存在的 文件夹路径 ，你需要根据路径名创建一个新的文件夹。如果有上层文件夹路径不存在，那么你也应该将它们全部创建。这个函数的返回类型为 void 。

addContentToFile： 输入字符串形式的 文件路径 和 文件内容 。如果文件不存在，你需要创建包含给定文件内容的文件。如果文件已经存在，那么你需要将给定的文件内容 追加 在原本内容的后面。这个函数的返回类型为 void 。

readContentFromFile： 输入 文件路径 ，以字符串形式返回该文件的 内容 。

## LEETCODE常见算法之深度优先搜索DFS超详细白话讲解(下)

```输入: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]

1. 题目给出了矩阵上每一点的值，而二叉树问题我们开始只能看到根节点。
2. 二叉树在进行DFS递归时，最多只存在2个子节点分叉，而本题，矩阵上的每一点最多可以向四个方向进发，也就是说会出现4个分叉（有些更复杂的题目会出现更多的分叉）。
3. 二叉树上的每一个点虽然存在0-2个子节点，但它的上一层父节点只有一个。而在矩阵中的每个点，不仅存在多个子节点，还有可能存在多个父节点（从多个节点到达当前节点）。
4. 二叉树的每条路径不存在回路，但矩阵上每个点都可以向四个方向进发，这样一定会出现回路。

```void dfs(Node node){
// 遇到叶子节点，递归终止
if(node.left==null&&node.right==null) return;
// 如果存在左子节点，dfs至左子节点
if(node.left!=null) dfs(node.left);
// 如果存在右子节点，dfs至右子节点
if(node.right!=null) dfs(node.right);
}
```

```boolean[][] visited = new boolean[][];
```

```void dfs(int row, int col){
// 遇到访问过的点，递归终止
if(visited[row][col]) return;
// 将当前点设置为已访问
visited[row][col]=true;
if(row+1<matrix.length){ // 如果下方没越界
dfs(row+1, col); // 向下移动一格
}
if(row-1>=0){ // 如果上方没越界
dfs(row-1, col); // 向上移动一格
}
if(col+1<matrix[0].length){ // 如果右方没越界
dfs(row, col+1); // 向右移动一格
}
if(col-1>=0){ // 如果左方没越界
dfs(row, col-1); // 向左移动一格
}
}
```

```void dfs(int row, int col){
// 遇到访问过的点，递归终止
if(visited[row][col]) return;
// 将当前点设置为已访问
visited[row][col]=true;
if(row+1<matrix.length){ // 如果下方没越界
dfs(row+1, col); // 向下移动一格
}
if(row-1>=0){ // 如果上方没越界
dfs(row-1, col); // 向上移动一格
}
if(col+1<matrix[0].length){ // 如果右方没越界
dfs(row, col+1); // 向右移动一格
}
if(col-1>=0){ // 如果左方没越界
dfs(row, col-1); // 向左移动一格
}
// 还原当前点的访问状态，设置为未访问
visited[row][col]=false; // 添加这一行即可
}
```

1. 由于起点不确定，因此我们需要以每一个点为起点做dfs路径搜索。
2. dfs递归时，我们向4个方向前进时，要判断下一个点的值是否要大于当前点，只有符合条件的方向才能继续向下dfs。
3. 记忆数组。

LEETCODE常见算法之动态规划DP超详细白话讲解(上)