Leetcode Contest 164 (1630 / 5907, 3 solved)

前言

最近發現中文版的Leetcode，也是自從今年七月到現在打的第二場，早上依舊還是習慣性的睡過頭，起床時已經10:15，只剩15分鐘的準備時間，刷個牙連早餐都沒吃就直接開始，不得不說這次的題目相對比較簡單，連第四題 Hard 我認為其實應該只有到 Medium 的難度，然而我因為前三題寫太久，導致最後一題一直到了12:15左右才寫出來，此時已經超過 Contest 時間，所以最後是以3題殘念，雖然還是沒有 辦法像朋友一樣四題全破，不過值得高興的是這次三題都一次　Bug Free 所以沒有被加上超時的懲罰 XD

在我還在想第一題時，前三名已經把全部都寫完了XD

周賽積分: 1711 中國積分 (2025/26207) 全球積分 (19709/131596)

我一直覺得有積分設定以及排行榜超酷的，不僅可以看到自己的排名是進步還是退步，還有點像在打電動遊戲爬天梯的感覺!?，接著就記錄一下題目跟解法～

1266. Minimum Time Visiting All Points

tags: easy

題目: On a plane there are n points with integer coordinates points[i] = [xi, yi]. Your task is to find the minimum time in seconds to visit all points.

You can move according to the next rules:

• In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
• You have to visit the points in the same order as they appear in the array.

Example 1:

Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
Time from [1,1] to [3,4] = 3 seconds 
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds

Example 2:

Input: points = [[3,2],[-2,2]]
Output: 5

Solution : 題目給定一矩陣，當中每一個元素為一個座標點(x,y)，依照每一節點的出現順序，求每次當前節點到下一矩陣中相鄰節點最短距離，每次可以選定水平，垂直，對角線，三種走法，成本皆為1。

從題目中可以發現關鍵在於對角線的成本跟垂直, 水平一致， 因此在走訪時若能走對角就不要走分成水平垂直兩個步驟，因為相比之下假設(0,0) 要到達(1,1)，直接走斜的成本只需要1，若分為先向x走1再向y走1則成本會變成1+1=2，有了這想法後再來就是在何種情況下需要捨棄對角線改走水平或垂直?這問題其實可以轉換成在何種情況下水平垂直的走法會比對角線好?答案就是只要x,y軸只要有一個其中一軸相同我們就可以改為朝數值不同的維度走，直到兩點重和，到此我們已經將所有關鍵找出。

• 只要起始點跟終點 x,y 軸其中一軸不同，則往終點方向對角線移動
• 直到 x,y 其中一軸相同，則往另一軸方向水平或垂直移動，直至兩點重和

ACCEPTED

class Solution:
    def minTimeToVisitAllPoints(self, points):
        res = 0
        for i in range(len(points)-1):
            x1 , y1 = points[i][0] , points[i][1]
            x2 , y2 = points[i+1][0] , points[i+1][1]

            while x1 != x2 and y1 != y2:
                if x2 > x1:
                    x1 += 1 
                    if y2 > y1:
                        y1 +=1
                    elif y2 < y1:
                        y1 -=1

                elif x2 < x1:
                    x1 -= 1
                    if y2 > y1:
                        y1 += 1
                    elif y2 < y1:
                        y1 -= 1 
                res += 1

            res += abs((x1 - x2)) + abs((y2 -y1))

        return res

雖然上述可以過OJ，但其實還有很多地方可以優化，從例子中可以發現要點A到點B只會有兩種情況，分別為 1. 先走對角線再走水平or垂直線 2. 只走水平or垂直線

由此可知要馬是水平垂直個移動一單位，要馬是水平或垂直其中一個移動一單位，然而不論走對角, 走水平, 走垂直，其x座標以及y座標至多只會增加1，因此我們假設 dx = |x1 - x2| , dy = |y1 - y2| 而兩點間的最短移動距離必定大於等於 MAX(dx , dy)　因此可以簡化如下：

ACCEPTED

class Solution:
    def minTimeToVisitAllPoints(self, points):
        res = 0
        x1, y1 = points.pop()
        while points:
            x2, y2 = points.pop()
            res += max(abs(y2 - y1), abs(x2-x1))
            x1, y1 = x2, y2
        return res

1267. Count Servers that Communicate

tags: ｍedium

題目: You are given a map of a server center, represented as a m * n integer matrix grid, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.

Return the number of servers that communicate with any other server.

Example 1:

Input: grid = [[1,0],[0,1]]
Output: 0
Explanation: No servers can communicate with others.

Example 2:

Input: grid = [[1,0],[1,1]]
Output: 3
Explanation: All three servers can communicate with at least one other server.

Example 3:

Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Explanation: The two servers in the first row can communicate with each other. The two servers in the third column can communicate with each other. The server at right bottom corner can't communicate with any other server.

