C语言双指针算法朋友过情人节我过算法

目录
  • 双指针
  • 对撞指针
  • 快慢指针
  • 真题实战

双指针

首先咱得知道何为双指针,听起来很上流,其实有手就行。

双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的。

换言之,双指针法充分使用了数组有序这一特征,当遇到有序数组时,应该优先想到双指针来解决问题,因两个指针的同时遍历会减少空间复杂度和时间复杂度从而在某些情况下能够简化运算

对撞指针

类似于相遇问题,对撞指针是指在有序数组中,将指向最左侧的索引定义为左指针,最右侧的定义为右指针,然后分别从两侧出发,相向遍历链表,这个过程就形象化为对撞,习惯上就将左右指针定义为 left 和 right,我们给出一个大致代码逻辑:

void hit(int *arr,int arrsize)
{
int* left = arr;
int* right = arr + arrsize -1;
while(left<=right)
{
条件语句;
left++;
条件语句;
right--;
}
}

对撞指针适用于二分查找,链表对象求和等,也就是说当你遇到题目给定有序数组时,应该第一时间想到的思路就是使用对撞指针。

快慢指针

类似于龟兔赛跑,快慢指针是两个链表上的指针从同一节点出发,其中一个指针前进速度比另一个快,两个指针以不同的策略移动,直到两个指针的值达成某个条件为止,如图(ppt绘图+手残勿喷):

我们同样将左右指针定义为 slow,fast,要实现其中一个指针比另一个快,我们无可厚非就两种方法:

1.同时起步,fast 比 slow 多走n步;

2.fast 先走,slow后走;

那我们给出他的逻辑代码:
同时走:

void speed(int *arr)
{
   int* fast = arr;
   int* slow = arr;
   while(slow<fast)
   {
   条件;
   slow++(非条件下fast++);
   }
}

先后走:

void speed(int *arr)
{
int* slow =arr;
int* fast = arr;
while(条件1)
{
slow++;
}
while(条件2)
{
fast++;
}
}

真题实战

1.调整数组顺序使奇数位于偶数前面

int* reOrderArray(int* array, int arrayLen, int* returnSize ) {
  *returnSize = arrayLen;
   int* left = array;
	int* right = array + arrayLen - 1;
	while (left < right)//(1)
	{
		while (left < right && *left % 2 == 1)//(2)
			left++;
		while (left < right && *right % 2 == 0)//(3)
			right--;
		if (left < right)//(4)
		{
			int tmp = *left;
			*left = *right;
			*right = tmp;
		}
		left++;
		right--;
	}
	return array;
}

这道题就是典型的对撞指针,我们遍历完整个数组时,左右指针路程各自一半,只需要 left 寻找奇数,right 寻找偶数做交换即可。

==Ps.==这里的* returnSize

2.Leetcode 真题:移除元素

int removeElement(int* nums, int numsSize, int val) {
	int* p1 = nums;
	int* p2 = nums;
	int sz = numsSize;
	for (; p1 < nums + numsSize; p1++)
	{
		if (*p1 != val)
		{
			*p2 = *p1;
			*p2++;
		}
		else
			sz--;
	}
	return sz;
}

这是典型的快慢指针,第一个指针用来遍历数组元素,判断是不是要删除的数,第二个指针用来存放数字。如果第一个指针指向的是要删除的元素,那么输出用来存放输出数组元素个数的整形变量sz就自减 1,然后第一个指针向后移动一位,第二个指针不动;如果第一个指针指向的不是要删除的数,那么就把这个数放到第二个指针指向的位置,然后第一个指针和第二个指针都向后移动一位。重复操作直到第一个指针遍历整个数组,此方法的时间复杂度是O(n)。

今天就到这里了,摸了家人们,情人节快乐!更多关于C语言双指针算法的资料请关注我们其它相关文章!

(0)

