算法笔记（持续更新）

循环数组 —— RingBuffer

在使用循环数组实现双向队列时，需要注意以下几点：

为了避免队列满时的条件与队列空时的条件相同，数组的大小 Capacity 为队列的大小加1
front 变量指向队头元素的索引，rear 变量指向下一个队尾元素将被放置的索引
队列为空条件为 front == rear，队列为满条件为 front == (rear + 1) mod Capacity
入队头时，如果队列为空则按照入队尾处理，反之则向前修改 front 索引再放入元素
入队尾时先放入元素，再向后修改 rear 索引

使用循环数组相较于使用双向链表具有更好的空间局部性以及节省空间

01BFS

5-29周赛最后一题需要求出到达角落需要移除障碍物的最小数目，这题的核心在于将经过障碍物的代价看作是1，将经过普通空格的代价看作是0，从而将原题转化为求到达角落的最短路径

在具体实现中主要有如下两点：

基于BFS进行遍历并使用一个二维数组记录下到达每个点的最短路径，在适当情况下进一步松弛对应的路径并更新队列（类似Dijk算法只有被松弛了的节点才有加入队列的价值）
使用双向队列替代优先队列，被松弛的节点如果是阻碍节点则加到队尾，反之加到队头

前缀和的前缀和

前缀和可以用来快速计算某个区间内各个元素的和，比如[i, j]区间内元素的和就等于s[j+1] - s[i]，而前缀和的前缀和则可以用来快速计算某个区间内各个子区间的和的和

设区间为[l, r]，在求所有包含了下标为i的元素的子区间的和之和的时候就可以使用上述技巧：

线段树

线段树中每个非叶子节点记录的是区间内元素的统计值，叶子节点存储的就是元素本身，另外还记录了自身区间的左右边界以及左右子树，子树一般都从当前区间的中间一半动态开点，线段树大致如下图所示：

线段树的使用场景就是，对于给定区间，进行更新区间和查询区间操作：

更新区间：更新区间中的一个元素或者一个区间的值。
查询区间：查询一个区间[i, j]的最大值、最小值、或者区间的数字和等统计值。

线段树的优点就是把两个操作的时间复杂度降到了O(logn)，另外线段树可以通过增加add懒标记字段的方式延迟更新子树的数据直到访问到对应子树，对应代码模板如下：

    class Node {
        Node left; Node right;
        int start; int end;
        int val; int add;

        public Node(int start, int end) {
            this.start = start;
            this.end = end;
        }

        public void update(int start, int end, int val) {
            if (start <= this.start && this.end <= end) {
                this.val = val;
                this.add = val;
                return;
            }
            pushDown();
            int mid = this.start + this.end >> 1;
            if (end <= mid) {
                this.left.update(start, end, val);
            }
            else if (start >= mid+1) {
                this.right.update(start, end, val);
            } 
            else {
                this.left.update(start, end, val);
                this.right.update(start, end, val);
            }
            pushUp();
        }

        private void pushDown() {
            int mid = this.start + this.end >> 1;
            if (this.left == null) {
                this.left = new Node(start, mid);
            }
            if (this.right == null) {
                this.right = new Node(mid+1, end);
            }
            if (this.add == 0) {
                return;
            }
            this.left.val = this.add; this.left.add = this.add;
            this.right.val = this.add; this.right.add = this.add;
            this.add = 0;
        }

        private void pushUp() {
            this.val = Math.max(this.left.val, this.right.val);
        }

        public int query(int start, int end) {
            if (start <= this.start && this.end <= end) {
                return this.val;
            }
            pushDown();
            int mid = this.start + this.end >> 1;
            int res = 0;
            if (start <= mid) {
                res = this.left.query(start, end);
            }
            if (end >= mid+1) {
                res = Math.max(res, this.right.query(start, end));
            }
            return res;
        }
    }

记忆化搜索

当使用DFS或者回溯超时的时候，可以考虑使用一个Map记录一下每个状态的结果并快速返回，这样有可能可以不超时

水塘抽样

