力扣编程题算法初阶之双指针算法+代码分析

这篇具有很好参考价值的文章主要介绍了力扣编程题算法初阶之双指针算法+代码分析。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 

目录

 文章来源地址https://www.toymoban.com/news/detail-756247.html

第一题:复写零

第二题:快乐数:

第三题:盛水最多的容器

第四题:有效三角形的个数


 

第一题:复写零

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

力扣编程题算法初阶之双指针算法+代码分析,算法,leetcode,c++,经验分享,其他思路:

上期介绍到双指针,这次来用双指针实际操作。第一种从前往后复写,会导致为复写的数字被覆盖,因此选择从后往前复写,那么先找到复写的最后一个元素,再从后往前复写即可。

步骤

1.初始化指针

2.找复写

3.处理边界问题

4.开始复写

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        	int cur = 0, dest = -1, n = arr.size();
while (cur < n)
{
	if (arr[cur]) dest++;//说明不用复写
	else dest += 2;
	if (dest >= n - 1)break;
	cur++;
}
//出来的时候cur就是莫位置
//处理边界
if (dest == n)
{
	arr[n - 1] = 0;
	cur--; dest -= 2;
}
//从后往前面复写
while (cur >= 0)
{
	if (arr[cur])//非0
		arr[dest--] = arr[cur--];
	else//为0
	{
		arr[dest--] = 0;
		arr[dest--] = 0;
		cur--;
	}
}

    }
};

第二题:快乐数:

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

力扣编程题算法初阶之双指针算法+代码分析,算法,leetcode,c++,经验分享,其他

 

思路:

这题通过在纸上演算可以发现,给定一个数他按照快乐数的定义,要么演变到1,要么将会重复他在演变过程中的一个数字,具体大家可以在纸上推算一遍

2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16,即形成了一个循环圈
而另外一种变成一,其实也可以看作是一个循环圈,即给定一个数,按照快乐数的定义,我给出两个指针,一个移动地快一个移动地慢,最终两个数一定会相等,倘若等于1,那么就是快乐数,倘若不等于1就不是快乐数
因此步骤
1.先把n的每一位提出,直到n为0
2.接着只要两个指针不相等就一直重复快乐数定义,直到相等退出循环,判断是否为1

class Solution
{
public:
	int bitSum(int n)
		int sum = 0;
	while (n)
	{
		int t = n % 10;
		sum += t * t;
		n /= 10;
	}
	bool isHappy(int n)
	{
		int slow = n, fast = bitSum(n);
		while (slow != fast)
		{
			slow = bitSum(slow);
			fast = bitSum(bitSum(fast));
		}
		return slow == 1;
	}
};

第三题:盛水最多的容器

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

力扣编程题算法初阶之双指针算法+代码分析,算法,leetcode,c++,经验分享,其他思路:

第一想法就是暴力枚举

s=h(高)*w(宽度)

即弄两个for循环,依次求出面积,再比较最大值,这样时间复杂度为n的平方会超时,因此

第二种就是双指针,观察发现,面积的高是由左右两边的低边界为准。就以上图为例,高是由右边那条高决定,左边高往右移动由于w一定减小,h要么减小要么不变,那么面积一定减小,所以我们就从两个边界开始来移动,记录每一次的面积,返回最大即可

注意,每次移动的是那个h小的,因为大h移动,s要么减少要么不变,而我们求的是最大的。

第一种:暴力求解

class Solution {
public:
	int maxArea(vector<int>& height) {
		int n = height.size();
		int ret = 0;
		// 两层 for 枚举出所有可能出现的情况
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				// 计算容积,找出最⼤的那⼀个
				ret = max(ret, min(height[i], height[j]) * (j - i));
			}
		}
		return ret;
	}
};

第二种:

对撞指针:

class Solution
{
public:
	int maxArea(vector<int>& height)
	{
		int left = 0, right = height.size() - 1, ret = 0;
		while (left < right)
		{
			int v = min(height[left], height[right]) * (right - left);
			ret = max(ret, v);
			// 移动指针
			if (height[left] < height[right]) left++;
			else right--;
		}
		return ret;
	}
};

第四题:有效三角形的个数

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

力扣编程题算法初阶之双指针算法+代码分析,算法,leetcode,c++,经验分享,其他思路:

在判断一个三角形时,如果对于一对升序数组a,b,c

如果a+b>c那么即可构成三角形,不需要判断三次

原因,如果上述条件成立那么,b+c>a,a+c>b一定成立,因为c是最大的数

第一思路就是暴力求解,先把给定数组排序,然后从第一个元素开始遍历,用三个for循环实现,但是时间复杂度较大,运行会超时

class Solution {
public:
	int triangleNumber(vector<int>& nums) {
		// 1. 排序
		sort(nums.begin(), nums.end());
		int n = nums.size(), ret = 0;
		// 2. 从⼩到⼤枚举所有的三元组
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				for (int k = j + 1; k < n; k++) {
					// 当最⼩的两个边之和⼤于第三边的时候,统计答案
					if (nums[i] + nums[j] > nums[k])
						ret++;
				}
			}
		}
		return ret;
	}
};

