培训网站建设情况,英文公司网站模板,扶贫工作网站怎么做,vs网站开发需要的组件1.优化版暴力求解
如果能构成三⻆形#xff0c;需要满⾜任意两边之和要⼤于第三边。实际上只需让较⼩的两条边之和⼤于第三边即可。将原数组排序#xff0c;从⼩到⼤枚举三元组#xff0c;这样三层 for 循环枚举出的三元组只需判断较⼩的两条边之和是否⼤于第三边。
class…
1.优化版暴力求解
如果能构成三⻆形需要满⾜任意两边之和要⼤于第三边。实际上只需让较⼩的两条边之和⼤于第三边即可。将原数组排序从⼩到⼤枚举三元组这样三层 for 循环枚举出的三元组只需判断较⼩的两条边之和是否⼤于第三边。
class Solution
{
public:int triangleNumber(vectorint nums){sort(nums.begin(), nums.end());int n nums.size(), ret 0;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;}
};2.排序二分
在 [j1,n−1] 的下标范围内使用二分查找找出最大的满足 nums[k]nums[i]nums[j]的下标 k在 [j1,k] 范围内的下标都可以作为边 c 的下标将该范围的长度 k−j 累加。在枚举a和b时出现了0那么 nums[i] 一定为 0。边c需要满足c nums[i] nums[j] nums[j]而下标在[j1,n-1]范围内的元素一定都是大于等于 nums[j]的因此二分查找会失败。若二分查找失败我们可以令kj此时对应的范围长度k-j0我们也就保证了答案的正确性。
class Solution
{
public:int triangleNumber(vectorint nums){int n nums.size();sort(nums.begin(), nums.end());int ret 0;for (int i 0; i n; i){for (int j i 1; j n; j){int left j 1, right n - 1, k j;while (left right){int mid (left right) / 2;if (nums[mid] nums[i] nums[j]){k mid;left mid 1;}else{right mid - 1;}}ret k - j;}}return ret;}
};
3.排序双指针
此法是对上述两种方法的优化。 排序过后数组数据为递增排列。 首先我们先来看这样一个数学常识 将一个递增排序的数组分为两部分
如果此时有Left Right Max 那么 Right Right-1 Right Right-2 Right … Right Left 的值都大于Max。那么能够构成△的二元组个数为right - left个 此时 right 位置元素的所有情况相当于全部考虑完毕 right – 进⼊下⼀轮判断同上如果 nums[left] nums[right] nums[i] 说明 left 位置的元素是不可能与 [left 1, right] 位置上的元素构成满⾜条件的⼆元组left 位置的元素可以舍去 left 进⼊下轮循环。 代码 class Solution
{
public:int triangleNumber(vectorint nums){sort(nums.begin(), nums.end());int ret 0, n nums.size();for (int cur n - 1; cur 2; cur--){int left 0, right cur - 1;while (left right){if (nums[left] nums[right] nums[cur]){ret right - left;right--;}elseleft;}}return ret;}
};
