沒事的時候打算開始玩一玩leetcode，不然天天寫代碼，卻對算法沒啥認(rèn)識還是有點(diǎn)尷尬的。雖說是做題，其實(shí)大部分就是為了看看別人牛逼的思路。盡量每天一題把～

創(chuàng)新互聯(lián)公司專注于企業(yè)網(wǎng)絡(luò)營銷推廣、網(wǎng)站重做改版、巴中網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5響應(yīng)式網(wǎng)站、商城網(wǎng)站制作、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站制作、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計(jì)等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為巴中等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

1.兩數(shù)之和

給定一個整數(shù)數(shù)組和一個目標(biāo)值，找出數(shù)組中和為目標(biāo)值的兩個數(shù)。

你可以假設(shè)每個輸入只對應(yīng)一種答案，且同樣的元素不能被重復(fù)利用。
例：
        給定 nums = [2, 7, 11, 15], target = 9

        因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
        所以返回 [0, 1]

第一種方法就是便利數(shù)組，隨著數(shù)組長度增加，執(zhí)行時間指數(shù)型增加。

#時間復(fù)雜度：O(n^2)
#空間復(fù)雜度：O(1)
func twoSum(nums []int, target int) []int {
    for firstIndex,firstNum := range nums{
        for secondIndex,secondNum := range nums{
            if firstIndex != secondIndex && firstNum + secondNum == target{
                return []int{firstIndex, secondIndex}
            }
        }
    }
    return nil
}

第二種方式是以空間換時間，把數(shù)據(jù)存在哈希表里面，最多只用完全遍歷一次數(shù)組，就能得到結(jié)果。

#時間復(fù)雜度：O(n)
#空間復(fù)雜度：O(n)
func twoSumHash(nums []int, target int) []int {
    m :=  make(map[int]int)
    for index,num := range nums{
        i,ok := m[target - num]
        if ok {
            return []int{i,index}
        }
        m[num] = index
    }
    return nil
}

題目鏈接：https://leetcode-cn.com/problems/two-sum/description/

作為腦子是條直線的小白，解題的方法是第一種，打死估計(jì)都想不到第二種把。

2.兩數(shù)相加

給定兩個非空鏈表來表示兩個非負(fù)整數(shù)。位數(shù)按照逆序方式存儲，它們的每個節(jié)點(diǎn)只存儲單個數(shù)字。將兩數(shù)相加返回一個新的鏈表。

你可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)字都不會以零開頭。

示例：

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8 
原因：342 + 465 = 807

這個題主要有兩個地方卡了我一下，第一，輸入的兩個鏈表可能是不一樣長的，第二，最后一位相加可能會進(jìn)1，所以此時，輸出比輸入多一位數(shù)字，就是多一個節(jié)點(diǎn)。
我在思考次題目時候，想方設(shè)法的想把輸出鏈表的第一個節(jié)點(diǎn)，填入數(shù)字，其實(shí)可以這樣。鏈表第一個節(jié)點(diǎn)可以為空，然后從第二個節(jié)點(diǎn)賦值，最后return時候，返回head.Next?？瓤龋缫淹洰?dāng)年學(xué)數(shù)據(jù)結(jié)構(gòu)的時候，就是這么干的。
我的答案：

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    l := new(ListNode)
    temp := l
    lsum := 0
    for  {
        if l1 != nil{
            lsum += l1.Val
            l1 = l1.Next
        }
        if l2 != nil{
            lsum += l2.Val
            l2 = l2.Next
        }
        temp.Val = lsum % 10
        lsum = lsum / 10
        if lsum != 0 || l1 != nil || l2 != nil{
            nextNode := new(ListNode)
            temp.Next = nextNode
            temp = temp.Next
        }else{
            break
        }

    }
    return l

}

網(wǎng)站給出的答案：

func addTwoNumbers2(l1 *ListNode, l2 *ListNode) *ListNode{
    dummyHead := new(ListNode)
    p,q,curr := l1,l2,dummyHead
    carry := 0
    for p !=nil || q != nil{
        x,y := 0,0
        if p != nil {
            x = p.Val
        }
        if q != nil {
            y = q.Val
        }
        sum := x + y + carry
        carry = sum /10
        curr.Next = new(ListNode)
        curr = curr.Next
        curr.Val = sum % 10
        if p !=nil{
            p = p.Next
        }
        if q !=nil{
            q = q.Next
        }
    }
    if carry > 0{
        curr.Next = &ListNode{Val:carry}
    }
    return dummyHead.Next
}

網(wǎng)站的答案會把l1和l2賦值給一個臨時變量，這樣就不會影響函數(shù)外的l1，l2，這是我所忽略的。
網(wǎng)站的答案，把sum和carry分成兩個變量，增強(qiáng)了可讀性，我放在一起，基本上就看不出來為啥，除以10賦值給sum。然后我變量命名過于隨意。

3. 無重復(fù)字符的最長子串

看見字符串匹配的題的就慫，所以卡了好幾天不敢做。我自己的答案倒是嘗試快10次了。才通過所有的測試。坑的點(diǎn)還是不少的。說下我的實(shí)現(xiàn)思路吧。

