本文主要是介绍【LeetCode刷题】有效三角形个数、查找总价值为目标值的两个商品,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【LeetCode刷题】Day 5
- 题目1:611.有效三角形个数
- 思路分析:
- 思路1:暴力枚举O(N^3^)
- 思路2:单调性,双指针解法O(NlogN+N^2^)
- 题目2:LCR 179.查找总价格为目标值的两个商品
- 思路1:暴力枚举O(N^2^)
- 思路2:单调性,双指针O(N)
- 今日收获:
题目1:611.有效三角形个数
思路分析:
判断三边能形成三角形的条件:
- 任意两边之和大于第三边。
a+b>c && a+c>b && b+c>a;
- 已知:
a<= b <= c
,只需要a+b>c
即可。因为c最大,加上任意一个数肯定大于第三个
。
思路1:暴力枚举O(N3)
三层循环,一层确定一个数,然后再判断,即可。
思路2:单调性,双指针解法O(NlogN+N2)
举例说明:如上图[2,2,3,4,5,9,10]
,先固定10,再两个指针分别指向第二大数9和最小数2,2+9>10,增加2,肯定也成立,则2到5都成立。反之,则移动左指针,指向更大的数,寻找是否有成立的数。直到左右指针相同,则与10有关的结束,在统计与9有关且不与10有关的组合。
代码实现:
注意:此处代码采取的是逆序,与上面分析相反。
class Solution {
public:int triangleNumber(vector<int>& nums) {if (nums.size() < 3)return 0;sort(nums.begin(), nums.end(), greater());int count = 0;for (size_t i = 0; i < nums.size() - 2; i++) {int left = i + 1, right = nums.size() - 1;while (left != right) {if (nums[right] + nums[left] > nums[i]) {count += right - left;left++;} elseright--;}}return count;}
};
LeetCode链接:611.有效三角形个数
题目2:LCR 179.查找总价格为目标值的两个商品
思路1:暴力枚举O(N2)
思路2:单调性,双指针O(N)
这里的数组都是有序的,所以最大值加最小值所得的sum,如果sum大于target,则减小最大值;
反之,增加最小值;直到找到相等;
代码实现:
class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int left = 0, right = price.size() - 1;while (left < right) {if (price[left] + price[right] > target)right--;else if (price[left] + price[right] == target)return {price[left], price[right]};elseleft++;}return {};}
};
LeetCode链接:LCR 179.查找总价格为目标值的两个商品
今日收获:
- 双指针和单调性的结合;
- 返回是vector时,可以返回{};
这篇关于【LeetCode刷题】有效三角形个数、查找总价值为目标值的两个商品的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!