每日第1題為中文站(LCCN) ，第2題為英文站(LCUS) ，題目連結皆統一為英文站的題目連結。
Easy 、Medium 、Hard 難度的題目分別用🟢🟡🔴表示。
若為周賽題目會額外標註由 @zreotrac 零神計算的rating分數。

All problems solved by python

2023-12-21

🟡 2866. Beautiful Towers II 2072

題意

  • 給定一個長度為 nn 的整數陣列 maxHeightsmaxHeights ，你的任務是在座標軸上建造 nn 座塔。 第 ii 座塔的下標為 ii ，高度為 heights[i]heights[i] ，並滿足以下條件：
    1. 1<=heights[i]<=maxHeights[i]1 <= heights[i] <= maxHeights[i]
    2. heightsheights 是一個 山脈 陣列。
      • 對於所有 0<j<=i0 < j <= i ，都有 heights[j−1]<=heights[j]heights[j - 1] <= heights[j]
      • 對所有 i<=k<n−1i <= k < n - 1 ，都有 heights[k+1]<=heights[k]heights[k + 1] <= heights[k]
  • 請你返回可行方案中，高度和的最大值 。

思路：單調棧 + 前後綴分解

  • 題目要求的 山脈 陣列，可以分成兩個部分，前半部分是遞增的，後半部分是遞減的，且分界點可以是 00 到 n−1n - 1 之間的任意一個位置。
  • 因此問題可以拆分成兩個部分：構建出前半部分的遞增陣列，和構建出後半部分的遞減陣列。將長度為 xx 的遞增陣列和長度為 n−xn -x 的遞減陣列合併，可以直接得到一個長度為 nn 的 山脈 陣列。
    • 遞增陣列的最後一個元素，和遞減陣列的第一個元素，兩者較大的即為 山脈 陣列的最高點，因此 不用考慮最高點為何，只需要構建遞增和遞減陣列 。
  • 為了構建出最大值，我們可以使用 Monotonic Stack(單調棧) 來構建遞增和遞減陣列，對於後半部分的遞減陣列，可以由後往前構建遞增陣列，然後將其反轉即可。
    • 單調棧的作用是，對於每個元素 xx ，找到最大的 yy ，使得 yy 在 xx 的左邊，且 yy 滿足某種條件。
    • 這裡的條件是，yy 在 xx 的左邊，且 yy 的高度小於等於 xx 的高度。
    • 這樣的 yy 可以用單調棧來找到，且單調棧中的元素都是由底到上 遞增 的。
  • 令單調棧內保存最大高度的下標 st[−1]=jst[-1] = j ，則 jj 對答案的貢獻為 maxHeights[j]∗(j−k)maxHeights[j] * (j - k) ，其中 kk 為單調棧中 jj 的下一個元素的下標。
    • 為了計算第一個元素的貢獻，我們可以在單調棧的底部加入一個 dummy 元素，在計算前綴部分時，其下標為 −1-1 ；在計算後綴部分時，其下標為 nn 。
  • 對於新加入的元素 xx ，我們需要將單調棧中所有高度大於等於 ≥x\geq x 的元素彈出，並計算其對答案的貢獻。
    • 這是因為，這些元素的高度都不能 >x>x ，否則就不是 山脈 陣列了。
    • 為了維持單調性，對於高度=x=x的元素，也需要彈出。
    • 這些元素的高度都是 xx ，因此對答案的貢獻為 x∗(i−st[−1])x * (i - st[-1]) ，其中 ii 為 xx 的下標，st[−1]st[-1] 為棧頂元素的下標。
  • 用同樣的方法計算前綴和和後綴和，即可得到答案。
    • 前綴和 pre[i]pre[i] 表示 [0,i][0, i] 區間所構建的遞增陣列的最大值。
    • 後綴和 suf[i]suf[i] 表示 [i,n)[i, n) 區間所構建的遞減陣列的最大值。
    • 答案為 max0≤i<n(pre[i]+suf[i+1])max_{0 \leq i < n}(pre[i] + suf[i + 1])
  • 時間複雜度 O(n)O(n)
  • 空間複雜度 O(n)O(n)
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
class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        n = len(maxHeights)

        # 前綴部分
        pre = [0] * (n + 1)
        st = [-1] # dummy, 用於計算區間長度
        s = 0
        for i, x in enumerate(maxHeights):
            while len(st) > 1 and x <= maxHeights[st[-1]]:
                j = st.pop()
                s -= maxHeights[j] * (j - st[-1]) # 這段區間的高度不能為 maxHeights[j] 了，所以要撤銷
            s += x * (i - st[-1]) # 這段區間的高度都是 x
            pre[i] = s
            st.append(i)

        # 後綴部分
        suf = [0] * (n + 1)
        st = [n] # dummy, 用於計算區間長度
        s = 0
        for i in range(n - 1, -1, -1):
            x = maxHeights[i]
            while len(st) > 1 and x <= maxHeights[st[-1]]:
                j = st.pop()
                s -= maxHeights[j] * (st[-1] - j) # 這段區間的高度不能為 maxHeights[j] 了，所以要撤銷
            s += x * (st[-1] - i) # 這段區間的高度都是 x
            suf[i] = s
            st.append(i)

        # 結果
        ans = suf[0]
        for i in range(n):
            ans = max(ans, pre[i] + suf[i + 1])
        return ans

類題

前後綴分解

單調棧

矩形系列

字典序(最小)

貢獻法（計算所有子陣列的……的和）

題單來自：@灵茶山艾府 [1], [2], [3]

🟡 1637. Widest Vertical Area Between Two Points Containing No Points 1487

題意

  • 給定 nn 個二維平面上的點 pointspoints ，其中 points[i]=[xi,yi]points[i] = [x_i, y_i] ，返回兩點之間內部不包含任何點的 最寬垂直區域 的寬度。
  • 垂直區域 的定義是固定寬度，而 y 軸上無限延伸的一塊區域（也就是高度為無限大）。 最寬垂直區域 為寬度最大的一個垂直區域。
  • 在垂直區域 邊界上 的點，被視為在 不在 區域內。