相关推荐

  • C语言指针详解及用法示例

    新手在C语言的学习过程中遇到的最头疼的知识点应该就是指针了,指针在C语言中有非常大的用处.下面我就带着问题来写下我对于指针的一些理解. 指针是什么? 指针本身是一个变量,它存储的是数据在内存中的地址而不是数据本身的值.它的定义如下: int a=10,*p; p=&a int a=10; int *p=&a; 首先我们可以理解 int* 这个是要定义一个指针p,然后因为这个指针存储的是地址所以要对a取地址(&)将值赋给指针p,也就是说这个指针p指向a. 很多新手都会对这两种定义方法

  • C语言中的指针以及二级指针代码详解

    很多初学者都对C中的指针很迷糊,希望这篇blog能帮助到大家: 1.什么是"指针": 在执行C程序的时候,由于我们的数据是存储在内存中的.所以对于C程序本身来说,如果想找到相应被调用的数据,就要知道存储该数据的内存地址是多少,换言之,C程序通过已知的内存地址到相应的内存位置存储数据. 这里简单说一下内存管理(对于初学者来说.为了避免专业术语引发的理解问题,下面的叙述尽量避免专业定义:),对于现代计算机系统来说,内存空间分为两个区域,一个是"数据区",一个是"

  • 深入理解双指针的两种用法

    好久没有用过C/C++的二级指针了,总觉的它就是指针的指针,没什么大不了的,但是今天看到一道面试题,感觉自己对二级指针的理解还是不够深刻.于是,从网上找资料,学习了一番--题目是这样的: 复制代码 代码如下: #include "stdafx.h"#include <iostream>using namespace std;void GetMemory(char *p, int num){ p = (char *)malloc(sizeof(char) * num); //

  • C语言基础双指针移除元素解法

    本题方法:双指针.知识比较基础,思路简单 题目: 我的题解: int removeElement(int* nums, int numsSize, int val) { int i=0,j=0; int cnt=0; //计数器,用来统计val的个数 while(j<numsSize) { if(nums[j]!=val) //1 { nums[i]=nums[j]; i++; j++; } else //2 { j++; cnt++; } } return numsSize-cnt; //3

  • C语言双指针算法朋友过情人节我过算法

    目录 双指针 对撞指针 快慢指针 真题实战 双指针 首先咱得知道何为双指针,听起来很上流,其实有手就行. 双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的. 换言之,双指针法充分使用了数组有序这一特征,当遇到有序数组时,应该优先想到双指针来解决问题,因两个指针的同时遍历会减少空间复杂度和时间复杂度从而在某些情况下能够简化运算 对撞指针 类似于相遇问题,对撞指针是指在有序数组中,将指向最左侧

  • 浅谈c语言中一种典型的排列组合算法

    c语言中的全排列算法和组合数算法在实际问题中应用非常之广,但算法有许许多多,而我个人认为方法不必记太多,最好只记熟一种即可,一招鲜亦可吃遍天 全排列: #include<stdio.h> void swap(int *p1,int *p2) { int t=*p1; *p1=*p2; *p2=t; } void permutation(int a[],int index,int size) { if(index==size) { for(int i=0;i<size;i++) print

  • C语言实现运筹学中的马氏决策算法实例

    本文实例讲述了C语言实现运筹学中的马氏决策算法.分享给大家供大家参考,具体如下: 一.概述 马氏决策(Markov decision)是马尔可夫决策过程(Markov Decision Processes,简记为MDP)的简称,是研究随机序贯决策问题的一门重要理论.马氏决策是一类可连续进行观察的随机动态系统的最优化决策,它将(确定性)动态规划与马尔可夫过程相结合,是随机离散事件动态系统惟一的动态控制方法. 关于马氏决策的具体说明可参考百度百科:https://baike.baidu.com/it

  • C语言实现文件内容按行随机排列的算法示例

    本文实例讲述了C语言实现文件内容按行随机排列的算法.分享给大家供大家参考,具体如下: 在实际工作上有种需求, 就是需要从给定的数据里,随机抽取一部分. 有一种简单的方法是根据总的数据条数和要抽取的数据条数, 通过简单方法,隔几行取一个,这样也能达到随机抽取一部分的目的. 但这样,源数据是顺序的,则抽取的数据也是顺序的,不满足一些情境. 这里实现的功能是: 将全部数据,按行重新随机排列, 这样从结果头部选几行,就是随机抽取的几行了,比较方便. 实现的思路:  对于N行的数据, 给每一行用[1-N]

  • c语言实现整蛊朋友小程序(附源码)

    前言 感觉学了c语言后仍然一无是处?!!想要整蛊一下朋友仍然不会?!! 别慌,看完这篇文章,你就会了. 下面给大家分享两个基础的整蛊小程序 1.我是猪关机程序 2.无限弹窗程序 一.我是猪关机程序 效果:运行程序后电脑在60s后关机,如果输入"我是猪"则取消关机:如果输入"你是猪"则立即关机:输入其他文字会提示重新输入:若强行关闭程序电脑仍会关机. 本程序基于控制台,其功能是通过dos命令来实现. 那么就先讲一下所用到的dos命令(shutdown -s -t 60

  • C语言编程之扫雷小游戏空白展开算法优化

    目录 写代码前,扫雷需要什么 进行主函数文件的代码 game文件以及函数步骤 在主函数文件中使用game函数 布值棋盘(雷盘和玩家棋盘) 打印棋盘函数 玩家排雷 计算雷数的函数 空白递归算法 写代码前,扫雷需要什么 1,游戏需要初始选择菜单 2,需要布置两个棋盘,一个布置雷,一个展示给玩家看 3,打印棋盘 4,玩家要输入选择的坐标,并且可以多次输入游戏坐标 5,每次输入后打印棋盘,同时判断是否继续还是输赢. 6,玩家每次输入坐标,都进行一次递归展开. 进行主函数文件的代码 void option

  • java数据结构与算法之noDups去除重复项算法示例

    本文实例讲述了java数据结构与算法之noDups去除重复项算法.分享给大家供大家参考,具体如下: public static void noDupa(int[] a){ int count = 0;//in int sub = 0;//计数器 for(int i=0; i<a.length-1; i++){//外层循环 if(a[i] != a[i+1]){ a[count] = a[i]; count++; } } } PS:感觉这个算法粗略看下觉得没啥子,实际上相当精妙!!先决条件---数

  • Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例

    本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法).分享给大家供大家参考,具体如下: # coding:utf-8 # Dijkstra算法--通过边实现松弛 # 指定一个点到其他各顶点的路径--单源最短路径 # 初始化图参数 G = {1:{1:0, 2:1, 3:12}, 2:{2:0, 3:9, 4:3}, 3:{3:0, 5:5}, 4:{3:4, 4:0, 5:13, 6:15}, 5:{5:0, 6:4}, 6:{6:0}} # 每次找到离源点最近的一个顶

  • C++算法系列之日历生成的算法代码

    日历在我们的生活中扮演着十分重要的角色,上班.上学.约会都离不开日历.每年新年开始,人们都要更换新的日历,你想知道未来一年的这么多天是怎么被确定下来的吗?为什么去年的国庆节是星期五而今年的国庆节是星期三?那就来研究一下日历算法吧.本文将介绍日历的编排规则,确定某日是星期几的计算方法,以及如何在计算机上打印某一年的年历. 要研究日历算法,首先要知道日历的编排规则,也就是历法.所谓历法,指的就是推算年.月.日的时间长度和它们之间的关系,指定时间序列的法则.我国的官方历法是中国公历,也就是世界通用的格

  • C++算法系列之中国农历的算法

    C++算法系列之日历生成的算法 所谓的"天文算法",就是利用经典力学定律推导行星运转轨道,对任意时刻的行星位置进行精确计算,从而获得某种天文现象发生时的时间,比如日月合朔这一天文现象就是太阳和月亮的地心黄经(视黄经)差为0的那一瞬间.能够计算任意时刻行星位置的一套理论就被称为星历表,比较著名的星历表有美国国家航空航天局下属的喷气推进实验室发布的DE系列星历表,还有瑞士天文台在DE406基础上拓展的瑞士星历表等等.根据行星运行轨道直接计算行星位置通常不是很方便,更何况大多数民用天文计算用

随机推荐