LeetCode 題目理解匯總

大三后，就開始折騰各種項目開發(fā)，再也沒有搞算法了，到現(xiàn)在，畢業(yè)后工作都快一年了，感覺自己腦子有時候反而變得不太靈活了，閑來無聊，想到杭電刷兩道題，結(jié)果死活記不起曾經(jīng)的號，算了，從頭開始，在LeetCode上注冊個賬號，有空刷上一兩道題，順便記錄下對題目的理解。

2. Add Two Numbers

圖片.png

這題目是最簡單的鏈表值相加，基礎(chǔ)算法題目，要注意的是，最后一位數(shù)是否要進位的問題，直接上代碼：

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    var number = 0
    var list: ListNode!
    var list1 = l1;
    var list2 = l2;
    var list3: ListNode!
    while list1 != nil && list2 != nil {
        let a = (list1?.val)!
        let b = (list2?.val)!
        if list == nil {
            list = ListNode((a + b + number) % 10)
            list3 = list
        } else {
            list3.next = ListNode((a + b + number) % 10)
            list3 = list3?.next
        }
        number = (a + b + number) / 10
        list1 = list1?.next
        list2 = list2?.next
    }
    var li: ListNode!
    if list1 != nil || list2 != nil {
        li = list1 != nil ? list1 : list2
        while li != nil {
            let a = li?.val
            if list == nil {
                list = ListNode((a! + number) % 10)
                list3 = list
            } else {
                list3.next = ListNode((a! + number) % 10)
                list3 = list3?.next
            }
            number = (a! + number) / 10
            li = li.next
        }
    }
    
    if number != 0 {
        list3.next = ListNode(number)
        list3 = list3?.next
    }
    return list
}

7. Reverse Integer

圖片.png

數(shù)字的反轉(zhuǎn)問題，需要注意，反轉(zhuǎn)后的值如果大于int32的最大值， 則返回0，水題，上代碼：

func reverse(_ x: Int) -> Int {
    let max_int = (1<<31)-1
    let min_int = -1<<31
    
    var flag = false
    var num = x
    var arr: [Int] = []
    if x == 0 {
        return x
    }
    
    if x < 0 {
        num = -num
        flag = true
    }
    
    while num != 0 {
        arr.append(num % 10)
        num /= 10
    }
    
    func power(_ a: Int, _ b: Int) -> Int {
        if b == 0 {
            return 1
        }
        var num = a
        for _ in 1..<b {
            num *= a
        }
        return num
    }
    
    var reverseNum = 0
    for index in 0..<arr.count {
        reverseNum += arr[arr.count - index - 1] * power(10, index)
    }
    
    if flag {
        reverseNum = -reverseNum
    }
    
    if reverseNum < min_int || reverseNum > max_int {
        return 0
    }
    
    return reverseNum
}

19. Remove Nth Node From End of List

64A63B0D-1C8A-4EBF-9D91-DD222F2A1526.png

刪除鏈表中的指定值，水題，不解釋，直接上代碼：

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    var list: ListNode!
    var list1 = head
    var list2: ListNode!
    var arr: [Int] = []
    while list1 != nil {
        let a = list1?.val
        arr.append(a!)
        list1 = list1?.next
    }
    if arr.count <= 0 {
        return head
    }
    
    for index in 0..<arr.count {
        if index == arr.count - n {
            continue
        }
        if list == nil {
            list = ListNode(arr[index])
            list2 = list
        } else {
            list2.next = ListNode(arr[index])
            list2 = list2?.next
        }
    }
    return list
}

25. Reverse Nodes in k-Group

69F7E7A0-CC8A-413F-9A33-E1C53C3D279C.png

