Google OA练习

算法

1509. Minimum Difference Between Largest and Smallest Value in Three Moves

You are given an integer array nums.

In one move, you can choose one element of nums and change it to any value.

Return the minimum difference between the largest and smallest value of nums after performing at most three moves.

1
2
3
4
5
6
7
Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

知道最大4和最小4即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <= 4:
            return 0
        # init
        min_list = []
        max_list = []
        min_list[:] = nums[:4]
        max_list[:] = nums[:4]
        # fill the list
        # or we can do sorted and take sorted_lst[:4] and sorted_lst[4:]
        # but it will be nlogn instead of n
        for i in nums[4:]:
            if i > min(max_list):
                max_list.remove(min(max_list))
                max_list.append(i)
            if i < max(min_list):
                min_list.remove(max(min_list))
                min_list.append(i)
        min_list = sorted(min_list)
        max_list = sorted(max_list)
        res = float('inf')
        for i in range(4):
            if max_list[i] - min_list[i] < res:
                res = max_list[i] - min_list[i]
        return 0 if res < 0 else res

1525. Number of Good Ways to Split a String

You are given a string s.

A split is called good if you can split s into two non-empty strings s_left and s_right where their concatenation is equal to s (i.e., s_left + s_right = s) and the number of distinct letters in s_left and s_right is the same.

Return the number of good splits you can make in s.

1
2
3
4
5
6
7
8
Input: s = "aacaba"
Output: 2
Explanation: There are 5 ways to split "aacaba" and 2 of them are good. 
("a", "acaba") Left string and right string contains 1 and 3 different letters respectively.
("aa", "caba") Left string and right string contains 1 and 3 different letters respectively.
("aac", "aba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aaca", "ba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aacab", "a") Left string and right string contains 3 and 1 different letters respectively.

第一感觉两字典然后一个遍历来实时更新两侧字典,检查key数量即可,实际实现后也是beat 32%runtime和95%Mem. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from collections import defaultdict
class Solution:
    def numSplits(self, s: str) -> int:
        left = defaultdict(int)
        right = defaultdict(int)
        for i in s:
            right[i] += 1
        
        res = 0
        for i in s:
            left[i] += 1
            right[i] -= 1
            if right[i] == 0:
                right.pop(i)
            if len(left.keys()) == len(right.keys()):
                res += 1
        return res

1736. Latest Time by Replacing Hidden Digits

You are given a string time in the form of hh:mm, where some of the digits in the string are hidden (represented by ?).

The valid times are those inclusively between 00:00 and 23:59.

Return the latest valid time you can get from time by replacing the hidden digits.

1
2
3
Input: time = "2?:?0"
Output: "23:50"
Explanation: The latest hour beginning with the digit '2' is 23 and the latest minute ending with the digit '0' is 50.

逻辑题 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maximumTime(self, time: str) -> str:
        res = list(time)
        if res[0] == '?':
            if res[1] == '?' or int(res[1]) < 4:
                res[0] = '2'
            else:
                res[0] = '1'
        if res[1] == '?':
            if res[0] == '2':
                res[1] = '3'
            else:
                res[1] = '9'
        if res[3] == '?':
            res[3] = '5'
        if res[4] == '?':
            res[4] = '9'

        return ''.join(res)

1049. Last Stone Weight II

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are destroyed, and If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x. At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

1
2
3
4
5
6
7
Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.

01背包,target为 0.5 * sum(stones) 

1
2
3
4
5
6
7
8
9
10
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        sum_ = sum(stones)
        target = sum_ // 2
        dp = [0 for i in range(target+1)]
        for i in stones:
            for j in range(target, -1, -1):
                if j >= i:
                    dp[j] = max(dp[j], dp[j-i]+i)
        return sum_ - 2 * dp[-1]

Most Booked Hotel Room

Given a hotel which has 10 floors [0-9] and each floor has 26 rooms [A-Z]. You are given a sequence of rooms, where + suggests room is booked, - room is freed. You have to find which room is booked maximum number of times.

You may assume that the list describe a correct sequence of bookings in chronological order; that is, only free rooms can be booked and only booked rooms can be freeed. All rooms are initially free. Note that this does not mean that all rooms have to be free at the end. In case, 2 rooms have been booked the same number of times, return the lexographically smaller room.

