基础算法汇总
admin
2024-03-05 06:16:56
0次

文章目录

    • 一、快速排序
      • 1. 快排
      • 2.第k个值(快排应用)
    • 二、归并排序
      • 3.归并排序
      • 4.逆序对(归并应用)
    • 三、二分
      • 5.数的范围(二分应用)
      • 6.数的三次方根(二分应用)
    • 四、高精度
      • 7.高精度加法
      • 8.高精度减法
      • 9.高精度乘法
      • 10.高精度除法
    • 五、前缀和与差分
      • 11.前缀和
      • 12.子矩阵的和(前缀和)
      • 13.差分(前缀和的逆运算)
      • 14.差分矩阵
    • 六、双指针
      • 15.最长连续不重复子序列(双指针)
      • 16.判断子序列
    • 七、位运算
      • 17.位运算
    • 八、离散化
      • 18.区间和(离散化:域很大,点稀疏)
    • 九、区间合并
      • 19.区间合并

一、快速排序

1. 快排

	static void sort(int[]arrays,int left,int right){if(left>=right)return;int ans=arrays[left];int l=left,r=right;while(leftwhile(left=ans){right--;}arrays[left]=arrays[right];while(leftleft++;}arrays[right]=arrays[left];}arrays[left]=ans;sort(arrays,l,left-1);sort(arrays,left+1,r);}

2.第k个值(快排应用)

    import java.util.*;public class Main{static int N = 100010;static int n;static int k;static int[] nums=new int[N];static int sort(int k,int l,int r){if(l>=r)return nums[k];int ans=nums[l],i=l-1,j=r+1;while(ido i++;while(nums[i]ans);if(iint tmp=nums[i];nums[i]=nums[j];nums[j]=tmp;}}if(k<=j)return sort(k,l,j);else return sort(k,j+1,r);}public static void main(String[]args){Scanner scanner=new Scanner(System.in);n=scanner.nextInt();k=scanner.nextInt();for(int i=0;inums[i]=scanner.nextInt();}System.out.println(sort(k-1,0,n-1));}}

二、归并排序

3.归并排序

    import java.util.*;public class Main{static int N = 100010;static int n;static int[]nums = new int[N];static int[]tmps = new int[N];static void sort(int l,int r){if(l>=r)return;int mid=(r+l)/2;sort(l,mid);sort(mid+1,r);int i=l,j=mid+1,k=0;while(i<=mid&&j<=r){if(nums[i]tmps[k++]=nums[i++];}else{ tmps[k++]=nums[j++];}}while(i<=mid){tmps[k++]=nums[i++];}while(j<=r){tmps[k++]=nums[j++];}for(int t=0,s=l;s<=r;t++,s++){nums[s]=tmps[t];}}public static void main(String[]args){Scanner scanner = new Scanner(System.in);n=scanner.nextInt();for(int i=0;inums[i]=scanner.nextInt();}sort(0,n-1);for(int i=0;iSystem.out.print(nums[i]+" ");}}}

4.逆序对(归并应用)

 	static long get(int l,int r){if(l>=r)return 0;int mid=(r+l)/2;long res=get(l,mid)+get(mid+1,r);int i=l,j=mid+1,k=0;while(i<=mid&&j<=r){if(nums[i]<=nums[j]){tmps[k++]=nums[i++];}else{ tmps[k++]=nums[j++];res+=mid-i+1;}}while(i<=mid){tmps[k++]=nums[i++];}while(j<=r){tmps[k++]=nums[j++];}for(int t=0,s=l;s<=r;t++,s++){nums[s]=tmps[t];}return res;}

三、二分

5.数的范围(二分应用)

  	import java.util.*;public class Main{public static void main(String[] args){Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();int q=scanner.nextInt();int[] nums=new int[n];for(int i=0;inums[i]=scanner.nextInt();}for(int i=0;iint target=scanner.nextInt();int l=0,r=n-1;//找左边界while(lint mid=(l+r)/2;if(nums[mid]>=target){r=mid;}else {l=mid+1;}}if(nums[l]!=target){System.out.println("-1 -1");}else{System.out.print(l+" ");l=0;r=n-1;//找右边界while(lint mid=(l+r+1)/2;if(nums[mid]<=target){l=mid;}else {r=mid-1;}}System.out.println(l+" ");}}}}

6.数的三次方根(二分应用)

 	import java.util.*;public class Main{public static void main(String[]args){Scanner scanner=new Scanner(System.in);double n=scanner.nextDouble();double l=-1000,r=1000;while(r-l>1e-8){double mid = (l+r)/2.0;if(mid*mid*mid>=n){r=mid;}else{l=mid;}}System.out.printf("%.6f",l);}}

四、高精度

7.高精度加法

	List res = new ArrayList<>();int k=0;for(int i=0;iif(ik+=aa.get(i);}if(ik+=bb.get(i);}res.add(k%10);k=k/10;}if(k>0){res.add(1);}

8.高精度减法

	static void subtract(ArrayList a,ArrayListb){int k=0;for(int i=0;ik=a.get(i)-k;if(ik-=b.get(i);}res.add((k+10)%10);if(k<0)k=1;else k=0;}while(res.size()>1&&res.get(res.size()-1)==0){res.remove(res.size()-1);}}

9.高精度乘法

	static void multiply(){for(int i=0,t=0;i0;i++){if(it+=aa.get(i)*b;}res.add(t%10);t=t/10;}//去除前导零while(res.size()>1&&res.get(res.size()-1)==0){res.remove(res.size()-1);}}

10.高精度除法

	static void div(){r=0;for(int i=0;ir=r*10+nums.get(i);res.add(r/b);r=r%b;}while(res.size()>1&&res.get(0)==0){res.remove(0);}}

五、前缀和与差分

11.前缀和

	for(int i=0;isum[i+1]=sum[i]+nums[i];}

12.子矩阵的和(前缀和)

  for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+nums[i][j];}}System.out.println(sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]);

13.差分(前缀和的逆运算)

Bi=Ai-A(i-1)

Bi的前缀和就是A数组

Ai=Bi+B(i-1)+…+B1

    //接下来输入 m 个操作,每个操作包含三个整数 l,r,c,表示将序列中 [l,r] 之间的每个数加上 cimport java.util.*;public class Main{static final int N = 100010;static int[]a=new int[N];static int[]b=new int[N];static void insert(int l,int r,int c){b[l]+=c;b[r+1]-=c;}public static void main(String[]args){Scanner scanner = new Scanner(System.in);int n=scanner.nextInt();int m=scanner.nextInt();for(int i=1;i<=n;i++){a[i]=scanner.nextInt();insert(i,i,a[i]);}for(int i=0;iint l=scanner.nextInt();int r=scanner.nextInt();int c=scanner.nextInt();insert(l,r,c);}for(int i=1;i<=n;i++){b[i]+=b[i-1];}for(int i=1;i<=n;i++){System.out.print(b[i]+" ");}}}

14.差分矩阵

    static void insert(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;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){insert(i,j,i,j,a[i][j]);}}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];}}

