国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Two Sum系列 Leetcode解題記錄

andong777 / 3316人閱讀

摘要:如果沒(méi)有,就到里面復(fù)雜度分析就是,因?yàn)橹粧吡艘槐閿?shù)組。復(fù)雜度分析當(dāng)然就是最壞情況了,也是標(biāo)準(zhǔn)的雙指針復(fù)雜度。復(fù)雜度分析這種題應(yīng)該不太需要分析復(fù)雜度吧,能實(shí)現(xiàn)就行。復(fù)雜度分析還是最后再說(shuō)兩句所以可以看出,很多題目思路一致,換湯不換藥。

Two Sum

友情提示:篇幅較長(zhǎng),找題目的話,右邊有目錄,幸好我會(huì)MarkDown語(yǔ)法。
改成了系列模式,因?yàn)轭愃频念}不少,本質(zhì)上都是換殼,所以在同一篇文章里面把這類問(wèn)題匯總一下。先說(shuō)2 Sum。這道題非常出名,因?yàn)檫@是leetcode的第一道題。很多人說(shuō)一些公司招聘的時(shí)候,這道題專門出給他們想招進(jìn)來(lái)的人,因?yàn)檫@不是放水,簡(jiǎn)直就是洪水。要做的就是已知一個(gè)數(shù)組,和一個(gè)target值。返回兩個(gè)目標(biāo)的index,這兩個(gè)目標(biāo)求和就是target值。

解決思路

這題不難,只需要熟悉hashtable即可。在hashtable里面,key是差,value是index。比如例子中的[2,7,11,15],target是9。那么在2的時(shí)候就存入7 0,下一位找到7的時(shí)候,之前有個(gè)差值是7,那么就返回7對(duì)應(yīng)的index,0,以及當(dāng)前這個(gè)7的index,就是1。

code
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        //創(chuàng)建一下數(shù)組,要存兩個(gè)index的數(shù)組。
        int[] result = new int[2];
        //這里用hashtable也行,看心情。
        Map map = new HashMap();
        //掃一遍數(shù)組,一邊掃一邊存
        for(int i = 0; i < nums.length; i++){
            int cur = nums[i];
            //這里搞出來(lái)個(gè)差值,其實(shí)差值是在沒(méi)找到之后添加到map里面的。
            int toFind = target - cur;
            //如果發(fā)現(xiàn)之前需要這個(gè)差值,那就找index。
            if(map.containsKey(cur)){
                result[0] = map.get(cur);
                result[1] = i;
                return result;
            }
            //如果沒(méi)有,就put到map里面
            else{
                map.put(toFind, i);
            }
        }
        return result;
    }
}
復(fù)雜度分析

就是O(n),因?yàn)橹粧吡艘槐閿?shù)組。

最后再說(shuō)兩句

雖然這題非常簡(jiǎn)單,但是14年秋天第一次看到這題的時(shí)候感覺(jué)還是難到爆炸,無(wú)從下手。因?yàn)橐唤z編程基礎(chǔ)都沒(méi)有,現(xiàn)在兩年過(guò)去了,用腳趾都能敲出來(lái)。其實(shí)行業(yè)之間努力其次,路徑非常重要,在這里感謝一下點(diǎn)撥我的老鄉(xiāng)和兄弟們。而且重新寫了幾次,連變量命名都是一樣的。

Two Sum II - Input array is sorted 解決思路

這題用sorted當(dāng)做題目,好比路邊的一些職業(yè)勾引男性行人,非常直接的就意味著二分搜索。一次查一半,所以剛開始只用到了二分搜索。但是有個(gè)問(wèn)題,二分搜索的步子太大,可能把目標(biāo)值跳過(guò),那么還要借鑒雙指針的全盤掃描的特點(diǎn)。

