双指针(5)_单调性_有效三角形的个数

2024-09-07 22:28

本文主要是介绍双指针(5)_单调性_有效三角形的个数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

个人主页:C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

双指针(5)_单调性_有效三角形的个数

收录于专栏【经典算法练习
本专栏旨在分享学习C++的一点学习笔记,欢迎大家在评论区交流讨论💌

目录

1. 题目链接:

2.题目描述 :

3.解法 :

    解法一(暴力枚举) :

    算法思路 :

    代码展示 :

暴力枚举优化:

    结果分析 :

    解法二(排序 + 双指针) :

    算法思路 :

    代码展示 :

    结果分析 :

    4.总结 :


1. 题目链接:

--------有效三角形的个数

2.题目描述 :

给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

输入: nums = [4,2,3,4]
输出: 4

提示:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

3.解法 :

    解法一(暴力枚举) :

    算法思路 :

利用三层for循环遍历整个数组

注意:

1. 这道题不需要去重处理,比如示例一中的2,3,4出现了两次,但其中的2分别是第一个和第二个.

2. 这道题的数据范围:nums.lengh <= 1000,我们三层for循环时间复杂度就为O(n^3),我们还需要进行判断,整体下来还是O(N^3),数据量超过10^9,可能会超时!!!

伪代码展示:

for (int i = 0; i < n; i++)
{for (int j = i + 1; j < n; j++){for (int k = j + 1; k < n; k++){check(i, j, k);}}
}

    代码展示 :

class Solution {
public:bool check(int a, int b, int c){if((a + c > b) && (a + b > c) && (b + c > a)) return true;else return false;}int triangleNumber(vector<int>& nums) {int sum = 0, n = nums.size();for(int i = 0; i < n; i++)for(int j = i + 1; j < n; j++)for(int k = j + 1; k < n; k++)if(check(nums[i], nums[j], nums[k])) sum++;return sum;}
};

 

很显然,在算法题中想要用暴力做出来是基本不可能的,更何况这道题还是中等的难度,通过率仅仅50%,这里我使用暴力只通过了231个例子,这里说一下暴力算法主要是为了蓝桥杯(暴力杯),当我们没有思路时,可以选择暴力方法通过一部分例子,也可以帮助我们分析题目.

优化暴力算法: 

我们可以发现,我们使用三层循环时间复杂度为O(N^3),数据量为10^9,按道理应该勉强能过,但实际上,我们三层循环里还要进行一次判断,所以时间复杂度可以细化为O(3N^3),那我们能不能把判断这个环节进行优化呢?答案是可以的!

优化判断函数check:

假设我们的数组是有序的,拿我们判断三个有序的数是否能构成三角形是不是只需要判断a + b > c就可以了,因为a <= b, b <= c,那我们的a + c一定是大于b,同理b + c 也一定大于a.

在这个思路上,我们就可以首先对数组进行排序,排序的时间为O(Nlog(N))(sort底层用的是快排),这样三层循环内的判断只需要进行一次,总体时间复杂度为O(N^3 + Nlog(N)) 是远小于 O(3N^3)的,我们看一下优化后的暴力算法能不能蒙混过关!

暴力枚举优化:

class Solution {
public:bool check(int a, int b, int c){if(a + b > c) return true;else return false;}int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int sum = 0, n = nums.size();for(int i = 0; i < n; i++)for(int j = i + 1; j < n; j++)for(int k = j + 1; k < n; k++)if(check(nums[i], nums[j], nums[k])) sum++;return sum;}
};

 

???????????????????????????????????????????????????????????????

不是,我就试一试,你就让我过了?

这道题真是中等难度吗?

说实话,我一开始只是认为会多通过几个例子,没想到它直接通过了!!!

那现在看来暴力算法还是可以作为先锋的,万一过了呢?

    结果分析 :

因为这道题数据给的比较低,数组中的数小于1000,这就给了暴力算法窜了空子,稍微优化一下,我们的暴力算法就可以通过.