题目描述：给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。

解法：遍历 nums，当我们第 i 次遇到值为target 的元素时，随机选择区间 [0,i)内的一个整数，如果其等于 0，则将返回值置为该元素的下标，否则返回值不变，可以证明重复元素数字的每个索引成为最终返回值的概率均为1 / k：

最大连续1的个数

该题大致描述如下：在二进制数中，可以最多反转k个0使其变为1，求最大连续1的个数。

由于最终结果的最大连续1必定是一个区间也即一个窗口，因此考虑采用滑动窗口的方式去做，在实现过程中，核心在于维护一个窗口中已经反转数的数量的变量，当该变量超过k时，则收缩窗口并将原来反转的数取消反转直到该变量小于等于k，并且在每次迭代结束都去更新一下最大连续1的个数。

快速幂

在只能使用乘法的情况下去实现幂，一种简单的方式是基于递归来实现，这里不再赘述，另外一种是使用循环的方式去实现，其核心在于将指数看作是二进制数，以5 ^ 11为例，此时将11看作二进制数则11 = 二进制(1011) = 1*(2^3) + 0*(2^2) + 1*(2^1) + 1*(2^0)，再将其原表达式展开可得5 ^ 11 = 5 ^ (1*(2^3) + 0*(2^2) + 1*(2^1) + 1*(2^0)) = (5^8)^1 * (5^4)^0 * (5^2)^1 * (5^1)^1，可以看出底数分别是5的二指数次幂，而至于对应的底数是否会被选择，取决于指数中对应的二进制数是否为1，因此使用循环去实现快速幂(此处底数和指数都是正整数)：

public double pow(double a, double b) {
    double res = 1;
    while (b != 0) {
        if (b % 2 == 1) {
            res *= a;
        }
        a *= a;
        b >>= 1;
    }
    return res;
}

另外一个与快速幂类似的就是快速乘了，对于快速乘只需要将乘法替换为加法就可以了，原理一致，此处不再赘述。

搜索旋转排序数组

搜索旋转排序数组也可以使用与搜索排序数组类似的二分法进行搜索，其核心在于另外将nums[0]作为比较目标，因为nums[0]的大小划分了是左侧上升区域还是右侧上升区域，左侧上升区域的值都大于等于nums[0]，反之则小于nums[0]，因此在每次二分的时候，除了比对nums[mid]和target，同时还要比对nums[mid]和nums[0]以及target和nums[0]来判断mid对应的数和target在不在同一个区域

差分数组

差分数组是用来记录相邻元素之间差值的数组，其定义如下：diff[i] = nums[i] - nums[i-1]，当求某个元素nums[i]只需要基于差分数组进行累加即可：nums[i] = BASE + diff[0] + diff[1] + ... + diff[i]，其中BASE一般为0因此也可以视作：nums[i] = sum(diff[j]) 0 <= j <= i

差分数组往往用在区间更新且写多读少的情况情况，比如对于区间[1, 10]中的元素都减去2的一个更新操作，那么相较于去更新每一个元素，使用差分数组只需要更新diff[1]-=2以及diff[10]+=2即可

Top K

TopK可以使用快排的Partition方法实现（排序需要从大到小），在该方法中，个人更喜欢使用单指针 + 顺序遍历的方式去实现，其核心在于在交换指针之前的数必然是小于等于目标数的，但是指针指向的数并不是一定大于等于目标数的（因此会有原地交换的情况），当顺序遍历到小于等于目标数的时候，则将指针对应的数和遍历到的数进行替换，然后指针向后顺延一位，在算法开始的时候，交换指针与遍历指针是重叠的，此时则会原地交换，当遍历结束后，注意需要将交换指针指向的前一个数和目标数进行交换

另外在海量数据的情况下，Top K更倾向于使用堆去实现，这里需要注意的是最大的Top K时使用小根堆，最小的Top K时使用大根堆1

状态压缩

