「704. 二分查找 」| leetcode 刷題009

題目1

統(tǒng)計字符串中的單詞個數(shù),這里的單詞指的是連續(xù)的不是空格的字符莫换。

請注意霞玄,你可以假定字符串里不包括任何不可打印的字符骤铃。

示例:

輸入: "Hello, my name is John"
輸出: 5

解答

class Solution(object):
    def countSegments(self, s):
        """
        :type s: str
        :rtype: int
        """
        return len(s.split())

split()函數(shù)可以分割任何符號坷剧,包括逗號,句號惫企,什么亂七八糟的符號。相比較來說狞尔,其他語言可沒有這么簡潔的用法。

題目2

給定一個 n 個元素有序的(升序)整型數(shù)組 nums 和一個目標值 target 沪么,寫一個函數(shù)搜索 nums 中的 target,如果目標值存在返回下標禽车,否則返回 -1。

示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標為 4
示例 2:

輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1

提示:

  • 你可以假設(shè) nums 中的所有元素是不重復(fù)的州胳。
  • n 將在 [1, 10000]之間。
  • nums 的每個元素都將在 [-9999, 9999]之間栓撞。

解答

剛開始我沒有看見題目碗硬,自己一看這么簡單瓤湘,順手就寫了

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if target in nums:
            return nums.index(target)
        else:
            return -1

寫完之后我覺得不對恩尾,再看看題目,說的是二分查找翰意。所謂二分查找就是把列表一分為二,在左右兩邊查找醒第,確定元素區(qū)間之后再次一分為二,直至確定元素稠曼。

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left, right = 0, len(nums)-1
        while (left <= right):
            mid = (left+right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid -1 
            else:
                left = mid + 1
        return -1

這才是這道題要考察的二分查找堤如。
查看執(zhí)行結(jié)果36ms蒲列。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市搀罢,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌榔至,老刑警劉巖,帶你破解...
    沈念sama閱讀 218,546評論 6 507
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件铅鲤,死亡現(xiàn)場離奇詭異枫弟,居然都是意外死亡邢享,警方通過查閱死者的電腦和手機淡诗,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,224評論 3 395
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來款违,“玉大人群凶,你說我怎么就攤上這事插爹∏肷遥” “怎么了?”我有些...
    開封第一講書人閱讀 164,911評論 0 354
  • 文/不壞的土叔 我叫張陵萍虽,是天一觀的道長形真。 經(jīng)常有香客問我杉编,道長咆霜,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,737評論 1 294
  • 正文 為了忘掉前任光酣,我火速辦了婚禮脉课,結(jié)果婚禮上救军,老公的妹妹穿的比我還像新娘。我一直安慰自己唱遭,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 67,753評論 6 392
  • 文/花漫 我一把揭開白布疫鹊。 她就那樣靜靜地躺著司致,像睡著了一般。 火紅的嫁衣襯著肌膚如雪脂矫。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,598評論 1 305
  • 那天奕枢,我揣著相機與錄音,去河邊找鬼缝彬。 笑死,一個胖子當(dāng)著我的面吹牛谷浅,可吹牛的內(nèi)容都是我干的奶卓。 我是一名探鬼主播一疯,決...
    沈念sama閱讀 40,338評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼墩邀,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了眉睹?” 一聲冷哼從身側(cè)響起废膘,我...
    開封第一講書人閱讀 39,249評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎丐黄,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,696評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡坏瞄,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,888評論 3 336
  • 正文 我和宋清朗相戀三年甩卓,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片猛频。...
    茶點故事閱讀 40,013評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡蛛勉,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出毡熏,到底是詐尸還是另有隱情,我是刑警寧澤痢法,帶...
    沈念sama閱讀 35,731評論 5 346
  • 正文 年R本政府宣布杜顺,位于F島的核電站,受9級特大地震影響躬络,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜穷当,卻給世界環(huán)境...
    茶點故事閱讀 41,348評論 3 330
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望馁菜。 院中可真熱鬧,春花似錦汪疮、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,929評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽坯苹。三九已至摇天,卻和暖如春恐仑,著一層夾襖步出監(jiān)牢的瞬間为鳄,已是汗流浹背裳仆。 一陣腳步聲響...
    開封第一講書人閱讀 33,048評論 1 270
  • 我被黑心中介騙來泰國打工孤钦, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人偏形。 一個月前我還...
    沈念sama閱讀 48,203評論 3 370
  • 正文 我出身青樓,卻偏偏與公主長得像队橙,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子捐康,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,960評論 2 355

推薦閱讀更多精彩內(nèi)容

  • 動態(tài)規(guī)劃 111. 爬樓梯思路類似斐波那契數(shù)列注意考慮第 0 階的特殊情況 272. 爬樓梯 II思路類似上題庸蔼,只...
    6默默Welsh閱讀 2,431評論 0 1
  • 1 二分查找jdk源碼 時間O(logn)空間O(1) 遞歸式寫法: 時間和空間都是O(logn) 2. 二分插入...
    少冰三hun甜閱讀 375評論 0 1
  • 一姐仅、快捷鍵 ctr+b 執(zhí)行ctr+/ 單行注釋ctr+c ...
    o_8319閱讀 5,821評論 2 16
  • 相愛的人,一定是這樣子的壤追。 吵架,往往是各種小事大事思想碰撞的火花行冰,只不過分大小而已。 小靜和他那個曖昧的男人就是...
    景家大小姐99閱讀 1,002評論 0 0
  • 生命里悼做,一些繾綣,無論素凈肛走,還是喧嘩,都已經(jīng)被歲月賦予了清喜的味道,一些閑詞组题,或清新,或淡雅崔列,總會在某一個回眸的時...
    邱紫璇閱讀 279評論 0 0