小李飛刀：刷題第十三彈！

lixiang 發布于2019-07-31 10:20 / 1291人閱讀

摘要：寫在前面今天的小李的目標是排序算法，果然還是要下手寫才會更有體會，也更記得住。排序算法冒泡排序主要是比對相鄰兩個數之間的大小關系，不斷將較大值交換至最后。

寫在前面

今天的小李的目標是排序算法，果然還是要下手寫才會更有體會，也更記得住。

認真做題的分割線

第一題

215. 數組中的第K個最大元素
難度：中等
在未排序的數組中找到第k個最大的元素。請注意，你需要找的是數組排序后的第k個最大的元素，而不是第k個不同的元素。
示例 1:

輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5

示例 2:

輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4

說明:
你可以假設 k 總是有效的，且 1 ≤ k ≤ 數組的長度。

我的題解:

    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        num = quicksort(nums,0,len(nums)-1)
        return num[len(nums)-k]
    
def quicksort(v,start,end):
    if start < end:
        i,j = start,end
        base  = v[i]
        while i < j:
            while i < j and v[j] >= base:
                j -= 1
            v[i] = v[j]
            while i < j and v[i] < base:
                i +=1
            v[j] = v[i]
        v[i] = base
        quicksort(v,start,i-1)
        quicksort(v,j+1,end)
    return v

我的思路:
通過快速排序算法,對數據進行排序后,找到對應的值.
排序算法:
快排的主體思路是,找到對應的標桿值,然后對標桿值兩側進行劃分,然后分而治之,對兩側再進行遞歸的切分標桿值.
所以常見的是遞歸的思路.
之前看《算法圖解》的代碼，今晚嘗試了下：

def quicksort(array):
    if len(array) < 2:
        return array
    temp = array[0]
    less = [ i for i in array[1:] if i <= temp]
    greater = [i for i in array[1:] if i > temp]
    return quicksort(less) + temp + quicksort(greater)

比較能夠明顯的顯示快排的思路，但是這個效率并不高，因為每次遞歸都需要對兩側的數組進行一次硬性排序。
且return 不支持不同類型（list和int）一起。
優化后，我們采用的方式是加入了start和end的參數，依然是對標桿值兩側進行劃分，但是會減少排序重復量，降低了復雜度。

第二題

215. 數組中的第K個最大元素
難度：中等
給定一個非空的整數數組，返回其中出現頻率前k高的元素。

示例 1:

輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]

示例 2:

輸入: nums = [1], k = 1
輸出: [1]

說明：
你可以假設給定的k總是合理的，且 1 ≤ k ≤ 數組中不相同的元素的個數。
你的算法的時間復雜度必須優于O(n log n), n 是數組的大小。

我的題解:

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        l = dict()
        res = []
        for i in nums:
            if i in l:
                l[i] += 1
            else:
                l[i] = 1
        items = list(l.items())
        items.sort(key = lambda x:x[1],reverse = True)
        for i in range(k):
            res.append(items[i][0])
        return res

我的思路:
這題按正常題解，應該使用桶排序。
我用的方案是用hash表記錄對應的值，然后將hash表轉成二維list，并對二級域進行排序。
然后輸出對應值。
其他:
這題要再嘗試下桶排序的方式，主要是對sort()函數參數有了新的認識。

sorted(iterable[, cmp[, key[, reverse]]])

iterable指定要排序的list或者iterable

cmp為函數，指定排序時進行比較的函數，可以指定一個函數或者lambda函數

key為函數，指定取待排序元素的哪一項進行排序，用于指定哪一個域

第三題

215. 數組中的第K個最大元素
難度：中等
給定一組非負整數，重新排列它們的順序使之組成一個最大的整數。

示例 1:

輸入: [10,2]
輸出: 210

示例 2:

輸入: [3,30,34,5,9]
輸出: 9534330

說明: 輸出結果可能非常大，所以你需要返回一個字符串而不是整數。

