国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

【算法挨揍日記】day03——雙指針算法_有效三角形的個數(shù)、和為s的兩個數(shù)字

這篇具有很好參考價值的文章主要介紹了【算法挨揍日記】day03——雙指針算法_有效三角形的個數(shù)、和為s的兩個數(shù)字。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方,請大家不吝賜教,您也可以點擊"舉報違法"按鈕提交疑問。

【算法挨揍日記】day03——雙指針算法_有效三角形的個數(shù)、和為s的兩個數(shù)字,算法挨揍日記,Leetcode,算法,職場和發(fā)展??

611. 有效三角形的個數(shù)

611.?有效三角形的個數(shù)https://leetcode.cn/problems/valid-triangle-number/

題目描述:

給定一個包含非負整數(shù)的數(shù)組?nums?,返回其中可以組成三角形三條邊的三元組個數(shù)。

【算法挨揍日記】day03——雙指針算法_有效三角形的個數(shù)、和為s的兩個數(shù)字,算法挨揍日記,Leetcode,算法,職場和發(fā)展

解題思路:

本題是一個關(guān)于三角形是否能成立的題目,首先我們假設(shè)三角形的三邊(a,b,c),我們要保證兩邊之和大于第三邊

?【算法挨揍日記】day03——雙指針算法_有效三角形的個數(shù)、和為s的兩個數(shù)字,算法挨揍日記,Leetcode,算法,職場和發(fā)展

?題目給我們nums是亂序的,如果我們一個個abc去實驗就是會超時(時間復(fù)雜度O^3)

當我們將sort排序一下,這樣的話假設(shè)a<b<c的情況下,我們就只要去判斷a+b>c是否成立!

這里我們遍歷每個c(從后往前),這樣時間復(fù)雜度就變成了N^2+NlogN也就是N^2

解題代碼:

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        //假設(shè)a<b<c
        int num=0;
        int n=nums.size();
        for(int i=n-1;i>=2;i--)
        {
            int left=0;
            int right=i-1;
            while(left<right)
            {
                if(nums[left]+nums[right]>nums[i])
                {
                    num+=(right-left);
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return num;
    }
};

??劍指 Offer 57.?和為s的兩個數(shù)字

劍指 Offer 57.?和為s的兩個數(shù)字https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/

題目描述:

輸入一個遞增排序的數(shù)組和一個數(shù)字s,在數(shù)組中查找兩個數(shù),使得它們的和正好是s。如果有多對數(shù)字的和等于s,則輸出任意一對即可。

【算法挨揍日記】day03——雙指針算法_有效三角形的個數(shù)、和為s的兩個數(shù)字,算法挨揍日記,Leetcode,算法,職場和發(fā)展

解題思路:?

首先本題是升序數(shù)組,這里如果我們用暴力的話會超時

這里我們使用雙指針,我們讓一個指向頭left一個指向尾right,這里left、right和target會有三種關(guān)系

我們假設(shè)sub=right-left

【算法挨揍日記】day03——雙指針算法_有效三角形的個數(shù)、和為s的兩個數(shù)字,算法挨揍日記,Leetcode,算法,職場和發(fā)展

?第一種情況很顯然直接返回就好了我們來研究一下第二種和第三種情況:

【算法挨揍日記】day03——雙指針算法_有效三角形的個數(shù)、和為s的兩個數(shù)字,算法挨揍日記,Leetcode,算法,職場和發(fā)展

解題代碼:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n=nums.size();
        int left=0;
        int right=n-1;
        while(nums[right]>target)
        {
            right--;
        }
        while(left<right)
        {
            int sub=target-nums[right];
            if(sub==nums[left])
            {
                return {nums[left],nums[right]};
            }
            else if(sub>nums[left])
            {
                left++;
            }
            else//sub<nums[left]
            {
                right--;
            }
        }
        return {-1,-1};
    }
};

?

?文章來源地址http://www.zghlxwxcb.cn/news/detail-659118.html

到了這里,關(guān)于【算法挨揍日記】day03——雙指針算法_有效三角形的個數(shù)、和為s的兩個數(shù)字的文章就介紹完了。如果您還想了解更多內(nèi)容,請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!

本文來自互聯(lián)網(wǎng)用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務(wù),不擁有所有權(quán),不承擔相關(guān)法律責(zé)任。如若轉(zhuǎn)載,請注明出處: 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符,請點擊違法舉報進行投訴反饋,一經(jīng)查實,立即刪除!

領(lǐng)支付寶紅包贊助服務(wù)器費用