You may assume:

  • N (length of input) is an integer within the range [1, 600]
  • each element of array A is a string consisting of three characters: "+" or "-"; a digit "0"-"9"; and uppercase English letter "A" - "Z"
  • the sequence is correct. That is every booked room was previously free and every freed room was previously booked.

counter加个sort 

1
2
def most_booked(lst):
    return sorted(Counter(filter(lambda x: x[0]=='+', lst)).items(), key=lambda y: (-y[-1], -ord(y[0][-1])))[0][0]

1007. Minimum Domino Rotations For Equal Row

In a row of dominoes, tops[i] and bottoms[i] represent the top and bottom halves of the ith domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)

We may rotate the ith domino, so that tops[i] and bottoms[i] swap values.

Return the minimum number of rotations so that all the values in tops are the same, or all the values in bottoms are the same.

If it cannot be done, return -1. 

1
2
3
4
5
Input: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
Output: 2
Explanation: 
The first figure represents the dominoes as given by tops and bottoms: before we do any rotations.
If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.

一开始用的bit_mask遍历复杂幂函数TLE,后续考虑统计频率然后遍历AC 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        if len(set(tops)) <= 1 or len(set(bottoms)) <= 1:
            return 0
        ctr_top = Counter(tops)
        ctr_btm = Counter(bottoms)
        sorted_ctr = sorted(list(ctr_top.items())+list(ctr_btm.items()), key=lambda x: -x[1])
        solution = len(tops)
        for k, v in sorted_ctr:
            for i in range(len(tops)):
                if tops[i] != k and bottoms[i] != k:
                    break
                elif i == len(tops) - 1:
                    res = min(v, len(tops)-v)
                    solution = solution if solution < res else res
        if solution == len(tops):
            return -1
        return solution
看了下其他人的solution,贴一个简洁的代码 
1
2
3
4
5
6
class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        for x in [tops[0], bottoms[0]]:
            if all(x in lst for lst in zip(tops,bottoms)):
                return len(tops) - max(tops.count(x), bottoms.count(x))
        return -1

主要思路 top[0] 或 bottom[0] 必须包含在成立结果中

1165. Single-Row Keyboard

Imagine you have a special keyboard with all keys in a single row. The layout of characters on a keyboard is denoted by a string keyboard of length 26. Initially your finger is at index 0. To type a character, you have to move your finger to the index of the desired character. The time taken to move your finger from index i to index j is abs(j - i).

Given a string keyboard that describe the keyboard layout and a string text, return an integer denoting the time taken to type string text.

1
2
3
4
5
6
7
Input: keyboard = "abcdefghijklmnopqrstuvwxy", text = "cba" 
Output: 4
Explanation:
Initially your finger is at index 0. First you have to type 'c'. The time taken to type 'c' will be abs(2 - 0) = 2 because character 'c' is at index 2.
The second character is 'b' and your finger is now at index 2. The time taken to type 'b' will be abs(1 - 2) = 1 because character 'b' is at index 1.
The third character is 'a' and your finger is now at index 1. The time taken to type 'a' will be abs(0 - 1) = 1 because character 'a' is at index 0.
The total time will therefore be 2 + 1 + 1 = 4.
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def fn(self, keyboard, text) -> int:
        res = 0
        curr = 0
        key_map = dict()
        for index, key in enumerate(keyboard):
            key_map[key] = index
        for char in text:
            v = key_map[char]
            res += abs(v - curr)
            curr = v
        return res

1161. Maximum Level Sum of a Binary Tree

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level x such that the sum of all the values of nodes at level x is maximal.

blacsheep 

1
2
3
4
5
6
7
Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

bfs即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        level = 0
        parent = []
        child = [root]
        dict_ = {}
        while child:
            level += 1
            parent = child
            child = []
            level_sum = 0
            for node in parent:
                if node.left:
                    child.append(node.left)
                if node.right:
                    child.append(node.right)
                level_sum += node.val
            dict_[level] = level_sum
        return sorted(dict_.items(), key=lambda x: (-x[1],x[0]))[0][0]

Hotel Bookings Possible

A hotel manager has to process N advance bookings of rooms for the next season. His hotel has C rooms. Bookings contain an arrival date and a departure date. He wants to find out whether there are enough rooms in the hotel to satisfy the demand. Write a program that solves this problem in time O(NlogN).