最近在美团周赛的最后一题中用到了状态压缩的技巧，这里将该技巧记录如下：状态压缩其实就是把某个状态（往往是一种方案），使用二进制数（“压缩”到这个二进制数中，有时候也会使用三进制数等其他进制）来表示和操作，从而降低比较两个方案是否相同的复杂度，其中往往会用到二进制中的与、或、取反、移位等操作，以旅行商问题为例，可以将当前到过的城市的状态定义为一个二进制数01101101，其中1代表到达某个城市，0代表没有到达某个城市(比较两个已到达城市集合需要O(n)时间复杂度，但是比较两个二进制数只需要O(1)），相较于暴力搜索(n-1)!的时间复杂度，通过状态压缩结合dp可以直接复用一些重复子问题，从而将时间复杂度降低到O((2 ^ n) * (n ^ 2))

对角线映射

在需要快速判断某个点的对角线上是否已经有了其他点的时候，可以基于对角线斜率为1或-1的特性推导出该对角线上的所有点都满足表达式x + y = C 或 x - y = C，其中C为常值，因此可以对于每个点都计算其x + y 以及 x - y的值并记录到HashSet中，如果在HashSet中有对应的值已经存在则可以快速判断该点的对角线上已经存在了其他值

单调栈

单调栈往往用在求每一个元素离它最近的较大或较小元素时，通过单调栈可以在O(n)时间内解决上述问题，每个元素最多被遍历两次

其诀窍在于：求较小元素时使用单调递增栈，求较大元素时使用单调递减栈

其核心在于：在栈中的元素都不可能是彼此的解也不会影响彼此

举例如下：要求下一个较小的元素时需要使用递增栈，递增栈中的元素必然都是每一个都比上一个大，因此在同一个栈中的元素必然不可能是下一个较小元素，当较小元素出现时，大于该元素的栈中元素则都找到了对应的下一个较小元素，出栈并记录，最后再把新元素放入即可，对于仍然在栈中的元素而言，出栈了的元素本来就都比它们大，因此对它们并无影响

约瑟夫环问题

约瑟夫环问题的原来描述为，设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。稍微简化一下问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

一方面约瑟夫环问题可以通过使用链表模拟实现，另一方面约瑟夫环问题也可以通过找出数学递推公式然后结合递归进行实现，其数学推导如下：

1. 一开始队列如下：0, 1, 2, 3, ..., n-1
2. 不妨设第一轮取出了第m-1个元素，此时队列如下：0,      1,       2, ...,    m-2,    m, m+1, m + 2, ... ,n-1
3. 此时将下标为m的元素，视作新队列的第一个元素，并顺序映射得到新的长度为n-1的队列，此时在新队列中下标为i的元素，对应于原队列中下标为(i + m) % n 的元素
4. 不妨设在新队列中的解为x = f(n-1)，此时可以得到该值在原队列中的解为：f(n) = (f(n-1) + m) % n
5. 同理可得：f(n-1) = (f(n-2) + m) % (n-1), ..., f [ i ] = ( f [i -1] + m) % i, ..., f(1) = 0
6. 针对上述的递推公式，基于递归即可得到答案

p.s. 上述的数字皆为队列中每个元素的下标而非元素本身，该类型问题的核心就是找出f(i) 和 f(i-1)之间的映射，也即如何把原队列在经过了1次操作之后再重新转换成一个可以直接递归的新队列，然后寻找元素下标之间的映射关系！

KMP算法

KMP算法用来在O(m + n)时间复杂度内解决字符串匹配的问题，KMP算法的核心在于以下两点：

KMP 利用已匹配部分中相同的「前缀」和「后缀」来加速下一次的匹配：使用双指针构造Next数组，对于Target字符串的任意一个位置而言，由该位置发起的下一个匹配点位置其实与Source字符串无关
KMP 的原串指针不会进行回溯（没有朴素匹配中回到下一个「发起点」的过程）：如果Target字符串的当前字符i不和Source字符串的当前字符j匹配的话，会通过Next数组去匹配Source字符串中的向前有重复关系的另外一个字符k，如果都没有匹配的话，那么可以保证[0, i]范围内的字符都不可能成为Source的首字符，因此可以直接从i + 1开始重新匹配而不必回溯到原来的发起点的位置了

KMP的算法模板如下：

    public int strStr(String ss, String pp) {
        if (pp.isEmpty()) return 0;
        
        // 分别读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串前面都加空格，使其下标从 1 开始
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        int[] next = new int[m + 1];
        // 双指针构造Next数组过
        // i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 2, j = 0; i <= m; i++) {
            // 匹配不成功的话，j = next(j)
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++
            if (p[i] == p[j + 1]) j++;
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }


        // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 1, j = 0; i <= n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配成功，直接返回下标
            if (j == m) return i - m;
        }

        return -1;
    }

