首页 > 编程语言 >408---必须能手搓的算法

408---必须能手搓的算法

时间：2023-12-19 17:22:06浏览次数：46  
标签：10 return int --- debug Root2 Root1 能手 408

一、快速排序

无需多言

// 2023-12-19
#include <iostream>
#include <cstring>
using namespace std;


void debug(int A[],int n){
    for(int i=0;i<n;i++) printf("%d ",A[i]);
    puts("");
}


void Qsort(int A[],int left,int right){
    if(left >= right) return ;
    int l,r,pivot;
    l=left,r=right,pivot = A[left];
    while(l<r){
        while(l<r && A[r] >= pivot) r--;
        A[l] = A[r];
        while(l<r && A[l] <= pivot) l++;
        A[r] = A[l];
    }
    A[l] = pivot;
    
    Qsort(A,left,l-1);
    Qsort(A,l+1,right);

}


int main(){
    int A[20] = {0};    
    for(int i=0;i<=19;i++) A[i]=50-i+1;
    debug(A,20);
    Qsort(A,0,19);
    debug(A,20);

    return 0;
}

 

 

二、归并排序

// 2023-12-19
#include <iostream>
#include <cstring>
using namespace std;

void debug(int A[],int n){
    for(int i=0;i<n;i++) printf("%d ",A[i]);
    puts("");
}


void TMerge(int A[],int left,int mid,int right){
    int i,j,k;
    int *B = (int *)malloc(sizeof(int) * 20);
    
    i=left,j = mid+1,k = left;
    while(i<=mid && j<=right){
        if(A[left] < A[right]) B[k++] = A[i++];
        else B[k++] = A[j++];
    }
    while(i<=mid) B[k++] = A[i++];
    while(j<=right) B[k++] = A[j++];
    for(i=left;i<=right;i++){
        A[i] = B[i];
        B[i] = 0;
    }

    free(B);
}

void Merge(int A[],int left,int right){
    if(left >= right) return ;

    int mid = left+right >> 1;
    Merge(A,left,mid);
    Merge(A,mid+1,right);

    TMerge(A,left,mid,right);
}


int main(){
    int A[20];
    for(int i=0;i<=19;i++) A[i] = 50-i;
    debug(A,20);
    Merge(A,0,19);
    debug(A,20);
    
    return 0;
}

三、并查集及其优化

#include <stdio.h>
#include <math.h>
int find(int A[],int m);
void Init(int A[],int len){
    for(int i=0;i<len;i++)A[i]=-1; 
}

void debug(int A[],int len){
    for(int i=0;i<len;i++) printf("%3d ",A[i]);
    puts("");
}
void Union(int A[],int x1,int x2){
    int root1 = find(A,x1);
    int root2 = find(A,x2);
    if(root1 != root2){
        A[root1] = root2;        // 把x1合并到x2中 
    }
}

int find(int A[],int m){
    if(A[m] < 0) return m;
    return find(A,A[m]);
}


int optfind(int A[],int m){
    if(A[m] < 0) return m;
    int root = find(A,A[m]);
    A[m] = root;               // 让路过的元素都指向root
    return root;    
}
void opt1Union(int A[],int x1,int x2){
    int root1 = optfind(A,x1);
    int root2 = optfind(A,x2);
    if(root1 != root2){
        A[root1] = root2;        // 把x1合并到x2中 
    }
}

void opt2Union(int A[],int x1,int x2){      // 结点小的树合并到结点多的树，俗称大树合并到小树
    int root1 = optfind(A,x1);
    int root2 = optfind(A,x2);
    if(root1 == root2) return ;
    if(abs(A[root1]) > abs(A[root2])){  // 越大的结点越多
        A[root1] += A[root2];
        A[root2] = root1;         
    }else{
        A[root2] += A[root1];
        A[root1] = root2;  
    }
}


