Leetcode(C++)
題目 : https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/ 。
想法 :
Greedy,類似經典的社團活動題。
用尾巴的大小排序,因為第一個區間總是需要被射掉,所以就以第一個區間當作指標開始射。
如果下一個區間的開頭比現在的指標還要大了,那就代表我們需要第二枝箭了。
以此往下遞推。
證明 : 區間內射掉的某一個區間與現在的互換,不影響箭矢數量,反而有可能增加。
時間複雜度 : O(n)。
程式碼 :
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
int l=points.size(), ans=0, end;
if(l == 0) return 0;
if(l == 1) return 1;
sort(points.begin(), points.end(), [](auto &v1, auto &v2){
return v1[1] < v2[1];
});
/*for(int i=0 ; i<l ; i++){
cout << points[i][0] << " " << points[i][1] << endl;
}*/
end=points[0][1];
for(auto p:points){
if(p[0] <= end) continue;
else{
ans++; end=p[1];
}
}
return ++ans;
}
};
題目 : https://leetcode.com/problems/richest-customer-wealth/ 。 想法 : 語法。 時間複雜度 : O(n*m)。 程式碼 : (JAVA)
Feb 5, 2022題目 : https://leetcode.com/problems/coin-change-2/ 。 想法 : 無窮背包問題。 時間複雜度 : O(n*m)。 程式碼 : (JAVA)
Feb 5, 2022題目 : https://leetcode.com/problems/integer-break/ 。 想法 : 規律就在2跟3身上(?),把一個數字分解成2跟3的總和就好。 時間複雜度 : O(1)。 程式碼 : (JAVA)
Feb 5, 2022題目 : https://leetcode.com/problems/longest-common-subsequence/ 。 想法 : LCS。 if(str[i] == str[j]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
Feb 5, 2022or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up