鏈接的反轉(zhuǎn)，思路是每隔k個就進行反轉(zhuǎn)一次，把鏈表轉(zhuǎn)成數(shù)組就很好處理了，這題目是hard類的，好像感覺挻水的，不過一開始我也錯了兩次，主要是沒有注意讀題目，沒看清楚，以為只反轉(zhuǎn)前面k個，原來每k個就進行反轉(zhuǎn)一次，這里直接上代碼了：

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
    var list: ListNode!
    var list1 = head
    var list2: ListNode!
    var arr: [Int] = []
    while list1 != nil {
        let a = list1?.val
        arr.append(a!)
        list1 = list1?.next
    }
    if k == 0 || arr.count <= 0 || k > arr.count {
        return head
    }
    
    let count = arr.count / k
    var reverseArr: [Int] = []
    for index in 1...count {
        for ind in 1...k {
            reverseArr.append(arr[k * index - ind])
        }
    }
    
    if arr.count % k != 0 {
        for index in k*count..<arr.count {
            reverseArr.append(arr[index])
        }
    }
    
    for index in 0..<reverseArr.count {
        if list == nil {
            list = ListNode(reverseArr[index])
            list2 = list
        } else {
            list2.next = ListNode(reverseArr[index])
            list2 = list2?.next
        }
    }
    return list
}

41. First Missing Positive

圖片.png

刷了些題目后，發(fā)現(xiàn)自己看英（裝）文（逼）水平又提高的節(jié)奏，這題目的大意是求數(shù)組中沒有的最小正整數(shù)，這題目是看林總簡書上算法題目分享，然后自己也去做了他分享的第一題，也就是這題目，在公車上和回家路上思考了20分鐘，回家后開電腦，提交了4次才ac，好吧，水平有待提高。

思路：這題目的難點是空間復(fù)雜度是常數(shù)級別，所以說，不能開數(shù)組?。?！不能開，不能開數(shù)組，只能用重復(fù)利用原來的數(shù)組了，因為求數(shù)組中沒有的最小正整數(shù)，所以答案的范圍就是 1~n+1（n是數(shù)組的大?。斫膺@個，整個問題應(yīng)該很好理解，就是如果存在k(1-n+1范圍內(nèi))，就把nums[k-1]標記為存在，再將nums[k-1]原來的值遞歸執(zhí)行這個操作，當遍歷整個數(shù)組時，沒有被標記的下標就是答案了，如果都被標志了，那就是n+1了。

不懂或者沒看明白，看下下面的ac代碼：

func firstMissingPositive(_ nums: [Int]) -> Int {
    var arr = nums
    if nums.count <= 0 {
        return 1
    }
    // 這里其實就是避免出現(xiàn)-1， 然后將-1當成標識
    for index in 0..<nums.count {
        if arr[index] < 0 {
           arr[index] -= 1
        }
    }
    // 遞歸思想
    for index in 0..<nums.count {
        var flag = nums[index]
        while flag > 0 && flag <= nums.count {
            let f = flag
            flag = arr[flag - 1]
            arr[f - 1] = -1
        }
    }
    for index in 0..<arr.count {
        if arr[index] != -1 {
            return index + 1
        }
    }
    return nums.count + 1
}

這里好像可以少一個for循環(huán)的，現(xiàn)在思路不太清晰，回頭想下的。

53. Maximum Subarray

圖片.png

一看，求最大值的連續(xù)序列，其實這題，暴力解決，很是容易，直接多重循環(huán)就好，但這不是我們這種優(yōu)美的程序員所做的事情，我們來尋求最優(yōu)解決，時間復(fù)雜度O(n)。

思路：當前連續(xù)的子串的值如果為負時，就不可能成為最大連續(xù)子串的前綴或者后綴

這句話有點繞，要自己慢慢體會，直接看代碼應(yīng)該就能明白，如果還是不太懂，拿起筆來，比畫下就更加容易明白了：

func maxSubArray(_ nums: [Int]) -> Int {
    var sum = 0
    var maxsum = 0
    var max = 0
    for index in 0..<nums.count {
        if index == 0 {
            max = nums[index]
        }
        if nums[index] > max {
            max = nums[index]
        }
        sum += nums[index]
        if sum > maxsum {
            maxsum = sum
        } else if sum < 0 {
            sum = 0
        }
    }
    if max <= 0 {
        return max
    }
    return maxsum
}