相關(guān)文章

  • 【雙指針】:Leetcode611.有效三角形的個數(shù)

    【雙指針】:Leetcode611.有效三角形的個數(shù)

    朋友們、伙計們,我們又見面了,本專欄是關(guān)于各種算法的解析,如果看完之后對你有一定的啟發(fā),那么請留下你的三連,祝大家心想事成! C 語 言 專 欄: C語言:從入門到精通 數(shù)據(jù)結(jié)構(gòu)專欄: 數(shù)據(jù)結(jié)構(gòu) 個? 人? 主? 頁?: stackY、 C + + 專 欄? ?: C++ Linux 專?欄? : Linu

    2024年02月20日
    瀏覽(24)
  • 每日一題 611有效三角形的個數(shù)(相向雙指針)

    給定一個包含非負整數(shù)的數(shù)組? nums ?,返回其中可以組成三角形三條邊的三元組個數(shù)。 示例 1: 示例 2:

    2024年02月13日
    瀏覽(28)
  • 【LeetCode】雙指針妙解有效三角形的個數(shù)

    【LeetCode】雙指針妙解有效三角形的個數(shù)

    Problem: 611. 有效三角形的個數(shù) 首先我們來分析一下本題的思路 看到題目中給出的示例 題目的意思很簡單,就是將給到的數(shù)字去做一個組合,然后看看這三條邊是否可以構(gòu)成三角形。那判斷的方法不用我說,相信大家如果讀過小學(xué)的話應(yīng)該都明白的,即 三角形兩邊之和大于第

    2024年02月10日
    瀏覽(18)
  • 【算法挨揍日記】day16——525. 連續(xù)數(shù)組、1314. 矩陣區(qū)域和

    【算法挨揍日記】day16——525. 連續(xù)數(shù)組、1314. 矩陣區(qū)域和

    525.?連續(xù)數(shù)組 給定一個二進制數(shù)組? nums ?, 找到含有相同數(shù)量的? 0 ?和? 1 ?的最長連續(xù)子數(shù)組,并返回該子數(shù)組的長度。 本題的元素只有0和1,根據(jù)題目意思,我們可以把題目看成找一段最長的子區(qū)間使得區(qū)間的0 和1的數(shù)量相同,我們可以對其優(yōu)化將所有的0變成-1,這樣這

    2024年02月03日
    瀏覽(20)
  • 【算法挨揍日記】day04——15. 三數(shù)之和、18. 四數(shù)之和

    【算法挨揍日記】day04——15. 三數(shù)之和、18. 四數(shù)之和

    ? 15.?三數(shù)之和 https://leetcode.cn/problems/3sum/ 給你一個整數(shù)數(shù)組? nums ?,判斷是否存在三元組? [nums[i], nums[j], nums[k]] ?滿足? i != j 、 i != k ?且? j != k ?,同時還滿足? nums[i] + nums[j] + nums[k] == 0 ?。請你返回所有和為? 0 ?且不重復(fù)的三元組。 注意: 答案中不可以包含重復(fù)的三元

    2024年02月09日
    瀏覽(26)
  • 「優(yōu)選算法刷題」:有效三角形的個數(shù)

    給定一個包含非負整數(shù)的數(shù)組? nums ?,返回其中可以組成三角形三條邊的三元組個數(shù)。 示例 1: 示例 2: 這道題,有一點挺新鮮的:構(gòu)成三角形的三條邊,僅需滿足 2 條最短邊之和大于等于第三條邊即可。 以前的羅根,就總是傻傻地求 3 次?? 今天這道題,算是又打開了我新世

    2024年01月20日
    瀏覽(21)
  • 【算法挨揍日記】day07——904. 水果成籃、438. 找到字符串中所有字母異位詞

    【算法挨揍日記】day07——904. 水果成籃、438. 找到字符串中所有字母異位詞

    904.?水果成籃 你正在探訪一家農(nóng)場,農(nóng)場從左到右種植了一排果樹。這些樹用一個整數(shù)數(shù)組? fruits ?表示,其中? fruits[i] ?是第? i ?棵樹上的水果? 種類 ?。 你想要盡可能多地收集水果。然而,農(nóng)場的主人設(shè)定了一些嚴格的規(guī)矩,你必須按照要求采摘水果: 你只有? 兩個

    2024年02月07日
    瀏覽(21)
  • 【編程題】有效三角形的個數(shù)

    給定一個包含非負整數(shù)的數(shù)組 nums ,返回其中可以組成三角形三條邊的三元組個數(shù)。 示例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 構(gòu)成三角形的條件 :任意兩條邊之和大于第三邊,其

    2024年02月11日
    瀏覽(25)
  • 力扣:611. 有效三角形的個數(shù)

    力扣:611. 有效三角形的個數(shù)

    今日為大家分享一道力扣611有效三角形的個數(shù)!本文將會為大家為大家講解題目,然后算法思路,最后再進行代碼的實現(xiàn)!希望看完本文能對讀者有一定的收獲! 通過題目的描述可以看出,意思是給定一個數(shù)組,然后觀察數(shù)組中能元素組成三角形的個數(shù)! 題目上面那個例題

    2024年02月08日
    瀏覽(23)
  • 每日一題:LeetCode-611. 有效三角形的個數(shù)

    每日一題:LeetCode-611. 有效三角形的個數(shù)

    前言: ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ????如果說代碼有靈魂,那么它的靈魂一定是???? 算法 ????,因此,想要寫出??優(yōu)美的程序??,核心算法是必不可少的,少年,你渴望力量嗎????,想掌握程序的靈魂嗎???那么就必須踏上這樣一條漫長

    2024年02月01日
    瀏覽(53)

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包,優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包