Note-If we have arrival and departure on the same date then arrival must be served before the departure.

1
2
3
4
5
6
7
8
9
10
Input 1:
A = [1, 3, 5]
B = [2, 6, 8]
C = 1
# output: 0

A = [1, 2, 3]
B = [2, 3, 4]
C = 2
# output: 1

排序, 指针扫一遍即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    # @param arrive : list of integers
    # @param depart : list of integers
    # @param K : integer
    # @return a boolean
    def hotel(self, arrive, depart, K):
        arrive = sorted(arrive)
        depart = sorted(depart)
        people = 0
        chair = 0
        i_index = 0
        o_index = 0
        while o_index < len(depart):
            while arrive[i_index] <= depart[o_index]:
                people += 1
                i_index += 1
                chair = max(chair, people)
                if i_index == len(arrive):
                    return chair <= K
            o_index += 1
            people -= 1
        return chair <= K

973. K Closest Points to Origin

Given an array of points where points[i] = [x_i, y_i] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)^2 + (y1 - y2)^2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

1
2
3
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.

经典KNN 

1
2
3
class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        return list(sorted(points, key=lambda x: x[0]*x[0] + x[1]*x[1]))[:k]

975. Odd Even Jump

You are given an integer array arr. From some starting index, you can make a series of jumps. The (1st, 3rd, 5th, ...) jumps in the series are called odd-numbered jumps, and the (2nd, 4th, 6th, ...) jumps in the series are called even-numbered jumps. Note that the jumps are numbered, not the indices.

You may jump forward from index i to index j (with i < j) in the following way:

During odd-numbered jumps (i.e., jumps 1, 3, 5, ...), you jump to the index j such that arr[i] <= arr[j] and arr[j] is the smallest possible value. If there are multiple such indices j, you can only jump to the smallest such index j. During even-numbered jumps (i.e., jumps 2, 4, 6, ...), you jump to the index j such that arr[i] >= arr[j] and arr[j] is the largest possible value. If there are multiple such indices j, you can only jump to the smallest such index j. It may be the case that for some index i, there are no legal jumps. A starting index is good if, starting from that index, you can reach the end of the array (index arr.length - 1) by jumping some number of times (possibly 0 or more than once).

Return the number of good starting indices.

1
2
3
4
5
6
7
8
Input: arr = [10,13,12,14,15]
Output: 2
Explanation: 
From starting index i = 0, we can make our 1st jump to i = 2 (since arr[2] is the smallest among arr[1], arr[2], arr[3], arr[4] that is greater or equal to arr[0]), then we cannot jump any more.
From starting index i = 1 and i = 2, we can make our 1st jump to i = 3, then we cannot jump any more.
From starting index i = 3, we can make our 1st jump to i = 4, so we have reached the end.
From starting index i = 4, we have reached the end already.
In total, there are 2 different starting indices i = 3 and i = 4, where we can reach the end with some number of jumps.

描述挺复杂的,但说人话就是永远从左往右跳,奇数跳跳大于等于自己的,偶数跳跳小于等于自己的,永远跳绝对值和自己差最小的,并且有相同值跳近的.

第一感觉可以从后向前推, 只要最后把奇数跳起步的能满足的加起来就行,同时维护一个偶数跳dp组用来更快捷的判断. 但是可惜并没有写出来,选择了比较笨的从前往后推.

遍历arr,把index和value丢字典,然后维护一个key_set. 非常笨,优化也不太行.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def oddEvenJumps(self, arr: List[int]) -> int:
        dict_arr = defaultdict(list)
        key = sorted(list(set(arr)))
        res_list = [[1, 0] for i in range(len(arr))]
        for index, value in enumerate(arr):
            dict_arr[value].append(index)
        
        for index, v in enumerate(arr):
            # same item exist
            if len(dict_arr[v]) > 1:
                same_item_index = dict_arr[v][1]
                res_list[same_item_index][0] += res_list[index][1]
                res_list[same_item_index][1] += res_list[index][0]

            else:
                v_index = bisect.bisect_left(key, v)
                lower_v = key[v_index-1] if v_index >= 1 else None
                upper_v = key[v_index+1] if v_index <= len(key)-2 else None
                if lower_v:
                    lower_index = dict_arr[lower_v][0]
                    res_list[lower_index][0] += res_list[index][1]
                if upper_v:
                    upper_index = dict_arr[upper_v][0]
                    res_list[upper_index][1] += res_list[index][0]
            dict_arr[v].pop(0)
            if not dict_arr[v]:
                key.pop(v_index)
        return sum(res_list[-1])

