tech-cow
commented
6 years ago Easy
345 Reverse Vowels of a String
类型: 双指针斗鸡眼 Time Complexity: O(N * M) Space Complexity: O(M)
只要没有达到要求，增加或者递减左右坐标。
达到要求对换。这里想了想，没有必要把vowel设置成字典，因为本身这个vowel的长度就很短，所以O(N)的搜索在这里不会变的很慢。
class Solution:
def reverseVowels(self, s):
vowel = 'aeiouAEIOU'
arr = list(s)
l, r = 0, len(s) - 1
while l < r:
while l < r and arr[l] not in vowel:
l += 1
while l < r and arr[r] not in vowel:
r -= 1
arr[l], arr[r] = arr[r], arr[l]
l += 1
r -= 1
return ''.join(arr)
246. Strobogrammatic Number
类型: 双指针斗鸡眼 + 字典 Time Complexity: O(N) Space Complexity: O(N)
这题主要Tricky的地方就是在6和9的两个Case,题目要求反转一样的话，那么可以使用字典来表达6和9相对应的关系，然后左右指针缩进比对即可
class Solution:
def isStrobogrammatic(self, nums):
dic = {'1': '1', '0': '0', '6': '9', '8': '8', '9': '6'}
l, r = 0, len(nums) - 1
while l <= r:
if nums[l] not in dic or dic[nums[l]] != nums[r]:
return False
l += 1
r -= 1
return True
844. Backspace String Compare
类型: Stack Time Complexity: O(N) Space Complexity: O(N)
不解释了，基本Stack
class Solution:
def backspaceCompare(self, str1, str2):
return self.stack(str1) == self.stack(str2)
def stack(self, str):
stack = []
for char in str:
if char is not '#':
stack.append(char)
else:
if not stack:
continue
stack.pop()
return stack
Follow up: O(1) Space
类型: 双指针 Time Complexity: O(N) Space Complexity: O(1)
从两个String里面抽离一个Char然后比对。
抽数的条件要满足一些 本题的特定条件。
class Solution:
def backspaceCompare(self, str1, str2):
end1 = len(str1) - 1
end2 = len(str2) - 1
while end1 >= 0 or end2 >= 0:
char1 = char2 = ''
if end1 >= 0:
char1, end1 = self.getChar(str1, end1)
if end2 >= 0:
char2, end2 = self.getChar(str2, end2)
if char1 != char2:
return False
return True
def getChar(self, s, end):
count = 0
char = ''
while end >= 0 and not char:
if s[end] == '#':
count += 1
elif count == 0:
char = s[end]
else:
count -= 1
end -= 1
return char, end
276. Paint Fence
类型: Dynamic Programming Time Complexity: O(N) Space Complexity: O(1) 以下解释来源：Grandyang
这道题让我们粉刷篱笆，有n个部分需要刷，有k种颜色的油漆，规定了不能有超过两个的相同颜色涂的部分，问我们总共有多少种刷法。那么我们首先来分析一下，如果n=0的话，说明没有需要刷的部分，直接返回0即可，如果n为1的话，那么有几种颜色，就有几种刷法，所以应该返回k，当n=2时，k=2时，我们可以分两种情况来统计，一种是相邻部分没有相同的，一种相同部分有相同的颜色，那么对于没有相同的，对于第一个格子，我们有k种填法，对于下一个相邻的格子，由于不能相同，所以我们只有k-1种填法。而有相同部分颜色的刷法和上一个格子的不同颜色刷法相同，因为我们下一格的颜色和之前那个格子颜色刷成一样的即可，最后总共的刷法就是把不同和相同两个刷法加起来，参见代码如下：
class Solution:
def numWays(self, n, k):
if n == 0:
return 0
same = 0
diff = k
for i in range(1, n):
total = diff + same
same = diff
diff = total * (k - 1)
return same + diff
359. Logger Rate Limiter
类型: Hash Table Time Complexity: O(1) Space Complexity: O(N)
不多解释了，用字典简历以下Message和时间的关系
class Logger:
def __init__(self):
self.time_keeper = {}
def shouldPrintMessage(self, timestamp, message):
if message in self.time_keeper and timestamp - \
self.time_keeper[message] < 10:
return False
self.time_keeper[message] = timestamp
return True
今日计划
择日起，周末刷面经。今天Google面经一天
总结:
需要迅速补充以下知识点：DP, BFS, 递归