int main(){
    int A[20] = {0};
    Init(A,20);


    // Union(A,1,2);
    // debug(A,10);
    // Union(A,3,2);
    // debug(A,10);
    // Union(A,5,6);
    // debug(A,10);
    // Union(A,7,6);
    // debug(A,10);
    // Union(A,2,4);
    // debug(A,10);
    // Union(A,6,4);    
    // debug(A,10);

/*
           4

    2              6

1       3       5       7

*/
/*
 -1   2  -1  -1  -1  -1  -1  -1  -1  -1 
 -1   2  -1   2  -1  -1  -1  -1  -1  -1 
 -1   2  -1   2  -1   6  -1  -1  -1  -1 
 -1   2  -1   2  -1   6  -1   6  -1  -1 
 -1   2   4   2  -1   6  -1   6  -1  -1 
 -1   2   4   2  -1   6   4   6  -1  -1 
*/


    // opt1Union(A,1,2);
    // debug(A,10);
    // opt1Union(A,3,2);
    // debug(A,10);
    // opt1Union(A,5,6);
    // debug(A,10);
    // opt1Union(A,7,6);
    // debug(A,10);
    // opt1Union(A,2,4);
    // debug(A,10);
    // opt1Union(A,1,6);
    // debug(A,10);




/*
    4
            
    2                            6

1       3                   5       7

*/
// =========> opt1Union(1,6)
/*

                6

1       2       4        5      7
        
        3

*/

/*
 -1   2  -1  -1  -1  -1  -1  -1  -1  -1 
 -1   2  -1   2  -1  -1  -1  -1  -1  -1 
 -1   2  -1   2  -1   6  -1  -1  -1  -1 
 -1   2  -1   2  -1   6  -1   6  -1  -1 
 -1   2   4   2  -1   6  -1   6  -1  -1 
 -1   4   4   2   6   6  -1   6  -1  -1 
*/
// 在把1合并到6结点的时候可以发现，find函数并不是把1所在的子树的所有结点都连接到6结点下，而是先把1所在子树的结点都指向1所在子树的根，再把根指向6所在结点的根
// 可以看这种图: /i/l/?n=23&i=blog/2433096/202311/2433096-20231130194814117-562472168.png
    


    opt2Union(A,1,2);
    debug(A,10);
    opt2Union(A,3,2);
    debug(A,10);
    opt2Union(A,5,6);
    debug(A,10);
    opt2Union(A,7,6);
    debug(A,10);
    opt2Union(A,2,4);
    debug(A,10);
    opt2Union(A,1,6);
    debug(A,10);

/*

 -1   2  -2  -1  -1  -1  -1  -1  -1  -1 
 -1   2  -3   2  -1  -1  -1  -1  -1  -1 
 -1   2  -3   2  -1   6  -2  -1  -1  -1 
 -1   2  -3   2  -1   6  -3   6  -1  -1
 opt2Union(A,2,4); //我们原本想让2合并到4，但由于2是大树，故只能4合并到2
 -1   2  -4   2   2   6  -3   6  -1  -1 
 -1   2  -7   2   2   6   2   6  -1  -1 

*/


    return 0;
}

 