349. Intersection of Two Arrays

56E69F31-BF8E-47CC-91F8-48D736A37DCB.png

求集合的交集，但交集中無重復(fù)的值，如上面給出來的例子，重復(fù)的2只保留一個。

比較水的題目，代碼實現(xiàn):

func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
    var set: Set<Int> = []
    var arr: [Int] = []
    for index in 0..<nums1.count {
        
        if !set.contains(nums1[index]) {
            set.insert(nums1[index])
        }
    }
    for index in 0..<nums2.count {
        if set.contains(nums2[index]) {
            arr.append(nums2[index])
            set.remove(nums2[index])
        }
    }
    return arr;
}

做這題目的時候，一共快刷了6道了，雖然都是比較簡單的問題，但是都是通過自己思考，沒有看ac答案，比起以前總喜歡看別人的解決方案，已經(jīng)有所進步。算法題目可以讓自己的頭腦更加清晰，有空的時候還是可以多做過，結(jié)合自己的一些工作經(jīng)驗，比起以前只為刷題而刷題收獲得更多。

350. Intersection of Two Arrays II

998C4DF0-4FA1-4057-9AC0-4485875E91A3.png

這題目求的是兩個數(shù)組的交集，暴力點的解決方法是一個個枚舉，但也可以通過快排來提高效率，但要明確的一點，快排的最壞情況也是O(n*n)。

  • 方法一：快排
func quickSort(data: [Int]) -> [Int] {
    if data.count <= 1 {
        return data;
    }
    
    var left: [Int] = []
    var right: [Int] = []
    let midpoint = data[data.count - 1]
    
    for index in 0..<data.count - 1 {
        if data[index] < midpoint {
            left.append(data[index])
        } else {
            right.append(data[index])
        }
    }
    var result = quickSort(data: left)
    result.append(midpoint)
    let rightResult = quickSort(data: right)
    result.append(contentsOf: rightResult)
    return result
}

func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
    let n1 = quickSort(data: nums1)
    let n2 = quickSort(data: nums2)

    var i = 0
    var j = 0
    var arr: [Int] = []
    
    while i < n1.count {
        while j < n2.count {
            if n1[i] < n2[j] {
                break
            } else if n1[i] > n2[j] {
                j += 1
                continue
            } else {
                arr.append(n1[i])
                j += 1
                break
            }
        }
        i += 1
    }
    return arr
}

這里看下所有人的運行效率圖：

圖片.png

這里明顯有更加效率的方法，可以自己思考下，有沒有辦法將時間復(fù)雜度降到O(n)呢。

  • hashMap 方式：
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
    var dict1 = Dictionary<Int, Int>()
    var dict2 = Dictionary<Int, Int>()
    var arr: [Int] = []
    for index in 0..<nums1.count {
        if dict1[nums1[index]] == nil {
            dict1[nums1[index]] = 1;
        } else {
            dict1[nums1[index]] = dict1[nums1[index]]! + 1;
        }
    }
    for index in 0..<nums2.count {
        if dict2[nums2[index]] == nil {
            dict2[nums2[index]] = 1;
        } else {
            dict2[nums2[index]] = dict2[nums2[index]]! + 1;
        }
    }
    
    for key in dict1.keys {
        if dict2[key] != nil && dict1[key] != nil {
            let count = dict2[key]! > dict1[key]! ? dict1[key]! : dict2[key]!
            for _ in 0..<count {
                arr.append(key)
            }
        }
    }
    
    return arr
}

這里通過hashMap的方式實現(xiàn)的，上面的時間復(fù)雜度應(yīng)該是O(n)，但在leetcode上面運行的時間卻比第一種的方式慢，是不是寫入速度慢呢，這個再研究下才知道結(jié)論。

414. Third Maximum Number

圖片.png