code
public class Two_Sum_II {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        //這里用二分搜索,我常用start和end來(lái)命名兩頭,middle是中間。
        int start = 0;
        int end = numbers.length-1;
        //這個(gè)while循環(huán)條件很巧妙,二分搜索建議固定一個(gè)模板,這個(gè)就挺好固定的。
        while (start + 1 < end) {
            //看,我剛說(shuō)的是實(shí)話,而且這里middle的計(jì)算方法是防止越界。
            int middle = start + (end-start)/2;
            if (numbers[start] + numbers[end] < target) {
                //這里需要判斷,到底是跳一半還是走一步,就再加個(gè)判斷。
                if (numbers[middle] + numbers[end] < target) {
                    start = middle;
                }
                else {
                    start++;
                }
            }
            else if(numbers[start] + numbers[end] > target) {
                if (numbers[middle] + numbers[start] > target) {
                    end = middle;
                }
                else {
                    end--;
                }
            }
            else {
                break;
            }
        }
        //題目中保證了有結(jié)果,還不是zero-based,那么就把result兩項(xiàng)都續(xù)一秒。
        result[0] = start+1;
        result[1] = end+1;
        return result;
    }
}
復(fù)雜度分析

當(dāng)然就是最壞情況O(n)了,也是標(biāo)準(zhǔn)的雙指針復(fù)雜度。不過(guò)二分搜索方法是它最優(yōu)情況是O(nlgn)。

最后再說(shuō)兩句

不得不說(shuō),這個(gè)題目把二分搜索和雙指針拼在一起非常有創(chuàng)意。只用二分搜索讓我多交了一個(gè)submit,好題一個(gè)。

Two Sum III - Data structure design
Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

鎖住的題,罕見(jiàn)的一道design題目和Google沒(méi)關(guān)系,tag只有Linkedin,怪不得被收購(gòu)了。

解決思路

這是一道入門級(jí)別的design題目,當(dāng)然第一次遇到design這個(gè)詞我就像腦血栓般渾身發(fā)抖。不過(guò)好在它脫胎于Two Sum,本質(zhì)上還是不難的,我們要做的就是套上design的外殼,解決掉它。值得注意的是,一個(gè)數(shù)字只能用1次,所以還是要記錄一下數(shù)字出現(xiàn)的次數(shù)的。

code
public class TwoSumIII {
    //用一個(gè)List當(dāng)容器裝數(shù)字,用Map來(lái)記錄數(shù)字出現(xiàn)的次數(shù)
    List list = new ArrayList<>();
    Map map = new HashMap();
    // Add the number to an internal data structure.
    public void add(int number) {
        list.add(number);
        //非常常規(guī)的往map里記錄出現(xiàn)個(gè)數(shù)的寫法
        if (map.containsKey(number)) {
            map.put(number, map.get(number)+1);
        }
        else {
            map.put(number,1);
        }
    }

    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        for (int i = 0; i < list.size(); i++) {
            int cur = list.get(i);
            int toFind = value - cur;
            //這里還是Two Sum的求法,取一個(gè),找另一個(gè)。值得注意的是需要看求和的兩個(gè)數(shù)是不是相等。
            if (cur != toFind) {
                //根據(jù)leetcode測(cè)試,在map里面找比在list找目標(biāo)數(shù)字更快一些。
                if (map.containsKey(toFind)) {
                    return true;
                }
            }
            else {
                if (map.get(cur) > 1) {
                    return true;
                }
            }
        }
        return false;
    }
}
復(fù)雜度分析

這種題應(yīng)該不太需要分析復(fù)雜度吧,能實(shí)現(xiàn)就行。每次都是遍歷一遍L(zhǎng)ist,所以就是O(n)。

最后再說(shuō)兩句

寫的時(shí)候發(fā)現(xiàn)其實(shí)遍歷一下Map也行,可以省去一個(gè)list。但我偏偏不省,因?yàn)長(zhǎng)ist不要錢,能加就加,而且看著也方便,一個(gè)map用于不同的用途,可能會(huì)引起線程沖突。出來(lái)混,多一事不如少一事。

