# 数据结构+算法总结

**Repository Path**: WuJinbo1998/DataStructure-AlgorithmSummary

## Basic Information

- **Project Name**: 数据结构+算法总结
- **Description**: Java数据结构 + JavaAPI
一、数据结构声明
二、数据结构/数据类型 转换
三、其他常用API
四、Collection / Map
1. 数组List
2. 栈
3. 队列
4. 集合
5. 哈希表
算法总结
一、方法出发
1. 递归
2. 并查集
3. 动态规划
4. 排序相关
5. 位运算
6. 链表操作
7. 树的操作
8. 快慢指针（双指针）
9. 字典树字符串
10. 前缀和
- **Primary Language**: Java
- **License**: MulanPSL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2022-04-25
- **Last Updated**: 2026-04-16

## Categories & Tags

**Categories**: Uncategorized

**Tags**: 数据结构, 算法

## README

「」
时间复杂度：O(n)，空间复杂度：O(1)

写题之前仔细审题！1. 理解题意 2. 方法选择（根据数据量选择合适的复杂度）3. 数据结构优化

# Java数据结构 + JavaAPI

## 一、数据结构声明

声明时用接口，创建对象时用具体的实现类，方便使用多态

但对于数据结构，声明时最好使用具体实现类，声明为接口，看不到具体的方法，e.g. 声明为Map而创建时使用TreeMap，看不到TreeMap的方法

数组
int[] = new int[];

列表
List<Object> list = new ArrayList<>(); 

栈/双端队列
Deque<Object> deque = new LinkedList<>(); // 元素可以为null
Deque<Object> deque = new ArrayDeque<>(); // 元素不能为null

队列
Queue<Object> queue = new LinkedList<>(); // 元素可以为null
Queue<Object> queue = new ArrayDeque<>(); // 元素不能为null

集合
Set<Object> set = new HashSet<>();

链式集合
Set<Object> set = new LinkedHashSet<>();

有序集合（排序二叉树）
TreeSet<Object> set = new TreeSet<>();

哈希表
Map<K, V> map = new HashMap<>();

链式哈希表
Map<K, V> map = new LinkedHashMap<>();

有序哈希表
TreeMap<K, V> map = new TreeMap<>();

堆（优先队列）
Queue<Object> queue = new PriorityQueue<>(InComparator);

字符串
String s = new String(String/char[]/StringBuilder);
StringBuilder sb = new StringBuilder(String);

## 二、数据结构/数据类型 转换

- Array转List（一般还要放入实现类的构造器中，asList返回的是内部类） 

List<Object> list = new ArrayList<>(Arrays.asList(T..)); 

若传入数组，则返回以数组为基本元素的List

数据类型必须是引用数据类型，不能是基础数据类型，Integer[]才能转为List<Integer>

- List转Array 

Object[] array = list.toArray(new Object[list.size()]);// Object[] array = list.toArray(Object::new);

数据类型必须是引用数据类型，不能是基础数据类型，List<Integer>只能转为Integer[]

- 二维数组List转二维数组Array list.toArray(new int[list.size()][]);

注：二维数组的长度必须相等，不等长数组无法一步到位

- HashMap转Set

Set<Map.Entry<K, V>> entrySet = map.entrySet();

K key = entry.getValue();

V value = entry.getKey();

Set<K> keySet= entry.keySet();

Set<V> valueSet = entry.values();

- String

s.toLowerCase(); //转小写

s.toUpperCase(); //转大写

char[] charArray = s.toCharArray(); 转Array字符数组

String.valueOf();//基本上所有其他类型转String

- StringBuilder

String s = sb.toString();

String s = new String(sb);

- Character

char - '0' 作差求值（char 转 int）

char c = (char)(n+'0');//（int 转 char）

char c = Character.toLowerCase(char); //转小写

char c = Character.toUpperCase(char); //转大写

- Integer

int i = Integer.valueOf(String);//String转int

int ascii = Integer.valueOf(Char);//Char转int 是 转换成对应ASCII码，不同于作差取值 char - '0'

int ascii = Integer.parseInt(String);

## 三、其他常用API

### 1. Collections

Collections.reverse(); //反转

Collections.sort();

Collections.sort(, c);