這個問題就是求數(shù)組里面的第n大的值，上面要求時間最長是O(n)， 所以暴力排序的方法肯定是過不了的。

思路:

  1. 從數(shù)組里讀取三個不一樣的值進行排序；
  2. 然后遍歷數(shù)組中的其它值，分別和前面取出來的三個數(shù)值進行比較，去掉值最少的那個，并且所有數(shù)值不能重復(fù)；

這個問題類似于求數(shù)組中第k大值的問題，直接上傳碼：

func thirdMax(_ nums: [Int]) -> Int {
    if nums.count == 1 {
        return nums[0]
    }
    if nums.count == 2 {
        return nums[0] > nums[1] ? nums[0] : nums[1]
    }
    var dict = Dictionary<Int, Int>()
    var flag = false;
    var arr: [Int] = []
    for index in 0..<nums.count {
        if !flag {
            if dict[nums[index]] == nil {
                dict[nums[index]] = nums[index]
            }
            if dict.keys.count >= 3 {
                flag = true
                for item in dict.values {
                    arr.append(item)
                }
                
                if arr[0] < arr[1] {
                    let flag = arr[0]
                    arr[0] = arr[1]
                    arr[1] = flag
                }
                
                if arr[0] < arr[2] {
                    let flag = arr[0]
                    arr[0] = arr[2]
                    arr[2] = flag
                }
                
                if arr[1] < arr[2] {
                    let flag = arr[1]
                    arr[1] = arr[2]
                    arr[2] = flag
                }
            }
        } else {
            
            if nums[index] < arr[2] {
                continue
            }
            
            if nums[index] > arr[0] {
                arr[2] = arr[1]
                arr[1] = arr[0]
                arr[0] = nums[index];
            } else if nums[index] > arr[1] {
                arr[2] = arr[1]
                arr[1] = nums[index];
            } else if nums[index] > arr[2] {
                arr[2] = nums[index]
            }
        }
    }
    if arr.count >= 3 {
        return arr[2]
    } else {
        return arr[0]
    }
}

看下運行的時間分布圖：

圖片.png

最快的是22ms，上面的代碼是25ms，相對來說，算是比較快的速度，后面有時間再來想想怎樣才能達到最優(yōu)。

442. Find All Duplicates in an Array

圖片.png

因為數(shù)組的值只會出現(xiàn)一次或者2次，這樣直接用字典來保存的同時判斷下是否重復(fù)就可以了，時間復(fù)雜度n，代碼：

func findDuplicates(_ nums: [Int]) -> [Int] {
    var dict = Dictionary<Int, Int>()
    var arr: [Int] = []
    for index in 0..<nums.count {
        if dict[nums[index]] != nil {
            arr.append(nums[index])
        }
        dict[nums[index]] = nums[index]
    }
    return arr;
}

448. Find All Numbers Disappeared in an Array

圖片.png

水題，該注意的地方也標出來了，思維路是用hashMap來實現(xiàn)，實際時間復(fù)雜度是 2 * n，直接上代碼：

func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
    var dict = Dictionary<Int, Int>()
    for index in 0..<nums.count {
        dict[nums[index]] = nums[index]
    }
    var arr: [Int] = []
    if nums.count > 0 {
        for index in 1...nums.count {
            if dict[index] == nil {
                arr.append(index)
            }
        }
    }
    return arr;
}

468. Validate IP Address

圖片.png

字符串的判斷，把各種情況考慮上就可以了，代碼：

