数据结构笔记1.斐波那契函数除去前几个特例后面的数均为前一个数后面一个数public static long Fib(int N){if(N 3){return 1;}else{return Fib(N-1) Fib(N-2);}}2.复杂度只说最坏情况下。3.1、用常数1取代运行时间中的所有加法常数。2、在修改后的运行次数函数中只保留最高阶项。3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。4.二分查找中间索引为向下取整3.5取3。5. java中的小数计算会自动取整。12/21;但数太大时最高位会变成符号位即突破正整数限制变为以负号开头的数字。这个时候就开始使用右移运算符,即在二进制层面右移一位来代替除号÷的弊端。6. 二分查找核心循环左闭右开区间 [left, right)。7.如果righta.length ;则代表右侧指针不进行数据比对只用来进行缩小边界此时while(1right-left)。8.数组采用二分查找中间项是数组的中间序列号要生成一个临时变量将数组中间序列号所代表的值赋给它例如int midVal a[mid]; 之后才能进行后续比较。9.java中的绝对值函数Math.abs()。10. 数组复制函数System.arraycopy旧数组起始位置目标数组插入点的起始位置原数组复制到新数组的长度例如旧数组为123复制的长度为2根据数组下标应该复制数组下标1之前的内容1和2。11.找最左边第一个目标数缩右边界因为对象数组本身已经就是从右到左的从小到大的有序数组缩右边界就是要排除左边是否还有目标数反之找最右边第一个目标数则缩左边界。12.二分查找的通用公式class Solution{public int search( int[ ] nums, int target){int left 0;int right nums.length-1;while(left right){int mid left(left right)/2;int midval nums[mid];if( targetmidval){return mid;}if(targetmidval){right mid -1; //核心操作是通过 target 满足条件来操控一边的指针一直移动另一边不动直到不满足while的()中的前提条件从而跳出循环}else{left mid 1;}}return -1;}}13.Leftmost: 找靠左返左 改动原始二分查找代码return -1; 改为 return left; 意味返回值为target的***最靠左的索引***。14.Rightmost:找靠右返右 改动原始二分查找代码return -1; 改为 return left -1或 return right; 意味返回值为target的***最靠右的索引*** 。15.求排名: Leftmost(target) target的索引 1 。16求前任Leftmost(target) target的索引 - 1 。17.求后任Rightmost(target) target的索引 1 。