Day 11 | 7/14

[tech-cow]

今日计划

择日起，周末刷面经。今天Google面经一天

Easy(5)

• 345 Reverse Vowels of a String
• 246 Strobogrammatic Number
• 844 Backspace String Compare
• 276 Paint Fence
• 359 Logger Rate Limiter

Medium(8)

• 280 Wiggle Sort
• 259 3Sum Smaller
• 200 Number of Islands
• 288 Unique Word Abbreviation
• 289 Game of Life
• 388 Longest Absolute File Path
• 616 Add Bold Tag in String
• 418 Sentence Screen Fitting

总结:

需要迅速补充以下知识点：DP, BFS, 递归

[tech-cow]

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

[tech-cow]

Medium

280 Wiggle Sort

类型: Sort, 双指针
Time Complexity: O(N)
Space Complexity: O(1)

唯一要担心的是nums[i+1]越界，所以在那之前假如一个Condition：i + 1 < n

class Solution(object):
    def wiggleSort(self, nums):
        if not nums:
            return
        n = len(nums)
        for i in range(1, n, 2):
            if nums[i] < nums[i - 1]:
                nums[i], nums[i - 1] = nums[i - 1], nums[i]

            if i + 1 < n and nums[i] < nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]

259 3Sum Smaller

类型: 双指针斗鸡眼
Time Complexity: O(N^2)
Space Complexity: O(1)

3Sum变种，不需要去重。需要考虑到多次相等的Case res += r-l

class Solution:
    def threeSumSmaller(self, nums, target):
        if len(nums) < 3:
            return 0
        nums.sort()
        res = 0

        for i in range(0, len(nums) - 2):
            l, r = i + 1, len(nums) - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < target:
                    res += r - l
                    l += 1
                else:
                    r -= 1
        return res

200. Number of Islands

类型: DFS
Time Complexity: O(N*M)
Space Complexity: O(1)

看答案的，了解非常片面，需要对BFS/DFS进行系统训练后，在返回