拓扑排序

拓扑排序往往都是基于BFS + 队列实现的，其中有个小技巧是另外通过一个数组去记录所有节点的入度，这样便可以无需遍历图就能找到下一个在剔除了当前节点之后入度为0的节点了，从而可以在O(1)时间复杂度入队列，另外由于是拓扑排序遍历，因此可以认为所有被遍历过的节点，都已经是处理过了的节点了，也即在它看来它已经是最优的了，所以在有关系传递的情况下，当前节点只需要和它的所有父节点比较即可，而无需和祖先节点比较。

拓扑排序遍历的伪代码如下：

Queue<Integer> q = new LinkedList<>();
for (int i=0; i<in.length; ++i) {
    if (in[i] == 0) {
        q.offer(i);
    }
}
while (!q.isEmpty()) {
    int node = q.poll();
    /*
    * 这里会对当前节点做一些逻辑处理
    */
    for (int i=0; i<num; ++i) {
        if (graph[node][i]) {        
            /*
            * 这里会对后继节点做一些逻辑处理
            */
            if (--in[i] == 0) q.offer(i);
        }
    }
}

DP回溯

DP一般都是用来求最优解的，但是如果在题目中问到最优解是如何组成的情况下就需要通过DP回溯来一步一步你推找到最优解的组成了，其实DP回溯很简单，其核心就是从最优解所在的DP值开始，结合DP的状态转移公式来判断做了什么选择，也即根据DP的状态转移公式遍历所有的上一个可能状态，然后找出导致了当前状态的上一个状态是什么也就找出了对应的选择是什么，通过上述方式递归回溯到初始状态也就可以知道最优解的组成了。

多路归并

多路归并的核心在于使用一个最小堆（优先级队列）实现多路归并，在算法开始的时候最小堆中存了所有链表的头节点，然后每次拿出其中最小的那一个节点，因为每条链表本身是递增的，因此可以保证最小堆中最小的节点也是全局最小的节点，在获得了最小的节点之后再将该节点之后的节点（链表新的头节点）入队，重复上述过程直到最小堆被拿空则完成了对应的多路归并，整体复杂度为O(Log(K)*n)，多路归并可以用来是完成:

LeetCode的第786题——第K个最小的素数分数：把每个分母看作是一个递增的分数列表，然后进行K次多路合并即可
LeetCode的第23题——合并K个有序链表：模板题

快速寻找最接近的2次幂（扩容）

在非常多的算法中，为了追求性能，在取余时使用&取代%，而这样做的前提是对应的base应该是2的幂也即2^n，因此许多扩容操作都是基于2次幂来进行的，对应的快速寻找最接近的2次幂算法如下：

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

其思路类似快速乘和快速幂因为每次右移的都是自身，所以对于任何一个为1的位而言，第一次可以向右扩展为2个1，第二次4个1，第三次8个1...一直到从开始第一个为1的最高位到最低位都是1，此时再加1即可得到最接近的2次幂

猜数字、砸鸡蛋等问题

这些问题看似是一个二分搜索问题，但是其实是一个二维dp，因为并不是要求最少次数猜中，而是最少代价猜中（其中猜中代价为每次猜都要花猜的数对应的或者楼数对应的钱钱）,核心如下：

二维DP状态，分别为猜的数的下限和上限
每次猜必定会猜错，并且承受最大的代价（最小最大代价）