但是,假如这道题数组中的数小于10000时,暴力算法无论怎么优化都不行,因为它的时间复杂度本质就是O(N^3),当数据量为10000时,我们就得考虑时间复杂度为O(N^2)或者O(Nlog(N))的算法了

    解法二(排序 + 双指针) :

    算法思路 :

先将数组排序.

根据[解法一]中的优化思想,我们可以固定一个[最长边],然后在比这条小的有序数组中找出一个二元组,使这个二元组之和大于这个最长边.由于数组是有序的,我们可以利用[对撞指针]来优化.

设最长枚举i位置,区间[left, right]是i位置的左边的区间(也就是比它小的区间):

        如果nums[left] + nums[right] > nums[i]:

                说明[left, right-1] 区间上的所有元素均可以与nums[right]构成比nums[i]大的二元组

                满足条件的有right - left

                此时right位置的元素的所有情况相当于全部考虑完毕,right--,进入下一轮判断

        如果nums[left] + nums[right] <= nums[i]:

                说明left位置的元素是不可能与[left + 1, right]位置上的元素构成满足条件的二元组

                left位置的元素可以舍去,left++进入下轮循环

思路图解:

 

    代码展示 :

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int sum = 0, n = nums.size() - 1;while(n >= 2){int left = 0, right = n - 1;while(left < right){if(nums[left] + nums[right] > nums[n]) sum += right - left, right--;else left++;}n--;}return sum;}
};

 

    结果分析 :

顺利通过!!!

时间复杂度分析:

外层n进行了一层循环,内层left和right共同完成了对数组的遍历

整体的时间复杂度为O(N^2),比前面的暴力算法还是快了不少!!!

    4.总结 :

大家做算题题时,一定要优先查看题目的数据范围,这样能提前Pass掉一些时间复杂度过高的方法,为大家节约时间,当然如果你实在没招,暴力枚举你可以尝试一下,特别是在蓝桥杯中!!!

最后我每天都会更新一道经典算法题(正常情况下),感兴趣的宝子们可以关注我!!!

欢迎 点赞👍 收藏✨ 留言✉ 加关注💓

所有算法题我都会放在我的专栏[经典算法练习],大家也可以关注下,我们明天见!!!

这篇关于双指针(5)_单调性_有效三角形的个数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

【WebGPU Unleashed】1.1 绘制三角形

一部2024新的WebGPU教程,作者Shi Yan。内容很好,翻译过来与大家共享,内容上会有改动,加上自己的理解。更多精彩内容尽在 dt.sim3d.cn ,关注公众号【sky的数孪技术】,技术交流、源码下载请添加微信号:digital_twin123 在 3D 渲染领域,三角形是最基本的绘制元素。在这里,我们将学习如何绘制单个三角形。接下来我们将制作一个简单的着色器来定义三角形内的像素

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

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

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

C语言指针入门 《C语言非常道》

C语言指针入门 《C语言非常道》 作为一个程序员,我接触 C 语言有十年了。有的朋友让我推荐 C 语言的参考书,我不敢乱推荐,尤其是国内作者写的书,往往七拼八凑,漏洞百出。 但是,李忠老师的《C语言非常道》值得一读。对了,李老师有个官网,网址是: 李忠老师官网 最棒的是,有配套的教学视频,可以试看。 试看点这里 接下来言归正传,讲解指针。以下内容很多都参考了李忠老师的《C语言非

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor

C和指针:字符串

字符串、字符和字节 字符串基础 字符串就是一串零个或多个字符,并且以一个位模式为全0的NUL字节结尾。 字符串长度就是字符串中字符数。 size_t strlen( char const *string ); string为指针常量(const修饰string),指向的string是常量不能修改。size_t是无符号数,定义在stddef.h。 #include <stddef.h>

O(n)时间内对[0..n^-1]之间的n个数排序

题目 如何在O(n)时间内,对0到n^2-1之间的n个整数进行排序 思路 把整数转换为n进制再排序,每个数有两位,每位的取值范围是[0..n-1],再进行基数排序 代码 #include <iostream>#include <cmath>using namespace std;int n, radix, length_A, digit = 2;void Print(int *A,