六、双指针

15.最长连续不重复子序列(双指针)

  import java.util.*;class Main{public static void main(String[] args){Scanner scanner=new Scanner(System.in);int[] as=new int[100005];int n=scanner.nextInt();int[] nums=new int[n];for(int i=0;inums[i]=scanner.nextInt();}int res=0;for(int i=0,j=0;iwhile(jas[nums[j]]++;j++;}res=Math.max(res,j-i);as[nums[i]]--;}System.out.println(res);}}

16.判断子序列

  int i=0,j=0;while(iif(a[i]==b[j])i++;j++;}

七、位运算

17.位运算

n的二进制第k位是几

  public static void main(String[] args) {int n=10;for(int k=3;k>=0;k--) {System.out.print(n>>k&1);}}

lowbit(x):返回x的最后一位1

eg: 10=>1010,lowbit(10)=10

-x=(~x+1)

  static long lowbit(long x){return x&(-x);}

二进制中1的个数

	import java.util.*;public class Main {static long lowbit(long x){return x&(-x);}public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();while((n--)>0){long k=scanner.nextLong();int cnt=0;while(k>0){k-=lowbit(k);cnt++;}System.out.print(cnt+" ");}}}

八、离散化

18.区间和(离散化:域很大,点稀疏)

   	import java.util.*;public class Main {static final int N = 300010;// 记录每个坐标static ArrayList alls = new ArrayList<>();static int find(int x) {int l = 0, r = alls.size() - 1;while (l < r) {int mid = l + r >> 1;if (alls.get(mid) >= x)r = mid;elsel = mid + 1;}return r + 1;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();// 离散化对应的值int[] a = new int[N];// 前缀和int[] s = new int[N];// 保存添加的位置和值ArrayList add = new ArrayList<>();// 保存求和区间ArrayList query = new ArrayList<>();for (int i = 0; i < n; i++) {int x = scanner.nextInt();int c = scanner.nextInt();add.add(new Pair(x, c));alls.add(x);}for (int i = 0; i < m; i++) {int l = scanner.nextInt();int r = scanner.nextInt();query.add(new Pair(l, r));alls.add(l);alls.add(r);}// 对alls进行去重并排序alls = new ArrayList(new HashSet<>(alls));Collections.sort(alls);// 进行离散化for (Pair pair : add) {int x=find(pair.first);a[x]+=pair.second;}//前缀和for(int i=1;i<=alls.size();i++) {s[i]=s[i-1]+a[i];}for(Pair pair:query) {int l=find(pair.first);int r=find(pair.second);System.out.println(s[r]-s[l-1]);}}}class Pair {int first;int second;public Pair(int first, int second) {this.first = first;this.second = second;}public String toString() {return first + " " + second;}}

九、区间合并

19.区间合并

 	import java.util.*;public class Main {static ArrayList merge(ArrayList list) {ArrayList res = new ArrayList();int st=(int) -2e9,ed=(int) -2e9;for(Pair pair:list) {if(edif(st!=-2e9) {res.add(new Pair(st, ed));}st=pair.first;ed=pair.second;}else {ed=Math.max(ed, pair.second);}}if(st!=-2e9) {res.add(new Pair(st, ed));}return res;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();ArrayList list = new ArrayList();while ((n--) > 0) {int l = scanner.nextInt();int r = scanner.nextInt();list.add(new Pair(l, r));}Collections.sort(list, new Comparator() {@Overridepublic int compare(Pair a, Pair b) {return a.first - b.first;}});list=merge(list);System.out.println(list.size());}}class Pair {int first;int second;public Pair(int first, int second) {this.first = first;this.second = second;}public String toString() {return first + " " + second;}}

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...