由此dp状态转移公式如下：

dp[i][j] = Math.min{k + Math.max(dp[i][k-1], dp[k+1][j])} (k: i, i+1, ..., j)

解释如下：猜测范围在从i到j的数字的最小代价等于分别猜i, i+1, .., j然后承受猜错了之后需要承受最大代价的情况下的代价最小的情况

K个逆序对数组

题目如下：给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。

逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a[i] > a[j]，则其为一个逆序对；否则不是。

很容易想到基于DP的解法，定义dp[n][k]为在数1…n的情况下有k个逆序对的情况数量，由于将第n个数插入由1…n-1构成的数组共有n种情况（分别放在index分别为0…n的地方），又由于第n个数大于1…n-1，因此每种情况增加的逆序对数都是固定的，分别是：n-1, n-2, … , 0，因此可以得到递推公式如下：

dp[n][k]=dp[n-1][k]+dp[n-1][k-1]+…+dp[n][k-n+1]

但是这样会导致超时，因为时间复杂度为O(nnk)，此时可以换个角度从列与列的角度观察dp[n][k]和dp[n][k-1]的递推公式的关系来进行前缀和优化：

dp[n][k]=dp[n-1][k]+dp[n-1][k-1]+…+dp[n][k-n+1]
dp[n][k-1]=dp[n-1][k-1]+dp[n-1][k-2]+…+dp[n][k-n]

可得：

dp[n][k]=dp[n][k-1]+dp[n-1][k]-dp[n][k-n]

此时时间复杂度为O(n*k)

另外由于结果数字很大，需要转换成取余的数，因此在处理mod的时候，对于每一个值判断如下：if (dp[i][j] >= mod) dp[i][j] -= mod，另外由于dp[i][j]的计算中涉及到减法，因此dp[i][j]可能会小于零（被减数被mod了但是减数没有被mod），所以还需要一个判断如下：if (dp[i][j] < 0) dp[i][j] += mod

另外一道已知一个序列求逆序对数量的题可以基于MergeSort在Merge的时候额外记录逆序对的数量以O(n * log(n))时间复杂度实现

接雨水问题

接雨水问题的核心在于两点：

木桶效应：如果当前点的高度高于木桶中最低的那块木板，那么对于当前点来说它必定接不到雨水，但是可以用它来替代木桶中最低的那块木板，形成新的木桶；反之，它能且只能接到木桶中最低的那块木板减去当前点高度的雨水，此时木桶中中最低的木板的高度依然是原来的，但是位置变成了当前点的位置
自外向内：最外侧一圈肯定是接不到雨水的，因此它们形成最初的木桶，并且每次挑选出木桶中最低的那块木板（使用优先队列），对它的周围（上下左右）进行遍历计算，并生成新的木桶

正则表达式匹配

正则表达式匹配的核心在于动态规划中对于*号的处理上当遇到*号的时候，需要拿出模式中的上一位的字符c1去和字符串当前的字符c2作比较，其中i代表模式的当前索引，j代表字符串的当前索引

c1 == c2时（如果c1=='.'的话肯定相同），则dp[i][j] = dp[i-2][j] || dp[i][j-1]
c1 != c2时，dp[i][j] = dp[i-2][j]

另外注意需要对于abc*这样的模式进行预处理使得dp[0][0]=dp[2][0]=dp[4][0]=dp[6][0]=true

带重复数字的全排列