Collections.swap(, i, j); //交换位置

Collections.max();

Collections.min();

注意：javaAPI的二分查找只要找到符合要求的值就会返回，如果有重复数时，想达到查找第一个大于/小于某值的目的，需要自己手写二分查找

Collections.binarySearch(list, key); //实现comparable接口

Collections.binarySearch(list, key, c); //比较器 c

### 2. Set

Set newSet = Set.copyOf(set); // 得到一个复制的不可变集合，通常用于快照进行遍历，且遍历时需要修改集合内容

### 3. Arrays

Arrays.fill(arr, val); //指定所有元素的值

Arrays.sort(arr);

Arrays.sort(arr, c); // (x, y) -> (x - y) 数组升序 (x, y) -> (y - x) 数组降序 //比较器 c

返回值：若有该key，返回索引 >=0 ；若无，返回负数-(insertion point) - 1

Arrays.equals(int[] a, int[] b);

Arrays.copyOf(arr, length); //返回复制的新数组

Arrays.copyOfRange(arr, from, to); //返回复制的新数组

注意：javaAPI的二分查找只要找到符合要求的值就会返回，如果有重复数时，想达到查找第一个大于/小于某值的目的，需要自己手写二分查找

Arrays.binarySearch(int[] a, int key); //a要升序

Arrays.binarySearch(int[] a, int fromIndex, int toIndex, int key);//前闭后开

### 4. Math

Math.max(,);

Math.min(,);

Math.pow(double a, double b);//a^b

Math.abs(); //取绝对值

Math.round();//整数的四舍五入（可拓展到小数的四舍五入）

### 5. Integer

使用==比较值的大小，如果值在[-128,127]会被cache缓存，超过这个范围则比较的是对象是否相同，> < >= <= 没有歧义，可以直接使用（自动拆箱）。
equals()重写过，比较的是内部value的值，建议判断两个Integer是否相等时使用equals()，e.g. if(queue.peekFirst()==monoqueue.peekFirst())（被坑惨了）
<!-- 或者是将其中一个Integer转为int再与另一个Integer==比较（自动拆箱） -->

32位 最低位记为0，最高位31为符号位，正整数区间为30至0，则最大值为 2^31-1 = 2147483647

Integer.MAX_VALUE 2^31-1 2147483647
                         2147447412
Integer.MIN_VALUE -2^31 -2147483648

（最高位是符号位？）

### 6. String

String类型是引用数据类型，但是因为有字符串常量池，做参数是值的复制（使用时看做是基本数据类型即可）

StringBuilder是引用数据类型，做参数是传递地址

值传递：引用数据类型做方法参数时，在方法里使用new对其赋值，仅仅使当前局部变量指向新开辟的空间，局部变量及其指向的空间会随着方法结束而收回，应当在调用方法前对其new，使用方法改变值

e.g. sb并没有赋上值，仅仅只是当前局部变量指向了堆中一块新开辟的空间，方法结束就收回了
```
StringBuilder sb = new StringBuilder();
method(sb);

void method(StringBuilder sb){
    if(...){
        sb = new StringBuilder(temp);
    }
}
```

正确的方式：
```
StringBuilder sb = new StringBuilder();
method(sb);

void method(StringBuilder sb){
    if(...){
        sb.append(temp);
    }
}
```
s.charAt();

s.length();

s.split(","); 拆分

s.substring(i, j); [i, j) 取子串

s.trim();  去除首尾空格

s.toCharArray(); 转Array字符数组

s.equals(); //比较字符串是否相等，lc上面有时候使用==不对，最好使用equals而不是直接使用==

s.replace(Char/CharSequence target, replacement);

s.indexOf(String str); -1表示没有该子串，>=0表示子串起始位置

s.startsWith(String str); boolean

s.contains(String str); boolean

对于变位词，可考虑将字符串映射成长度为26的数组

String.valueOf(char...);

new String(String/char[]);

s.toLowerCase(); //转小写

s.toUpperCase(); //转大写

String.format("%.2f", f); //保留两位小数（并非四舍五入）

(double)(Math.round(a*100))/100; //四舍五入

- StringBuilder（尽量还是用String吧...）

StringBuilder sb = new StringBuilder(s);

sb.toString();