后续看了下别人的代码,发现可以用栈来处理 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
    def oddEvenJumps(self, arr: List[int]) -> int:
        if not arr:
            return 0
        
        def next_greater_element(arr):
            n = len(arr)
            result = [None]*n
            stack = []
            
            for i in range(n):
                while stack and arr[stack[-1]] < arr[i]:
                    result[arr[stack.pop()]] = arr[i]
                stack.append(i)
            del stack
            return result
        
        n = len(arr)
        arr_sorted = sorted(range(n), key=lambda x: arr[x])
        odd = next_greater_element(arr_sorted)
        
        arr_sorted.sort(key=lambda x: arr[x], reverse=True)
        even = next_greater_element(arr_sorted)
        
        # Index 0, represents path starting with odd jump
        # Index 1, represents path starting with even jump
        dp = [[0, 0] for i in range(n)]
        
        # Last Index is always reachable.
        dp[-1] = [1, 1]
        
        for i in range(n-2, -1, -1):
            
            # If Odd Jump is possible
            if odd[i] is not None:
                dp[i][0] = dp[odd[i]][1]
                
            # If Even Jump is possible
            if even[i] is not None:
                dp[i][1] = dp[even[i]][0]
        
        return sum([i[0] for i in dp])

这里arr_sorted返回依据value排序的index列表,然后next_greater_element依据此列表算出所有元素的下一跳index,这样即可得到odd jump的列表, even jump的话reverse=True再sort一遍丢进去即even jump列表.

最后依据两个列表从后往前推导即可.

482. License Key Formatting

You are given a license key represented as a string s that consists of only alphanumeric characters and dashes. The string is separated into n + 1 groups by n dashes. You are also given an integer k.

We want to reformat the string s such that each group contains exactly k characters, except for the first group, which could be shorter than k but still must contain at least one character. Furthermore, there must be a dash inserted between two groups, and you should convert all lowercase letters to uppercase.

Return the reformatted license key.

1
2
3
Input: s = "2-5g-3-J", k = 2
Output: "2-5G-3J"
Explanation: The string s has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above.
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        s = ''.join(s.split('-')).upper()
        if len(s) <= k:
            return s
        seperate = len(s)%k
        ret = s[:seperate]
        
        for i in range(seperate, len(s), k):
            ret += '-' + s[i:i+k]
        return ret if seperate else ret[1:]

929. Unique Email Addresses

描述很复杂, 简单表述就是修复localname.

方法:localname里面的句号无视掉, 加号算注释符, domain不变

求修复localname后不同的邮件地址数.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def numUniqueEmails(self, emails: List[str]) -> int:
        ret = []
        for email in emails:
            local_name, domain = email.split('@')
            fixed_local_name = ''
            for i in local_name:
                if i not in ['.', '+']:
                    fixed_local_name += i
                elif i == '+':
                    break
            ret.append((fixed_local_name, domain))
        return len(set(ret))

904. Fruit Into Baskets

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

  • You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
  • Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
  • Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array fruits, return the maximum number of fruits you can pick.

1
2
3
4
Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: We can pick from trees [2,3,2,2].
If we had started at the first tree, we would only pick from trees [1,2].

双指针 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        l, r = 0, 0
        basket = defaultdict(int)
        res = 0
        while r != len(fruits):
            basket[fruits[r]] += 1
            r += 1
            if len(basket) > 2:
                res = max(res, r - l - 1)
                while len(basket) > 2:
                    l_fruit = fruits[l]
                    basket[l_fruit] -= 1
                    if basket[l_fruit] == 0:
                        del basket[l_fruit]
                    l += 1
        return max(res, r - l)

1482. Minimum Number of Days to Make m Bouquets

You are given an integer array bloomDay, an integer m and an integer k.

You want to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.

The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.

Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.

1
2
3
4
5
6
7
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