大致思路和不带重复数字的全排列一样，采用回溯就可以解决了，至于如何解决重复数字，则先通过排序将所有的重复数字放到一起，然后将同一个重复数字按照先后顺序编上号，如：111则看作1_0,1_1,1_2，从而转化为不同的数字，然后在回溯的时候保证编号顺序不能发生变化即可，也即：1_0一定在1_1的前面，1_1一定在1_2的前面，也就是说当排列编号较大的数字的时，编号较小的数字一定已经排列好了，具体实现使用如下表达式即可：if ((i > 0 && !vis[i - 1] && nums[i] == nums[i - 1]) continue;

用Rand7实现Rand10

对于RandN而言，如果要用它实现Rand(N-x)，那么只要简单地一直调用RandN一直到出现小于等于（N-x）的数就可以了，由无限等比数列结合概率可以证明该算法下Rand(N-x)中各个数的比例是一样的都等于1 / (N-x)，如果要用它实现Rand(N+x)，则只要将N等比例放大到NN大于(N+x)再结合刚刚的算法就可以了（此时具体算法可以通过取余优化），扩大到NN的算法可以通过RanN + N * (RandN - 1)实现，也就是1到N*N只有一种组合方式

求众数

算法大致思路如下：以n个数为一组进行迭代，并在每轮迭代开始的时候将这n个数加入map中并设置对应的count加一，在每轮迭代结束的时候对于map中记录的每个数对应的count减一，如果count为0则从map中移除，若当前轮元素不满n个，则不做减一移除操作，在完成了迭代之后，将还在map中的key作为候选者再次代入原数组计算出现次数即可

算法原理：1. 如果一个数是众数，那么平摊下来在每个以n个数为一组的组中至少出现1次，且至少得有个组中出现2次，所以当计数归零时，该数肯定不可能是候选者 2. 每轮迭代结束相当于将n个数为一组的组丢弃并重新计算计数，另外每n个数的组丢弃并不影响候选人的选拔

前缀树

前缀树中每个节点都会有一个大小为26（26个英文字母）的child数组，同时使用一个类型为boolean的字段标识当前节点是否是某个单词的末尾

    private class TrieNode {
        TrieNode[] child = new TrieNode[26];
        boolean isWord = false;
    }

前缀树的核心在于，它的节点只对应状态（当前节点是否是某个单词的末尾），它的边才对应单词中的字母

折半查找

当发现数据集并不大，但是直接暴力搜索会TLE的时候，可以考虑将数据集分成大小相同的两份，然后在每份数据集上进行暴力搜索枚举，最后再将两份数据集的结果合并起来

在具体实现中一般都会对于第一份数据集暴力枚举之后的结果进行排序，然后第二份数据集在暴力枚举的过程中对于每个结果都在第一份数据集上进行二分搜索找到最接近的值然后相减即可

一般折半查找的题往往需要对于原题目进行转换，如LeetCode-2035，需要先将题目转换成给原数组的每个元素插入总数量相同正负符号使得加和sum最小，然后再转化为加和也等于前一半的和减去后一半的和负数，因此使得前一半的正符号数量和后一半的正符号数量相等即可，最后再基于折半查找和二分搜索就可以了

二分搜索

二分搜索核心点在于关注左边界left和右边界right的定义以及target就在左右区间里：

如果是左闭右开，则对应的终止条件为left == right
如果是左闭右闭，则对应的终止条件为left > right

为了便于理解，一般采用左闭右开的定义, 二分搜索的模板如下：

while(left < right) {
    int mid = (left + right) / 2;
    if (num[left] == target) {
        // 通过向左压缩寻找左边界 right = mid;
        // 通过向右压缩寻找右边界left = mid + 1;
    }
    else if (num[mid] < target) {
        left = mid + 1;
    }
    else if (num[mid] > target) {
        right = mid;
    }
    return left; // 寻找左边界
    return left - 1; // 寻找右边界 为什么要减一，是因为 left = mid + 1，因此mid =  left - 1
}

基于寻找左边界的二分搜索得到的索引对应的值一定是大于等于target的，因为left的定义就是小于left的值必定是小于target的，而right的定义就是大于等于right的值必定是大于等于target的，当收敛到最后时，left = right，因此此时得到的索引left对应的值根据right的定义一定是大于等于target的同理，基于寻找右边界的二分搜索得到的索引对应的值一定是小于等于target的

回溯和DFS的区别

回溯和DFS本质上都是对树或者图的遍历，只是前者更关注边（选择）而后者更关注节点，因此前者在for循环内部针对边做选择和排错，而后者在for循环外部针对节点做选择和排错