7.18 - medium總結(jié)17

323. Number of Connected Components in an Undirected Graph: 這題算是比較典型的圖的問題圈盔,有三種解法最筒,bfs笤喳,dfs弯予,union-find:

class Solution(object):
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        m = range(n)
        res = set()
        # union-find的含義就是找到某個節(jié)點的最終的root
        # 在這里肛跌,因為用index作為map的key
        # 對于每一條邊,每加入一個邊钢猛,就檢查兩個點,e[0]為root轩缤,e[1]為child
        # 看看這兩個點的最終father是誰命迈,然后再把這兩個最終father聯(lián)系起來
        for e in edges:
            self.union(m, e[0], e[1])
        # 用一個set記錄所有的最終father的數(shù)量
        for i in m:
            res.add(self.find(m, i))
        return len(res)

    def find(self, m, node):
        if node == m[node]:
            return node
        return self.find(m, m[node])
    
    def union(self, m, node1, node2):
        father1 = self.find(m, node1)
        father2 = self.find(m, node2)
        if father1 != father2:
            m[father2] = father1

class Solution(object):
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """     
        visited = [0] * n
        g = {x:[] for x in xrange(n)} # g[n] 表示n 和哪些值相連接, 其實就是用list和map構(gòu)造一個圖的表示形式。
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
            
        ret = 0
        for i in xrange(n): # 對于每一個節(jié)點火的,如果沒有被訪問過壶愤,就對其進行dfs
            if visited[i] == 0:
                self.dfs(i, g, visited) # 每遍歷一次連接,就在ret上加一
                ret += 1
                
        return ret
    
    def dfs(self, n, g, visited):
        if visited[n]:
            return
        visited[n] = 1
        for x in g[n]:
            self.dfs(x, g, visited)
class Solution(object):
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        # bfs也類似馏鹤,也要創(chuàng)造出圖的表示方式
        g = {x:[] for x in xrange(n)}
        visited = [0 for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
            
        ret = 0
        for i in xrange(n):
            if visited[i] == 0:
                # 如果沒有被visited過征椒,則創(chuàng)建一個新的queue
                queue = [i]
                ret += 1
                while queue:
                    j = queue.pop(0)
                    visited[j] = 1
                    for k in g[j]:
                        if visited[k] == 0:
                            queue += [k]

        return ret

324. Wiggle Sort II: sort一下再排序就好了,但是如果要O(N)的復(fù)雜度湃累,O(1)的space的話勃救,需要用到quick select, 但是接下來怎么做實在是太復(fù)雜了碍讨,感覺意義不是很大
325. Maximum Size Subarray Sum Equals k: 利用前綴和,雖然自己的解法AC了蒙秒,但是有比較好的解法勃黍,在loop過程中直接計算前綴和,然后利用hash來記錄
328. Odd Even Linked List: 用一個even和一個odd來分別記錄晕讲,然后拼起來就行了
331. Verify Preorder Serialization of a Binary Tree:沒做出來覆获,感覺體力被那道wiggle sort耗盡了,這題的思路其實也不難瓢省,就是碰到兩個#就把它們從stack pop出來弄息,再pop出來它們的parent并且push一個#進去。循環(huán)這么做就可以了勤婚。體力耗盡就是心浮氣躁疑枯。先休息一下再做。

class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        stack = []
        top = -1
        preorder = preorder.split(',')
        for s in preorder:
            stack.append(s)
            top += 1
            while(self.endsWithTwoHashes(stack,top)):
                h = stack.pop()
                top -= 1
                h = stack.pop()
                top -= 1
                if top < 0:
                    return False
                h = stack.pop()
                stack.append('#')
        if len(stack) == 1:
            if stack[0] == '#':
                return True
        return False

    def endsWithTwoHashes(self,stack,top):
        if top<1:
            return False
        if stack[top]=='#' and stack[top-1]=='#':
            return True
        return False

332. Reconstruct Itinerary: 休息了一下蛔六,沉下心來荆永,用backtracking作出一個TLE版本,還可以接受国章。不過DFS的正確打開方式如解法2具钥,詳細解釋:https://discuss.leetcode.com/topic/36370/short-ruby-python-java-c, 我覺得我能做出TLE的已經(jīng)滿足了液兽,解法2只能背下來骂删,真正面試時候?qū)儆谥谰椭溃恢谰屠沟慕夥ㄋ膯D怠!?/p>

class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        m = {}
        for i in range(len(tickets)):
            m[tickets[i][0]] = m.get(tickets[i][0], [])+ [i] # 從這個t[0] 出發(fā)柑晒,用了第幾張票
        
        used = [False for _ in range(len(tickets))]
        self.res = []
        self.dfs(m, ["JFK"], used, tickets)
        return self.res
        
    
    def dfs(self, m, cur, used, tickets):
        if len(cur) == len(tickets)+1:
            if not self.res or self.res > cur:
                self.res = cur[:]
            return
        for c in m.get(cur[-1], []):
            if used[c]:
                continue
            used[c] = True
            cur.append(tickets[c][1])
            self.dfs(m, cur, used, tickets)
            cur.pop()
            used[c] = False
class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        # build graph
        graph = {}
        for t in tickets:
            graph[t[0]] = graph.get(t[0], []) + [t[1]]
        
        for k, v in graph.iteritems():
            graph[k] = sorted(v)
        
        departure = "JFK"
        path = []
        self.dfs(graph, departure, path)
        
        return path
    
    def dfs(self, graph, departure, path):
        arrivals = graph.get(departure)
        while arrivals:
            self.dfs(graph, arrivals.pop(0), path)
        path.insert(0, departure)
                

333. Largest BST Subtree: 還算是簡單的divide and conquer
334. Increasing Triplet Subsequence:可以記錄前兩個最小值欧瘪,或者記錄一下兩位上升序列中的后一個值。
337. House Robber III:divide and conquer匙赞,返回值分成with root和without root兩種情況就可以了
338. Counting Bits:一道dp題佛掖,推導(dǎo)公式如下: if i < 2**(k+1): dp[i] = dp[i-2**k] + 1 elif i == 2**(k+1): k += 1, dp[i] = 1

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市涌庭,隨后出現(xiàn)的幾起案子芥被,更是在濱河造成了極大的恐慌,老刑警劉巖坐榆,帶你破解...
    沈念sama閱讀 222,865評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件拴魄,死亡現(xiàn)場離奇詭異,居然都是意外死亡,警方通過查閱死者的電腦和手機匹中,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,296評論 3 399
  • 文/潘曉璐 我一進店門夏漱,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人职员,你說我怎么就攤上這事麻蹋。” “怎么了焊切?”我有些...
    開封第一講書人閱讀 169,631評論 0 364
  • 文/不壞的土叔 我叫張陵扮授,是天一觀的道長。 經(jīng)常有香客問我专肪,道長刹勃,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,199評論 1 300
  • 正文 為了忘掉前任嚎尤,我火速辦了婚禮荔仁,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘芽死。我一直安慰自己乏梁,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 69,196評論 6 398
  • 文/花漫 我一把揭開白布关贵。 她就那樣靜靜地躺著遇骑,像睡著了一般。 火紅的嫁衣襯著肌膚如雪揖曾。 梳的紋絲不亂的頭發(fā)上落萎,一...
    開封第一講書人閱讀 52,793評論 1 314
  • 那天,我揣著相機與錄音炭剪,去河邊找鬼练链。 笑死,一個胖子當(dāng)著我的面吹牛奴拦,可吹牛的內(nèi)容都是我干的媒鼓。 我是一名探鬼主播,決...
    沈念sama閱讀 41,221評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼粱坤,長吁一口氣:“原來是場噩夢啊……” “哼隶糕!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起站玄,我...
    開封第一講書人閱讀 40,174評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎濒旦,沒想到半個月后株旷,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,699評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,770評論 3 343
  • 正文 我和宋清朗相戀三年晾剖,在試婚紗的時候發(fā)現(xiàn)自己被綠了锉矢。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,918評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡齿尽,死狀恐怖沽损,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情循头,我是刑警寧澤绵估,帶...
    沈念sama閱讀 36,573評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站卡骂,受9級特大地震影響国裳,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜全跨,卻給世界環(huán)境...
    茶點故事閱讀 42,255評論 3 336
  • 文/蒙蒙 一缝左、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧浓若,春花似錦渺杉、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,749評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至诵原,卻和暖如春英妓,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背绍赛。 一陣腳步聲響...
    開封第一講書人閱讀 33,862評論 1 274
  • 我被黑心中介騙來泰國打工蔓纠, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人吗蚌。 一個月前我還...
    沈念sama閱讀 49,364評論 3 379
  • 正文 我出身青樓腿倚,卻偏偏與公主長得像,于是被迫代替她去往敵國和親蚯妇。 傳聞我的和親對象是個殘疾皇子敷燎,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,926評論 2 361

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

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗。 張土汪:刷leetcod...
    土汪閱讀 12,749評論 0 33
  • 導(dǎo)語: 如果你已經(jīng)加入了iOS攻城獅隊伍箩言,那么我們由衷地祝賀您正式成為一名終身學(xué)習(xí)的程序猿硬贯;有人覺得這句話...
    超人猿閱讀 2,302評論 3 19
  • //作者:JRZAlan //備注:第一次做簡書,希望能對大家起到幫助。 這是對一些計算機編程語言的一些英語單詞,...
    JRZAlan閱讀 16,927評論 0 77
  • LeetCode 刷題隨手記 - 第一部分 前 256 題(非會員)陨收,僅算法題饭豹,的吐槽 https://leetc...
    蕾娜漢默閱讀 17,819評論 2 36
  • 你如何在看似悠悠如水的歲月里鸵赖,可以陪伴自己好好走一段,然后也去看待人世間的不圓滿拄衰,但卻用自己的眼光它褪,自己的身體力行...
    w00ds閱讀 225評論 0 0