003 二进制和位运算
1. 一个简便的得到负数二进制位的方式
对应正数减1再按位取反：
比如-1, 就是( 0001 - 1 ) 再按位取反，变成 1111
当然，知道一个负数本身，想知道其十进制对应的是谁，就要先按位取反，然后再+1 就好了
2. 二进制的空间范围
对于一个n位的二进制数而言，其表达空间为 2^n, 非负数（0+所有正数）和负数的个数是相同的。
那么最小的值，比如-8， 相反数是没法得到的，其相反数会和自己相同。
同样的，对于一个整数来说，比如Integer的最小值，其取绝对值也还是自己。
得到一个数的相反数，等于这个数按位取反然后+1
下面两个式子等价：
int a = (-b);
int a = (~b) + 1
3. | 的穿透性
|| 只有一路是false，才会从左向右穿透，不然会直接从左往右返回第一个值
但是| 而言，如果是 a|b ，那么a和b都会进行验证之后再来判断
对于 & 而言是一样的，如果是 & ，那么会穿透左右两边都执行再判断，而 &&就不会，第一个是false那么就会短路
4. 为什么要这样设计二进制
原因在于对于负数，正数互相相加的时候，只要忽略溢出位，可以统一按照二进制的加法来做，这样就避免了在相加时候的条件转移（如果是正数+负数/正数+正数……）
那么也可以看出来，在计算的时候，是否溢出应该是程序员本身来保证，计算机只是按照二进制位运算的规律进行计算而已，不负责校验是否溢出
为什么要让加法运算这么快
计算机内部本身并没有真正用来做加减乘除的单元，只有用来做位运算的单元，加减乘除本质实现都是优化之后的加法。
5 对数器
对数器的基本原理：
对于一个算法题目而言，暴力解好想，但是最优解可能出错。
那么构造一个对数器，其输入的长度和数值范围都是我们随机生成的（为了暴力解不超时，可以先构造范围小一些的），然后多次比较二者的输出，如果相同，那么就是没问题。不同的话就打印出来不同的数据集进行debug。
前提条件：保证自己的暴力解正确.
关键：找到一个数据量很小的错误样本
6. 二分搜索
在有序数组上面进行搜索。
个人认为，二分算法要点以下：
注意边界值，mid = l + (r-l)/2, 所以可能和l或者r相同。这种情况如果有 l-1 或者 r+1 的值的判断（比如峰值），就要注意是否可能会溢出边界。
对于可能溢出边界的值，直接进行一开始的枚举，把可能溢出的数据进行排除之后再进行逐步二分
每次二分之后，得到的中间值一般都在下一次循环之中舍去，取其左边或者右边作为下一次的边界。原因是要么不符合，要么已经在答案之中记录了
6.1 在有序数组确定num是否存在
对数器思路：直接从左往右遍历，有就是有，没有就是没有。
6.2 寻找峰值问题
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
class Solution {
public int findPeakElement(int[] nums) {
int ans = -1, len = nums.length;
if(nums == null || len ==0){
return ans;
}
if(len == 1 ){
return 0;
}
if(nums[0]>nums[1]){
return 0;
}
if(nums[len-2]<nums[len-1]){
return len-1;
}
int l=1, r= len-2, mid;
while(l<=r){
mid = l+(r-l)/2;
if(nums[mid]<nums[mid-1]){
r= mid-1;
}else if(nums[mid]<nums[mid+1]){
l=mid+1;
}else{
ans = mid;
break;
}
}
return ans;
}
}
6.3 山脉数组的峰顶索引
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int ans = 0;
int l = 1, r = arr.length - 2, mid;
if (arr[1] > arr[0] && arr[1] > arr[2]) {
return 1;
}
if (arr[r - 1] > arr[r] && arr[r - 1] > arr[r - 2]) {
return r - 1;
}
while (l <= r) {
mid = l + (r - l) / 2;
if (arr[mid] < arr[mid - 1]) {
r = mid - 1;
} else if (arr[mid] < arr[mid + 1]) {
l = mid + 1;
} else {
ans = mid;
break;
}
}
return ans;
}
}
7. 时间复杂度和空间复杂度
时间复杂度
时间复杂度是本质上面的运算速度，所以只看最高项的部分，其他在数据量趋于无穷时候的低阶项相比较之下都可以忽略
随机流程和固定流程算法的时间复杂度
-
严格固定流程的算法，一律用最差情况进行估计
-
随机流程的方法，用平均值作为估计
举例：生成一个相邻值不等的随机数组，如果是最差情况，永远都是得到同样的值，那么就无法进行下去，复杂度是无穷大；应该按照期望来看，是O(N)
空间复杂度
强调额外空间.
均摊复杂度
动态数组的扩容，如果要放入N个数，其扩容次数小于 2N，均摊到每一个数字上面，其复杂度为 O(1)
调和级数
不要用代码结构来判断时间复杂度，比如：N/1 + N/2 + N/3 + … + N/N，这个流程的时间复杂度是O(N * logN)，著名的调和级数
常见时间复杂度
O(1) O(logN) O(N) O(N*logN) O(N^2) … O(N^k) O(2^N) … O(k^N) … O(N!)