new String(StringBuilder);

sb.charAt();

sb.length();

sb.append(String/char);

sb.deleteCharAt();

sb.setCharAt(index, char);

sb.reverse(); 反转

没有重写equals()!!

### 7. Character

char - '0' 作差求值（char 转 int）

boolean b = Character.isLetter(char); //是否是字符

boolean b = Character.isDigit(char); //是否是数字

boolean b = Character.isLetterOrDigit(char); //是否是字符或者数字

char c = Character.toLowerCase(char); //转小写

char c = Character.toUpperCase(char); //转大写

(char)(n+'0') int 转 char

### 8. Long

在定义long类型时, 如果数据类型超过int类型的取值范围, 数据后面要加l或L, 不超过则不需要加（会当做是int）

e.g. 0L

### 9. double

Double.MAX_VALUE = 1.7976931348623157E308

Double.MIN_VALUE = 4.9E-324 // 接近0

实际最小值应该使用 - Double.MAX_VALUE // 负数

e.g. 1.0d / 1.0

### 10. Stream 数组相关的流处理

Arrays.stream(T[]); // 数组 转 流 Stream<T> 或 IntStream

(IntStream) stream.sum(); //求和

stream.foreach(函数式接口); //对流中的每个元素做操作

stream.toArray(函数式接口); //基本数据类型数组 转 引用数据类型数组（Integer[] 转 int[] 貌似没有api）

stream.boxed(); // 基本数据类型流 转 包装类流 e.g. IntStream 转 Stream<Integer>

e.g.

Arrays.stream(strs).mapToInt(Integer::parseInt).sum(); //string[] 转 int 求和

Arrays.stream(strs).sorted().map(str->str+" ").forEach(System.out::print); //string[] 排序 加空格 打印

Arrays.stream(data).boxed().toArray(Integer[]::new); // int[] 转 Integer[]

Arrays.stream(array).min().getAsInt(); 求int[]中最小值

### 11. 增强for循环可遍历的结构

数组[], List, Set（并非插入集合的顺序，而是哈希值顺序）

### 12. 数据结构的复制 new

Object det = new Object(src)

### 13. 获取随机值 Random类

```
Random random = new Random();
int pivotIndex = random.nextInt(right - left + 1) + left;// 在前闭后开区间[left, right+1)之间随机选择一个pivot
int pivotIndex = random.nextInt(origin, bound);// 在前闭后开区间[origin, bound)之间随机选择一个pivot

```

### 14. System

System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length) // native 方法，复制数组

### 15. int[]

arr.clone() //复制数组

## 四、Collection / Map

### 1. 数组 / List

实现：List<Object> list = new ArrayList<>(); 

实现：List<Object> list = new LinkedList<>(); 

list.add(ele);

// 插入
list.add(index, ele);

list.get(index);

list.set(index, ele);

list.remove(index);

list.size();

list.clear();

list.contains(ele);

- 二维数组的创建

List<List<E>> list = new ArrayList<>(); 内外层长度不定

List<List<E>> list = new ArrayList<List<E>>(); 

List<int[]> list = new ArrayList<>(); 外层长度不定

List<E>[] list = new ArrayList[n]; 内层长度不定（注意声明方式）

int directions[][] = new int[][]{{1,0},{-1,0},{0,1},{0,-1}}; 

### 2. 栈 

实现：Deque<Object> deque = new LinkedList<>(); // 模拟栈

实现：Stack<Object> stack = new Stack<>(); // 老旧集合类

deque.push(); 压入栈顶 

deque.pop(); 弹出栈顶元素并返回（对应pollFirst()）（调用之前要保证栈不为空，否则抛出异常）

deque.peek(); 返回栈顶元素（对应peekFirst()）（调用之前要保证栈不为空，否则抛出异常）

deque.size();

deque.isEmpty();

### 3. 队列

实现：Queue<Object> queue = new LinkedList<>(); 

queue.offer(); 加入队尾 

queue.poll(); 移除并返回队头 

queue.peek(); 返回队头 

queue.size();

queue.isEmpty();

- 双端队列（单调队列）

实现：
Deque<Object> deque = new LinkedList<>(); // 元素可以为null
Deque<Object> deque = new ArrayDeque<>(); // 元素不能为null