Solution : 題目要求返回所有x,y軸其中一軸有互聯電腦總數，直觀的使用兩個hash table 去紀錄當前的x軸以及y 軸的電腦總數，例如要得知X==3的所有電腦，只需利用dict[3]去進行存取，而為了能夠在 O(1) 的時間內存取該row所有的電腦總數，hash table 中也是用 hash table or set 去紀錄，只要該row 或是該 column 的長度大於一則我們可以保證除了自身還有其他電腦並代表該電腦可以聯網。

ACCEPTED

class Solution(object):
    def countServers(self, grid):
        m = len(grid)
        n = len(grid[0])

        row_dict = collections.defaultdict(set)
        col_dict = collections.defaultdict(set)
        res = 0 

        # create hash table
        for r in range(m):
            for c in range(n):
                ele = grid[r][c] 
                if ele == 1 :
                    row_dict[r].add(c)
                    col_dict[c].add(r)

        # iterate all element 
        for r in range(m):
            for c in range(n):
                ele = grid[r][c]
                if ele == 1 :
                    row_set = row_dict[r]
                    col_set = col_dict[c]

                    if len(row_set) > 1 or len(col_set ) > 1 :
                        res+=1 
        return res

1268. Search Suggestions System

tags: ｍedium

題目: Given an array of strings products and a string searchWord. We want to design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return list of lists of the suggested products after each character of searchWord is typed.

**Example 1:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]
After typing mou, mous and mouse the system suggests ["mouse","mousepad"]

Example 2:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Example 3:

Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

Example 4:

Input: products = ["havana"], searchWord = "tatiana"
Output: [[],[],[],[],[],[],[]]

Solution : 給定一商品串列products，以及一搜尋字串searchWord，設計一個推薦系統，在依次輸入單詞 searchWord 的每一個字母后，推薦 products 數組中前綴與 searchWord 相同的最多三個產品。如果前綴相同的可推薦產品超過三個，請按字典序返回最小的三個。

• 將字串先進行排序 (題目要求按字典序返回最小的三個)
• 首先要建立索引表，其索引表的 Key 為當前字串，value 為商品串列中跟這三字相似度最高的字串
• 假設 apple 為搜尋字串，則我們分別建立 a, ap ,app ,appl ,apple 等相似索引串列
• 只要當前搜尋結果大於等於三個則進行下一輪

ACCEPTED

class Solution(object):
    def suggestedProducts(self, products, searchWord):
        d = collections.defaultdict(list)
        products = sorted(products)
        # create hash 
        for w in products : 
            for i in range(len(w)+1):
                d[w[:i]].append(w)

        res = []
        for i in range(1,len(searchWord)+1):
            key = searchWord[:i]
            tmp = []            
            for word in d[key]:
                if word not in res:
                    tmp.append(word)
                if len(tmp) >2 :
                    break
            res.append(tmp)

        return res

Discuss 中大神的解法

reference:lee215 Explanation For any two word w1 and w2 from all words, If word w1 is prefix of w2, w1 and w2 must be neighbours in the sorted words A.

The same, we can binary search the position of each prefix of search word, and check if the next 3 words is valid.

ACCEPTED

    def suggestedProducts(self, A, word):
        A.sort()
        res, prefix, i = [], '', 0
        for c in word:
            prefix += c
            i = bisect.bisect_left(A, prefix, i)
            res.append([w for w in A[i:i + 3] if w.startswith(prefix)])
        return res

1269. Number of Ways to Stay in the Same Place After Some Steps

tags: hard

題目: You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place (The pointer should not be placed outside the array at any time).

Given two integers steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay

Example 2:

Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay

Example 3:

Input: steps = 4, arrLen = 2
Output: 8

Solution : 題意求在有長度限制的串列中，起始點從0開始，每回合能進行三種操作 1. 停止 2. 左走 3. 右走

試問最後停在原點0有多少種走法? 當中該注意的就是我們應該將當前節點以及當前剩餘步數進行快取，以避免重複計算(概念類似費氏數列)。

ACCEPTED

class Solution(object):
    def numWays(self, steps, arrLen):
        self.d = {}
        self.arrLen = arrLen
        return self.dfs(steps ,0) % (10**9 + 7)

    def dfs(self , step , now_idx ):

        if now_idx == self.arrLen or now_idx < 0 :
            return 0 

        if step == 0 :
            if now_idx == 0:
                return 1         
            return 0 

        if (step , now_idx) in self.d:
            return self.d[(step , now_idx)]

        else:
            l = self.dfs(step-1 , now_idx-1 )
            r = self.dfs(step-1 , now_idx+1 )
            stop = self.dfs(step-1 , now_idx)

            res = l + r +stop             
            self.d[(step , now_idx )] = res
            return res 

使用 lru_cache 實作，概念相同 reference:douzigege

ACCEPTED

from functools import lru_cache

class Solution:
    def numWays(self, steps: int, n: int) -> int:

        MOD = 10**9 + 7

        @lru_cache(None)
        def calculate(pos, steps):
            if pos < 0 or pos >= n: return 0
            if pos > steps: return 0
            if steps == pos: return 1
            steps -= 1
            return (calculate(pos+1, steps) + calculate(pos-1, steps) + calculate(pos, steps)) % MOD

        return calculate(0, steps)