3 Sum

這題用腳后跟看都是2Sum的follow up。就是在一個(gè)數(shù)組里面挑3個(gè)數(shù)字,這三個(gè)數(shù)字的和為0就行。需要注意的是triplet這個(gè)單詞的拼寫和發(fā)音,還有不能有重復(fù)的triplet,不能重復(fù)這一點(diǎn)還是有點(diǎn)兒小麻煩的

解決思路

既然是follow up,解決思路也就是follow up。follow up是什么意思呢,我們翻譯一下,follow就是跟隨,up就是上面。就是跟隨上面的意思,我們往上看,上面只有2Sum一題,那我們就跟隨一下。A+B是2Sum,A+B+C是3Sum,那么稍加修改A+(B+C)就成了這兩道題連接的橋梁。所以這題的基本思路就是套了個(gè)殼子而已。
值得一提的是,此題可能有重復(fù)數(shù)字,而且要求不能有重復(fù)結(jié)果,所以使用雙指針?lè)āG懊孢@句的不是很理所當(dāng)然,在這里就當(dāng)經(jīng)驗(yàn)記錄一下了,強(qiáng)行解釋就是指針可以跳過(guò)重復(fù)的數(shù)字,而且求和也很容易。

code
public class ThreeSum {
    public List> threeSum(int[] nums) {
        //首先把輸出寫出來(lái)
        List> result = new ArrayList<>();
        //雙指針出馬之前數(shù)組通常需要排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            //這個(gè)本意是重復(fù)數(shù)字的話可以跳過(guò)。因?yàn)橹暗臄?shù)字已經(jīng)打頭過(guò)了,重復(fù)的就沒(méi)必要打頭了。
            if (i > 0 && cur == nums[i-1]) {
                continue;
            }
            //雙指針出馬,這里注意了我一般命名成left和right。
            int left = i+1;
            int right = nums.length-1;
            //這里注意了開始2Sum過(guò)程。
            while (left < right) {
                int two_sum = nums[left] + nums[right];
                if (two_sum < -1*cur) {
                    //說(shuō)明加和小了,那把左指針往右移動(dòng)
                    left++;
                }
                else if (two_sum > -1 * cur) {
                    //大了那就往左移動(dòng)
                    right--;
                }
                else {
                    List list = new ArrayList<>();
                    list.add(cur);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    //把這次記錄的結(jié)果加到result里面
                    result.add(list);
                    //下回測(cè)試corner case的時(shí)候就一群0,這次4個(gè)0就吃虧了,忘了這個(gè)while循環(huán),所以要跳過(guò)重復(fù)數(shù)字。
                    while(left+1 < right && nums[left] == nums[left+1]){
                        left++;
                    }
                    while (right-1 > left && nums[right] == nums[right-1]) {
                        right--;
                    }
                    //跳過(guò)之后,繼續(xù)挪動(dòng)一下。
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
}
復(fù)雜度分析

這個(gè)排序的復(fù)雜度是O(nlgn),循環(huán)的復(fù)雜度就是O(n^2),所以就是循環(huán)的復(fù)雜度n方。

最后再說(shuō)兩句

其實(shí)這種數(shù)組題,無(wú)論多么的熟練,都要在紙上先勾畫一下思路,尤其是這道題里面重復(fù)數(shù)字的處理,其實(shí)也可以用個(gè)set來(lái)去重,但那樣畢竟顏值不行,不符合我自拍的一貫水準(zhǔn)。跳過(guò)相等數(shù)字,最后再挪動(dòng)一下,code里面不好分析,在紙上畫畫一目了然。

3 Sum Smaller
Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.
Return 2. Because there are two triplets which sums are less than 2:
  [-2, 0, 1] [-2, 0, 3]

Follow up:
Could you solve it in O(n2) runtime?

這題居然是鎖住的,company tag只有一個(gè)Google,所以把題目?jī)?nèi)容貼上來(lái)。

解決思路

這題說(shuō)老實(shí)話讓我很困惑,為啥這題都能當(dāng)一道題出了。其實(shí)就是3Sum稍微變一下,然后返回個(gè)個(gè)數(shù)而不是一群triplet。而且要求是O(n2),那類比3Sum的雙指針?lè)椒梢詽M足。