func validIPAddress(_ IP: String) -> String {
    if IP.contains(".") {
        let arr = IP.components(separatedBy: ".")
        if arr.count != 4 {
            return "Neither"
        }
        for item in arr {
            if (item.hasPrefix("0") && item.characters.count > 1) || item.hasPrefix("-") {
                return "Neither"
            } else {
                let a = Int(item)
                if a == nil || a! < 0 || a! > 255 {
                   return "Neither"
                }
            }
        }
        return "IPv4"
    } else if IP.contains(":") {
        let arr = IP.components(separatedBy: ":")
        if arr.count != 8 {
            return "Neither"
        }
        for item in arr {
            if item.characters.count > 4 || item.characters.count <= 0 {
                return "Neither"
            }
            for ite in item.characters {
                let value = UnicodeScalar(String(ite))?.value
                if value! < 48 || (value! > 57 && value! < 65) || (value! > 70 && value! < 97) || value! > 102 {
                    return "Neither"
                }
            }
        }
        return "IPv6"
    } else {
        return "Neither"
    }
}

485. Max Consecutive Ones

86DBE1FF-73B7-47BE-8A72-D8A2BE27C99A.png

這道是水題，求連續(xù)最長的1的長度，直接帖代碼：

func findMaxConsecutiveOnes(_ nums: [Int]) -> Int {
    var max = 0
    var sum = 0
    for index in 0..<nums.count {
        if nums[index] == 0 {
            if sum > max {
                max = sum
            }
            sum = 0
        } else {
            sum += 1
            if sum > max {
                max = sum
            }
        }
    }
    return max
}

495. Teemo Attacking

圖片.png

這題目，又想起曾經(jīng)超鬼的經(jīng)歷，哈哈，好像已經(jīng)有一年沒有玩過了，這題目就是要求TM隊長攻擊敵人的中毒時長，數(shù)組內(nèi)傳的是攻擊的時候，第二個參數(shù)是中毒的時長。

比如：[1, 2], 3，1秒的時候攻擊了敵人，中毒時間是3秒，在第2秒的時候又攻擊了敵人，因為已經(jīng)中毒了，就不會重復(fù)中毒，但中毒時間會重復(fù)計算。所以中毒時間是， 1、2、3、4、5， 一共5秒。

這樣的話，就很好理解了，可以分為兩種情況：

1. 如果前后兩個攻擊時差大于5秒時，那么中毒的時間就增加5秒；
2. 如果兩次攻擊的時間少于或等于5秒時，那就中毒的時間就會在增加兩次攻擊的時間差；

理解了邏輯，就很容易寫出代碼了：

func findPoisonedDuration(_ timeSeries: [Int], _ duration: Int) -> Int {
    var count = duration
    if timeSeries.count == 0 {
        return duration
    }
    if timeSeries.count < 2 {
        return count
    }
    for index in 0..<timeSeries.count - 1 {
        if timeSeries[index] + duration - 1 < timeSeries[index + 1] {
            count += duration
        } else {
            count = count + timeSeries[index + 1] - timeSeries[index];
        }
    }
    
    return count
}

這里需要注意的兩處就是數(shù)組為空和只有一次攻擊的時候，這兩種情況需要另外的處理，然后然后就AC了~~~

待續(xù)~~~

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗。 張土汪：刷leetcod...
    土汪閱讀 12,890評論 0贊 33
  • 新的學期又開始了，和室友們都陸陸續(xù)續(xù)的回到了寢室。大家都在你一言我一語的分享假期的事情。 最讓我感興趣的是其中一個...
    焰嗬閱讀 359評論 0贊 0
  • “?！庇矌艗伋鲆粭l美麗的弧線在空中不斷地翻轉(zhuǎn)著。字就去打針，花就不打了，望著空中還在翻轉(zhuǎn)的硬幣，我伸手一把抓...
    程佳平閱讀 668評論 0贊 7
  • 《世說新語》有一章叫排調(diào)，排調(diào)的意思就是幽默，魏晉人士的排調(diào)不是一般意義上的戲謔或調(diào)笑，而包含了學識、智慧、才情、...
    山妖妙妙閱讀 3,027評論 6贊 23
  • 我叫冉。 我們的種族和人們相擁，相眠，我們的名字也由人們贈予。 女孩西曦喜歡的是我，不管是什么。因為我們幾乎有三分...
    仙貝red閱讀 572評論 0贊 0

友情鏈接更多精彩內(nèi)容