deque.offerFirst(); 队头入队

deque.offerLast(); 队尾入队

deque.peekFirst(); 返回队头元素（对应栈顶元素 peek()）

deque.pollFirst(); 移除并返回队头元素（对应栈顶元素 pop()）

deque.peekLast(); 返回队尾元素

deque.pollLast(); 移除并返回队尾元素

- 堆（优先队列）

实现：PriorityQueue<Object> priorityQueue = new PriorityQueue<>(initialCapacity, InComparator); 或本身实现了Comparable接口

initialCapacity是初始队列容量，而不是队列固定容量

默认小根堆

priorityQueue.offer(); 入队

priorityQueue.peek(); 返回头元素 

priorityQueue.poll(); 移除并返回头元素

(m, n) -> m - n; //顺序作差，小根堆

(m, n) -> n - m; //逆序作差，大根堆

### 4. 集合

实现：Set<Object> set = new HashSet<>();

set.add(index);

set.remove(index); 

set.set(index, ele);

set.contains();

set.hashCode(); //返回此集合的哈希代码值，集合的哈希代码定义为集合中元素的哈希代码之和

- 链式集合

实现：Set<Object> set = new LinkedHashSet<>();

- 有序集合（排序二叉树）

实现：TreeSet<Object> set = new TreeSet<>();

set.add();

set.floor(e); 前一个（小于等于）

set.ceiling(e); 后一个（大于等于）

set.lower(e);（严格小于）

set.higher(e);（严格大于）

set.contains(e);

### 5. 哈希表

实现：Map<K, V> map = new HashMap<>();

map.put(key, value); 

map.putIfAbsent(key, value);

map.get(key);

map.remove(key);

map.containsKey(key);

map.containsValue(value); 

map.getOrDefault(key, 0); 默认值一般为0，多用于计数

map.computeIfAbsent(k, mapping function);

如果指定的键尚未与值关联（或映射为null），则尝试使用给定的mapping函数计算其值，并将其输入此mapping函数，键与此输出关联，返回键值
如果指定的键有值，则返回该值

- 批量初始化
```
Map<K, V> = new HashMap<>(){
    {
        put();
        put();
    }
};
```

- 链式哈希表

实现：Map<K, V> map = new LinkedHashMap<>();

- 有序哈希表

实现：TreeMap<K, V> map = new TreeMap<>();

map.put(k, v);

map.floorKey(k); 前一个（小于等于）

map.ceilingKey(k); 后一个（大于等于）

map.lowerKey(k);（严格小于）

map.higherKey(k);（严格大于）

map.firstKey(); 第一个

map.lastKey(); 最后一个

# 算法总结

## 一、方法出发

### 1. 递归

- dfs：遍历的思想

分治：先分后治，由尾到头合并

递归与动态规划：递归，更适合求完整路径（解决方法）的情况；动态规划，更适合只要求返回是否的情况

前缀和的递归回溯思路：从当前节点反推到根节点(反推比较好理解，正向其实也只有一条)，有且仅有一条路径，因为这是一棵树

操作共享数据的递归，记得在结束递归时还原相关改动

递归时如果涉及非常多的数组index变化，可以考虑使用其他数据结构（比如队列）

递归中多次调用递归时，可以画一下递归树帮助理解

- bfs：遍历的思想（利用辅助队列），更适合求最短路

双向bfs

优先队列bfs

### 2. 并查集

parent数组，长度为节点数，默认为自己

union方法：路径压缩：合并两节点的祖先节点（选择一个为准），不路径压缩则是其中一个节点parent指向另一个节点

find方法：递归找到节点的祖先节点（一直找parent，直到找到parent是自己的节点）

不相交集合数（连通分支数）：parent为自己的节点数

### 3. 动态规划

有点递归（上一状态，下一状态）+ 贪心（状态递推）结合的感觉，但是用递归做复杂度太高

只关心多少种方案，数字能统计的，而不关心具体路径或组成

动态规划的总体思路：找到一个递推关系式（状态转移方程）

每一个dp值有几个状态，就是几元dp

dp一般就用数组，使用容器难免会降低效率

- 尽量减少判断是否存在某状态

e.g. dp[j] += dp[j - num]; dp[j]|=dp[j-num];

