2020-2-22 刷题记录

0X00 leetcode 刷题 5 道

• leetcode 84. Largest Rectangle in Histogram
• leetcode 91. Decode Ways
• leetcode 674. Longest Continuous Increasing Subsequence
• leetcode 361. Bomb Enemy
• leetcode 85. Maximal Rectangle(超时)

0X01 每道题的小小记录

84. Largest Rectangle in Histogram

这道题还是很有难度和技巧性的

在做这道题的时候,首先我们要搞清楚,要计算那一部分的面积,进行比较后取最大

要计算的面积有:

• 最高的
• 小于最高的,但是能够和其他矩阵连成一片的

我们用「严格单调递增栈」来模仿这一行为

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxArea = 0
        stack = [-1]
        # 退栈时往前计算面积
        for i, h in enumerate(heights):
            while stack[-1] != -1 and heights[stack[-1]] >= h:
                topIdx = stack.pop()
                maxArea = max(maxArea, heights[topIdx] * (i - stack[-1] - 1)) 
            stack.append(i)
        
        # 计算比较小的连成一片的面积
        while stack[-1] != -1:
            idx = stack.pop()
            maxArea = max(maxArea, (len(heights) - stack[-1] - 1)* heights[idx])
        
        return maxArea

91. Decode Ways

思路在这里(来自 pris_bupt ):

条件判断还是挺多的

class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == "0": return 0
        first, second = 1, 1

        for i in range(len(s)):
            if i == 0: continue
            if s[i] == '0':
                cur = 0
                if 1 <= int(s[i-1]) <= 2: cur = first
                else: return 0
            elif s[i-1] == "1" or (s[i-1] == "2" and int(s[i]) <= 6):
                cur = first + second
            else:
                cur = second

            first, second = second, cur

        return second

674. Longest Continuous Increasing Subsequence

简单的动态规划

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        preValue, preSum = nums[0], 1
        ans = 1

        for i in range(len(nums)):
            if i == 0: continue
            cur = 1
            if nums[i] > preValue:
                cur += preSum
            ans = max(ans, cur)
            preValue, preSum = nums[i], cur
        
        return ans

361. Bomb Enemy

四个方向的动态规划

class Solution(object):
    def maxKilledEnemies(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        # base case 
        if not grid: return 0
        row, col = len(grid), len(grid[0])
        ans = 0
        arr = [[0]*col for i in range(row)]
        # from left to right
        for i in range(row):
            count = 0
            for j in range(col):
                if grid[i][j] == 'E':
                    count += 1
                elif grid[i][j] == 'W':
                    count = 0
                else:
                    arr[i][j] += count
                    
        # from right to left
        for i in range(row):
            count = 0
            for j in range(col-1, -1, -1):
                if grid[i][j] == 'E':
                    count += 1
                elif grid[i][j] == 'W':
                    count = 0
                else:
                    arr[i][j] += count
        # from up to down
        for j in range(col):
            count = 0
            for i in range(row):
                if grid[i][j] == 'E':
                    count += 1
                elif grid[i][j] == 'W':
                    count = 0
                else:
                    arr[i][j] += count
                    
        # from down to up
        for j in range(col):
            count = 0
            for i in range(row-1, -1, -1):
                if grid[i][j] == 'E':
                    count += 1
                elif grid[i][j] == 'W':
                    count = 0
                else:
                    arr[i][j] += count
                    ans = max(ans, arr[i][j])
                    
        return ans

85. Maximal Rectangle(超时)

很可惜的一道题,用了动态规划还是超时了,以后再做吧

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if len(matrix) == 0: return 0
        m, n = len(matrix), len(matrix[0])
        sums = [[int(val) for val in line] for line in matrix]
        pos = []

        for x in range(m):
            for y in range(n):
                if matrix[x][y] == "1": pos.append((x, y))
                t = 0
                if x == 0 and y == 0: continue
                elif x == 0: t = sums[x][y-1]
                elif y == 0: t = sums[x-1][y]
                else: t = sums[x][y-1] + sums[x-1][y] - sums[x-1][y-1]
                sums[x][y] += t 

        def helper(x1, y1, x2, y2):
            size = 0
            if x1 == 0 and y1 == 0: size = sums[x2][y2]
            elif x1 == 0: size = sums[x2][y2]  - sums[x2][y1-1]
            elif y1 == 0: size = sums[x2][y2] -  sums[x1-1][y2]
            else:size = sums[x2][y2] - sums[x2][y1-1] - sums[x1-1][y2] + sums[x1-1][y1-1]
            if  (x2 - x1 + 1) * (y2- y1 + 1) == size:
                return size
            return -1

        maxArea = 0
        lenPos = len(pos)
        i = j = 0
        while i < lenPos:
            j = i
            x, y = pos[i]
            i += 1
            while j < lenPos:
                x1, y1 = pos[j]
                j += 1
                if (x1 - x + 1) * (y1- y + 1) < maxArea:
                    continue 
                size = helper(x, y, x1, y1)
                if size != -1:
                    maxArea = max(maxArea, size)
               
        return maxArea