简易版(无分析数据版

// 2023-12-19
// 估计是考前最后一次手搓并查集及其优化了

#include <iostream>
#include <cstring>
using namespace std;



void Init(int A[],int n){
    for(int i=0;i<n;i++) A[i] = -1;
}


int find(int A[],int x){
    return A[x] > 0 ? A[x] : x;
}

int optfind(int A[],int x){
    if(A[x] < 0) return x;
    int Root = optfind(A,A[x]);
    A[x] = Root;                // 比起朴素的find操作，增添了这项代码
    return Root;
}

void Union(int A[],int x1,int x2){   // x1的根合并到x2中
    int Root1 = find(A,x1); int Root2 = find(A,x2);
    if (Root1 == Root2) return ;
    A[Root1] = Root2;
    
    return ;
}

void opt1Union(int A[],int x1,int x2){
    int Root1 = optfind(A,x1); int Root2 = optfind(A,x2);
    if (Root1 == Root2) return ;
    A[Root1] = Root2;
    
    return ;
}

int abs(int m){// 取绝对值
    return m>0 ? m : -m;
}
void opt2Union(int A[],int x1,int x2){          // 小树合并到大树上
    int Root1 = optfind(A,x1); int Root2 = optfind(A,x2);
    if(Root1 == Root2) return ;
    if(abs(A[Root1]) > abs(A[Root2])){
        A[Root1] += A[Root2];
        A[Root2] = Root1;
    }else{
        A[Root2] += A[Root1];
        A[Root1] = Root2;
    }
    
}


void debug(int A[],int n){
    for(int i=0;i<n;i++) printf("%3d ",A[i]);
    puts("");
}


int main(){
    int A[20] = {0};
    Init(A,20);
    // debug(A,20);

// 朴素算法
// 一次Find 最坏时间复杂度 : O(n)
// 总体是O(n^2)的时间复杂度
   
   
    // Union(A,1,2);
    // debug(A,10);
    // Union(A,3,2);
    // debug(A,10);
    // Union(A,5,6);
    // debug(A,10);
    // Union(A,7,6);
    // debug(A,10);
    // Union(A,2,4);
    // debug(A,10);
    // Union(A,6,4);
    // debug(A,10);

// 优化一---find路径压缩
// 一次Find 最坏时间复杂度 : O(α(n))
// 总体是 : O(n · α(n))  

    // opt1Union(A,1,2);
    // debug(A,10);
    // opt1Union(A,3,2);
    // debug(A,10);
    // opt1Union(A,5,6);
    // debug(A,10);
    // opt1Union(A,7,6);
    // debug(A,10);
    // opt1Union(A,2,4);
    // debug(A,10);
    // opt1Union(A,1,6);
    // debug(A,10);



// 优化二---大树合并小树
// 一次Find 最坏时间复杂度 : $O(log_2n)$
// 总体是 : $O(log_2n)$

    opt2Union(A,1,2);
    debug(A,10);
    opt2Union(A,3,2);
    debug(A,10);
    opt2Union(A,5,6);
    debug(A,10);
    opt2Union(A,7,6);
    debug(A,10);
    opt2Union(A,2,4);
    debug(A,10);
    opt2Union(A,1,6);
    debug(A,10);


    
    
    return 0;
}

 

标签：10,return,int,---,debug,Root2,Root1,能手,408
From： https://www.cnblogs.com/lordtianqiyi/p/17914259.html

相关文章

  • Spring Boot学习随笔- 实现AOP（JoinPoint、ProceedingJoinPoint、自定义注解类实现切面
    学习视频：【编程不良人】2021年SpringBoot最新最全教程第十一章、AOP11.1为什么要使用AOP问题现有业务层开发存在问题额外功能代码存在大量冗余每个方法都需要书写一遍额外功能代码不利于项目维护Spring中的AOPAOP：Aspect切面+Oriented面向Programmaing......
  • 07信息打点-资产泄漏&CMS 识别&Git 监控&SVN&DS_Store&备份
    一、知识点CMS指纹识别源码获取方式习惯&配置&特性等获取方式托管资产平台资源搜索监控二、详细点源码泄漏原因：从源码本身的特性入口从管理员不好的习惯入口从管理员不好的配置入口从管理员不好的意识入口从管理员资源信息搜集入口源码泄漏集合：composer.jsongit源码泄露svn......
  • 50种网络故障解决方案-下篇
    ......
  • prtainer-test 升级
    停止容器lenovo@lenovo-laptop:~$dockerstopprtainer-test删除容器lenovo@lenovo-laptop:~$dockerrmprtainer-test下载镜像lenovo@lenovo-laptop:~$dockerpullportainer/portainer-ce运行容器lenovo@lenovo-laptop:~$dockerrun-d-p8000:8000-p9000:9000--......
  • 格式工厂MP4视频转格式（H265->H264）图文详解
    最近上传到网站上的视频播放时只有声音没有图像，但是在本地播放一切正常，检查后发现问题是有些浏览器不支持播放H265格式的视频。不能让访问网站的用户去换浏览器或者单独安装浏览器插件，最简单的解决办法还是自己转化视频格式重新上传。推荐一个老牌免费使用简单的视频格式转换软件—......
  • MySQL运维11-Mycat分库分表之应用指定分片
    一、应用指定分片此规则是在运行阶段有应用自主决定路由到那个分片，根据提供的字段，然后按照指定的规则，截取该字段的部分子字符串当做分片的依据，该分别方法比较灵活，适用于某个字段有几个特殊的字符串拼接而成的这种场景，例如：一个学校的学号：小学部的学号以0开头，形式为：0xxxxx(......
  • 你牛什么牛 (女汉子版) - 唐古 发行时间:2014年12月25日
    唐古演唱的歌曲《你牛什么牛》是甜心才女唐古为微电影《我们都是女汉子》演唱的主题曲。发行时间:2014年12月25日  你牛什么牛(女汉子版)-唐古词：师立宅曲：李风持编曲：南少东后期：王路遥总监制：刘晓洪出品人：石太锋你牛你牛你牛你呀牛什么牛你牛你牛你牛你呀牛什......
  • C9800-VLAN Group
    在AireOS的环境下，如果我们想让一个WLAN对应多个VLAN，通常来说，大家的选择可能是通过interfaceGroup的方式来实现WLAN和多个VLAN的对应。而在C9800的环境下，不再是接口和WLAN绑定的概念，在C9800上，是在PolicyProfile中配置需要的VLAN。 但是，在使用VLANGroup，需要注意相关的限制，尤其......
  • 打工笔记--------------------winform程序报错CLR20r3签名System.I0.IOException
    先看问题编写了一个程序在我本机运行没有问题，放到别人电脑上就有可能报这种错误System.I0.IOException  首先我问了一下ChatPgt:他说：CLR20r3是一个通用的错误代码，表示在.NETFramework中发生了未处理的异常。System.IO.IOException是与输入/输出操作相关的一个常见......
  • 搭建lnmp环境-php
    系统环境：centos7php7.4 ===安装php===#安装EPEL源yuminstall-yepel-release#安装Remi源yuminstall-yhttps://rpms.remirepo.net/enterprise/remi-release-7.rpm#安装yum包管理器工具（类似php的composer）yuminstall-yyum-utils#通过Remi指定PHP版本（后面安......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99