应次这里换一种高效方法就是用双指针来实现,因为已经排完升序,依据暴力解法,可以先固定一条最长边,然后找出比这条边小的二元组,让着个二元组的和大于最长边,即可利用对撞指针来实现。

最长边枚举i位置,区间[left,right]是i位置左边区间,
如果nums[left]+nums[right]>num[i],那么就有right-left种,因为是升序
否则,那么就舍弃left当前元素,left++进入下一轮循环
class Solution
{
public:
	int triangleNumber(vector<int>& nums)
	{
		// 1. 优化
		sort(nums.begin(), nums.end());
		// 2. 利⽤双指针解决问题
		int ret = 0, n = nums.size();
		for (int i = n - 1; i >= 2; i--) // 先固定最⼤的数
		{
			// 利⽤双指针快速统计符合要求的三元组的个数
			int left = 0, right = i - 1;
			while (left < right)
			{
				if (nums[left] + nums[right] > nums[i])
				{
					ret += right - left;
					right--;
				}
				else
				{
					left++;
				}
			}
		}
		return ret;
	}
};

 

 

 

到了这里,关于力扣编程题算法初阶之双指针算法+代码分析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言初阶之扫雷代码详解(含递归展开)

    主要分为下面几个过程: 1、建立棋盘 2、初始化棋盘 3、设置棋盘雷数 4、打印棋盘 5、玩家找雷 6、判定胜负 文件名:game.h 代码如下: 在game头文件中,首先包含会使用到的库头文件,这里的ROW以及COL是雷区的行和列大小,也就是说这是玩家实际能看到的行数及列数,而RO

    2024年02月03日
    浏览(36)
  • 数据结构初阶之二叉树性质练习与代码练习

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶    Linux 欢迎大家点赞,评论,收藏。 一起努力,共赴大厂。 目录 1.前言 2.性质练习 3.代码练习  3.1单值二叉树 3.2检查两颗树

    2024年02月04日
    浏览(44)
  • 算法修炼之路之双指针含多道leetcode 经典题目

    目录 前言  一:普通双指针 1.经典题目一  283移动0问题 分析 代码实现 2.经典题目二 1089复写0  分析 代码实现 二:解决成环类问题-快慢指针  经典例题一 202快乐数 分析  代码实现   三:左右相遇指针 经典例题一 11 盛最多水的容器 分析  代码实现    接下来的日子会顺

    2024年04月13日
    浏览(76)
  • 算法通关村第一关——链表经典问题之双指针笔记

    基本结构 1.寻找中间结点 2.寻找倒数第k个元素 3.旋转链表

    2024年02月14日
    浏览(38)
  • 第11章:C语言数据结构与算法初阶之排序

    排序是一种非常重要的算法。 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,

    2024年02月12日
    浏览(44)
  • 算法通关村第一关——链表经典问题之双指针专题笔记

    我一直觉得双指针是一个非常好用的方法,在链表中可以使用,在数组中依然可以,很灵活。 1. 寻找中间结点         用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步, fast 一次走两步。那么当 fast 到达链表的末尾时,slow 必然位于中间。 2. 寻找倒数第K个元素 在这

    2024年02月15日
    浏览(40)
  • C++初阶之内存分布

    我们先来看下面的一段代码 : 实际输出和对应的内存分布 我在Linux进程一文当中对内存分布和虚拟内存有详细讲解,不了解的小伙伴可以去看看这篇文章: Linux进程 说明: 栈又叫堆栈–非静态局部变量/函数参数/返回值等等,栈是向下增长的。 内存映射段是高效的I/O映射方

    2024年02月16日
    浏览(34)
  • 数据结构初阶之排序

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶    Linux 欢迎大家点赞,评论,收藏。 一起努力,共赴大厂。 目录 一.前言 二.选择排序 2.1选择排序思想 2.2代码实现 三.快速

    2024年01月18日
    浏览(43)
  • C++初阶之模板深化讲解

    非类型模板 (Non-Type Template)是 C++ 中的一种模板形式,它允许你在模板中传递除了类型以外的其他值,比如整数、枚举、指针等。这些参数可以在编译时被解析,用于生成模板的实例化版本。 非类型模板参数 (Non-Type Template Parameter)是在模板声明中,作为参数的一部分,而

    2024年02月13日
    浏览(31)
  • C++初阶之C++入门最全详解

    C++总计63个,C语言32个 在C/C++中,变量、函数和后面要学到的类都是大量存在的,这些变量、函数和类的名称将都存 在于全局作用域中,可能会导致很多冲突。使用命名空间的目的是对标识符的名称进行本地化, 以避免命名冲突或名字污染,namespace的出现

    2024年02月16日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包