一开始觉得遍历n,然后跑了4000ms,就感觉不太对,后续看了下solution发现跑二分. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def check(time):
            flower = 0
            bouquet = 0
            for i in bloomDay:
                if i <= time:
                    flower += 1
                else:
                    flower = 0
                if flower == k:
                    bouquet += 1
                    flower = 0
                    if bouquet == m:
                        return True
            return False

        if not check(1e9):
            return -1

        l = min(bloomDay)
        r = max(bloomDay)
        while l <= r:
            mid = l + (r - l) // 2
            if check(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l

Fill Matrix

Given a NxN matrix. Fill the integers from 1 to n*n to this matrix that makes the sum of each row, each column and the two diagonals equal.

1
2
3
4
5
6
7
8
9
Input: n = 3
Output:
[[8, 3, 4],
 [1, 5, 9],
 [6, 7, 2]]
Explanation: We need to fill [1, 2, 3... 9] into a 3x3 matrix. This is one way to do it
Each row [8, 3, 4] [1, 5, 9] [6, 7, 2] sum is 15.
Each column [8, 1, 6] [3, 5, 7] [4, 9, 2] sum is 15.
The two diagonals [8, 5, 2] [4, 5, 6] sum is 15.

只会一手爆破写法,复杂度高了直接不行,最多到4. 优化懒得考虑了,感觉不得行 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
def check_row(board, row, n):
    ret = 0
    for i in range(n):
        if board[row][i] == None:
            return -1
        ret += board[row][i]
    return ret

def check_col(board, col, n):
    ret = 0
    for i in range(n):
        if board[i][col] == None:
            return -1
        ret += board[i][col]
    return ret

def check_diagnal(board, n, tl2br=True):
    ret = 0
    if tl2br:
        for i in range(n):
            if board[i][i] == None:
                return -1
            ret += board[i][i]
    else:
        for i in range(n):
            if board[i][n - i - 1] == None:
                return -1
            ret += board[i][n - i - 1]
    return ret

def fillMatrix(n: int) -> int:
    def fill(board, index, value_set, n):
        if len(value_set) == 0:
            return board
        row = index // n
        col = index % n
        new_board = board.copy()
        for value in value_set:
            new_board[row][col] = value
            new_value_set = value_set - {value}
            if row == n - 1 or col == n - 1:
                if row == n - 1:
                    if check_col(new_board, col, n) != avg:
                        continue
                if col == n - 1:
                    if check_row(new_board, row, n) != avg:
                        continue

                if row == n - 1 and col == n - 1:
                    if check_diagnal(new_board, n) != avg:
                        continue

                elif row == n-1 and col == 0:
                    if check_diagnal(new_board, n, False) != avg:
                        continue

            ret = fill(new_board, index + 1, new_value_set, n)
            if ret == -1:
                continue
            elif row == n - 1 and col == n - 1:
                return new_board
            else:
                return ret
        return -1

    board = [[None for i in range(n)] for j in range(n)]
    all_value = set(range(1, n**2+1))
    avg = sum(all_value) // n
    ret = fill(board, 0, all_value, n)
    if ret != -1:
        return ret
    else:
        return -1

# check
n=4
res = fillMatrix(n)
if res != -1:
    # matrix
    print("Matrix:")
    for i in res:
        print(i)
    print()

    # row check
    print("rows:", end='')
    for i in range(n):
        ret = 0
        for j in range(n):
            ret += res[i][j]
        print(ret, end=' ')
    print()

    # col check
    print("cols:", end='')
    for i in range(n):
        ret = 0
        for j in range(n):
            ret += res[j][i]
        print(ret, end=' ')
    print()

    print("tlbr diagonal:", end='')
    ret = 0
    for i in range(n):
        ret += res[i][i]
    print(ret)

    print("trbl diagonal:", end='')
    ret = 0
    for i in range(n):
        ret += res[i][n-1-i]
    print(ret)
else:
    print("Not Exist!")

300. Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

1
2
3
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

一开始是觉得是dp, 外层遍历所有元素, 内层遍历找最长路径, dp元素表示到达某个index的最长路径,复杂度O(n^2),但题目要求nlogn,想了半天没想出来,看了下别人的答案,理解了之后自己写了一遍. 

1
2
3
4
5
6
7
8
9
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        lst = [nums[0]]
        for num in nums[1:]:
            if num > lst[-1]:
                lst.append(num)
            else:
                lst[bisect.bisect_left(lst, num)] = num
        return len(lst)
主要就是一旦新元素大于最右侧必然导致长度加一,否则可以丢到list里面去当作新case来储存,一旦这个新case达到最大长度或者新来的元素大于所有元素都会被考虑到,而我们并不在乎原来的list是什么,所以最后list会被打乱,但是不影响最终返回是最大长度.

Maximum Distance

Problem statement You are given an array of binary strings ‘arr’ of size ‘N’. Your task is to find out the maximum distance between the pair of strings.

The distance between two binary strings is defined as the sum of their lengths after removing the common prefix.

For example: You are given ‘arr’ = [ “01011”, “010110”, “0111”], Here the strings with the maximum distance between them are “010110” and “0111”, where the prefix is “01”, hence the maximum distance is 4 + 2 = 6. Hence the answer is 6.

第一感觉暴力求解,然后就写了一份然后AC了,看了答案发现用trie做的,第一次见这个数据结构,也算是记一下了. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# brute force

from typing import *
def maximumDistance(arr: List[str]) -> int:
    length = len(arr)
    def diff(str1, str2):
        l1, l2 = len(str1), len(str2)
        min_length = min(l1, l2)
        same_length = 0
        for char_index in range(min_length):
            if str1[char_index] == str2[char_index]:
                same_length += 1
            else:
                break
        return l1 + l2 - 2 *same_length

    result = 0
    for i in range(length-1):
        for j in range(i+1, length):
            result = max(result, diff(arr[i], arr[j]))
    return result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
# trie
'''
    Time Complexity: O(N*M)
    Space Complexity: O(N*M)

    Where N is the number of strings and M is the average length of each string
'''

from queue import deque
from typing import *


class TrieNode:

    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.isEnd = False


# Function to build the trie Node
def buildTree(arr: List[str], root: TrieNode) -> None:

    for currString in arr:

        # Set starting node as root
        currNode = root

        for i in range(len(currString)):

            # Get the distance of current character from the end of the string
            distance = len(currString) - i

            # If the current character is 0 the add the distance towards the left child
            if(currString[i] == '0'):

                if(not currNode.left):

                    # If node doesn't exist create and add the distance of the node
                    currNode.left = TrieNode(distance)

                else:
                    currNode.left.val = max(currNode.left.val, distance)

                # Move the current node towards left
                currNode = currNode.left

            # If the current character is 1 the add the distance towards the right child
            else:

                if(not currNode.right):
                    currNode.right = TrieNode(distance)

                else:
                    currNode.right.val = max(currNode.right.val, distance)
                currNode = currNode.right

        # Set the isEnd true for the last node in the string
        currNode.isEnd= True


def maximumDistance(arr: List[str]) -> int:

    # Build the current node dummy root node for the trie
    root = TrieNode(0)

    buildTree(arr, root)

    maxDistance = 0

    # Initialise an empty queue
    q = deque()
    q.append(root)

    # Do a BFS on the trie
    while(len(q) > 0):

        currNode = q.popleft()

        if(currNode.left or currNode.right):

            # If both left and right is present them the string differ from here
            if(currNode.left and currNode.right):

                # Therefore we add the distance
                maxDistance = max(maxDistance, currNode.left.val + currNode.right.val)

            # If current node is the last node of the string then only one of left or right is present
            if(currNode.isEnd):
                maxDistance = max(maxDistance, currNode.left.val if currNode.left else currNode.right.val)

        if(currNode.left):
            q.append(currNode.left)

        if(currNode.right):
            q.append(currNode.right)

    # Finally return the maxDistance
    return maxDistance

475. Heaters

Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.

Every house can be warmed, as long as the house is within the heater's warm radius range.

Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.

Notice that all the heaters follow your radius standard, and the warm radius will the same.

1
2
3
Input: houses = [1,2,3,4], heaters = [1,4]
Output: 1
Explanation: The two heaters were placed at positions 1 and 4. We need to use a radius 1 standard, then all the houses can be warmed.

排序加二分, nlogn 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        res = 0
        houses = sorted(houses)
        heaters = sorted(heaters)
        for i in houses:
            nearest_index = bisect.bisect_left(heaters, i)
            if 1<= nearest_index <= len(heaters) - 1:
                res = max(res, min(abs(heaters[nearest_index-1]-i),abs(heaters[nearest_index]-i)))
            else:
                if nearest_index == 0:
                    res = max(res, abs(heaters[0]-i))
                else:
                    res = max(res, abs(heaters[-1]-i))
        return res