思路：排序 + 找最大差值

  • 根據題意，我們可以對陣列 pointspoints 依照 xx 升序排列，計算相鄰兩點之差的最大值，即max1≤i<n(xi−xi−1)max_{1 \leq i < n}(x_{i} - x_{i-1}) ，即為答案。
  • 時間複雜度 O(nlogn)O(nlogn)，主要是排序的時間複雜度。
  • 空間複雜度 O(n)O(n)
1
2
3
4
5
6
7
8
class Solution:
    def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
        n = len(points)
        points.sort(key=lambda x: x[0])
        ans = 0
        for i in range(1, n):
            ans = max(ans, points[i][0] - points[i - 1][0])
        return ans

2023-12-22

🔴 1671. Minimum Number of Removals to Make Mountain Array 1913

題意

  • 給定一個整數陣列 numsnums ，請你返回使 numsnums 成為 山形陣列(mountain array) 的 最少 刪除次數。
  • 當 arrarr 滿足以下條件時，則稱 arrarr 是 mountain array ：
    1. arr.length>=3arr.length >= 3
    2. 存在某個下標 ii （從 00 開始）滿足 0<i<arr.length−10 < i < arr.length - 1 且：
      • arr[0]<arr[1]<...<arr[i−1]<arr[i]arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
      • arr[i]>arr[i+1]>...>arr[arr.length−1]arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

思路：最長遞增子序列(LIS) + 前後綴分解

  • 上禮拜剛寫過
  • 題意要求最少的刪除次數，等價於求最長的山形陣列的長度 。
  • 這題相比昨天的 2866. Beautiful Towers II ，我們並不在意每個元素的高度，而只在意最長的山形陣列的長度，因此並不需要單調棧來維護最大高度。
  • 這題可以轉換成求Longest Increasing Subsequence (LIS)的問題：：
    • 令 dp1[i]dp1[i] 表示由前往後，以 nums[i]nums[i] 結尾的 LIS 長度。
    • 令 dp2[i]dp2[i] 表示由後往前，以 nums[i]nums[i] 結尾的 LIS 長度。
    • 令 maxLenmaxLen 表示最長的山形陣列的長度。
    • 則 maxLen=max1≤i<n−1(dp1[i]+dp2[i]−1)maxLen = max_{1 \leq i < n-1}(dp1[i] + dp2[i] - 1) ，其中 nn 為陣列長度，−1-1 是因為 ii 位置被重複計算了兩次。
    • 需要注意，若 dp1[i]==1dp1[i] == 1 或 dp2[i]==1dp2[i] == 1 ，代表山頂前/後沒有比它小的數字，根據定義， ii 位置不可能是山形陣列的山頂，因此不應該考慮此位置。
  • 若要進一步提升時間複雜度，在計算LIS的時候，可以用貪心+二分搜尋，上禮拜寫的 這篇文章
  • 時間複雜度：O(n2)O(n^2)
  • 空間複雜度：O(n)O(n)
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
class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        # 1. Find LIS from left to right
        dp1 = [1] * n # dp[i] 表示由前往後，以 nums[i] 結尾的 LIS 長度
        for i in range(1, n): # 枚舉所有位置 i
            for j in range(i): # 枚舉 i 前面的所有位置 j
                if nums[j] < nums[i]: # nums[i] 可以接在 nums[j] 後面
                    if dp1[j] + 1 > dp1[i]: # 若可以得到更大的LIS長度，更新 dp[i] 和 prev[i]
                        dp1[i] = dp1[j] + 1
        # 2. Find LIS from right to left
        dp2 = [1] * n # dp[i] 表示由後往前，以 nums[i] 結尾的 LIS 長度
        for i in range(n-2, -1, -1): # 枚舉所有位置 i
            for j in range(n-1, i, -1): # 枚舉 i 後面的所有位置 j
                if nums[j] < nums[i]: # nums[i] 可以接在 nums[j] 前面
                    if dp2[j] + 1 > dp2[i]: # 若可以得到更大的LIS長度，更新 dp[i] 和 prev[i]
                        dp2[i] = dp2[j] + 1
        # 3. Find the maximum length of mountain array
        max_len = 0
        for i in range(1, n-1): # 以 i 為山頂
            # 若 dp1[i] == 1 代表山頂前沒有比它小的數字，根據定義，不是山形陣列
            # 若 dp2[i] == 1 代表山頂後沒有比它小的數字，根據定義，不是山形陣列
            if dp1[i] != 1 and dp2[i] != 1:
                max_len = max(max_len, dp1[i] + dp2[i] - 1)
        return n - max_len

類題

最長遞增子序列(LIS)

前後綴分解 (同昨日)

題單來自：@灵茶山艾府 [1], [2]

🟢 1422. Maximum Score After Splitting a String 1238

題意

給定一個由若干 00 和 11 組成的字串 ss ，請你計算並返回將該字串分割成兩個非空子字串（即左子字串和右子字串）後，左字串中 00 的數量加上右字串中 11 的數量的最大值。

思路：簡單模擬

  • 先計算出 ss 中 11 的總數 cnt1cnt1 ，接著枚舉分割點 ii ：
    • 若 s[i]=0s[i] = 0 代表右子串中有一個 00 跑到左子串中，因為 00 只在左子串中存在貢獻，因此答對答案的貢獻 +1+1
    • 若 s[i]=1s[i] = 1 代表右子串中有一個 11 跑到左子串中，因為 11 只在右子串中存在貢獻，因此答對答案的貢獻 −1-1
  • 思考上，可以先令 lcnt0lcnt0 和 rcnt1rcnt1 分別表示左子串中 00 的數量和右子串中 11 的數量，但事實上兩個變數對答案的貢獻變化相同，可以合併。
  • 時間複雜度 O(n)O(n)
  • 空間複雜度 O(1)O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxScore(self, s: str) -> int:
        n = len(s)
        ans = 0
        # lcnt0, rcnt1 = 0, s.count('1')
        cur = s.count('1')
        for ch in s[:n-1]:
            # if ch == '0':
            #     lcnt0 += 1
            # else:
            #     rcnt1 -= 1
            cur += 1 if ch == '0' else -1
            # ans = max(ans, lcnt0 + rcnt1)
            ans = max(ans, cur)
        return ans

