双指针【1】两数之和基础版 归并排序

2024-06-16 14:04

本文主要是介绍双指针【1】两数之和基础版 归并排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

基础两数之和

给定递增序列,输出所有和为k的种数

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100001;int n,m,k,num1[N],num2[N]; 
int sum2()
{int i=0,j=n-1,ans=0;while(i<j){if(num1[i]+num1[j]==k) {ans++;i++;j--;}else{if(num1[i]+num1[j]<k) i++;else j--;}}return ans;
}int main()
{//printf("%lf",(double)9/2);scanf("%d",&n);scanf("%d",&k);for(int i=0;i<n;i++) scanf("%d",&num1[i]); printf("%d",sum2());
}

归并排序

 需要会写合并两个序列(双指针),上一节试过。

使用递归

这个代码有点问题

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=10001;int n,m,k,num1[N],num2[N],ans[N]; 
void merge(int a[],int left,int c,int d,int right)
{int i=left;int j=d;int b=0;while(i<=c && j<=right ){if(a[i]<=a[j]){//printf("一%d%d",b,a[i]);ans[b]=a[i];i++;b++;}else{//printf("二%d%d",b,a[j]);ans[b]=a[j];j++;b++;}}
//	for(int k=0;k<b;k++)printf("!%d",ans[k]);if(i<=c){for (int k=i;k<=c;k++){ans[b]=a[k];b++;}}else{for(int k=j;k<=right;k++){ans[b]=a[j];b++;}}for (int k=left;k<=right;k++)
{a[k]=ans[k-left];//!!!!!!一开始写的a[k]=ans[k]找了半天错误呜呜呜呜呜呜
//printf("!%d!",a[k]);}	//printf("三"); 
}
void mergesort(int left,int right,int a[])
{
int l=left+(right-left)/2;
if(right>left) {//printf("?");
mergesort(left,l,a);
mergesort(l+1,right,a);	
merge(a,left,l,l+1,right);
}}int main()
{//printf("%lf",(double)9/2);
//int num3[]={2,1};
//merge(num3,0,0,1,1);
//	for(int i=0;i<5;i++) printf("%d",num3[i]); scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&num1[i]); mergesort(0,n-1,num1);for(int i=0;i<n;i++) {printf("%d",num1[i]); if(i<n-1) printf(" ");}
}

 

这篇关于双指针【1】两数之和基础版 归并排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1066637

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

【Linux 从基础到进阶】Ansible自动化运维工具使用

Ansible自动化运维工具使用 Ansible 是一款开源的自动化运维工具,采用无代理架构(agentless),基于 SSH 连接进行管理,具有简单易用、灵活强大、可扩展性高等特点。它广泛用于服务器管理、应用部署、配置管理等任务。本文将介绍 Ansible 的安装、基本使用方法及一些实际运维场景中的应用,旨在帮助运维人员快速上手并熟练运用 Ansible。 1. Ansible的核心概念

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别,使用new关键字创建变量时,需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时,不必自己去调用delete,甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针,是一种作用域指针,意思是当指针超出该作用域时,会自动调用delete。它名为unique的原因是这个

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组,例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量,换值int temp;in

音视频入门基础:WAV专题(10)——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础:WAV专题(6)——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道,通过FFprobe命令可以打印WAV音频文件每个packet(也称为数据包或多媒体包)的信息,这些信息包含该packet的pts、dts: 打印出来的“pts”实际是AVPacket结构体中的成员变量pts,是以AVStream->time_base为单位的显