807. 保持城市天際線

時間：2019年05月28日16:39:59
難度：中等
編號：11
進度：2/5 21/52
語言：python3
類型：模擬，矩陣

思路：naive解法

class Solution(object):
    def maxIncreaseKeepingSkyline(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        vertical = []
        for each in grid:
            vertical.append(max(each))
        horizontal = []
        for i in range(len(grid[0])):
            line = 0
            for j in range(len(grid)):
                if grid[j][i]>line:
                    line = grid[j][i]
            horizontal.append(line)
            
        num = 0
        for i in range(len(grid[0])):
            for j in range(len(grid)):
                num = num + min(vertical[i],horizontal[j])-grid[j][i]
        
        return num
                
            
        

執(zhí)行用時 : 100 ms, 在Max Increase to Keep City Skyline的Python提交中擊敗了32.81% 的用戶
內存消耗 : 11.6 MB, 在Max Increase to Keep City Skyline的Python提交中擊敗了39.47% 的用戶

1051. 高度檢查器

時間：2019年05月29日10:45:12
難度：簡單
編號：12
進度：3/5 21/52
語言：python3
類型：數(shù)組, 簡單的漢明距離問題

思路：創(chuàng)建一個新的數(shù)組，排序后，比較原數(shù)組和排序后數(shù)組有多少個數(shù)字發(fā)生了變動

class Solution(object):
    def heightChecker(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        people = [each for each in heights]
        people.sort()
        num = 0
        for i in range(len(people)):
            if people[i] != heights[i]:
                num+=1
        return num

執(zhí)行用時 : 56 ms, 在Height Checker的Python提交中擊敗了9.09% 的用戶
內存消耗 : 11.5 MB, 在Height Checker的Python提交中擊敗了100.00% 的用戶

比較trick的寫法：

class Solution:
    def heightChecker(self, heights):
        ans = 0
        for i, j in zip(heights, sorted(heights)):
            if i != j:
                ans += 1
        return ans

執(zhí)行用時 : 28 ms, 在Height Checker的Python提交中擊敗了95.45% 的用戶
內存消耗 : 11.8 MB, 在Height Checker的Python提交中擊敗了100.00% 的用戶

1052. 愛生氣的書店老板

時間：2019年05月29日17:21:39
難度：中等
編號：13
進度：4/5 21/52
語言：python3
類型：滑動窗口

思路：樸素解法，用數(shù)組存，可是會超時，也浪費空間

class Solution(object):
    def maxSatisfied(self, customers, grumpy, X):
        """
        :type customers: List[int]
        :type grumpy: List[int]
        :type X: int
        :rtype: int
        """
        ans = []
        for i in range(len(customers)-X+1):
            num = 0
            for k in range(i):
                if grumpy[k] == 0:
                    num+=customers[k]
                    
            num += sum(customers[i:i+X])
            
            for k in range(i+X,len(customers)):
                if grumpy[k] == 0:
                    num+=customers[k]
            ans.append(num)
        return max(ans)
            
        

超出時間限制

思路：滑動窗口

設置一個X的窗口，先存下前X全部滿意的值，然后算上X后面所有書店老板不生氣的值。
當窗口移動時，如果下一個值老板生氣，則加上人數(shù)，否則不操作；如果窗口挪開的時候書店老板生氣，則減掉人數(shù)。
最后留下最大值。

class Solution(object):
    def maxSatisfied(self,customers, grumpy, X):
        ans = []
        nums = 0
        for i in range(len(customers)):
            if i < X or grumpy[i] == 0:
                nums += customers[i]
        i = X
        ans = nums
        while i < len (customers):
            if grumpy[i] == 1:
                nums+=customers[i]
            if grumpy[i-X] == 1:
                nums-=customers[i-X]
            i+=1
            ans = max(nums,ans)

        return ans
            
        

執(zhí)行用時 : 504 ms, 在Grumpy Bookstore Owner的Python提交中擊敗了53.33% 的用戶
內存消耗 : 13.5 MB, 在Grumpy Bookstore Owner的Python提交中擊敗了100.00% 的用戶

1046. 最后一塊石頭的重量

時間：2019年05月30日10:57:21
難度：簡單
編號：14
進度：5/5 21/52
語言：python3
類型：湊數(shù)題

思路 ：超級樸素的，排個序，然后依次減掉就是了。沒有什么技巧。

class Solution(object):
    def lastStoneWeight(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        stones.sort(reverse = True)
        while len(stones)>=2:
            first = stones[0]
            second = stones[1]
            if len(stones)==2:
                return stones[0] -stones[1] 
            else:
                stones = stones[2:]
            if first-second >0:
                stones.append(first-second)
            stones.sort(reverse = True)
        if len(stones)==2:
            return stones[0] -stones[1]
        return stones[0]
            
            

執(zhí)行用時 : 20 ms, 在Last Stone Weight的Python提交中擊敗了96.08% 的用戶
內存消耗 : 11.7 MB, 在Last Stone Weight的Python提交中擊敗了100.00% 的用戶

高階思路：題目中每次都要選出最大的兩塊石頭粉碎，自然而然想到先建立一個大根堆 然后每次在這個大根堆里取出頭兩個元素出來進行粉碎，如果兩塊石頭不相等就將粉碎后的新石頭重新放進大根堆 這樣循環(huán)下去直到大根堆里的元素少于兩塊石頭就結束 此時已經沒法再粉碎了
實際寫代碼可以發(fā)現(xiàn)，速度沒有直接排序的快。但是這是一種思路的鍛煉：

class Solution(object):
    def lastStoneWeight(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        import heapq
        heap = []
        for each in stones:
            heapq.heappush(heap,each*-1)
        
        nums = len(stones)
        while nums>1:
            first = heapq.heappop(heap)
            second = heapq.heappop(heap)
            if first!= second:
                heapq.heappush(heap,first-second)
                nums-=1
            else:
                nums-=2
        if len(heap) == 1:
            return heap.pop()*(-1)
        return 0

執(zhí)行用時 : 32 ms, 在Last Stone Weight的Python提交中擊敗了29.41% 的用戶
內存消耗 : 11.8 MB, 在Last Stone Weight的Python提交中擊敗了100.00% 的用戶

1047. 刪除字符串中的所有相鄰重復項

時間：2019年05月30日12:40:40
難度：簡單
編號：15
進度：6/5 21/52
語言：python3
類型：棧

思路：利用棧的特點；從后往前，如果棧頂元素和即將壓棧的元素比較，如果相同，則pop，否者入棧。

class Solution(object):
    def removeDuplicates(self, S):
        """
        :type S: str
        :rtype: str
        """
        data =[]
        for i in range(len(S)-1,-1,-1):
            if len(data)==0:
                data.append(S[i])
            else:
                if data[-1] == S[i]:
                    data.pop()
                else:
                    data.append(S[i])
        return "".join(data[::-1])

執(zhí)行用時 : 100 ms, 在Remove All Adjacent Duplicates In String的Python提交中擊敗了65.22% 的用戶
內存消耗 : 12.8 MB, 在Remove All Adjacent Duplicates In String的Python提交中擊敗了100.00% 的用戶