2023-12-23

🟡 1962. Remove Stones to Minimize the Total 1419

題意

  • 給定一個整數陣列 pilespiles ，其中 piles[i]piles[i] 表示第 ii 堆石頭中的石頭數量。另給定一個整數 kk ，表示可以操作的次數。
  • 在每次操作中，可以從 pilespiles 中選擇一堆石頭，並從中移除 floor(piles[i]/2)floor(piles[i] / 2) 顆石頭，可以對同一堆石頭多次執行此操作。
  • 返回執行 kk 次操作後，剩下石子的 最小 總數。

思路：Greedy + Heap

  • 很顯然地，要使剩下的石頭數量最小，每次都要盡可能地移除最多的石頭。因此可以建立一個Max Heap，每次從堆中取出最大的元素，並將其減半後放回堆中。
  • 這樣做的好處是，每次取出的元素都是當前堆中最大的元素，因此可以保證每次取出的元素都是最佳的選擇。
  • 時間複雜度 O(n+klog⁡n)O(n + k \log n) ，heapify 的時間複雜度為 O(n)O(n) (buttom-up)，每次從堆中取出元素的時間複雜度為 O(log⁡n)O(\log n) ，總共取出 kk 次。
  • 空間複雜度 O(n)O(n)
1
2
3
4
5
6
7
8
9
class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        n = len(piles)
        hp = [-x for x in piles]
        heapify(hp)
        for _ in range(k):
            x = -heappop(hp)
            heappush(hp, -(x - x // 2))
        return -sum(hp)

🟢 1496. Path Crossing 1508

題意

  • 給定一個字串 pathpath ，其中 path[i]path[i] 可以是 ′N′'N'、′S′'S'、′E′'E' 或 ′W′'W'，分別代表向北、南、東、或西移動一個單位。
  • 從二維平面的原點 (0,0)(0, 0) 開始，並按照 pathpath 指定的路徑行走。如果路徑在任何點出現交叉，也就是說，走到之前訪問過的位置，則返回 truetrue；否則，返回 falsefalse。

思路：簡單模擬 + 雜湊表

  • 建一個雜湊表 visitedvisited ，用來記錄走過的位置，若某個位置已經在 visitedvisited 中，則代表路徑出現交叉，返回 truetrue ，否則返回 falsefalse 。
  • 時間複雜度 O(n)O(n)
  • 空間複雜度 O(n)O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isPathCrossing(self, path: str) -> bool:
        visited = set([(0,0)])
        x, y = 0, 0
        for ch in path:
            if ch == "N":
                y += 1
            elif ch == "S":
                y -= 1
            elif ch == "E":
                x += 1
            else:
                x -= 1
            if (x, y) in visited:
                return True
            visited.add((x, y))
        return False

2023-12-24

🟡 1954. Minimum Garden Perimeter to Collect Enough Apples 1759

題意

  • 給定一個無限大的二維平面，每一個整數座標 (i,j)(i,j) 上都有 ∣i∣+∣j∣|i| + |j| 個蘋果樹。又給定一個整數 neededApplesneededApples ，表示需要獲取的蘋果數量。
  • 以二維平面的原點 (0,0)(0, 0) 為中心，找到最小的正方形土地，使得土地中裡面或邊緣上包含的蘋果數量 至少 為 neededApplesneededApples ，並返回該土地的 最小周長 。

思路：數學 + 二分搜尋

  • 令右上角座標為 (n,n)(n, n) 的正方形表示第 nn 層，即邊長為 2n2n、周長為 8n8n 的正方形。
  • 首先推導每層的蘋果數量：
    • 第 00 層：00
    • 第 11 層：4×(2+1)4 \times (2+1)
    • 第 22 層：4×((4+3)+(2+3))4 \times ((4+3) + (2+3))
    • 第 33 層：4×((6+5+4)+(3+4+5))4 \times ((6+5+4) + (3+4+5))
    • 第 nn 層：4×(((2n)+(2n−1)+...+(n+1))+((n)+(n+1)+...+(2n−1)))4 \times (((2n)+(2n-1)+...+(n+1)) + ((n)+(n+1)+...+(2n-1)))
  • 得第 nn 層的蘋果數量為 4×((3n+1)∗n2+(3n−1)∗n2)=12×n24 \times (\frac{(3n+1)*n}{2} + \frac{(3n-1)*n}{2}) = 12 \times n^2
  • 因此前 nn 層的蘋果數量為 Σi=1n12×i2=12×n(n+1)(2n+1)6=2×n(n+1)(2n+1)\Sigma_{i=1}^{n} 12 \times i^2 = 12 \times \frac{n(n+1)(2n+1)}{6} = 2 \times n(n+1)(2n+1)
  • 對於給定的 neededApplesneededApples ，我們可以二分搜尋 nn ，使得 2×n(n+1)(2n+1)≥neededApples2 \times n(n+1)(2n+1) \geq neededApples ，即可得到答案。
  • 時間複雜度 O(log⁡m)O(\log m)，其中 mm 為 neededApplesneededApples 的上界。
  • 空間複雜度 O(1)O(1)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minimumPerimeter(self, neededApples: int) -> int:
        def calc(n): # 計算前 n 層的蘋果數量
            return 2 * n * (n + 1) * (2 * n + 1)
        left, right = 0, 10 ** 5
        while (left <= right):
            mid = (left + right) // 2
            if calc(mid) >= neededApples:
                right = mid - 1
            else:
                left = mid + 1
        return 8 * left # 每層的邊長為 8 * n

🟢 1758. Minimum Changes To Make Alternating Binary String 1354

題意

  • 給定一個僅由字元 00 和 11 組成的字串 ss 。在每次操作中，可以將任一 ′0′'0' 變成 ′1′'1' ，或將 ′1′'1' 變成 ′0′'0' 。
  • 返回使 ss 變成 交替字串 所需的 最少 操作次數。 交替字串 定義為：如果字串中不存在相鄰兩個字元相等的情況，那麼該字串就是交替字串。例如，字串 ′010′'010' 是交替字串，而字串 ′0100′'0100' 不是。

思路：簡單模擬

  • 由於 ss 是二進位字串，因此ss 只有「從 00 開始」或「從 11 開始」兩種可能，模擬交替字串的構建過程，返回這兩種情況中的最小值即可。
  • 時間複雜度 O(n)O(n)
  • 空間複雜度 O(1)O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def minOperations(self, s: str) -> int:
        # return min(sum([(ch == '1') if i % 2 == 0 else (ch == '0') for i, ch in enumerate(s)]), sum([(ch == '0') if i % 2 == 0 else (ch == '1') for i, ch in enumerate(s)]))
        ans1 = ans2 = 0
        for i, ch in enumerate(s):
            if i % 2 == 0:
                if ch == '1':
                    ans1 += 1
                else:
                    ans2 += 1
            else:
                if ch == '0':
                    ans1 += 1
                else:
                    ans2 += 1
        return min(ans1, ans2)

2023-12-25

🟡 1276. Number of Burgers with No Waste of Ingredients 1386

題意

  • 給定兩個整數 tomatoSlicestomatoSlices 和 cheeseSlicescheeseSlices ，表示番茄片和起司片的數量。
  • 製作A漢堡需要 44 片番茄和 11 片起司，製作B漢堡需要 22 片番茄和 11 片起司，返回能夠剩下的番茄片和起司片數量都為 00 的 [A漢堡的數量, B漢堡的數量] ，若無法使剩下的番茄片和起司片數量都為 00 ，則返回 [][] 。

思路：數學

  • 根據題意，可以列出以下兩個方程式：
    • 4x+2y=tomatoSlices4x + 2y = tomatoSlices
    • x+y=cheeseSlicesx + y = cheeseSlices
  • 解方程式，得到：
    • x=(tomatoSlices−2×cheeseSlices)/2x = (tomatoSlices - 2 \times cheeseSlices) / 2
    • y=(4×cheeseSlices−tomatoSlices)/2y = (4 \times cheeseSlices - tomatoSlices) / 2
  • 最後檢查 xx 和 yy 是否為非負整數，若是，則返回 [x,y][x, y] ，否則返回 [][] 。
  • 時間複雜度 O(1)O(1)
  • 空間複雜度 O(1)O(1)
1
2
3
4
5
6
7
class Solution:
    def numOfBurgers(self, tomatoSlices: int, cheeseSlices: int) -> List[int]:
        x = (tomatoSlices - 2 * cheeseSlices) / 2
        y = (4 * cheeseSlices - tomatoSlices) / 2
        if x < 0 or y < 0 or x != int(x) or y != int(y):
            return []
        return [int(x), int(y)]

🟡 91. Decode Ways

題意

  • 給定一個只含數字的 非空 字串 s ，請計算並傳回 解碼 方法的 總數 。
  • 一條包含字母 A-Z 的訊息，透過 A→1,B→2,...,Z→26A \rightarrow 1, B \rightarrow 2, ..., Z \rightarrow 26 的對應關係進行了 編碼。
    • 例如，"BEAN""BEAN" 可以編碼為 "25114""25114" （B→2B \rightarrow 2、E→5E \rightarrow 5、A→1A \rightarrow 1、N→14N \rightarrow 14）。
  • 要 解碼 已編碼的訊息，所有數字必須以上述對應的關係，反向映射回字母（可能有多種方法）。例如，"11106""11106" 可以映射為：
    • "AAJF""AAJF" ，將訊息分組為 (1,1,10,6)(1,1,10,6)
    • "KJF""KJF" ，將訊息分組為 (11,10,6)(11,10,6)
  • 注意，訊息不能分組為  (1,11,06)(1,11,06) ，因為"06""06" 不能映射為"F""F" ，這是由於"6""6" 和"06""06" 在映射中並不等價 。

思路：DP

  • 令 dp[i]dp[i] 表示 s[:i]s[:i] 的解碼方法總數，則 dp[i]dp[i] 可以由以下兩種情況轉移而來：
    • 若 s[i−1]≠0s[i-1] \neq 0 且 s[i−2:i]∈[10,26]s[i-2:i] \in [10, 26] ，則 dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1] + dp[i-2] 。
    • 若 s[i−1]≠0s[i-1] \neq 0 且 s[i−2:i]∉[10,26]s[i-2:i] \notin [10, 26]，則 dp[i]=dp[i−1]dp[i] = dp[i-1] 。因為 s[i−1]≠0s[i-1] \neq 0 ，因此 s[i−1]s[i-1] 可以單獨解碼，且 s[i−1]s[i-1] 不能和 s[i−2]s[i-2] 組合解碼。
    • 剩餘情況，dp[i]=0dp[i] = 0 。
  • 時間複雜度 O(n)O(n)
  • 空間複雜度 O(n)O(n)，可以透過只保留前兩項的狀態優化到 O(1)O(1)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n+1)
        dp[0] = 1
        dp[1] = 1 if s[0] != '0' else 0
        for i in range(2, n+1):
            if s[i-1] != '0':
                dp[i] += dp[i-1]
            if s[i-2] != '0' and int(s[i-2:i]) <= 26:
                dp[i] += dp[i-2] 
        return dp[-1]

