本周学习：时间复杂度，二分查找，二分答案，一二维前缀和和差分。
前提：时间空间复杂度计算都遵循大O渐进法则
大O渐进法则：
1.常数1取代运行时间中的所有加法常数
例：5*N^2+2^N+8 ----> 5*N^2+N+1
2.只保留最高项
例：5*N^2+N+1 ------> 5*N^2
3.如果最高项存在且系数不是一，去除最高项常数
例：5*N^2 -----> N*2 最后得到O(n^2)
1.时间空间复杂度
1.1 时间复杂度：算法运算的时间,节省测试时间
从小到大分为O(1) ,O(log2 n) , O(n) , O(nlog2 n) , O(n^2),O(2^n) ,O(n!)
嵌套相乘，其他相加，计算的时候遵循大O渐进法则
1.2 空间复杂度：算法运行过程中空间存储的估计量
情况分为：普通定义O(1)，数组O(n)/O(n^2)，循环O(n)/...，递归(递归次数*层数
2.二分法
2.1 情况一 二分查找：适用于数组的排序和查找，给出数组类型题。定义两个指针，确定中间值，比对目标大小，移动指针，改变中间值，最终比对成功。位运算>>1,作用除以2^1,向下取整,时间复杂度O(logN)
算法模板：
//模板一：尽量往左找目标 while(l<r) { int mid = l+r >>1; //(l+r)/2 if(check(mid)) r = mid; else l = mid +1; } //模板二：尽量往右找目标 while(l<r) { int mid = l+r+1 >>1; //(l+r+1) /2 if(check(mid)) l = mid; else r = mid-1; }
eetcode练习：练习题1——模板练习
leetcode34：解题思路：题目要求时间复杂度为O(logN)，所以使用二分来解决，找到第一个target，然后使target+1，找到比目标大一的数，最后减一就可以实现，题目所给数组已经为升序，最后返回数组即可。
class Solution { public int[] searchRange(int[] nums, int target) { int l = search(nums,target); int r = search(nums,target+1); if(l==nums.length || nums[l] != target) { return new int []{-1,-1}; } return new int []{l,r-1}; } public static int search(int nums[],int target) { int left = 0,right = nums.length; while(left<right) { int mid = left+(right-left)/2; int num = nums[mid]; if(num >= target) { right = mid; }else{ left = mid + 1; } } return left; } }
leetcode33:解题思路：题目对一个已经按照升序排好的数组中的某个下标进行数组反转，这样的话就形成了两个区域，[left,mid] 和 [mid,right]，例如[4,5,6,7,0]，形成的区域一个是有序的，另一个可能有序，也可能无序，所以解题步骤要先分析区域是否有序，然后再进行左右指针的移动。 1.先判断mid左右任意一区间是否是有序 2. 然后判断target在哪一块区间 。通过比对nums[mid] 和 nums[0] 的大小 分为左右两块，然后假设情况target所在的取值范围，一边是有序的的，一边可能有序，可能无序，对于另一边进行继续二分探索。
class Solution { public int search(int[] nums, int target) { int left = 0,right = nums.length; while(left<right) { int mid =left+(right-left)/2; if(nums[mid] == target) { return mid; } if(nums[mid] >= nums[0]) { if(target>=nums[0] && target < nums[mid]) { right = mid; }else{ left = mid +1; } }else{ if(target>nums[mid] && target<=nums[right-1]) { left = mid+1; }else{ right = mid; } } } return -1; }
2.2 情况二：二分答案
适用：直接搜索不好搜，判断一个数可不可行，答案在一个区间内
根据题意，所求为最大切割木块长度，选用模板二
package exercise; import java.util.Scanner; class two_search { static int n,k; static int a [] ; public static void main(String[]args) { Scanner s = new Scanner(System.in); n = s.nextInt(); k = s.nextInt(); a = new int [n]; int max = 0; int sum =0; for(int i = 0;i<n;i++) { a[i] = s.nextInt(); sum+=a[i]; max=Math.max(max,a[i]); } if(sum<k) { System.out.println(0); return; } int l=1,r=max; int mid =0; while(l<r) { mid = l+r+1 >>1; if(Check(mid)) { l =mid; }else { r = mid -1; } } System.out.println(l); } public static boolean Check(int mid) { int duan = 0; for(int i = 0;i<a.length;i++) { duan+=a[i]/mid; } return duan>=k; }
3.前缀和
3.1一维前缀和：时间复杂度O(n)
//定义一个数组sum,从一开始 //一维前缀和预处理公式： int length,m; int l = 0,r = 0; for(int i =1;i<length;i++) { sum[i] = scanner.nextInt(); sum[i] += sum[i-1]; } while(m-->0) { l =.... r = .... System.out.print(sum[r]-sum[l-1]);
3.2二维前缀和：时间复杂度O(nm)
遍历求取一个矩形块内的数值和，结论：左上角(x1,y1),右下角(x2,y2) 的子矩阵和为;s[x2][y2] - s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]; 用两个二维数组，一个用来存a[i][j]， 一个用来存s[i][j]，首先用含a的式子表示s，之后带入x1.y1，x2，y2，得到范围矩阵的数字和。
模板
// n行m列 int a [][] = new int [n+1][m+1]; int s [][] = new int [n+1][m+1]; for(int i =1 ;i<=n;i++) { for(int j =1;j<=m;j++) { a[i][j] = scanner.nextInt(); } } for(int i =1 ;i<=n;i++) { for(int j =1;j<=m;j++) { s[i][j] = s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1]; } } ...... //最后输出 System.out.print(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1])
4.差分
4.1一维差分：时间复杂度O(n)
方法一：理解：有前缀和数组a，则有差分数组b[i] = a[i]-a[i-1] 举例：因为a[i]是前缀和，当如b[1]+c 后，每一个a[i]中都含有b[1]，相当于a[i]每个数都+c，给定加减数范围之后，对于范围之内的数都+c，即b[l] += c,同时也满足了a[l到end]每个数都加+c,再让b[r+1] -=c,将范围之后的数全部恢复原状，就可以达到目的。
模板：
import java.util.Scanner; class two_search { static int b[]; public static void main(String[]args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); int m = s.nextInt(); int a [] = new int [n+1]; b= new int [n+2]; for(int i =1;i<=n;i++) { a[i] = s.nextInt(); } for(int i =1;i<=n;i++) { b[i] = a[i] -a[i-1]; } while(m-->0) { int l = s.nextInt(); int r = s.nextInt(); int c = s.nextInt(); b[l] += c; b[r+1] -=c; } for(int i = 1;i<=n;i++) { b[i] += b[i-1]; System.out.print(b[i]+" "); } } }
方法二：通过引入insert()函数，来表示前缀和a和差分数组b的关系，通过键盘输入a数组，然后定义差分数组b，没有赋值，所以数组里b[i] = 0,通过调用insert(i,i,a[i]),来表明a与b之间的关系。举例：insert(1,1,a[1])，则有b[1] = a[1],b[2] = -a[1] ,当i=2时，b[2]=a[2]-a[1],b[3] = -a[2]，由于我们时遍历到n，所以无需关心b[n+1]，只需要扩大数组空间，防止溢出就可以。
模板：
import java.util.Scanner; class two_search { static int b[]; public static void main(String[]args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); int m = s.nextInt(); int a [] = new int [n+1]; b= new int [n+2]; for(int i =1;i<=n;i++) { a[i] = s.nextInt(); insert(i, i, a[i]); } while(m-->0) { int l = s.nextInt(); int r = s.nextInt(); int c = s.nextInt(); insert(l, r, c); } for(int i = 1;i<=n;i++) { b[i] += b[i-1]; System.out.print(b[i]+" "); } } public static void insert(int l,int r,int c) { b[l] += c; b[r+1] -=c; }
4.2二维差分
左上角(x1,y1),右下角为(x2,y2)的矩阵中每个元素都加c为:
s[x1][y1] +=c , s[x2+1][y1] +=c , s[x1][y2+1] += c ,s[x2+1][y2+1] += c;
当数据规模过于庞大，可以使用BufferedReader来进行键盘读取，如果正常使用Scanner来读取数据，容易输入超时。
模板：类似于一维差分，只有方法有所变动
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; class two_search { public static void main(String[]args) throws IOException { //使用BufferedReader避免超时 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); String[] str1 = reader.readLine().split(" "); int n = Integer.parseInt(str1[0]); int m = Integer.parseInt(str1[1]); int q = Integer.parseInt(str1[2]); int N = 1010; int [][] a = new int [N][N]; int [][] b = new int [N][N]; //读入原数组 for(int i = 1;i<=n;i++) { String [] str2 = reader.readLine().split(" "); for(int j = 1;j<=m;j++) { a[i][j] = Integer.parseInt(str2[j-1]); insert(b, i, j, i, j, a[i][j]); } } while(q-->0) { String str3[] = reader.readLine().split(" "); int x1 = Integer.parseInt(str3[0]); int y1 = Integer.parseInt(str3[1]); int x2 = Integer.parseInt(str3[2]); int y2 = Integer.parseInt(str3[3]); int k = Integer.parseInt(str3[4]); insert(b, x1, y1, x2, y2, k); } for(int i =1;i<=n;i++) { for(int j = 1;j<=m;j++) { b[i][j] +=b[i][j-1]+b[i-1][j] -b[i-1][j-1]; writer.write(b[i][j]+" "); } writer.write("\n"); } writer.flush(); reader.close(); writer.close(); } public static void insert(int [][]b,int x1,int y1,int x2,int y2,int k) { b[x1][y1] += k; b[x2+1][y1] -= k; b[x1][y2+1] -=k; b[x2+1][y2+1] +=k; } }
