7.17 - medium总结16

上周状态太差了,重新振作一下!结果这一part的题目都好难。。。好在虽然不会做,但是心态还不错,没有烦躁。
307. Range Sum Query - Mutable: 做出来一个lowlow的解法,不过也AC了,看了一下tag,原来是segment tree。借这题把segment tree复习一遍。其实这道题完美的利用了segment tree的所有性质,create,update,query。其实segment tree就是在普通tree的基础上记录了更多的信息以便于查询。这里记录的是sum,也可以记录average。

class NumArray(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.root = self.buildTree(nums, 0, len(nums)-1)

    def buildTree(self, nums, start, end):
        if start > end:
            return None
        root = SegmentTreeNode(start, end)
        if start == end:
            root.sum = nums[start] # only one node
        else:
            mid = start  + (end - start) / 2             
            root.left = self.buildTree(nums, start, mid)
            root.right = self.buildTree(nums, mid + 1, end)
            root.sum = root.left.sum + root.right.sum
        return root     

    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: void
        """
        self.updateValue(self.root, i, val)
    
    def updateValue(self, root, pos, val):
        if root.start == root.end:
            root.sum = val
        else:
            mid = root.start + (root.end - root.start) / 2;
            if pos <= mid:
                self.updateValue(root.left, pos, val);
            else:
                self.updateValue(root.right, pos, val);
            root.sum = root.left.sum + root.right.sum;
    

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.sumRangeValue(self.root, i, j)
    
    def sumRangeValue(self, root, start, end):
        if root.end == end and root.start == start: # find the current range
            return root.sum
        else:
            mid = root.start + (root.end - root.start) / 2
            if end <= mid:
                return self.sumRangeValue(root.left, start, end)
            elif start >= mid+1:
                return self.sumRangeValue(root.right, start, end)
            else:   
                return self.sumRangeValue(root.right, mid+1, end) + self.sumRangeValue(root.left, start, mid)

            
class SegmentTreeNode(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.left = None
        self.right = None
        self.sum = 0

# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)

309. Best Time to Buy and Sell Stock with Cooldown:这题又是没想出来,虽然之前做过但是还是没什么思路,题目还是要尽力去思考,至少二十分钟没思路再去看答案,不过看过得答案也很快就忘记了。

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # 这类型的题目是DP问题,DP问题首先就要找到DP问题的state,按照最简易的方法
        # 可以找到三个state
        # buy[i] means before day i what is the maxProfit for any sequence end with buy
        # sell[i] means before day i what is the maxProfit for any sequence end with sell.
        # rest[i] means before day i what is the maxProfit for any sequence end with rest.
        # 他们之间的逻辑关系是,在买之前必须要rest,在卖之前必须要买。
        # buy[i]  = max(rest[i-1]-price, buy[i-1]) 
        # sell[i] = max(buy[i-1]+price, sell[i-1])
        # rest当天不产生交易,所以由前面的值所决定
        # rest[i] = max(sell[i-1], buy[i-1], rest[i-1])
        # 同时rest肯定是跟在sell后面的
        # rest[i] = sell[i-1]
        # 替代入前面的公式,可以推导出buy和sell的关系
        # buy[i] = max(sell[i-2]-price, buy[i-1])
        # sell[i] = max(buy[i-1]+price, sell[i-1])
        # Since states of day i relies only on i-1 and i-2 we can reduce the O(n) space to O(1). 
        if len(prices) < 2:
            return 0
        sell, buy, prev_sell, prev_buy = 0, -prices[0], 0, 0
        for price in prices:
            prev_buy = buy
            buy = max(prev_sell - price, prev_buy)
            prev_sell = sell
            sell = max(prev_buy + price, prev_sell)
        return sell

310. Minimum Height Trees: 这题做出了个TLE的版本,就是把每一个节点到其最远的节点的长度找一遍,然后选出最短的那些,看了答案后,有剪枝的方法,很奇妙。

class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        if n == 1: 
            return [0] 
        adj = [set() for _ in xrange(n)]
        for i, j in edges:
            adj[i].add(j)
            adj[j].add(i)
        # 这里有点像topology sort,先找出入度为1的
        leaves = [i for i in xrange(n) if len(adj[i]) == 1]

        while n > 2: #如果剩余的点超过两个
            n -= len(leaves) 
            newLeaves = []
            for i in leaves:
                j = adj[i].pop() # 因为len为1,所以pop出来的只能是一个值
                adj[j].remove(i) # 然后从这个值的边中删掉进来的node
                if len(adj[j]) == 1: # 更新入度为1的值
                    newLeaves.append(j)
            leaves = newLeaves
        return leaves 
    # 这样的值只可能是两个,本质就是找出图中端到端的最长路径,这个最长路径的中间一个点或者两个点就是,找的方法就是从外向内进行bfs剪枝    

311. Sparse Matrix Multiplication: 终于写出来了一题。。。都是泪。。。
313. Super Ugly Number: 又手写出来一题yeah!
314. Binary Tree Vertical Order Traversal:level traversal,只是要记录每一个值的degree,root的degree为0,left就减一,right就加一,然后记录到一个hashtable里就可以了
318. Maximum Product of Word Lengths:比较两个字符串是否有重复的字母,就把字符串映射到数字上,26位的bit,用1代表有,0代表无。
319. Bulb Switcher:一道数学证明题,不过要找出其中的规律,把事情说明白也是一个挺绕的过程
320. Generalized Abbreviation: 实在是不会做,连答案都没看懂,明明就是一道backtracking的题目,不过感觉好难

class Solution(object):
    def generateAbbreviations(self, word):
        """
        :type word: str
        :rtype: List[str]
        """
        res = []
        self.dfs(res, word, 0, "", 0)
        return res
    
    def dfs(self, res, word, pos, cur, count):
        if pos == len(word):
            if count > 0:
                cur += str(count)
            res.append(cur);
        else:
            # 缩减当前的字母(也就是说跳过当前的字母),增加pos和count的值
            self.dfs(res, word, pos + 1, cur, count + 1) # abbreviate the current character, cur 不变化只增加pos和count
            # 如果count大于0那么重新组合cur,保留当前的字母
            if count > 0:
                cur = cur + str(count) + word[pos]
            else:
                cur = cur + word[pos]
            # 增加pos,重置count为0
            self.dfs(res, word, pos + 1, cur, 0) # keep the current character, cur变化但是加上了当前的char,和之前留下的count

322. Coin Change: 这道题还算是简单

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,723评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,485评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,998评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,323评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,355评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,079评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,389评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,019评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,519评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,971评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,100评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,738评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,293评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,289评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,517评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,547评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,834评论 2 345

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,724评论 0 33
  • LeetCode 刷题随手记 - 第一部分 前 256 题(非会员),仅算法题,的吐槽 https://leetc...
    蕾娜漢默阅读 17,692评论 2 36
  • 目录 简书的 markdown 都不支持 [TOC] 语法……我就不贴目录了。下面按照类别,列出了29道关于二叉树...
    被称为L的男人阅读 3,290评论 0 8
  • Onsite talk 1.了解自己的项目细节 Question: 1.思考BST level order tra...
    Uchiha朵朵阅读 329评论 0 0
  • 总结类型: 完全子树(#222) BST(左右子树值的性质,注意不仅要满足parent-child relatio...
    __小赤佬__阅读 678评论 0 0