算法笔记（一）（教你系统学习基础算法）
（一）基礎算法
目錄
（一）基礎算法
1、快速排序
例題1：第k個數(shù)
2、歸并排序
例題一：逆序對的數(shù)量
?
3、二分
例題一：數(shù)的范圍
例題二：數(shù)的三次方根
4、前綴和與差分
例題一：前綴和
例題二：子矩陣和
例題三：差分?
例題四：差分矩陣
5、雙指針算法
例題一：最長連續(xù)不重復子序列
例題二：數(shù)組元素的目標和
例題三：判斷子序列
6、位運算
例題一：二進制中一的個數(shù)
7、離散化
例題一：區(qū)間和
8、區(qū)間合并
例題一：區(qū)間合并
1、快速排序
? ? ? ??(158條消息) 什么？一篇理解排序算法（下）_yan揚的博客-CSDN博客https://blog.csdn.net/qq_59539549/article/details/123609047?spm=1001.2014.3001.5501
由于之前的博客已經(jīng)詳細快排和歸并的實現(xiàn)原理和邏輯 這里不再贅述 僅給出實現(xiàn)代碼和例題
快排代碼實現(xiàn)（左右指針）
import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);//讀取數(shù)據(jù)（數(shù)組長度）int n=sc.nextInt();int[] nums=new int[n];//接受數(shù)據(jù)的數(shù)組for(int i=0;i<n;i++){nums[i]=sc.nextInt();//給數(shù)組賦值}quickSort(nums,0,n-1);//對數(shù)組下標 0~n-1 進行排序for(int i=0;i<n;i++){System.out.print(nums[i]+" ");}}public static void quickSort(int[] nums,int st,int ed){if(st>=ed) return;//一個數(shù)時默認有序int l=st;//定義左右指針int r=ed;int temp=nums[l];//privot元素 大于等于該值放右邊 小于等于放左邊while(l<r){while(l<r&&nums[r]>=temp){r--; //在右邊找比temp小的元素}while(l<r&&nums[l]<=temp){l++; //在左邊找嚴格大temp的元素}swap(nums,l,r);}swap(nums,st,l);//讓temp處于在自己該待的位置quickSort(nums,st,l);quickSort(nums,l+1,ed);}public static void swap(int[] nums,int i,int j){ //交換函數(shù)int t=nums[i];nums[i]=nums[j];nums[j]=t;} }這里補充一點：遞歸左邊進行快排時 右邊界 是 l 和 l-1 其實都是可以的 因為我們選作最左邊的元素作為privot作為temp 不會出現(xiàn)死循環(huán) 因為每次調(diào)用最起碼要去掉一個?
例題1：第k個數(shù)
給定一個長度為?nn?的整數(shù)數(shù)列，以及一個整數(shù)?kk，請用快速選擇算法求出數(shù)列從小到大排序后的第?kk?個數(shù)。
輸入格式
第一行包含兩個整數(shù)?nn?和?kk。
第二行包含?nn?個整數(shù)（所有整數(shù)均在?1～1091～109?范圍內(nèi)），表示整數(shù)數(shù)列。
輸出格式
輸出一個整數(shù)，表示數(shù)列的第?kk?小數(shù)。
數(shù)據(jù)范圍
1≤n≤1000001≤n≤100000,
1≤k≤n1≤k≤n
輸入樣例：
5 3 2 4 1 5 3輸出樣例：
3思路：快排的思路 我們每次可以確定一個值 左邊的數(shù)都比他小 右邊的數(shù)都比他大 因此我們一定知道當前這個數(shù)是?“第幾大” 的數(shù)?因此我們每次遞歸只需要選擇一側去遞歸 如果k<=左側長度 我們就遞歸左邊 否則遞歸右邊 （但要記得 k要變?yōu)?k- 左側長度 ）
代碼實現(xiàn)：
import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int k=sc.nextInt();int[] nums=new int[n];for(int i=0;i<n;i++){nums[i]=sc.nextInt();}int res=quickCheck(nums,0,n-1,k);System.out.print(res);}public static int quickCheck(int[] nums,int st,int ed,int k){if(st==ed){return nums[st];//就是我們要找到的}int l=st;int r=ed;int temp=nums[st];while(l<r){while(l<r&&nums[r]>=temp){r--;}while(l<r&&nums[l]<=temp){l++;}swap(nums,l,r);}swap(nums,st,l);int len=l-st+1;//計算左側長度 判斷k在左還是右if(k<=len){return quickCheck(nums,st,l,k);}else{return quickCheck(nums,l+1,ed,k-len);//記得傳進去的是 k-len}}public static void swap(int[] nums,int i,int j){int t=nums[i];nums[i]=nums[j];nums[j]=t;} }2、歸并排序
同理：之前寫過相關原理 這里僅給出代碼
import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int[] nums=new int[n];for(int i=0;i<n;i++){nums[i]=sc.nextInt();}mergeSort(nums,0,n-1);for(int i=0;i<n;i++){System.out.print(nums[i]+" ");}}public static void mergeSort(int[] nums,int st,int ed){if(st==ed) return;//一個元素時默認有序int mid=st+ed>>1;mergeSort(nums,st,mid);//把數(shù)組分割成小數(shù)組 再合并兩個有序的小數(shù)組mergeSort(nums,mid+1,ed);int p1=st;int p2=mid+1;int k=0;//輔助數(shù)組合并時的下標int[] help=new int[ed-st+1];//輔助數(shù)組while(p1<=mid&&p2<=ed){if(nums[p1]<=nums[p2]){help[k++]=nums[p1++];}else{help[k++]=nums[p2++];}}while(p1<=mid){help[k++]=nums[p1++];}while(p2<=ed){help[k++]=nums[p2++];}for(int i=0;i<k;i++){nums[st+i]=help[i];}} }例題一：逆序對的數(shù)量
給定一個長度為?nn?的整數(shù)數(shù)列，請你計算數(shù)列中的逆序對的數(shù)量。
逆序對的定義如下：對于數(shù)列的第?ii?個和第?jj?個元素，如果滿足?i<ji<j?且?a[i]>a[j]a[i]>a[j]，則其為一個逆序對；否則不是。
輸入格式
第一行包含整數(shù)?nn，表示數(shù)列的長度。
第二行包含?nn?個整數(shù)，表示整個數(shù)列。
輸出格式
輸出一個整數(shù)，表示逆序對的個數(shù)。
數(shù)據(jù)范圍
1≤n≤1000001≤n≤100000，
數(shù)列中的元素的取值范圍?[1,109][1,109]。
輸入樣例：
6 2 3 4 5 6 1輸出樣例：
5核心思路：依然是把數(shù)組先拆分成小數(shù)組，我們總的逆序對數(shù)量=左段逆序對數(shù)+右端逆序對數(shù)+合并時產(chǎn)生的逆序對數(shù)（p1指針后的所有數(shù)都大于當前數(shù)）
易錯點：在合并時 如果遇到兩個數(shù)組中值相同 我們一定要左側的先放進輔助數(shù)組 如果右側的先放 可能會導致 左側后邊還有比當前值大的數(shù)，但我們這個數(shù)已經(jīng)放進輔助數(shù)組被丟棄了 也就是有逆序對沒有被計算? ?另一個易錯點是需要用long類型 否則int會溢出
import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int[] nums=new int[n];for(int i=0;i<n;i++){nums[i]=sc.nextInt();}long res=mergeSum(nums,0,n-1);System.out.print(res);}public static long mergeSum(int[] nums,int st,int ed){if(st==ed) return 0;//分成只含一個元素的數(shù)組 自然沒有逆序對int mid=st+ed>>1;long left=mergeSum(nums,st,mid);long right=mergeSum(nums,mid+1,ed);int[] help=new int[ed-st+1];int p1=st;int p2=mid+1;int k=0;long res=left+right;while(p1<=mid&&p2<=ed){if(nums[p1]<=nums[p2]){help[k++]=nums[p1++];}else{help[k++]=nums[p2++];res+=mid-p1+1;}}while(p1<=mid){help[k++]=nums[p1++];}while(p2<=ed){help[k++]=nums[p2++];}for(int i=0;i<k;i++){nums[st+i]=help[i];}return res;} }3、二分
?二分常被用來尋找一段擁有單調(diào)性的區(qū)間邊界
比如：
在這段區(qū)間里 我們想尋找最靠近綠色的紅色下標 只需要控制我們的查找值永遠處于我們的l到r之間
不難寫出以下偽代碼
//首先二分肯定是需要在一段區(qū)間上進行二分 int l; int r; int mid=l+r>>1; if(check(nums[mid])==red){//如果滿足紅色區(qū)間 我們縮小邊界l=mid; //為什么是l等于mid 因為我們要保證這個最接近綠色的紅色邊界永遠處于我們的l到r之間 }else{r=mid-1; }?但此時還有一個問題 就是說假如 l=r-1? ，由于mid存在向下取整? 當l=mid 后 第二次 的循環(huán)依舊是 mid=l 所以查找區(qū)間還是原來的 [l,r]?會造成死循環(huán) 因此我們在一開始的mid求值時 需要改為 l+r+1>>1
反之如果我們尋找綠的的最靠左邊界 mid求值時把r改為mid 不會造成死循環(huán)
例題一：數(shù)的范圍
給定一個按照升序排列的長度為?nn?的整數(shù)數(shù)組，以及?qq?個查詢。
對于每個查詢，返回一個元素?kk?的起始位置和終止位置（位置從?00?開始計數(shù)）。
如果數(shù)組中不存在該元素，則返回?-1 -1。
輸入格式
第一行包含整數(shù)?nn?和?qq，表示數(shù)組長度和詢問個數(shù)。
第二行包含?nn?個整數(shù)（均在?1～100001～10000?范圍內(nèi)），表示完整數(shù)組。
接下來?qq?行，每行包含一個整數(shù)?kk，表示一個詢問元素。
輸出格式
共?qq?行，每行包含兩個整數(shù)，表示所求元素的起始位置和終止位置。
如果數(shù)組中不存在該元素，則返回?-1 -1。
數(shù)據(jù)范圍
1≤n≤1000001≤n≤100000
1≤q≤100001≤q≤10000
1≤k≤100001≤k≤10000
輸入樣例：
6 3 1 2 2 3 3 4 3 4 5輸出樣例：
3 4 5 5 -1 -1?思路：先對數(shù)組排序 分別求>=k 的最小值 以及<=k的最大值即可
import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int q=sc.nextInt();int[] nums=new int[n];for(int i=0;i<n;i++){nums[i]=sc.nextInt();}while(q-->0){int k=sc.nextInt();int l=0;int r=n-1;while(l<r){int mid=r+l>>1;if(nums[mid]>=k){r=mid;}else{l=mid+1;}}if(nums[l]==k){System.out.print(l+" ");l=0;r=n-1;while(l<r){int mid=l+r+1>>1;if(nums[mid]<=k){l=mid;}else{r=mid-1;}}System.out.print(l);//上一個找的到 這個就一定找得到}else{System.out.printf("%d %d",-1,-1);}System.out.println();}} }例題二：數(shù)的三次方根
給定一個浮點數(shù)?nn，求它的三次方根。
輸入格式
共一行，包含一個浮點數(shù)?nn。
輸出格式
共一行，包含一個浮點數(shù)，表示問題的解。
注意，結果保留?66?位小數(shù)。
數(shù)據(jù)范圍
?10000≤n≤10000?10000≤n≤10000
輸入樣例：
1000.00輸出樣例：
10.000000思路：由于浮點數(shù)二分不存在取整問題 因此每次的范圍必定縮小一半 我們只需要控制 當l和r之間的差值要多小的時候將它看作一個數(shù)即可?
易錯點：浮點數(shù)求mid時不能使用l+r>>1? 必須使用（l+r）/2?? ?
import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);double n=sc.nextDouble();double l=-10000;double r=10000;while(r-l>1e-8){//精度通常比題目高兩位double mid=(l+r)/2;if(mid*mid*mid>=n){r=mid;}else{l=mid;}}System.out.printf("%.6f",l);} }4、前綴和與差分
例題一：前綴和
前綴和 顧名思義 假設有一個數(shù)組a 那么他的前綴和數(shù)組 b 中任一元素 b【i】就表示 a0+a1+...+a[i-1]+a[i]?
前綴和的作用：如果我們要求a數(shù)組中某一段數(shù)組的和 我們就可以用o（1）的復雜度求出
假設要求a中 l到 r 范圍的和 我們只需計算 b[r]-b[l-1]
輸入一個長度為?nn?的整數(shù)序列。
接下來再輸入?mm?個詢問，每個詢問輸入一對?l,rl,r。
對于每個詢問，輸出原序列中從第?ll?個數(shù)到第?rr?個數(shù)的和。
輸入格式
第一行包含兩個整數(shù)?nn?和?mm。
第二行包含?nn?個整數(shù)，表示整數(shù)數(shù)列。
接下來?mm?行，每行包含兩個整數(shù)?ll?和?rr，表示一個詢問的區(qū)間范圍。
輸出格式
共?mm?行，每行輸出一個詢問的結果。
數(shù)據(jù)范圍
1≤l≤r≤n1≤l≤r≤n,
1≤n,m≤1000001≤n,m≤100000,
?1000≤數(shù)列中元素的值≤1000?1000≤數(shù)列中元素的值≤1000
輸入樣例：
5 3 2 1 3 6 4 1 2 1 3 2 4輸出樣例：
3 6 10 import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();//接受數(shù)組的長度int m=sc.nextInt();//m個詢問int[] a=new int[n+1];//前綴和數(shù)組 為什么數(shù)組長度多開了一個1 int[] b=new int[n+1];//因為我們a[i]=a[i-1]+b[i] 多開一個1不需要對0特殊處理for(int i=1;i<=n;i++){b[i]=sc.nextInt();}for(int i=1;i<=n;i++){a[i]=a[i-1]+b[i];}while(m-->0){int l=sc.nextInt();int r=sc.nextInt();System.out.println(a[r]-a[l-1]);}} }例題二：子矩陣和
輸入一個?nn?行?mm?列的整數(shù)矩陣，再輸入?qq?個詢問，每個詢問包含四個整數(shù)?x1,y1,x2,y2x1,y1,x2,y2，表示一個子矩陣的左上角坐標和右下角坐標。
對于每個詢問輸出子矩陣中所有數(shù)的和。
輸入格式
第一行包含三個整數(shù)?n，m，qn，m，q。
接下來?nn?行，每行包含?mm?個整數(shù)，表示整數(shù)矩陣。
接下來?qq?行，每行包含四個整數(shù)?x1,y1,x2,y2x1,y1,x2,y2，表示一組詢問。
輸出格式
共?qq?行，每行輸出一個詢問的結果。
數(shù)據(jù)范圍
1≤n,m≤10001≤n,m≤1000,
1≤q≤2000001≤q≤200000,
1≤x1≤x2≤n1≤x1≤x2≤n,
1≤y1≤y2≤m1≤y1≤y2≤m,
?1000≤矩陣內(nèi)元素的值≤1000?1000≤矩陣內(nèi)元素的值≤1000
輸入樣例：
3 4 3 1 7 2 4 3 6 2 8 2 1 2 3 1 1 2 2 2 1 3 4 1 3 3 4輸出樣例：
17 27 21思路：本質(zhì)上就是二維的前綴和 只需要更改求前綴和的公式 此時a[i][j] 代表的是b中i，j左上部分所有的和? 因此更改 前綴和計算公式為 a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j]即可 而我們要求子矩陣的和 就是 a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1]??
import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();int q=sc.nextInt();int[][] b=new int[n+1][m+1];int[][] a=new int[n+1][m+1];//前綴和數(shù)組for(int i=1;i<=n;i++){ //接受數(shù)據(jù)for(int j=1;j<=m;j++){b[i][j]=sc.nextInt();}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];//二維前綴和求和公式}}while(q-->0){int x1=sc.nextInt();int y1=sc.nextInt();int x2=sc.nextInt();int y2=sc.nextInt();System.out.println(a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1]);}} }例題三：差分?
差分：假設a數(shù)組是b數(shù)組的前綴和數(shù)組 那么b就是a的差分 b【i】=a【i】-a【i-1】
差分的用處：假設我們要給a數(shù)組 l~r 范圍都加一個整數(shù)c 正常來說我們必須要依次把 l~r 范圍內(nèi)依次加c 但如果我們有差分數(shù)組 我們只要更改 b【i】+=c 由于a是b的前綴和 a中i 以后的元素都會多加一個c 我們再把b【r+1】-=c 那么 r+1之后的數(shù)又會少一個c 以此實現(xiàn) i~r 范圍內(nèi)數(shù)據(jù)的加值運算
易錯點：首先要明白 a數(shù)組并不會隨著b數(shù)組的改變而改變 因為即使有前綴和的定義 當b數(shù)組發(fā)生變化是 a數(shù)組是要重新求一編前綴和的? 有人可能會問：那我要這差分數(shù)組有什么用 ？
差分的作用體現(xiàn)在多次詢問時 我們只需要改變b這個差分數(shù)組多次 然后最后只求一次前綴和即可！
import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();int[] b=new int[n+2];//由于插入時涉及到 r+1 所以我們要多留一個空間 以防止數(shù)組越界for(int i=1;i<=n;i++){//我們沒有必要可以構建差分數(shù)組 采用插入的方式構建差分數(shù)組int c=sc.nextInt();insert(b,i,i,c);}while(m-->0){int l=sc.nextInt();int r=sc.nextInt();int c=sc.nextInt();insert(b,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[] b,int l,int r,int c){b[l]+=c;b[r+1]-=c;} }三個小tips：
1、開數(shù)組多開了一個 因為我們要用到b【r+1】+=c 這部操作 防止數(shù)組越界
2、其實我們沒有必要去構造b差分數(shù)組 想象一開始a數(shù)組中全為0 我們通過不斷插入 i~i 下表內(nèi) +a【i】?
3、最后求前綴和的時候其實有一步驟不容易看出 就是?b[i]+=b[i-1]; 為什么這一步可以求前綴和 而不是 b0+b1+。。。+b【i】 因為在我們i-1的步驟里 b【i-1】的定義已經(jīng)變成前綴和了?
因此我們求b【i】（前綴和）時只需要加上原來的b【i】（差分數(shù)組）即可
例題四：差分矩陣
輸入一個?n?行?m?列的整數(shù)矩陣，再輸入?qq?個操作，每個操作包含五個整數(shù)?x1,y1,x2,y2,cx1,y1,x2,y2,c，其中?(x1,y1)(x1,y1)?和?(x2,y2)(x2,y2)?表示一個子矩陣的左上角坐標和右下角坐標。
每個操作都要將選中的子矩陣中的每個元素的值加上?cc。
請你將進行完所有操作后的矩陣輸出。
輸入格式
第一行包含整數(shù)?n,m,qn,m,q。
接下來?nn?行，每行包含?mm?個整數(shù)，表示整數(shù)矩陣。
接下來?qq?行，每行包含?55?個整數(shù)?x1,y1,x2,y2,cx1,y1,x2,y2,c，表示一個操作。
輸出格式
共?nn?行，每行?mm?個整數(shù)，表示所有操作進行完畢后的最終矩陣。
數(shù)據(jù)范圍
1≤n,m≤10001≤n,m≤1000,
1≤q≤1000001≤q≤100000,
1≤x1≤x2≤n1≤x1≤x2≤n,
1≤y1≤y2≤m1≤y1≤y2≤m,
?1000≤c≤1000?1000≤c≤1000,
?1000≤矩陣內(nèi)元素的值≤1000?1000≤矩陣內(nèi)元素的值≤1000
輸入樣例：
3 4 3 1 2 2 1 3 2 2 1 1 1 1 1 1 1 2 2 1 1 3 2 3 2 3 1 3 4 1輸出樣例：
2 3 4 1 4 3 4 1 2 2 2 2很明顯 這道題要求我們把矩陣中的數(shù)字都加c 很容易想得到差分 但是對一個子矩陣中的值+c 應該如何計算呢？? 首先我們構建差分矩陣? b[x1][y1]+c 那么它的右下部分都將加上一個c 因此 我們需要 把 b[x2+1][y1]-c? ? ?b[x1][y2+1]-c? ? ? b[x2+1][y2+1]+c
那求前綴和公式呢？
b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j]
import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();int q=sc.nextInt();int[][] b=new int[n+2][m+2];for(int i=1;i<=n;i++){ //構建差分數(shù)組for(int j=1;j<=m;j++){int c=sc.nextInt();insert(b,i,j,i,j,c);}}while(q-->0){int x1=sc.nextInt();int y1=sc.nextInt();int x2=sc.nextInt();int y2=sc.nextInt();int c=sc.nextInt();insert(b,x1,y1,x2,y2,c);}for(int i=1;i<=n;i++){ //求前綴和for(int j=1;j<=m;j++){b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];}}for(int i=1;i<=n;i++){ //輸出矩陣for(int j=1;j<=m;j++){System.out.print(b[i][j]+" ");}System.out.println();}}public static void insert(int[][] b,int x1,int y1,int x2,int y2,int c){b[x1][y1]+=c;b[x1][y2+1]-=c;b[x2+1][y1]-=c;b[x2+1][y2+1]+=c;} }5、雙指針算法
雙指針應該是我們很常見的一種算法，一般分為兩種
一種是在兩個數(shù)組中兩個指針移動，例如我們在歸并中用到過的合并兩個有序數(shù)組
另一種是在同一個區(qū)間 ，根據(jù)兩個指針的前后關系來完成某些邏輯
例題一：最長連續(xù)不重復子序列
給定一個長度為?nn?的整數(shù)序列，請找出最長的不包含重復的數(shù)的連續(xù)區(qū)間，輸出它的長度。
輸入格式
第一行包含整數(shù)?nn。
第二行包含?nn?個整數(shù)（均在?0～1050～105?范圍內(nèi)），表示整數(shù)序列。
輸出格式
共一行，包含一個整數(shù)，表示最長的不包含重復的數(shù)的連續(xù)區(qū)間的長度。
數(shù)據(jù)范圍
1≤n≤1051≤n≤105
輸入樣例：
5 1 2 2 3 5輸出樣例：
3思路：我們維持兩個指針 i 和 j ，使得我們目前的不重復連續(xù)子序列永遠處于 i 到 j ，如果 我們當前區(qū)間沒有重復元素就擴充i，否則就需要通過移動 j 來實現(xiàn)“去重”，每次移動 i 時 都要判斷一次當前長度是不是最大長度的連續(xù)不重復子序列? 最后返回最大的長度即可
import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int[] nums=new int[n];for(int i=0;i<n;i++){nums[i]=sc.nextInt();} int[] a=new int[100010];//這里采用一種“桶”去重int j=0;//以 i 結尾 以 j 開頭 是我們要計算的不重復子序列的長度int res=-1;for(int i=0;i<n;i++){a[nums[i]]++; //桶里對應的nums【i】++ 表示這個數(shù) 在我們當前序列至少存在一個了while(a[nums[i]]>1){ //由于我們維持的是一個不重復序列 如果產(chǎn)生了重復 那一定是因為i的加入a[nums[j]]--; //去掉最后面的數(shù) 想要維持不重復的子區(qū)間 直到找到 “內(nèi)鬼”j++;}res=Math.max(res,i-j+1);}System.out.print(res);} }tips:這里采用了一種“桶”的方式去重 當然 我們也可以用hashmap 記錄當前元素上一次出現(xiàn)的下標 然后j在此位置上+1即可?
例題二：數(shù)組元素的目標和
給定兩個升序排序的有序數(shù)組?AA?和?BB，以及一個目標值?xx。
數(shù)組下標從?00?開始。
請你求出滿足?A[i]+B[j]=xA[i]+B[j]=x?的數(shù)對?(i,j)(i,j)。
數(shù)據(jù)保證有唯一解。
輸入格式
第一行包含三個整數(shù)?n,m,xn,m,x，分別表示?AA?的長度，BB?的長度以及目標值?xx。
第二行包含?nn?個整數(shù)，表示數(shù)組?AA。
第三行包含?mm?個整數(shù)，表示數(shù)組?BB。
輸出格式
共一行，包含兩個整數(shù)?ii?和?jj。
數(shù)據(jù)范圍
數(shù)組長度不超過?105105。
同一數(shù)組內(nèi)元素各不相同。
1≤數(shù)組元素≤1091≤數(shù)組元素≤109
輸入樣例：
4 5 6 1 2 4 7 3 4 6 8 9輸出樣例：
1 1思路：首先題目說明兩個數(shù)組已經(jīng)有序 我們創(chuàng)建兩個指針 i 和 j? ，i 指向第一個數(shù)組的開頭
j 指向第二個數(shù)組的末尾 ， 每次都計算 nums1【i】+nums2【j】 如果大于x 那么 j 肯定得 --
?因為i后邊的元素都是大于nums1【i】的，所以不可能湊出x 如果小于x 那么 x 肯定得++ 因為j 已經(jīng)是最大的了 要想更大 只能通過移動 i ！?
import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();int[] nums1=new int[n+1];int[] nums2=new int[m+1];int x=sc.nextInt();for(int i=0;i<n;i++){nums1[i]=sc.nextInt();}for(int i=0;i<m;i++){nums2[i]=sc.nextInt();}int j=m-1;for(int i=0;i<n;i++){while(nums1[i]+nums2[j]>x){j--;}if(nums1[i]+nums2[j]==x){System.out.print(i+" "+j);break;}}} }例題三：判斷子序列
給定一個長度為?nn?的整數(shù)序列?a1,a2,…,ana1,a2,…,an?以及一個長度為?mm?的整數(shù)序列?b1,b2,…,bmb1,b2,…,bm。
請你判斷?aa?序列是否為?bb?序列的子序列。
子序列指序列的一部分項按原有次序排列而得的序列，例如序列?{a1,a3,a5}{a1,a3,a5}?是序列?{a1,a2,a3,a4,a5}{a1,a2,a3,a4,a5}?的一個子序列。
輸入格式
第一行包含兩個整數(shù)?n,mn,m。
第二行包含?nn?個整數(shù)，表示?a1,a2,…,ana1,a2,…,an。
第三行包含?mm?個整數(shù)，表示?b1,b2,…,bmb1,b2,…,bm。
輸出格式
如果?aa?序列是?bb?序列的子序列，輸出一行?Yes。
否則，輸出?No。
數(shù)據(jù)范圍
1≤n≤m≤1051≤n≤m≤105,
?109≤ai,bi≤109?109≤ai,bi≤109
輸入樣例：
3 5 1 3 5 1 2 3 4 5輸出樣例：
Yes思路：很簡單的一道題 定義兩個指針分別指向 數(shù)組一 和 數(shù)組二 如果nums【i】==nums【j】如果匹配完了所有的 nums1中的元素 也就是i 成功走到了最后 則說明找到了返回yes?如果沒找到 返回no即可?
import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();int[] nums1=new int[n];int[] nums2=new int[m];for(int i=0;i<n;i++){nums1[i]=sc.nextInt();}for(int j=0;j<m;j++){nums2[j]=sc.nextInt();}int i=0;for(int j=0;j<m;j++){if(i>=n) break;if(nums1[i]==nums2[j]) i++;}if(i==n) {System.out.print("Yes");}else{System.out.print("No");}} }tips:雙指針是一種很巧妙的方法，他能把時間復雜度O（N^2) 變?yōu)镺（N）
為什么for循環(huán)里有個while 還是O（n）的時間復雜度呢？? 其實我們換個角度分析 每個數(shù)i 和j 都只經(jīng)過一次 所以總的來說計算次數(shù)應該是 2n 時間復雜度自然是 O（N）??
6、位運算
這里只介紹兩種運算：
1、計算二進制第k位? 只需把元素>> k位? 再&1 如果他是0 得到的就是0 如果是1 得到的就是1
2、獲取二進制最后一位1 首先我們要明白整數(shù)取他的負數(shù) 二進制代碼其實是反碼+1，那么我們通過 x&-x就能得到最后一位1所對應的整數(shù)
例題一：二進制中一的個數(shù)
給定一個長度為?nn?的數(shù)列，請你求出數(shù)列中每個數(shù)的二進制表示中?11?的個數(shù)。
輸入格式
第一行包含整數(shù)?nn。
第二行包含?nn?個整數(shù)，表示整個數(shù)列。
輸出格式
共一行，包含?nn?個整數(shù)，其中的第?ii?個數(shù)表示數(shù)列中的第?ii?個數(shù)的二進制表示中?11?的個數(shù)。
數(shù)據(jù)范圍
1≤n≤1000001≤n≤100000,
0≤數(shù)列中元素的值≤1090≤數(shù)列中元素的值≤109
輸入樣例：
5 1 2 3 4 5輸出樣例：
1 1 2 1 2思路：上邊我們講過獲取最后一位1對應的整數(shù) 的方式 因此我們可以通過 不斷地獲取最后一位1 然后再讓x-=這個獲取到的數(shù) 直到它為0? 我們只需要記錄次數(shù)即可?
import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int[] nums=new int[n];for(int i=0;i<n;i++){nums[i]=sc.nextInt();}for(int i=0;i<n;i++){int res=0;while(nums[i]!=0){nums[i]-=nums[i]&-nums[i];res++;}System.out.print(res+" ");}} }7、離散化
離散化，把無限空間中有限的個體映射到有限的空間中去，以此提高算法的時空效率。
通俗的說，離散化是在不改變數(shù)據(jù)相對大小的條件下，對數(shù)據(jù)進行相應的縮小。例如：
原數(shù)據(jù)：1,999,100000,15；處理后：1,3,4,2；
原數(shù)據(jù)：{100,200}，{20,50000}，{1,400}；
處理后：{3,4}，{2,6}，{1,5}；
例題一：區(qū)間和
假定有一個無限長的數(shù)軸，數(shù)軸上每個坐標上的數(shù)都是?00。
現(xiàn)在，我們首先進行?nn?次操作，每次操作將某一位置?xx?上的數(shù)加?cc。
接下來，進行?mm?次詢問，每個詢問包含兩個整數(shù)?ll?和?rr，你需要求出在區(qū)間?[l,r][l,r]?之間的所有數(shù)的和。
輸入格式
第一行包含兩個整數(shù)?nn?和?mm。
接下來?nn?行，每行包含兩個整數(shù)?xx?和?cc。
再接下來?mm?行，每行包含兩個整數(shù)?ll?和?rr。
輸出格式
共?mm?行，每行輸出一個詢問中所求的區(qū)間內(nèi)數(shù)字和。
數(shù)據(jù)范圍
?109≤x≤109?109≤x≤109,
1≤n,m≤1051≤n,m≤105,
?109≤l≤r≤109?109≤l≤r≤109,
?10000≤c≤10000?10000≤c≤10000
輸入樣例：
3 3 1 2 3 6 7 5 1 3 4 6 7 8輸出樣例：
8 0 5思路：這道題看起來字數(shù)很多 似乎很嚇人? 但其實我們仔細看一眼就發(fā)現(xiàn) 這不就是個求前綴和嘛? 但是題目說了數(shù)據(jù)范圍是10^9 但數(shù)據(jù)個數(shù)是10^5 因此我們自然而然想到用離散化節(jié)省空間?
再分析 ，題目說了 n次 操作 m 次查詢 一次查詢肯定是兩個下標 ，因此我們數(shù)組地大小肯定要達到3*(10^5)? ? ?
其次，查詢和操作一次都是兩個元素的，因此我們額外定義一個類Pair 里邊含有兩個元素 first 和 second?
在離散化的時候是需要查找下標的 我們通過二分來查找 因此首先要對數(shù)組進行排序并且去重? ? ?在存操作和詢問時 我們用ArrayList來存儲?
import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();int[] a=new int[300010];//離散化后的數(shù)組int[] s=new int[300010];//前綴和數(shù)組List<Integer> alls=new ArrayList();//存儲下標List<Pair> add=new ArrayList();List<Pair> query=new ArrayList();while(n-->0){ //操作int x=sc.nextInt();int c=sc.nextInt();add.add(new Pair(x,c));alls.add(x);}for(int i=0;i<m;i++){ //先把查詢下標錄入alls和queryint l=sc.nextInt();int r=sc.nextInt();query.add(new Pair(l,r));alls.add(l);alls.add(r);}Collections.sort(alls);int unique=unique(alls);alls=alls.subList(0,unique);for(Pair item:add){ //離散加值處理int index=find(alls,item.first);a[index]+=item.second;}for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i]; //求前綴和for(Pair item:query){ //查詢int l=find(alls,item.first);int r=find(alls,item.second);System.out.println(s[r]-s[l-1]);}}public static int find(List<Integer> alls,int x){ //查找離散后下標 int l=0;int r=alls.size()-1;while(l<r){int mid=l+r>>1;if(alls.get(mid)>=x){r=mid;}else{l=mid+1;}}return l+1; // 多加1是為了方便前綴和的求解}public static int unique(List<Integer> alls){int n=alls.size();int j=0;for(int i=0;i<n;i++){if(i==0||alls.get(i)!=alls.get(i-1)){alls.set(j++,alls.get(i));}}return j;} }class Pair{int first;int second;public Pair(int first,int second){this.first=first;this.second=second;}}tips：離散化其實利用了數(shù)之間的相對大小 把他們的大小順序映射為a數(shù)組的下標 ，進而節(jié)省了空間，當我們需要查找一個數(shù)的下標時，我們也只需要二分查找即可? 但是這道題求的是前綴和 其中不乏一些小細節(jié) 比如l+1 是為了后邊方便求前綴和等等 確實是一道很好的離散化題目?
8、區(qū)間合并
區(qū)間合并本質(zhì)上來說像是貪心？ 但是本質(zhì)上并不難理解 代碼也很簡單 ，先對數(shù)組進行排序? 維持start和end 區(qū)間? 如果當前區(qū)間的start<end? 那么就涉及合并 否則把前一個start ~end? 加入到結果集中 最后循環(huán)結束 把剩余的一對start和end 加入到結果集中即可?
例題一：區(qū)間合并
給定?nn?個區(qū)間?[li,ri][li,ri]，要求合并所有有交集的區(qū)間。
注意如果在端點處相交，也算有交集。
輸出合并完成后的區(qū)間個數(shù)。
例如：[1,3][1,3]?和?[2,6][2,6]?可以合并為一個區(qū)間?[1,6][1,6]。
輸入格式
第一行包含整數(shù)?nn。
接下來?nn?行，每行包含兩個整數(shù)?ll?和?rr。
輸出格式
共一行，包含一個整數(shù)，表示合并區(qū)間完成后的區(qū)間個數(shù)。
數(shù)據(jù)范圍
1≤n≤1000001≤n≤100000,
?109≤li≤ri≤109?109≤li≤ri≤109
輸入樣例：
5 1 2 2 4 5 6 7 8 7 9輸出樣例：
3 import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);List<Pair> query=new ArrayList();int n=sc.nextInt();for(int i=0;i<n;i++){int l=sc.nextInt();int r=sc.nextInt();query.add(new Pair(l,r));}Collections.sort(query);int st=(int)-1e9;int ed=(int)-1e9;List<Pair> res=new ArrayList();//存放無法合并的數(shù)組for(Pair item:query){if(ed<item.first){if(ed!=-1e9) res.add(new Pair(st,ed));st=item.first;ed=item.second;}else{ed=Math.max(ed,item.second);}}if(ed!=(int)-1e9) res.add(new Pair(st,ed)); //記得最后我們退出循環(huán)時 是沒有對上一步做總結的System.out.print(res.size());} } class Pair implements Comparable<Pair>{int first;int second;public Pair(int first,int second){this.first=first;this.second=second;}public int compareTo(Pair o){return Integer.compare(first,o.first);} }tips：此處必須要用一個list來存放無法合并的數(shù)組 而不能用res去記錄合并的次數(shù) 因為最后我們要返回的是 無法合并數(shù)組的個數(shù) 而不是你合并了多少次！
還有就是排序時 默認Pair類是無法比較的 所以我們重寫compare方法 ！
以上就是我目前總結的算法筆記第一章啦 所有內(nèi)容均來自yxc老師的算法基礎課 ~? 由于筆者水平有限 總結地方不乏一些錯誤 懇請大家斧正? 也歡迎大家來評論區(qū)交流算法~~
感謝閱讀！
總結
以上是生活随笔為你收集整理的算法笔记（一）（教你系统学习基础算法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： CvScalar
- 下一篇： Bootstrap table后端分页（