1. 折半
1.1 从一维数组中求一个值/下标
724.寻找数组的中心索引 Find Pivot Index medium
将(总数)减去(左边上一次累加的和)减去(本次的值) = O(N)，（如果有2个中心值，只保留左边的中间值）累加值可以对比前一次的，也可以对比当前的
747.最大值至少是其他值的两倍 Largest Number At Least Twice of easy
先求最大值下标，再遍历同事略过最大值下标O(N)，可以考虑用s++,e--改成O(N/2)
1.2 根据一维数组，处理后返回一维数组
66. 数值加一 Plus One easy
法1. 使用队列记录，并用一个进制位辅助表示是否+1(性能不好)
法2. 可以根据每个数是否为9，如果有一个不为9，都不会导致左位进1，如果全都是9，则数组长度+1，第一个值为1，其余值为0. time: O(n), space: O(1)
1.3 根据二维数组，找规律，处理后返回一维数组
498. 对角线遍历矩阵 Diagonal Traverse medium
难点在找规律，用row和col表示下标，返回的总数是mn个数组，方向就2个{上右{-1, 1}，左下{1, -1}}表示，并且出界情况就4种，row<0 || col<0 || row >m-1 || col >n-1，在不同的情况*下改变对应的row和col下标 以及 方向d{0, 1}
54. Spiral Matrix 螺旋矩阵 medium
找规律，用row和col表示下标，返回的总数是mn个数组，并且边界值[上下左右]，每次改变方向时要减少对应的边界值-1，在不同的情况*下改变对应的row和col下标，方向4个，{右{0,1}，下{1,0}，左{0,-1}，上{-1,0}}，
1.4 查询数据在有序列表中位置 若不存在则预估位置
35. 查询一维数组插入的位置 Search Insert Position easy
折半法要注意
(a + b) /2容易越界，可以用[a + (a-b)/2]
时间复杂度O(logn)，空间复杂度O(1)
折半法
取最后定位的下标low
74. 查询二维有序数组中某个值下标 search-a-2d-matrix easy
时间复杂度O(logn)，空间复杂度O(1)
折半法
虽然是二维数组，但是由于是有序的
240. 查询二维无序数组中某个值下标 Search a 2D Matrix II medium
时间复杂度O(m+n)，空间复杂度O(1)
找规律
找到第1列的最右值
如果值比目标大，则向下移动行
如果值比目标小，则向左移动列
153. 寻找旋转排序数组中的最小值(数据不重复) Find Minimum in Rotated Sorted Array medium
法1. dp方法 + 折半 同时运用了规则，有序时最小值一定是头一个，无序时遍历
时间复杂度O(logn)，空间复杂度O(1)
设置一个min=Integer.MAX_VALUE，每次传入对应的start和end，如果nums[start]<nums[end]说明nums[start]是最小的做比对直接返回，否则设下的一定是无序的，折半，if(nums[start]<=nums[mid])说明最小值在另一边
法2. 折半
时间复杂度O(logn)，空间复杂度O(1)
如果nums[mid]>nums[mid+1]则mid+1最小值，如果nums[mid-1]>nums[mid]则mid最小值，否则nums[mid]>nums[0]意味最小值在右边
法3. 折半
时间复杂度O(logn)，空间复杂度O(1)
先定位到最小值所在下标，nums[mid]>nums[hi]，意味着最小值在右侧->lo=mid+1; 否则在左侧->hi=mid;
33. 寻找旋转排序数组中值的下标(数据不重复) Search in Rotated Sorted Array medium
时间复杂度O(logn)，空间复杂度O(1)
先定位到最小值所在下标，由于数组是有序的，那下标则为偏移量，使用折半查找，每次中位数+偏移值
81. 搜索旋转排序数组(数据重复) II Search in Rotated Sorted Array II
todo
1.5 括号问题
20. 有效的括号 valid parentheses easy
使用stack校验
22. 输入括号，输出所有有效配对生成 Generate Parentheses medium
法1. 回溯法 时间复杂度O(),空间复杂度O(n)
使用开关括号的特性，进行回溯，记录一个值用s.length()==n做条件
1.6 快速逼近目标值
744. 寻找比目标字母大的最小字母 Find Smallest Letter Greater Than Target easy
法1. 时间复杂度O(logn) 空间复杂度O(1)
折半法，定位到i为目标值下标，判断i是否为最后一个值，是取第一个值
374. 猜数字大小 Guess Number Higher or Lower easy
法1. 时间复杂度O(logn) 空间复杂度O(1)
折半法，每次取中间值对比大小
375. 猜数字大小II Guess Number Higher or Lower II medium
todo
2. 字符串
2.1 传入字符串，处理逻辑，返回字符串
67. Add Binary 二进制求和 easy
从尾数开始，以长字符串做条件，从尾往头遍历，总和有3，2，1，0类型，设置一个全局增量
890. 查找和替换模式 Find and Replace Pattern
法1. 时间复杂度O(mn)，空间复杂度O(mn) ，m是字符串数组个数，n是字符串长度
使用两个Map，一个保存key=匹配模式,value=值，一个key=目标值,value=匹配模式，逐个对比
3. 字符串/数组/双指针
3.1 承载水位问题
11. 容器可承载最大水位 Container With Most Water medium
法1. 双指针，时间复杂度O(n)，空间复杂度O(1)
宽度总是减少的
每次将水位低的一边缩容，因为低的一方决定了上限