- 适当增加dp数组长度

方便处理边界值，e.g. 字符串等场景

- 滚动数组优化空间复杂度（代码可读性会变差）

注意先后顺序

- 二元动态规划（一个状态与两个参数有关）

- 解二元、二层动态规划一定要画图

- 时间复杂度O(n^2)的dp，一般先确定结束位置（范围从头到尾），再确定起始位置（范围从头到结束位置）

内层循环从少到多

#### 背包问题

状态/权重/总额-组合方案数：一般都是先遍历物品

变体：

状态/权重/总额-物品个数

- 1. 01背包

选0或1次

时间复杂度：O(n2)，空间复杂度：O(n)

顺序遍历每个物品，逆序遍历每种状态

- 2. 完全背包

选 0,1,2...+∞ 次

时间复杂度：O(n2)，空间复杂度：O(n)

顺序遍历每个物品，顺序遍历每种状态

顺序遍历每种状态，顺序遍历每个物品（选取顺序不同算不同方案）

- 3. 多重背包

选 0,1,2...s[i] 次

时间复杂度：O(n3)（可二进制优化），空间复杂度：O(n)

顺序遍历每个物品，逆序遍历每种状态，顺序遍历物品对应次数

- 4. 混合背包（1.2.3.的综合）

综合参考3.即可

- 5. 二维费用的01背包问题 O(n3)

时间复杂度：O(n3)，空间复杂度：O(n2)

顺序遍历每个物品，逆序遍历状态1，逆序遍历状态2

- 6. 分组背包

一组物品中选0或1个

时间复杂度：O(n3)，空间复杂度：O(n)

顺序遍历分组，逆序遍历状态，顺序遍历分组中的物品

- 7. 有依赖的背包问题（分组背包+树形dp）

先递归算出子树的每一个体积对应的最大价值，然后进行分组背包

- 8. 背包问题求方案数

在原来01背包的基础上加一个表示方案数的数组即可

- 9. 背包问题求具体方案

注意遍历顺序，输出可行的转移路径

### 4. 排序相关

- 堆 优先队列

要求空间复杂度，则用数组映射到堆树

前k个...的问题（也可利用快排思想）

- 快排范式

选择pivot，一般在区间内随机选择

pivot放首或尾，依次遍历其他元素（一般从头到尾），>（降序）/<（升序）pivot时，交换当前元素与index位置，index++，index始终指向<= / >= pivot的元素，即作为交换位，与>= / <= pivot的元素交换位置，最后记得交换哨兵位上的pivot和index

数据结构学的双指针的快排太复杂了

- 折半查找（二分查找）（双指针）（时间复杂度：O(logn)）

1. while(left < right) if拆分为2或3种情况

2. while(left <= right) if拆分为2或3种情况（一般情况下都用这种就好，涵盖更广的用途）

特殊：剑指Offer 11.旋转数组的最小数字

查找第一个不符合要求(!=target)的数，将条件从left<right改为left<=right，if拆分一般为2种情况

e.g.找到第一个大于target的数（<= left return left）

(nums[mid] > target) right = mid - 1;  (nums[mid] <= target) left = mid + 1; return left;

e.g.找到第一个大于等于target的数（< left return left）

e.g.找到第一个小于target的数（<= right return right）

e.g.找到第一个小于等于target的数（< right return right）

规律总结：大于left 小于right 等于条件不等于

3. 补充：一些结合二分的问题

- 378.有序矩阵中第K小的元素

二维数组中使用二分

二分范围为矩阵中的最小值到最大值，即二分查找进行次数为O(log(max−min))

每次二分，计算小于等于mid的数有多少个，跟k比较，即每次操作时间复杂度为O(n)

- 快速幂范式

计算a·m^n

初始化res=a 每轮：当n为奇数 res*=m，m=m*m，n/=2

### 5. 位运算

见二、运算技巧 位运算

### 6. 链表操作

优先级：迭代 > 递归

dummy node

快慢指针（双指针）

最适合归并排序

### 7. 树的操作

dfs 递归 迭代（1. 循环遍历左，无左则右，2. 右入栈，左入栈，后进先出）

bfs 辅助队列

- 树的序列化

