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

資訊專欄INFORMATION COLUMN

leetcode 二分查找 - easy

objc94 / 779人閱讀

摘要：如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。也因?yàn)槭桥判虻臄?shù)組，所以可以考慮二分法。計(jì)算并返回的平方根，其中是非負(fù)整數(shù)。輸入輸出說明的平方根是由于返回類型是整數(shù)，小數(shù)部分將被舍去。是一個(gè)非負(fù)整數(shù)，并且在位有符號(hào)整型的范圍內(nèi)。

有時(shí)候會(huì)抽時(shí)間看看題目，鍛煉一下
簡單記錄下二分查找吧，會(huì)持續(xù)更新的啊哈~~~
僅供參考，路過看下就行，歡迎交流~

第35題

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。
你可以假設(shè)數(shù)組中無重復(fù)元素。例如：
輸入: [1,3,5,6], 5 輸出: 2
輸入: [1,3,5,6], 2 輸出: 1
輸入: [1,3,5,6], 7 輸出: 4
輸入: [1,3,5,6], 0 輸出: 0

想法：簡單粗暴一點(diǎn)，因?yàn)槭桥判驍?shù)組，所以直接for遍歷就可以了。

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # 如果target大于max(nums),則直接插入最后位置
        for i in range(0,len(nums)):
            if nums[i] >= target:
                return i
        return len(nums)

但是若目標(biāo)值若是最大的，則得等循環(huán)len(nums)遍才能找到，時(shí)間復(fù)雜度高。也因?yàn)槭桥判虻臄?shù)組，所以可以考慮二分法。

class Solution(object):
    def searchInsert(self, nums, target):
        left = 0
        right = len(nums)-1
        while left <= right :
            # 中間的數(shù)
            middle = (right-left) / 2 + left
            if nums[middle] == target:
                return middle
            elif nums[middle] > target : # 即target在左邊
                right = middle - 1 
            else :
                left = middle + 1
        return left

第69題：x的平方根

實(shí)現(xiàn) int sqrt(int x) 函數(shù)。
計(jì)算并返回 x 的平方根，其中 x 是非負(fù)整數(shù)。
由于返回類型是整數(shù)，結(jié)果只保留整數(shù)的部分，小數(shù)部分將被舍去。
輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842...,

 由于返回類型是整數(shù)，小數(shù)部分將被舍去。
class Solution(object):
    def mySqrt(self, x):
        l, r = 0, x
        while l <= r:
            mid = l + (r-l)//2
            if mid * mid <= x < (mid+1)*(mid+1):
                return mid
            elif x < mid * mid:
                r = mid
            else:
                l = mid + 1

第367題：有效的完全平方數(shù)

給定一個(gè)正整數(shù) num，編寫一個(gè)函數(shù)，如果 num 是一個(gè)完全平方數(shù)，則返回 True，否則返回 False。
說明：不要使用任何內(nèi)置的庫函數(shù)，如 sqrt。
輸入：16 輸出：True
輸入：14 輸出：False

class Solution:
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        left = 0
        right = num
        #tag = None
        while left <= right :
            mid = (right-left)//2  + left   # 減少循環(huán)次數(shù)
            val = mid *mid 
            if val == num :
                #tag = True
                return True
            elif val > num :
                #tag = False
                right = mid - 1 
            else:
                #tag = False
                left = mid + 1
        #return tag  
        # 注釋掉部分減少運(yùn)行時(shí)間，其次通過val來減少中間運(yùn)算
        return False

第441題：排列硬幣

你總共有 n 枚硬幣，你需要將它們擺成一個(gè)階梯形狀，第 k 行就必須正好有 k 枚硬幣。
給定一個(gè)數(shù)字 n，找出可形成完整階梯行的總行數(shù)。
n 是一個(gè)非負(fù)整數(shù)，并且在32位有符號(hào)整型的范圍內(nèi)。
n = 5
硬幣可排列成以下幾行:
¤
¤ ¤
¤ ¤
因?yàn)榈谌胁煌暾苑祷?.

n = 8
硬幣可排列成以下幾行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因?yàn)榈谒男胁煌暾?，所以返?.

class Solution(object):
    def arrangeCoins(self, n):
        if n == 0:
            return 0
        left = 1
        right = n/2
        while left <= right:
            mid = (right-left)/2+left
            total = (mid * (mid+1)) / 2
            if total > n:
                right = mid - 1
            elif n - total < mid + 1:
                return mid
            elif n-total == mid + 1:
                return mid+1
            else:
                left = left + 1
        return left

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

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

相關(guān)文章

  • 大廠算法面試之leetcode精講9.位運(yùn)算

    摘要：空間復(fù)雜度方法是否為最大的冪的約數(shù)思路最大的的冪為，判斷是否是的約數(shù)即可。復(fù)雜度時(shí)間復(fù)雜度，一個(gè)整數(shù)統(tǒng)計(jì)二進(jìn)制的復(fù)雜度，最壞的情況下是。 大廠算法面試之leetcode精講9.位運(yùn)算視頻教程（高效學(xué)習(xí)）:點(diǎn)擊學(xué)習(xí)目錄：1.開篇介紹2.時(shí)間空間復(fù)雜度3.動(dòng)態(tài)規(guī)劃4.貪心5.二分查找6.深度優(yōu)先&廣度優(yōu)先7.雙指針...

    番茄西紅柿 評(píng)論0 收藏2637

  • LeetCode 之 JavaScript 解答第69題 —— X 的平方根（Squrt(x)）

    摘要：測(cè)試用例輸入輸入輸入負(fù)數(shù)的輸入平方根為正整數(shù)的輸入平方根為小數(shù)的代碼實(shí)現(xiàn)寫二分查找代碼需要注意的三點(diǎn)循環(huán)退出條件。使用二分查找之前，判斷問題是否滿足二分查找的要求。 Time：2019/4/17Title: sqrt(x)Difficulty: EasyAuthor: 小鹿 題目：sqrt(x) Implement int sqrt(int x). Compute and retu...

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

  • 70道前端LeetCode題目集合及視頻講解（持續(xù)更新中...）

    前端LeetCode刷題 下面是已刷的題目的目錄。GitHub：https://github.com/cunzaizhuy...每日打卡更新中，歡迎關(guān)注。 數(shù)組類 26 刪除排序數(shù)組中的重復(fù)項(xiàng) 27 移除元素 35 搜索插入位置 66 加1 80 medium 刪除排序數(shù)組中的重復(fù)項(xiàng)2 88 合并兩個(gè)有序數(shù)組 167 兩數(shù)之和II - 輸入有序數(shù)組 118 楊輝三角 169 easy 求眾數(shù) 1...

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

  • 大廠算法面試之leetcode精講7.雙指針

    摘要：空間復(fù)雜度雙指針，循環(huán)數(shù)組，較小的那個(gè)先向內(nèi)移動(dòng)如果高的指針先移動(dòng)，那肯定不如當(dāng)前的面積大計(jì)算面積更新最大面積相交鏈表方法哈希表思路將鏈表存入中，第一個(gè)相同的節(jié)點(diǎn)就是重合的節(jié)點(diǎn)復(fù)雜度時(shí)間復(fù)雜度，分別是兩個(gè)鏈表的長度。 大廠算法面試之leetcode精講7.雙指針視頻教程（高效學(xué)習(xí)）:點(diǎn)擊學(xué)習(xí)目錄：1.開篇介紹2...

    不知名網(wǎng)友 評(píng)論0 收藏0

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

0條評(píng)論

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