資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的有效三角形數
假如我們有一個非負整陣列成的陣列，我們的任務是計算從陣列中選出的那些三元組的數目，如果我們把它們作為三角形的邊長，就能夠組成三角形。因此，如果輸入類似 [2,2,3,4]，那麼結果將是 3，因為 [2,3,4] 使用第一個 2，[2,3,4] 使用第二個 2，[2,2,3] 是三個三角形。
為了解決這個問題，我們將遵循以下步驟——
- ret := 0，n := num 的大小，nums 排序
- 對於範圍 n – 1 到 0 的 i
- right := i – 1，left := 0
- while left < right
- sum := nums[left] + nums[right]
- 如果 sum > nums[i]，則令 ret 增加 right – left 減小 right 1，否則增加 left 1
- 返回 ret
讓我們看以下實現以獲得更好的理解——
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int triangleNumber(vector<int>& nums) {
int ret = 0;
int n = nums.size();
sort(nums.begin(), nums.end());
for(int i = n - 1; i >= 0; i--){
int right = i - 1;
int left = 0;
while(left < right){
int sum = nums[left] + nums[right];
if(sum > nums[i]){
ret += right - left;
right--;
}else left++;
}
}
return ret;
}
};
main(){
vector<int> v = {2,2,3,4};
Solution ob;
cout << (ob.triangleNumber(v));
}輸入
[2,2,3,4]
輸出
3
更新於：2020-05-04
507 次瀏覽
廣告