func lengthOfLongestSubstring(s string) int {
    filter := make(map[int32]int)         // 比較喜歡用哈希表統(tǒng)計(jì)重復(fù)
    lastKey := 0                          // 記錄重復(fù)時，與本次重復(fù)的上一次重復(fù)點(diǎn)的下一位的index（非重復(fù)開始的位置）
                                                //比如當(dāng)前字母的index為10，與之重復(fù)的字母的index為5，那么lastKey的值就賦值為5
    max := 0                              //大連續(xù)不重復(fù)字串的長度
    for k,v := range s{                   //遍歷字串
        index,ok := filter[v]            //判斷是否發(fā)生重復(fù)
        if ok {                            //發(fā)生重復(fù)
            if k - lastKey  >max{         //計(jì)算重復(fù)點(diǎn)到上一個重復(fù)點(diǎn)的長度
                max = k - lastKey         
            }
            for i := lastKey;i<index;i++{    //index是與當(dāng)前字母重復(fù)的所在位置，刪除此位置之前的所有字母。
                delete(filter, int32(s[i])) 
            }
            lastKey = index+1                
        }
        filter[v] = k                       //新增或更新當(dāng)前字母的index值
    }
    if len(s) - lastKey > max{            //有可能中間某個點(diǎn)，到最后一個字母都沒有重復(fù)，所以不會觸發(fā)ok里面的檢測，因此判斷非重復(fù)點(diǎn)到最后一個字母的距離。
        max = len(s) - lastKey
    }
    return max
}

網(wǎng)站給的答案：

1.滑動窗口，網(wǎng)站答案是用集合實(shí)現(xiàn)的，因?yàn)間o本身沒有集合的包，所以我還是用map

# i和j就是字串的開始坐標(biāo)和結(jié)束坐標(biāo)。遍歷字符串s，如果當(dāng)前字母，在字串i，j中沒有重復(fù)，則j加1，即字串長度加一，如果當(dāng)前字母在i，j中有重復(fù)的，則刪除字串的第一個字母。因?yàn)橛锌赡苤貜?fù)的字母在i，j中間，所以就會一直刪除字串的第一個字母，直到刪除至子串中沒有重復(fù)的字母。就得到了，非重復(fù)字串。
#思路是真的好呀。之前我一直糾結(jié)怎么，當(dāng)字串中有重復(fù)字母的時候，怎么確定，map中刪除哪些key，網(wǎng)站的思路就很流暢呀?。?！贊！

func lengthOfLongestSubstring(s string) int {
    filter := make(map[uint8]int)
    n := len(s)
    i,j,max := 0,0,0

    for i < n && j < n {
        _,ok := filter[s[j]]
        if !ok{
            filter[s[j]] = 0
            j++
            if j - i > max{
                max = j - i
            }
        }else {
            delete(filter,s[i])
            i++
        }
    }
    return max
}

2.優(yōu)化的滑動窗口,原來網(wǎng)站也有map的思路

#其實(shí)放入map中的值并不需要刪除....對比一下，我寫的答案太low了。。。
func lengthOfLongestSubstring(s string) int {
    filter := make(map[uint8]int)
    n := len(s)
    max := 0

    for i,j := 0,0; j < n; j++ {
        index,ok := filter[s[j]]       #判斷當(dāng)前字母是否在map中已存在
        if ok{                               #如果存在，就把index賦值給i
            if index > i {                   #比如map中有一個字母a，他的index為3,如果當(dāng)前字母也為a，就吧之前a的index保存到i中
                i = index                      #為什么判斷大小呢？假如a的index為3，他前面有一個字母b，當(dāng)前字母為a，所以i為3，如果下一個字母為b，因?yàn)樯弦粋€a之前有一個b，所以b是存在的，但是上一個b的在字母a前面，所以i不變。這就是map不用刪除key的原因
            }
        }
        if j - i +1 > max{
            max = j - i + 1
        }
        filter[s[j]] = j+1
    }
    return max
}

4. 兩個排序數(shù)組的中位數(shù)

題目：給兩個有序的數(shù)組，取兩個長度為n,m的數(shù)組的中位數(shù)，并且時間復(fù)雜度為Olog(min(n,m))
例1：

nums1 = [1, 3]
nums2 = [2]
中位數(shù)是 2.0

例2:

nums1 = [1, 2]
nums2 = [3, 4]
中位數(shù)是 (2 + 3)/2 = 2.5

其實(shí)這道題考的排序算法，所以哪個排序算法的時間復(fù)雜度是O(log n)呢，還給了兩個有序的數(shù)組，第一想到的就是歸并排序的最后一步。

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    i,j := 0,0
    sorted := make([]int,0)
    for i < len(nums1) && j < len(nums2){
        if nums1[i] > nums2[j]{
            sorted = append(sorted,nums2[j])
            j++
        }else {
            sorted = append(sorted,nums1[i])
            i++
        }
    }
    sorted = append(sorted,nums1[i:]...)
    sorted = append(sorted,nums2[j:]...)
    n := len(sorted)
    if n % 2 ==0{
        return (float64(sorted[n/2-1]) + float64(sorted[n/2]))/2
    }
    return float64(sorted[(n-1)/2])
}

嚶嚶嚶，網(wǎng)站答案看的腦殼疼。。。。
看完網(wǎng)站的答案，我掐指一算，我的時間復(fù)雜度是O(min(n,m)),想要時間復(fù)雜度為O(log(mint(n,m))),就得用二分法。分析過程好復(fù)雜，腦殼疼。實(shí)現(xiàn)也復(fù)雜，要考慮的因素好多。。。。

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

文章題目：leetcode記錄貼（go語言）-創(chuàng)新互聯(lián)
標(biāo)題來源：http://www.rwnh.cn/article4/doshoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、全網(wǎng)營銷推廣、網(wǎng)站維護(hù)、電子商務(wù)、服務(wù)器托管、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)