2020年06月24日

数组

优秀代码参考 ID题目大致内容解题思想注意点153寻找旋转排序数组中的最小值关键是需要找到旋转点。用二分法，终止条件是if (nums[mid] > nums[mid + 1]) { return nums[mid + 1]; }和if (nums[mid - 1] > nums[mid]) { return nums[mid]; }。需要注意的是，判断更新变量lo和hi的条件是if (nums[mid] >= nums[0])而不是if (nums[mid] >= nums[lo])162寻找峰值方法一 线性扫描。从第 0 个元素开始，它一定是上升的趋势，由于要找峰顶，所以当它第一次出现下降，下降前的值就是要找的。如果它一直上升到最后一个值，又因为 nums[n] 看做负无穷，所以最后一个值就可以看做一个峰顶。方法二 二分法。只要确定某一半至少存在一个峰顶，那么另一半就可以抛弃掉。如果 nums[mid] < nums[mid + 1]，此时在上升阶段，因为 nums[n] 看做负无穷，也就是最终一定会下降，所以 mid + 1 到 end 之间至少会存在一个峰顶，可以把左半部分抛弃;如果 nums[mid] > nums[mid + 1]，此时在下降阶段，因为 nums[0] 看做负无穷，最初一定是上升阶段，所以 start 到 mid 之间至少会存在一个峰顶，可以把右半部分抛弃。通过上边的切割，我们就保证了后续左边界一定是在上升，右边界一定是在下降，所以第二次、第三次… 的二分就和上边一个道理了。二分法可以写成递归或者迭代，由于递归形式比较简单，所以我们最好用迭代去实现，因为递归的话需要压栈的空间。虽然上边的递归是尾递归的形式，不需要压栈，但这需要编译器的支持。209长度最小的子数组方法一 暴力。遍历，从索引0开始，索引为i，当遍历的数组和大于等于s，则记录数组长度，更新长度最小值。i++;重复知道i=length-1。方法二 双指针/滑动窗口。第 1 步：right 向右移增大窗口，直到窗口内的数字和大于等于了 s。进行第 2 步：记录此时的长度，left 向右移动，开始减少长度，每减少一次，就更新最小长度。直到当前窗口内的数字和小于 s，回到第 1 步开始更新right。方法三 二分查找。把数组元素的累加和建成一个新数组，对新数组进行二分查找216组合总和 III动态规划加剪枝

常用方法积累

类名方法名解释ArrayListindexOf(value)返回value值对应的索引值，ArrayListcopyOfRange(T[ ] original,int from,int to)将原数组original，从下标from开始复制，复制到上标to，生成一个新的数组。ArrayListans.get(i).append©名为ans的ArrayList对象拿出索引i处的元素，并在其后追加一个字符或数字c。注意不是[index]HashMapgetOrDefault(Object key, V defaultValue)当Map集合中有这个key时，就使用对应的value值，如果没有就使用默认值defaultValueMapentrySet()获取所有key和value，遍历的时候用，例子：for (Map.Entry<String, String> entry : map.entrySet()) {System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());}IntegertoBinaryString(num)返回num整数的二进制字符串表达IntegertoHexString(num)返回num整数的十六进制字符串表达IntegerbitCount(num)返回num整数的二进制表达式中1的个数CharactertoLowerCase©返回c的字母小写形式CharactertoUpperCase©返回c的字母大写形式CharacterisLetter©判断c是否为字母Stringformat(patten,num)格式化字符串，比如format("%d:d",1,2),输出结果为1:02StringsubString(start,end)含start，不含endStringBuilderdeleteCharAt(index删除索引所在处的字符Arraysfill(Object[] a, Object val)再数组a中把所有值都填充为valArraysequals(s1,s2)比较两个数组元素是否相同ArraysasList(s1,…,sn)将一个数组s1,…,sn转换为 List.注意，数组元素不能是原生数据类型(int,long等)，要用其包装类Integer等Arraysset(index,element)修改列表中的值。（index指定下标，element指定要修改后元素的值）SystemarrayCopy(Object src, int srcPos, Object dest, int destPos, int length)Object src : 原数组; int srcPos:从元数据的起始位置开始; Object dest:目标数组; int destPos:目标数组的开始起始位置; int length:要copy的数组的长度TreeSetfloor(E e)返回在这个集合中小于或者等于给定元素的最大元素，如果不存在这样的元素,返回null.TreeSetceiling(E e)返回在这个集合中大于或者等于给定元素的最小元素，如果不存在这样的元素,返回null.

参考

leetcode-windliang