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
执行用时 : 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
类型：数组, 简单的汉明距离问题
思路：创建一个新的数组，排序后，比较原数组和排序后数组有多少个数字发生了变动
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
执行用时 : 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
执行用时 : 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
类型：滑动窗口
思路：朴素解法，用数组存，可是会超时，也浪费空间
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后面所有书店老板不生气的值。
当窗口移动时，如果下一个值老板生气，则加上人数，否则不操作；如果窗口挪开的时候书店老板生气，则减掉人数。
最后留下最大值。
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
执行用时 : 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
类型：凑数题
思路 ：超级朴素的，排个序，然后依次减掉就是了。没有什么技巧。
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]
执行用时 : 20 ms, 在Last Stone Weight的Python提交中击败了96.08% 的用户
内存消耗 : 11.7 MB, 在Last Stone Weight的Python提交中击败了100.00% 的用户
高阶思路：题目中每次都要选出最大的两块石头粉碎，自然而然想到先建立一个大根堆 然后每次在这个大根堆里取出头两个元素出来进行粉碎，如果两块石头不相等就将粉碎后的新石头重新放进大根堆 这样循环下去直到大根堆里的元素少于两块石头就结束 此时已经没法再粉碎了
实际写代码可以发现，速度没有直接排序的快。但是这是一种思路的锻炼：
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
执行用时 : 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])
执行用时 : 100 ms, 在Remove All Adjacent Duplicates In String的Python提交中击败了65.22% 的用户
内存消耗 : 12.8 MB, 在Remove All Adjacent Duplicates In String的Python提交中击败了100.00% 的用户
网友评论