code

public class Three_Sum_Smaller {

public int threeSumSmaller(int[] nums, int target) {
    //雙指針是一定要排序的,否則后面根據(jù)大小挪動(dòng)指針就沒(méi)有意義了。
    Arrays.sort(nums);
    int result = 0;
    for (int i = 0; i < nums.length-2; i++) {
        int left = i+1;
        int right = nums.length-1;
        int cur = nums[i];
        while (left < right) {
            int two_sum = nums[left] + nums[right];
            //這里需要注意如果滿足條件,接下來(lái)不需要移動(dòng)指針,直接把中間所有的可能性都加起來(lái)就可以
            if (cur + two_sum < target) {
                result += right - left;
                left++;
            }
            else {
                //只有和大了,才要讓右邊指針左移,讓整體小一些。
                right--;
            }
        }
    }
    return result;
}

}

復(fù)雜度分析

直接O(n2)了,就是兩重循環(huán),多說(shuō)一句,雙指針就是把O(n2)降成O(n)的,外面再套一層循環(huán),就是O(n2)了。

最后再說(shuō)兩句

這題會(huì)做了,Google是不是能過(guò)一輪了啊。就注意小于的情況直接求result就行。

3 Sum Closet

還是一個(gè)數(shù)組,還有個(gè)目標(biāo)數(shù)。返回距離目標(biāo)最近的一個(gè)和,這個(gè)和是3個(gè)數(shù)的和。

解決思路

和上面一樣,雙指針,看大小。

code
public class ThreeSumClosest {
    public int threeSumClosest(int[] nums, int target) {
        if(nums == null || nums.length < 3){
            return 0;
        }
        int res = 0;
        int diff = Integer.MAX_VALUE;
        Arrays.sort(nums);

        for(int cur = 0; cur < nums.length-2; cur++){
            int left = cur+1;
            int right = nums.length-1;
            int tempTar = target-nums[cur];
            while(left < right){
                int sum = nums[left] + nums[right];
                int value = Math.abs(sum-tempTar);
                //找到更小的就更新。
                if(value <= diff){
                    diff = value;
                    res = nums[cur] + nums[left] + nums[right];
                }
                if(sum < tempTar){
                    left++;
                    
                }
                else if(sum > tempTar){
                    right--;
                }
                else{
                    return target;
                }
            }
        }
        return res;
    }
}
復(fù)雜度分析

還是O(n2).

最后再說(shuō)兩句

所以可以看出,很多題目思路一致,換湯不換藥。都是雙指針掃數(shù)組,非常容易。

4 Sum

這次是4個(gè),就是找四個(gè)數(shù),它們的和是目標(biāo)數(shù)。

解決思路

這次就是3 Sum套了個(gè)殼而已,方法都是一樣的。

code
public class FourSum {
    public List> fourSum(int[] nums, int target) {
        List> res = new ArrayList<>();
        //象征性的說(shuō),如果沒(méi)有4個(gè)數(shù),那還玩?zhèn)€球啊
        if(nums.length < 4) return res;
        //雙指針排序,都看膩了吧
        Arrays.sort(nums);
        for(int i = 0; i < nums.length-3; i++){
            //去掉重復(fù)的數(shù)字,就是打頭不能相同
            if(i > 0 && nums[i] == nums[i-1]) continue;
            for(int j = i+1; j < nums.length-2; j++){
                //再去掉一遍
                if(j > i+1 && nums[j] == nums[j-1]) continue;
                //實(shí)力打臉,以后還是要left和right,low和high太low了。
                int low = j+1, high = nums.length-1;
                while(low < high){
                    int sum = nums[i] + nums[j] + nums[low] + nums[high];
                    if(sum == target){
                        //這里新建一個(gè)list也行。
                        res.add(Arrays.asList(nums[i],nums[j], nums[low], nums[high]));
                        while(low+1 < high && nums[low+1] == nums[low]){
                            low++;
                        }
                        while(high-1 > low && nums[high-1] == nums[high]){
                            high--;
                        }
                        low++;
                        high--;
                    }
                    else if(sum < target){
                        low++;
                    }
                    else{
                        high--;
                    }
                }
            }
        }
        return res;
    }
}
復(fù)雜度分析