我的題解:

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        l = len(nums)
        i = l
        #比較a+b 和 b+a
        while i > 0:
            for j in range(i-1):
                a = nums[j]
                b = nums[j+1]
                ab = int(str(a)+str(b))
                ba = int(str(b)+str(a))
                if ab < ba:
                    nums[j],nums[j+1] = nums[j+1],nums[j]
            i -=1
        res= ""
        for n in nums:
            if res == "" and n == 0:
                continue
            res += str(n)
        if res == "":
            return "0"
        return res

我的思路:
這題參考了小佳揚的寫法，主要是使用了冒泡排序。
但屬于自定義的冒泡排序，每次都比對字符串前后排序不同時得出的結果哪個更大，會獲得的更大值需要放在更前，相反則放后。

排序算法:
冒泡排序主要是比對相鄰兩個數之間的大小關系，不斷將較大值交換至最后。

總結

明天要繼續攻略排序算法。
紙上得來終覺淺，絕知此事要躬行。

GPU云服務器云服務器第十三天第十三篇飛刀小李

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/43661.html

小李飛刀：刷題第三彈！

摘要：刷題第三天正式刷題第三天。注意空字符串可被認為是有效字符串。錯誤的一次是因為沒有考慮空字符串，當存在為的時候，結果應該為。第二題加一難度簡單類型給定一個由整數組成的非空數組所表示的非負整數，在該數的基礎上加一。刷題第三天正式刷題第三天。之前看了個說法，挺認可的。就是不要太在意一天的能呈現的價值，但是要在意累計的價值。之前很多時候我會對今天一天沒有完成的計劃而沮喪，事實上，算法的實踐...

SillyMonkey 2019-07-31 10:02 評論0 收藏0
小李飛刀：做題第十一彈！

摘要：第五題對稱二叉樹難度簡單給定一個二叉樹，檢查它是否是鏡像對稱的。第十六題最大連續的個數難度簡單給定一個二進制數組，計算其中最大連續的個數。第十八題平方數之和難度簡單給定一個非負整數，你要判斷是否存在兩個整數和，使得。寫在前面最近忙著調教新裝備，沒有及時的寫題解，但是沒有在偷懶沒刷題喔~來認真整理下最近做的題目~ 之前考慮按tag來刷題，后來收到了推薦的leetcode題解，就根據上...

ytwman 2019-07-31 10:18 評論0 收藏0
小李飛刀：刷題第五彈！

摘要：寫在前面的話好幾天木有刷題啦，今天猛刷了一把，要梳理一個順序好好的學習啦一定要好好執行每天做題的計劃最近真的好忙碌啊，還要做視頻。第二題最大子序和難度簡單給定一個整數數組，找到一個具有最大和的連續子數組子數組最少包含一個元素，返回其最大和。寫在前面的話好幾天木有刷題啦，今天猛刷了一把，要梳理一個順序好好的學習啦~一定要好好執行每天做題的計劃！最近真的好忙碌啊，還要做視頻。不過呢，看...

Miracle 2019-07-31 10:08 評論0 收藏0
小李飛刀：做題第十二彈！

摘要：寫在前面今天沒有叨逼叨但是又一次錯過了競賽愛睡覺的小李下周要上班，下下周一定要參加了握拳認真做題的分割線第一題兩地調度公司計劃面試人。第人飛往市的費用為，飛往市的費用為。示例輸入輸出解釋第一個人去市，費用為。寫在前面今天沒有叨逼叨...但是又一次錯過了競賽...愛睡覺的小李...下周要上班，下下周一定要參加了（握拳認真做題的分割線第一題 1029. 兩地調度公司計劃面試2N人。...

yagami 2019-07-31 10:19 評論0 收藏0
小李飛刀：做題第十彈！

摘要：第二題漢明距離難度簡單兩個整數之間的漢明距離指的是這兩個數字對應二進制位不同的位置的數目。給出兩個整數和，計算它們之間的漢明距離。第三題買賣股票的最佳時機難度簡單給定一個數組，它的第個元素是一支給定股票第天的價格。寫在前面這幾天斷斷續續做了題目，也在慢慢體會一些數據思維。終于不用邊做視頻邊寫題目啦~開心~把這幾天的題解發一下~ 認真做題的分割線第一題 977. 有序數組的平方難度...

bingo 2019-07-31 10:13 評論0 收藏0