中序 + 先/后序 还原树

带null的先序（String用,隔开，null用None表示） 还原树，再按先序遍历反序列化

带null的层序 还原树

### 8. 快慢指针（双指针）
```
while(condition1){
    ...
    while(condition1){
       尽量避免这种情况！ 
    }
    ...
}
```

链表操作

两数之和

### 9. 字典树字符串

单词组合

### 10. 前缀和

连续子数组，值可能为负，此时不能使用滑动窗口或者双指针

### 11. 图

Floyd算法：k在最外层

最短路问题：最好用bfs，dfs可能无法求出最短路径

### 12. 线段树

e.g. 最大子序和（连续子数组的最大和）

[l, r] → [l, newr] + [newr+1, r], newr = l+(r-l)/2

### 13. 树状数组

树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于数组的单点修改&&区间求和，另外一个拥有类似功能的是线段树。

具体区别和联系如下：

1.两者在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树.

2.树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能够解决的问题树状数组未必能够解决.

3.树状数组的突出特点是其编程的极端简洁性, 使用lowbit技术可以在很短的几步操作中完成树状数组的核心操作，其代码效率远高于线段树。

树状数组是二进制的应用

<!-- 求数组下标二进制的非0最低位所表示的值 -->
int lowbit(int i)
    return i & -i;

- 两个操作

求区间[1, i]的和/个数

更新树

- 总结

树状数组的重点就是利用二进制的变化，动态地更新树状数组。

树状数组的每一个节点并不是代表原数组的值，而是包含了原数组多个节点的值。

所以在更新A[1]时需要将所有包含A[1]的C[i]都加上val这也就利用到了二进制的神奇之处。

如果是更新A[i]的值，则每一次对C[i] 中的 i 向上更新，即每次i+=lowbit(i),这样就能C[i] 以及C[i] 的所有父节点都加上val。

反之求区间和也是和更新节点值差不多，只不过每次 i-=lowbit(i)。

解释：

C[i]代表子树的叶子节点的权值之和

C[1]=A[1];

C[2]=A[1]+A[2];

C[3]=A[3];

C[4]=A[1]+A[2]+A[3]+A[4];

C[5]=A[5];

C[6]=A[5]+A[6];

C[7]=A[7];

C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

### 14. 差分数组

记录变化点 change[]


## 二、运算技巧

### 1. 求商

向下取整：a/b

向上取整：(a-1)/b +1

### 2. 位运算

与AND： &

或OR： |

异或XOR： ^ （用于取反）

无符号补位（即补0） <<< >>> //<< >>移动的是正数则补0，移动的是负数则补1

奇变偶，偶变奇：x = x^1

重复出现置0：a^a = 0，a^0 = a

异或的性质：a^b = ~ab+a~b

异或等价：x = i ^ j 等价于 j = x ^ i

Brian Kernighan 算法：x = x & (x − 1)，该运算将 x 的二进制表示的最后一个 1 变成 0

位运算参与其他运算时要加括号

能整体操作，就不要逐位操作

- 字典序法

规则一：x 的最低位为 1，这种情况下，
如果末尾由 t 个连续的 1，我们直接将倒数第 t 位的 1 和倒数第 t + 1 位的 0 替换，
就可以得到 next(x)。
如 0011→0101，0101→0110，1001→1010，1001111→1010111。

规则二：x 的最低位为 0，这种情况下，
末尾有 t 个连续的 0，而这 t 个连续的 0 之前有 m 个连续的 1，
我们可以将倒数第 t + m 位置的 1 和倒数第 t + m + 1 位的 0 对换，
然后把倒数第 t + 1 位到倒数第 t + m - 1 位的 1 移动到最低位。
如 0110→1001，1010→1100，1011100→1100011。

### 3. 哈希表

键值尽可能短

键值类型：整型比字符串快

哈希函数映射为整型，比直接用字符串快很多

### 4. 最大公约数

```
long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b);
}
public int gcd(int a, int b) {
    return b != 0 ? gcd(b, a % b) : a;
}
public int gcd(int x, int y) {
    return y > 0 ? gcd(y, x % y) : x;
}
```

### 5. 求中值

mid = left + ((right-left)>>1); // 注意 left right顺序 和 位运算外的括号