ACWing——算法基礎課

置頂思考：
算法的本質是什么樣的思想？
這種思想可以解決哪類問題？
有沒有其他的解決思路？
關注數值范圍，思考可不可以針對性解決問題？

在這里插入圖片描述

排序

785.快速排序
原地算法，不需要額外開辟空間
const int N = 1000010;可以寫成 1e6+10；
c++中用scanf接受數據很快，不要用cin
Java中用buffer read，不要用scanner
基準元素取端點在某些數據增強的情況下會超時，建議取中點
平均nlogn,最差n方

const int N=1e6+10;
int q[N];
void quickSort(int q[],int low,int high){if(low>=high)return;int i=low-1;int j=high+1;int temp=q[low+high>>1];while(i<j){do i++;while(temp>q[i]);do j--;while(temp<q[j]);if(i<j) swap(q[i],q[j]);}quickSort(q,low,j);quickSort(q,j+1,high);}

787. 歸并排序
妥妥nlogn

const int N = 1e6+10;
int q[N];
int temp[N];void mergeSort(int q[],int low,int high){if(low>=high) return;int mid=low+high>>1;int k=0;int i=low;int j=mid+1;mergeSort(q,low,mid);mergeSort(q,mid+1,high);while(i<=mid && j<=high) temp[k++]=q[i]<=q[j]?q[i++]:q[j++];while(i<=mid) temp[k++]=q[i++];while(j<=high) temp[k++]=q[j++];for (i=low,j=0; i <= high; i ++,j++ ) q[i]=temp[j];	
}

788. 逆序對的數量(歸并)
歸并子題
注意范圍超限，要使用long long
從兩個元素起，計算逆序對數，子數組排序，外部的相對位置關系并沒有改變

二分法

剪枝思想，縮小遍歷范圍，以降低時間復雜度
有單調性的題目一定可以二分法降低時間復雜度
無單調性有時也可以二分
二分問題的關鍵是邊界問題，需要考慮邊界范圍采用兩套模板
二分問題無非以下兩類：
左邊界問題：找滿足某個條件的第一個數——找大于等于某個數的第一個位置——r=mid;l=mid+1;
右邊界問題：找滿足某個條件的最后一個數——找小于等于某個數的最后一個位置——l=mid;r=mid-1;

//查找左邊界 SearchLeft 簡寫SL
int SL(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid; //找左邊界，r就要等于midelse l = mid + 1; }   return l;
}//查找右邊界 記憶方面：有加必右減（有+1，r就要mid-1）
int SR(int l, int r) 
{while (l < r){                   int mid = l + r + 1 >> 1; //需要+1 防止死循環if (check(mid)) l = mid;//找右邊界，l要等于midelse r = mid - 1; }return r; 
}

789. 數的范圍（二分）

790. 數的三次方根
逆向思維，將求根的問題轉化為，求冪的問題
printf(“%lf”,flo)默認輸出六位小數
當你要求六位精度時，計算時要增加兩位，至少求八位精度

高精度整數問題

加法：位數1e6
減法：位數1e6
乘法：位數1e6，數值1e9
除法
python和java自帶高精度函數
c++的vector作為數組存儲有size屬性，很方便
‘9’-‘0’=9(數字)
適當添加引用&，可以防止整個數組的復制，加快速度
思想：把數的每一位存入數組，從低位到高位存，個位放a[0]的位置
在這里插入圖片描述

注意學習Vector

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/bicheng/78362.shtml
繁體地址，請注明出處：http://hk.pswp.cn/bicheng/78362.shtml
英文地址，請注明出處：http://en.pswp.cn/bicheng/78362.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！