2023-12-26

🔴 1349. Maximum Students Taking Exam 2386

沒碰過狀態壓縮DP，本月第4次看題解。看是看懂了但要把思路完整地寫下來還是有點困難，思路待補。

題意

題意待補

思路：狀態壓縮DP + 位運算

思路待補 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        m, n = len(seats), len(seats[0])
        arr = [0] * m # arr[i] 是第 i 排的狀態，即可用椅子的下標集合(二進位)，0 表示可以坐，1 表示不能坐 
        for i, row in enumerate(seats):
            for j, ch in enumerate(row):
                if ch == '.':
                    arr[i] |= 1 << j
        # dfs(i, j) 表示第 i 排坐滿 j 這種狀態的最大人數，總共有 2^n 種狀態
        @cache # Memoization
        def dfs(i: int, j: int) -> int:
            if i == 0:
                lb = j & -j # low bit 最低位的 1，貪心思路，先坐最左邊(最低位)的人
                return dfs(i, j & ~(lb * 3)) + 1 if j else 0 # 由將 lb 和 lb 左邊的位置都設為 0 的狀態轉移，即 j & ~(lb | lb << 1) = j & ~(lb * 3)
            res = dfs(i - 1, arr[i - 1])  # 第 i 排不坐人
            s = j
            while s: # 枚舉 j 的子集 s，即當前這排的可能狀態
                if (s & (s >> 1)) == 0: # 左右相鄰的位置都沒有人，即 沒有連續兩個 1
                    t = arr[i - 1] & ~(s << 1 | s >> 1) # 當前狀態下，前一排可以坐的位置，即當前這排為1的位置的左右兩邊，在前一排都不坐人
                    res = max(res, dfs(i - 1, t) + s.bit_count()) # 狀態轉移，即前一排坐滿 t 這種狀態的最大人數 + 當前這排坐滿 s 這種狀態的人數
                s = (s - 1) & j # 考慮下一個子集
            return res
        return dfs(m-1, arr[-1]) # 第 m-1 排坐滿 arr[-1] 這種狀態的最大人數