class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
        return count

    def dfs(self, grid, i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(
                grid[0]) or grid[i][j] != '1':
            return
        grid[i][j] = '#'
        self.dfs(grid, i + 1, j)
        self.dfs(grid, i - 1, j)
        self.dfs(grid, i, j + 1)
        self.dfs(grid, i, j - 1)

288. Unique Word Abbreviation

类型: Hash Table
Time Complexity: O(N)
Space Complexity: O(N)

这题题目不难，但题目定义的让我一脸懵逼。
就是给了一组List，里面有若干个英语单词。然后除去头和尾，其他的字符都缩成了数字，比如：
"dear"的头是d，尾巴是r，中间的ea一共是2个字母，所以变成了2，最终缩完的output是：d2r

主方程isUnique()的判定条件是

1. 缩写完以后的input是否出现在字典中过，如果没出现过，则代表字典不包含当前input，则返回True。

2. 如果出现过，继续比对两个缩写单词的原词，举例：
   比如dear和door缩写完以后都为d2r，虽然在字典里的key同为d2r，但实际原词不一样
   如果原词一样，则表示这个单词任然是Unique，因为字典里包含的就是原词本身。
   如果不一样，则代表字典里有其他缩写相等的词，返回False

class ValidWordAbbr:
    def __init__(self, arr):
        """
        :type dictionary: List[str]
        """
        self.dic = {}
        for word in set(arr):
            abbr = self.abbrev(word)
            if abbr not in self.dic:
                self.dic[abbr] = word
            else:
                self.dic[abbr] = False

    def isUnique(self, word):
        abbr = self.abbrev(word)
        if abbr not in self.dic:
            return True
        else:
            return self.dic[abbr] == word

    def abbrev(self, word):
        if len(word) < 3:
            return word
        else:
            return word[0] + str(len(word) - 2) + word[-1]

289 Game of Life

类型: Matrix操作 | Bit Manipulation
Time Complexity: O(N^2)
Space Complexity: O(1)
注解参考：指尖飞舞

说多了都是泪，我耗了2小时，才懂题

生死判断条件：

1. 一个活的格子若只有一个或没有邻居, 在下一秒将因寂寞而亡；
2. 一个活的格子若有四个或四个以上的邻居, 在下一秒将因拥挤而亡；
3. 一个活的格子若有二个或三个邻居, 在下一秒将継续活着；
4. 一个死的格子若有三个邻居, 在下一秒将活过来；

题目要求inplace实现，不允许额外申请空间。

若是不考虑占用空间，我们很容易可以解决该问题。首先，保存原始棋盘用于计算邻居live状态的数目。然后依据条件修改board每个cell的状态即可。

若是不允许申请空间，我们必须在不改变原始棋盘状态的情况下，记录出每个cell应该怎么变化；
使用不同数值（十进制）代表状态 0 ：dead； 10 ：dead—>live； 11：live—>live； 1：live；

class Solution(object):
    def gameOfLife(self, board):
        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                neighbors = self.getNeighbors(board, i, j)
                # Dead
                if board[i][j] == 0:
                    if neighbors == 3:
                        board[i][j] += 10  # Dead -> Live
                else:
                    if neighbors == 2 or neighbors == 3:
                        board[i][j] += 10  # Live -> Live

        for i in range(m):
            for j in range(n):
                board[i][j] //= 10
        return

    def getNeighbors(self, board, row, col):
        m, n = len(board), len(board[0])
        cnt = 0
        for i in [row - 1, row, row + 1]:
            for j in [col - 1, col, col + 1]:
                if i == row and j == col or i < 0 or j < 0 or i >= m or j >= n:
                    continue
                if board[i][j] % 10 == 1:
                    cnt += 1
        return cnt

388. Longest Absolute File Path

类型: Hash Table
Time Complexity: O(N)
Space Complexity: O(N)
参考：pyufftj

class Solution(object):
    def lengthLongestPath(self, input):
        """
        :type input: str
        :rtype: int
        """

        dict = {}
        longest = 0
        fileList = input.split("\n")
        for i in fileList:
            if "." not in i:  # 是文件夹
                key = i.count("\t")  # 是几级文件夹
                value = len(i.replace("\t", ""))  # 除去\t后的长度，是实际长度
                dict[key] = value
            else:  # 是文件。
                key = i.count("\t")
                #　文件的长度：所有目录的长度＋文件的长度＋“\”的数量
                length = sum([dict[j] for j in dict.keys() if j <
                              key]) + len(i.replace("\t", "")) + key
                longest = max(longest, length)
        return longest

616. Add Bold Tag in String

类型: String
Time Complexity: O(N*M)
Space Complexity: O(N)

思路
子方程getRange()
建一个和input s 等长的Boolean数组status，用来表示在对应位置是否需要加粗。
我们对s进行遍历，如果s包含字典里的任意word，则将这个word的区间相对应的status进行Boolean转换。转换好以后，就可以加粗了

子方程addBold()
这个没啥多说的，区间已经定义好了，只需要将对应的区间左右加上即可。
扫描s，然后在检查status里面的Boolean来作为判定条件。

class Solution:
    def addBoldTag(self, s, dict):
        status = self.getRange(s, dict)
        return self.addBold(s, status)

    def getRange(self, s, dict):
        '''find the range of bold text and return a boolean array'''
        status = [False] * len(s)
        for word in dict:
            start = s.find(word)
            last = len(word)
            while start != -1:
                for i in range(start, last + start):
                    status[i] = True
                start = s.find(word, start + 1)
        return status

    def addBold(self, s, status):
        '''add Bold text to a given rage based on boolean value in array'''
        i = 0
        final = ""
        while i < len(s):
            if status[i]:
                final += "<b>"
                while i < len(s) and status[i]:
                    final += s[i]
                    i += 1
                final += "</b>"
            else:
                final += s[i]
                i += 1
        return final

418. Sentence Screen Fitting

类型: String
Time Complexity: O(N)
Space Complexity: O(1)

这题看了答案，具体操作把代码PO到这个网站跑一边就懂了。

大致就是用start来计算长度，想给Start赋予整个col的长度，然后在把start % len(s)，如果出现空格则对start进行缩减。

class Solution:
    def wordsTyping(self, sentence, rows, cols):
        s = ' '.join(sentence) + ' '
        start, l = 0, len(s)
        for i in range(rows):
            start += cols
            while s[start % l] != ' ':
                start -= 1
            start += 1
        return start // l