扫题 | 1

[tech-cow]

扫题

今天状态一般，扫一些Easy - Medium的题目练练手

Easy

• 804 Unique Morse Code Words
• 832 Flipping an Image
• 728 Self Dividing Numbers
• 561 Array Partition
• 339 Nested List Weight Sum
• 806 Number of Lines To Write String
• 811 Subdomain Visit Count

Medium

• 807 Max Increase to Keep City Skyline
• 544 Output Contest Matches
• 654 Maximum Binary Tree
• 861 Score After Flipping Matrix
• 797 All Paths From Source to Target

[tech-cow]

Easy

804. Unique Morse Code Words

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

这里可以直接创建set()，省了之后的去重

class Solution(object):
    def uniqueMorseRepresentations(self, words):
        dic = [".-","-...","-.-.","-..",".","..-.","--.","....","..",
               ".---","-.-",".-..","--","-.","---",".--.","--.-",".-.",
               "...","-","..-","...-",".--","-..-","-.--","--.."]
        res = set()
        
        for word in words:
            val = ""
            for char in word:
                val += dic[ord(char) -ord('a')]
            res.add(val)
        return len(res)

832. Flipping an Image

类型: Bit Manipulation
Time Complexity: O(N^2)
Space Complexity: O(N)

reverse完了以后xor

class Solution(object):
    def flipAndInvertImage(self, matrix):
        res = []
        for row in matrix:
            row = row[::-1]
            row = [num ^ 1 for num in row]
            res.append(row)
        return res

728. Self Dividing Numbers

类型: String
Time Complexity: O(N^2)
Space Complexity: O(N)

list(str(val)可以把数字变成拆分好的int数组。

class Solution(object):
    def selfDividingNumbers(self, left, right):
        res = []
        notDivide = False
        for i in range(left, right + 1):
            val = i
            for num in list(str(val)):
                if int(num) == 0 or i % int(num) != 0:
                    notDivide = True
                    break
            if not notDivide:
                res += [i]
            notDivide = False
        return res