參考資料

🟡 1155. Number of Dice Rolls With Target Sum 1654

題意

  • 給定 nn 顆相同的骰子，每個骰子有 kk 面，點數從 11 到 kk 。 求擲出的骰子點數總和為 targettarget 的擲骰子方法總數。
  • 由於答案可能很大，請將答案對 109+710^9 + 7 取模 後返回。

思路：DP

  • 這題可以視為分組背包問題：有 nn 組物品，每組物品都有 kk 個，大小分別為 1,2,...,k1,2,...,k ，求每組恰好選一個物品，組成大小為 targettarget 的方案數。
  • 令 dp[i][j]dp[i][j] 為擲 ii 顆骰子和為 jj 的方法數，在擲第 ii 顆骰子時，令第 ii 顆骰子的點數為 xx ，考慮前 ii 顆骰子和為 jj 的情況：
    • 若 j−x<0j - x < 0 ，則 dp[i][j]=0dp[i][j] = 0 ，因為 jj 不能由 ii 顆骰子構成。
    • 否則，dp[i][j]=Σx=1kdp[i−1][j−x]dp[i][j] = \Sigma_{x=1}^{k} dp[i-1][j-x] ，其中 j−x≥0j-x \geq 0 ，因為第 ii 顆骰子的點數為 xx ，因此 jj 可以由 j−xj-x 和 xx 構成。
  • 時間複雜度 O(n×k×target)O(n \times k \times target)
  • 空間複雜度 O(n×target)O(n \times target)，可以透過滾動陣列優化到 O(target)O(target)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        MOD = 10**9 + 7
        dp = [[0] * (target + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        for j in range(1, min(k, target) + 1): # 初始化一顆骰子的情況
            dp[1][j] = 1
        for i in range(2, n+1): # 骰子數
            for j in range(1, target+1): # 考慮和為j的情況
                for x in range(1, k+1): # 第i個骰子的點數為x
                    if j - x < 0:
                        break
                    dp[i][j] += dp[i-1][j-x] % MOD # 從前 i-1 顆骰子和為 j-x 的情況轉移過來
        return dp[n][target] % MOD

2023-12-27

🟢 2660. Determine the Winner of a Bowling Game 1324

題意

  • 給定一個保齡球比賽的記錄，兩個整數陣列 player1player1 和 player2player2 ，分別表示玩家 1 和玩家 2 每局擊中的瓶數，每局的瓶數為最多為 1010 。
  • 假設玩家在第 ii 局擊中 xix_i 瓶。 玩家第 ii 局的得分為：
    • 若玩家在該局的前兩局的任何一局中擊中了 1010 個瓶子，則為 2×xi2 \times x_i 。
    • 否則，為 xix_i 。
  • 玩家的得分是其 nn 局的總和。若玩家 11 的得分高於玩家 22 的得分，則返回 11 ；若玩家 22 的得分高於玩家 11 的得分，則返回 22 ；如果平局，則返回 00 。

思路：簡單模擬

  • 記錄前兩局是否擊中 1010 個瓶子，簡單模擬即可。
  • 時間複雜度 O(n)O(n)
  • 空間複雜度 O(1)O(1)
1
2
3
4
5
6
7
8
9
10
class Solution:
    def isWinner(self, player1: List[int], player2: List[int]) -> int:
        def f(player: List[int]) -> int:
            res = 0
            pre1 = pre2 = 0
            for x in player:
                res += x * 2 if pre1 or pre2 else x
                pre1, pre2 = pre2, x == 10
            return res
        return 1 if f(player1) > f(player2) else 2 if f(player1) < f(player2) else 0

🟡 1578. Minimum Time to Make Rope Colorful 1574

題意

  • 給定一個下標從 00 開始、長度為 nn 的字串 colorcolor ，其中 color[i]color[i] 表示第 ii 個氣球的顏色；以及一個下標從 00 開始、長度為 nn 的整數陣列 neededTimeneededTime ，其中 neededTime[i]neededTime[i] 表示移除第 ii 個氣球需要的時間。
  • 求移除部分氣球，使得相鄰的氣球顏色不同的最少時間。

思路：貪心 + 分組循環

  • 對於相鄰的 kk 個氣球，若 k>1k > 1，為使相鄰的氣球顏色不同，需要移除 k−1k-1 個氣球，基於貪心的思想，我們應該移除花費最低的 k−1k-1 個氣球，也就是保留花費最大的氣球。
  • 用分組循環的方式，將所有相鄰且顏色相同的氣球視為同一組，每一組中對答案的貢獻為：組內總和 - 組內最大值。可以在分組的過程中同時計算答案。
  • 時間複雜度 O(n)O(n) ，雖然有兩層循環，但每個下標只會被訪問一次。
  • 空間複雜度 O(1)O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        n = len(colors)
        ans = 0
        i = 0
        while i < n: # 分組循環
            st = i
            mx = s = neededTime[i] # 當前組內的總和, 最大值
            while i < n - 1 and colors[i] == colors[i + 1]: # 同一組
                i += 1
                mx = max(mx, neededTime[i]) # 更新組內最大值
                s += neededTime[i] # 組內總和
            if i > st: # 長度 > 1 的組
                ans += (s - mx)
            i += 1
        return ans

2023-12-28

🟡 2735. Collecting Chocolates 2043

題意

  • 給定一個長度為 nn 的整數陣列 numsnums ， nums[i]nums[i] 表示收集第 ii 種巧克力的成本。
  • 除此之外，在一次操作中，可以用 xx 的成本修改 所有 巧克力的類型，將第 ii 種巧克力的類型修改為 (i+1)mod  n(i+1) \mod n 。
  • 假設可以執行任意次操作，計算並返回收集所有類型巧克力所需的最小成本。

思路：分別計算貢獻

  • 對於第 ii 種類型的巧克力，做 00 次操作時其成本為 nums[i]nums[i] ，做 11 次操作時其最小成本為 min(nums[i],nums[(i+1)mod  n])min(nums[i], nums[(i+1) \mod n]) ，做 22 次操作時其最小成本為 min(nums[i],nums[(i+1)mod  n],nums[(i+2)mod  n])min(nums[i], nums[(i+1) \mod n], nums[(i+2) \mod n]) ，以此類推。
  • 令 ans[k]ans[k] 表示操作 k 次時，收集所有巧克力的最小總花費，則第 ii 種類型的巧克力對 ans[k]ans[k] 的貢獻為在操作 kk 次時，收集第 ii 種類型的巧克力的最小花費。此外，操作 kk 次需要花費 x×kx \times k (只計算一次)。
  • 因此得出 ans[k]=x×k+Σi=0n−1min(nums[i],nums[(i+1)mod  n],...,nums[(i+k)mod  n])ans[k] = x \times k + \Sigma_{i=0}^{n-1} min(nums[i], nums[(i+1) \mod n], ..., nums[(i+k) \mod n]) 。
  • 計算時可以枚舉每種巧克力，在依序枚舉操作次數，前一次操作時的最小花費可以用來計算當前操作時的最小花費，即 cost=min(cost,nums[(i+k)mod  n])cost = min(cost, nums[(i+k) \mod n]) 。 將結果累加至 ans[k]ans[k] 的貢獻，最後對 ansans 取最小值即可。
  • 時間複雜度 O(n2)O(n^2) ，總共 nn 種巧克力，每種枚舉1次，每次枚舉時計算 ans[k]ans[k] ， kk 從 00 到 n−1n-1 。
  • 空間複雜度 O(n)O(n)
1
2
3
4
5
6
7
8
9
class Solution:
    def minCost(self, nums: List[int], x: int) -> int:
        n = len(nums)
        ans = [x * i for i in range(n)] # ans[k] 表示操作 k 次時，收集所有巧克力的最小總花費
        for i, cost in enumerate(nums): # 枚舉每種巧克力，計算對操作 k 次的總花費的貢獻
            for k in range(n): # 操作次數
                cost = min(cost, nums[(i+k)%n]) # 第i種巧克力，操作 0~k 次的最小花費
                ans[k] += cost # 對操作 k 次的總花費的貢獻
        return min(ans)

🔴 1531. String Compression II 2576

題意

題意待補

思路：DP

思路待補
  • 將問題轉化成從 nn 個字元中「選擇」 n−kn-k 個字元，使得壓縮後的長度最小
  • dp[i][x]dp[i][x] 表示從第 i 個字元開始，已選擇 x 個字元的最小壓縮長度
  • 可以用 Recursive+記憶化搜索 或 Iterative 的方式實現。由於遞迴函數對同樣的傳入參數計算結果都是相同的，因此可以用 記憶化搜尋 來最佳化：
    • 如果一個傳入參數是第一次遇到，那麼可以在返回前，把狀態及其結果記到一個 memomemo 陣列 或 雜湊表 中
    • 如果再次遞迴到該狀態，那麼直接傳回 memomemo 中儲存的結果
    • Python 可以對函數加上 @cache 裝飾器實現記憶化搜索。
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
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        n = len(s)
        
        def calc(x): # 長度為 x 的相同字母壓縮後的長度
            if x == 1:
                return 1
            res = 0
            while x:
                x //= 10
                res += 1
            return res + 1

        @cache # Memoization
        def dp(i, x): # dp(i, x) 表示從第 i 個字元開始，已選擇 x 個字元的最小壓縮長度
            if x > (n-k): # 如果選擇的字元數量超過了 n-k，則不可行，返回 inf
                return float('inf') 
            if i == n: # 終點，如果正好選擇 n-k 個，則是一個可行解，否則不可行，返回 inf
                return 0 if x == n-k else float('inf')

            res = dp(i+1, x) # 不選第 i 個字元
            cnt = 0 # 計算第 i 個字元後面有多少個相同的字元
            for j in range(i, n):
                if s[i] == s[j]:
                    cnt += 1
                    res = min(res, dp(j+1, x+cnt) + calc(cnt)) # 選擇 cnt 個相同的字元，壓縮後的長度為 calc(cnt)
            return res
        return dp(0, 0)
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
class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        n = len(s)
        
        def calc(x): # 長度為 x 的相同字母壓縮後的長度
            if x == 1:
                return 1
            res = 0
            while x:
                x //= 10
                res += 1
            return res + 1

        # 1:1 翻譯成 recursive
        dp = [[float('inf')]*(n-k+1) for _ in range(n+1)]
        dp[n][n-k] = 0

        for i in range(n-1, -1, -1): # 從第 i 個字元開始，由後往前
            for x in range(n-k+1): # x 表示已選擇的字元數量
                cnt = 0
                dp[i][x] = dp[i+1][x] # 不選第 i 個字元
                for j in range(i, n):
                    if s[i] == s[j]:
                        cnt += 1
                        if x+cnt > n-k: # 如果已選擇的字元數量超過了 n-k，則不可行，跳出循環
                            break
                        dp[i][x] = min(dp[i][x], dp[j+1][x+cnt] + calc(cnt))
        return dp[0][0]

2023-12-29

🟢 2706. Buy Two Chocolates 1208

同 英文站(LCUS) 2023-12-20 的每日一題，直接複製過來，還好我聖誕節不用買巧克力送人。

題意

  • 給定一個整數陣列 pricesprices ，表示若干種巧克力的價格，同時給定一個整數 moneymoney，表示擁有的金錢數量
  • 返回購買兩種巧克力後，最多能剩下多少錢。如果無法購買任兩種巧克力，則返回 moneymoney。

思路：簡單模擬

  • 很顯然購買價格最低的兩種巧克力即可滿足條件，遍歷一遍 pricesprices，找到最小的兩個價格，然後計算剩下的錢即可。
  • 時間複雜度：O(n)O(n)，nn 為 pricesprices 的長度。
  • 空間複雜度：O(1)O(1)。
1
2
3
4
5
6
7
8
9
10
class Solution:
    def buyChoco(self, prices: List[int], money: int) -> int:
        min1 = min2 = float('inf')
        for p in prices:
            if p < min1:
                min2 = min1
                min1 = p
            elif p < min2:
                min2 = p
        return money - (min1 + min2) if money >= min1 + min2 else money

🔴 1335. Minimum Difficulty of a Job Schedule 2035

題意

  • 給定一個長度為 nn 的整數陣列 jobDifficultyjobDifficulty 表示每份工作的難度，以及一個整數 dd 表示需要在 dd 天內完成工作。
  • 制定一份工作計畫表，每天 至少 需要完成一項任務。且工作之間有依賴，要想執行第 ii 項工作，必須先完成全部 jj 項工作（ 0≤j<i0 \leq j < i ）。
  • 工作計畫的總難度是這 dd 天每一天的難度總和，而一天的工作難度是當天應該完成工作的最大難度。
  • 返回整個工作計畫的 最小難度 。如果無法制定工作計畫，則返回 −1-1 。

思路：DP

  • 由於在完成第 ii 項工作前，需要完成前面所有工作，因此任務一定是按照順序完成的，即 0,1,...,n−10, 1, ..., n-1 。
  • 因此可以將 jobDifficultyjobDifficulty 分成 dd 個互斥的子區間，且每個子區間不為空，求每個子區間的最大值，使得這些最大值的和最小。
  • 很明顯的，無法完成工作計畫的情況只有在當 n<dn < d 時才會發生，返回 −1-1 。
  • 令 dp[i][j]dp[i][j] 表示前 ii 天完成 jj 個工作的最小難度，則 dp[i][j]dp[i][j] 可以由以下兩種情況轉移而來：
    • 若 i=1i = 1 ，則 dp[i][j]=max(jobDifficulty[:j])dp[i][j] = max(jobDifficulty[:j]) ，即只有一天，則需要完成任務中的最小難度為這一天的最大難度。
    • 否則，dp[i][j]=min(dp[i−1][k]+max(jobDifficulty[k:j]))dp[i][j] = min(dp[i-1][k] + max(jobDifficulty[k:j])) ，其中 k∈[i−1,j−1]k \in [i-1, j-1] ，即前 i−1i-1 天完成 kk 個工作的最小難度，加上第 ii 天的最大難度。
  • 可以用 Recursive+記憶化搜索 或 Iterative 的方式實現。由於遞迴函數對同樣的傳入參數計算結果都是相同的，因此可以用 記憶化搜尋 來最佳化：
    • 如果一個傳入參數是第一次遇到，那麼可以在返回前，把狀態及其結果記到一個 memomemo 陣列 或 雜湊表 中
    • 如果再次遞迴到該狀態，那麼直接傳回 memomemo 中儲存的結果
    • Python 可以對函數加上 @cache 裝飾器實現記憶化搜索。
  • 時間複雜度 O(n2×d)O(n^2 \times d)
  • 空間複雜度 O(n×d)O(n \times d)，可以透過滾動陣列優化到 O(n)O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1

        @cache # Memoization
        def dp(i, j): # 令 dp(i, j) 表示前i天完成j個工作的最小難度
            if i == 1: # 只有一天，則最小難度為這一天的最大難度
                return max(jobDifficulty[:j])
            mx = jobDifficulty[j-1] # 今日至少要完成 第j個 工作，所以最大難度初始化為 jobDifficulty[j-1]
            res = dp(i-1, j-1) + mx # 今日的最大難度，從 前i-1天完成j-1個工作的最小難度 轉移
            for k in range(j-2, i-2, -1): # 可以從 前i-1天完成k個工作的最小難度 轉移，而前 i-1 天最少要完成 i-1 個工作
                mx = max(mx, jobDifficulty[k]) # 今日任務又多了一個，所以最大難度要更新
                res = min(res, dp(i-1, k) + mx)
            return res
        return dp(d, n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        
        # 1:1 翻譯成 Iterative
        dp = [[float('inf')]*(n+1) for _ in range(d+1)]
        for j in range(1, n+1):
            dp[1][j] = max(jobDifficulty[:j])
        for i in range(2, d+1):
            for j in range(i, n+1):
                mx = jobDifficulty[j-1]
                for k in range(j-1, i-2, -1):
                    mx = max(mx, jobDifficulty[k])
                    dp[i][j] = min(dp[i][j], dp[i-1][k] + mx)
        return dp[d][n]

2023-12-30

🟢 1185. Day of the Week 1382

題意

  • 給定三個整數 yearyear、monthmonth 和 dayday ，分別表示年、月、日，代表一個日期，請你設計一個演算法來判斷它是對應一週中的哪一天。
  • 返回的結果必須為 ["Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"]["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"] 中的一個。

思路：內建函數 / 找基準點 / 蔡勒公式

方法一：內建函數(built-in function)

  • 這題可以用內建函數解決，我是沒想到 LeetCode 的允許的函數庫包含 datetime，所以沒有用內建函數解決。

方法二：找基準點

  • 這題可以找一個基準點，例如 19711971 年 11 月 11 日是星期五，然後計算 yearyear 年 monthmonth 月 dayday 日與基準點的天數差，再對 77 取模即可。
思路待補

方法三：蔡勒公式

1
2
3
4
import datetime
class Solution:
    def dayOfTheWeek(self, day: int, month: int, year: int) -> str:
        return datetime.datetime(year, month, day).strftime("%A")
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    """
        Zeller's Congruence
    """
    def dayOfTheWeek(self, day: int, month: int, year: int) -> str:
        ANS_DICT = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]
        if month <= 2:
            year -= 1
            month += 12
        c = year // 100
        year %= 100
        return ANS_DICT[(year + (year // 4) + (c // 4) - 2 * c +  (13 * (month + 1)) // 5 + day - 1) % 7]

🟢 1897. Redistribute Characters to Make All Strings Equal 1309

題意

  • 給定一個字串陣列 wordswords ，判斷是否可以將所有字串中的字母重新排列，使得所有字串都相等。
  • 如果可以，返回 truetrue ；否則，返回 falsefalse 。

思路：雜湊表統計

  • 統計所有字母出現的次數，如果每個字母出現的次數都是 nn 的倍數，則可以構造出一個合法的答案，否則不行。
  • 時間複雜度 O(m×n)O(m \times n) ， nn 為 wordswords 的長度， mm 為 words[i]words[i] 的長度。
  • 空間複雜度 O(1)O(1) ，因為字母只有 2626 個。
1
2
3
4
5
class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        n = len(words)
        cnt = Counter([ch for word in words for ch in word])
        return all(v % n == 0 for v in cnt.values())

2023-12-31

🟢 1154. Day of the Year 1199

題意

  • 給定一個格式為 YYYY-MM-DD 的日期，求這一天是這一年的第幾天。

思路：前綴和 + 閏年判斷

  • 為了避免每次都要計算閏年，可以先計算出每個月的前綴和，即 S[i]S[i] 表示 11 月到 ii 月的天數總和，則 S[i]−S[i−1]S[i] - S[i-1] 表示第 ii 個月的天數。
  • 令 yy 表示年份， mm 表示月份， dd 表示日期，則答案為 S[m−1]+dS[m-1] + d ，但是需要考慮閏年的情況：
    • 如果 m>2m > 2 且 yy 是閏年，則答案需要加 11 。
    • 當 ymod  4=0∧ymod  100≠0∨ymod  400=0y \mod 4 = 0 \land y \mod 100 \neq 0 \lor y \mod 400 = 0 時，yy 是閏年。
  • 時間複雜度 O(1)O(1)
  • 空間複雜度 O(1)O(1)
1
2
3
4
5
6
7
class Solution:
    DAYS = [31,28,31,30,31,30,31,31,30,31,30,31]
    S = list(accumulate(DAYS, initial=0)) # Prefix sum
    def dayOfYear(self, date: str) -> int:
        y, m, d = map(int, date.split('-'))
        isLeap = (y%4==0 and y%100!=0) or y%400==0 # 閏年
        return self.S[m-1] + d + (m>2 and isLeap)

🟢 1624. Largest Substring Between Two Equal Characters 1282

題意

  • 給定一個字串 ss ，返回字串中兩個相同字元的最長子字串的長度，計算長度時不含這兩個字元。如果不存在這樣的子字串，則回傳 −1-1 。
  • 子字串 是字串中的一個連續字元序列。

思路

  • 其實就是對每個字元 chch ，計算出現的第一個位置 xx 和最後一個位置 yy ，則答案為 y−x−1y - x - 1 。
  • 由於 ss 中只有小寫字母，開一個大小為 26×226 \times 2 的陣列紀錄每個字母的出現位置即可。
  • 時間複雜度 O(n)O(n)
  • 空間複雜度 O(1)O(1)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        ans = -1
        pos = [[-1, -1] for _ in range(26)]
        for i, ch in enumerate(s):
            ch = ord(ch) - ord('a')
            if pos[ch][0] == -1:
                pos[ch][0] = i
            else:
                pos[ch][1] = i
                ans = max(ans, pos[ch][1] - pos[ch][0] - 1)
        return ans

寫在最後

每天寫解題紀錄是比寫題目更困難的事情，因為要把思路寫清楚，而且要寫得好看，這是一件很花時間的事情。但是我還是堅持下來了，之後1月因為要準備考試的關係，就先暫停一個月，等考完試再繼續。