O(n3),因?yàn)槭侨匮h(huán)。

最后再說(shuō)兩句

這個(gè)系列結(jié)束了,沒(méi)想到從2 Sum可以延伸這么長(zhǎng)。不過(guò)核心思想都差不多,一些細(xì)節(jié)處,比如去掉重復(fù)數(shù)字這種手法需要多加熟練。
這個(gè)9月加油找了。

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/65061.html

相關(guān)文章

  • LeetCode 167:兩數(shù)之和 II - 輸入有序數(shù)組 Two Sum II - Input a

    摘要:公眾號(hào)愛(ài)寫給定一個(gè)已按照升序排列的有序數(shù)組,找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)。函數(shù)應(yīng)該返回這兩個(gè)下標(biāo)值和,其中必須小于。示例輸入輸出解釋與之和等于目標(biāo)數(shù)。 公眾號(hào): 愛(ài)寫bug(ID:icodebugs) 給定一個(gè)已按照升序排列 的有序數(shù)組,找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)。 函數(shù)應(yīng)該返回這兩個(gè)下標(biāo)值 index1 和 index2,其中 index1 必須小于 index2。...

    張春雷 評(píng)論0 收藏0
  • LeetCode 167:兩數(shù)之和 II - 輸入有序數(shù)組 Two Sum II - Input a

    摘要:公眾號(hào)愛(ài)寫給定一個(gè)已按照升序排列的有序數(shù)組,找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)。函數(shù)應(yīng)該返回這兩個(gè)下標(biāo)值和,其中必須小于。示例輸入輸出解釋與之和等于目標(biāo)數(shù)。 公眾號(hào): 愛(ài)寫bug(ID:icodebugs) 給定一個(gè)已按照升序排列 的有序數(shù)組,找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)。 函數(shù)應(yīng)該返回這兩個(gè)下標(biāo)值 index1 和 index2,其中 index1 必須小于 index2。...

    Me_Kun 評(píng)論0 收藏0
  • LeetCode - 001 - 兩數(shù)之和(two-sum

    摘要:解法返回目錄解題代碼執(zhí)行測(cè)試解題思路使用雙重循環(huán)破解。解法返回目錄解題代碼執(zhí)行測(cè)試知識(shí)點(diǎn)遍歷數(shù)組,返回遍歷項(xiàng),返回當(dāng)前索引。 Create by jsliang on 2019-05-16 22:19:13 Recently revised in 2019-05-17 14:22:40 Hello 小伙伴們,如果覺(jué)得本文還不錯(cuò),記得給個(gè) star , 小伙伴們的 star 是我持續(xù)更新的動(dòng)...

    habren 評(píng)論0 收藏0
  • LeetCode 攻略 - 2019 年 7 月下半月匯總(100 題攻略)

    摘要:月下半旬攻略道題,目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題,所以后面會(huì)調(diào)整自己,在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí),攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題,目前已攻略 100 題。 一 目錄 不折騰的前端,和咸魚有什么區(qū)別...

    tain335 評(píng)論0 收藏0
  • LeetCode 攻略 - 2019 年 7 月上半月匯總(55 題攻略)

    摘要:微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言內(nèi)容,進(jìn)行補(bǔ)充,并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...

    warmcheng 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

andong777

|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<