因為昨天leetcode深夜時突然不能使用，就先暫時跳過一天，然後今天一起
但老實說，目前寫下來，我會覺得所有題目我會想過一陣子後再思考一次。
大概有4,5成題目都需要參考別人的寫法，也就是說不再重新思考一次就不會是自己的東西。
不得不說dynamic progrmaing對現在的我來說有點噁心，也有點想抱怨大學教授根本沒教這東西(雖然我也不是本科系就是了XD這樣子好像對教授不公平)

話說這幾天的easy題目都被我跳過了，那真的只是刷爽感的，暫時想先把腦力花在比較挫折的部分

139. Word Break (medium)
     https://leetcode.com/problems/word-break/description/
     Submission：https://leetcode.com/problems/word-break/submissions/860842176/
     Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.
檢查wordDict裡的單字是否可以組成s，單看題目很簡單，但思考方向一旦反了就掛點了。

一開始是先用這樣的寫法，思考可能沒錯，但最後幾組資料TLE。

class Solution:
    #第一眼看的時候想說有什麼難的，直接迭代wordList 用 in 檢查不就好了。
    #如果那樣做就中陷阱了，因為有可能wordList全都在，但還是有部分s不在
    #或者wordList真的有s全部內容，但實際上是組不成的
    #Example3示範得很清楚

    #TLE，不能夠這樣寫
    def wordBreak(self, s: str, wordList: List[str]) -> bool:
        temp1 = set("".join(wordList))
        temp2 = set(s)
        for i in temp2:
            if i not in temp1:
                return 0
        for i in temp1:
            if i not in temp2:
                return 0
        left,right = 0,1
        rec = []
        while right <= len(s) or rec:
            while right <= len(s):
                temp = s[left:right]
                if temp in wordList:
                    if right == len(s):
                        return 1
                    rec.append((left,right))
                    left = right
                    right = left + 1
                else:
                    right += 1
            if rec:
                left,right = rec.pop()
                right += 1
        return 0

後來參考別人的寫法

class Solution:
    def wordBreak(self, s: str, wordList: List[str]) -> bool:
        sL = len(s)
        dp = [0]*sL#用來記錄哪個位置可以變成接點
        for i in range(sL):
            for j in wordList:
            #用wordList裡面的word進行檢查就可以不用跟上個方法一樣，一個字母一個字母跑，跟智障一樣
                start = i - len(j) + 1
                if j == s[start:i+1] and (dp[start-1] == 1 or start == 0):
                    dp[i] = 1
        print(dp)
        return dp[-1]

42. Trapping Rain Water (Hard) (真的難得寫hard的題目)

https://leetcode.com/problems/trapping-rain-water/description/
Submission：https://leetcode.com/problems/trapping-rain-water/submissions/860859490/

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
會有很多座山(?
要檢查山與山之間可以蓄多少水。

我個人覺得這題hard比很多題好想....
反正就是爬斜坡就好了。

一開始的寫法，行數比較多了一些，因為我沒有把從左至右跟從右至左的斜坡合在一起寫。

class Solution:
    # hard的題目阿
    # 我直接把我不會勾上了，幾乎沒寫過，若會寫的話，那我就真的會寫了
    # 計算能裝多少水
    # 要怎麼找到邊界呢？
    # 找到邊界要怎麼計算容積？

    # 大小大 -> 山谷
    # 小中大 -> 斜坡
    # 大中小 -> 斜坡
    # 小大小 -> 山峰
    # 但實際上都是由斜坡組成
    # 所以我就做兩遍算斜坡的行為即可
    # 比我想像中簡單，但也卡很久==
    def trap(self, height: List[int]) -> int:
        #先把不可能的去掉
        if len(height) <= 2:
            return 0
        left = 0
        leftMax = height[0]
        ans = 0
        tempRangeHeight = 0
        for i in range(1,len(height)):#左斜坡，只找比他高的
            if height[i] >= height[left]:
                ans += (leftMax)*(i-left-1) - tempRangeHeight
                tempRangeHeight = 0
                leftMax = height[i]
                left = i
            else:
                tempRangeHeight += height[i]
        right = -1
        rightMax = height[-1]
        tempRangeHeight = 0
        for i in range(-2,-len(height)-1,-1):#右斜坡，只找比他高的
            if height[i] > height[right]:
                ans += (rightMax)*(right-i-1) - tempRangeHeight
                tempRangeHeight = 0
                rightMax = height[i]
                right = i
            else:
                tempRangeHeight += height[i]
        return ans

簡化後

class Solution:
    def trap(self, height: List[int]) -> int:
        hL = len(height)
        if hL <= 2:
            return 0
        left,right = 0,-1
        leftMax,rightMax = height[0],height[-1]
        ans = 0
        tempRangeHeightLeft,tempRangeHeightRight = 0,0
        for i in range(1,hL):
            if height[i] >= height[left]:
                ans += (leftMax)*(i-left-1) - tempRangeHeightLeft
                tempRangeHeightLeft = 0
                leftMax = height[i]
                left = i
            else:
                tempRangeHeightLeft += height[i]
            if height[-i-1] > height[right]:
                ans += (rightMax)*(right-(-i-1)-1) - tempRangeHeightRight
                tempRangeHeightRight = 0
                rightMax = height[-i-1]
                right = -i-1
            else:
                tempRangeHeightRight += height[-i-1]
        return ans

但還有一個別人的寫法，我暫時看不太明白，找天要好好地思考。

2500. Delete Greatest Value in Each Row (easy)
      https://leetcode.com/problems/delete-greatest-value-in-each-row/description/
      Submission：https://leetcode.com/problems/delete-greatest-value-in-each-row/submissions/860860495/
      You are given an m x n matrix grid consisting of positive integers.

Perform the following operation until grid becomes empty:

Delete the element with the greatest value from each row. If multiple such elements exist, delete any of them.
Add the maximum of deleted elements to the answer.
Note that the number of columns decreases by one after each operation.

Return the answer after performing the operations described above.

class Solution:
    #每一次動作刪除每一列裡面最大的數字
    #刪除的同時，把最大的數字加到ans裡
    #當每一列都保留最小值時，回傳ans
    def deleteGreatestValue(self, grid: List[List[int]]) -> int:
        for i in range(len(grid)):
            grid[i] = sorted(grid[i])
        newGrid = zip(*grid)
        ans = 0
        for i in newGrid:
            ans += max(i)
        return ans

2496. Maximum Value of a String in an Array (easy)

https://leetcode.com/problems/maximum-value-of-a-string-in-an-array/description/
Submission：https://leetcode.com/problems/maximum-value-of-a-string-in-an-array/submissions/860861961/
The value of an alphanumeric string can be defined as:

The numeric representation of the string in base 10, if it comprises of digits only.
The length of the string, otherwise.
Given an array strs of alphanumeric strings, return the maximum value of any string in strs.

class Solution:
    #找出strs裡的最大值
    #值的定義有兩種
    #若strs[i]只含數字那他就是只能取用數字
    #有含字母它就是文字
    #1. strs[i]裡的數字
    #2. strs[i]的長度
    def maximumValue(self, strs: List[str]) -> int:
        maxNum = 0
        for i in strs:
            temp = 0
            if i.isnumeric():
                temp = max(temp,int(i))
            else:
                temp = max(temp,len(i))    
            maxNum = max(temp,maxNum)
        return maxNum

413. Arithmetic Slices (medium)

https://leetcode.com/problems/arithmetic-slices/description/
Submission：https://leetcode.com/problems/arithmetic-slices/submissions/861493060/

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.
Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.
這題是要查說有多少個子數列可以形成等差數列

這是我一開始的寫法，有點硬來

class Solution:
    #arithmetic ：等差
    #至少三個元素
    #找出num底下所有的等差數列
    #去掉絕對不行的
    #因為是找subarray不需要排序，且需要黏在一起
    #是否要找出「差」
    
    #這樣寫會有問題，會抓到重複的東西，所以扣掉重複的即可
    #若加個dp，紀錄會重複呢？不需要
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        nL = len(nums)
        if nL < 3: return 0
        collect = []
        for i in range(nL-2):
            temp = 1
            d = nums[i+1] - nums[i]
            temp += 1
            while i+2 < nL and nums[i+1] + d == nums[i+2]:
                i += 1
                temp += 1
            collect.append(temp)
        # print(collect)
        ans = 0
        for i in collect:
            ans += (1+i-2)*(i-2)//2 #計算有幾組
            if i > 3: #扣掉重複的
                ans -= (1+i-3)*(i-3)//2
        return ans

後來參考別人的寫法才茅塞頓開

#別人寫的Bottom up DP
#老實說都知道這邊是dp了，這邊應該要這樣寫，我上面的寫法比較像是貪婪
#假設 1 2 3 4 5
#1 2 3 -> 1
#1 2 3 4 -> 1 (1 2 3 4) + 2 (1 2 3, 2 3 4)
#1 2 3 4 5 -> 1 (1 2 3 4 5) + 2 (1 2 3 4, 2 3 4 5) + 3(1 2 3, 2 3 4,3 4 5)
#幹，看了別人寫法一想就懂，難道我就沒有思考dp的天份?
class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        ans = 0
        for i in range(2, n):
            if nums[i-1] - nums[i-2] == nums[i] - nums[i-1]:
                dp[i] = dp[i-1] + 1
            ans += dp[i]
        return ans

91. Decode Ways (medium)

https://leetcode.com/problems/decode-ways/description/
Submission：https://leetcode.com/problems/decode-ways/submissions/861530899/

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

這題我必須說，包裝得很好，寫到後來才發現是爬樓梯

一開始的寫法TLE

class Solution:
    # 會給一組數字
    # 要檢查可以從這組數字映射出多少組英文字

    # tree? backtrack?
    # 0要注意，基本上遇到0就是直接把她跟前個數字擺一組
    # TLE
    def numDecodings(self, s: str) -> int:
        #反正在思考中，先寫一下可能會用到的東西
        alphaN = ['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']
        def run(s,n):
            if (len(s) == 1 and n == 1 or len(s) == 2 and n == 2) and s in alphaN:
                return 1
            elif len(s) == 1 and n == 2:
                return 0
            if s[:n] in alphaN:
                return 1*(run(s[n:],1) + run(s[n:],2))
            else:
                return 0
        return run(s,1) + run(s,2)

後來改善的版本

#改善版本
#後來發現，其實這就是走樓梯而已，一個精巧的包裝
class Solution:
    def numDecodings(self, s: str) -> int:
        alphaN = ['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']
        dp = [0]*(len(s)+1)
        dp[0] = 1
        if s[0] in alphaN: # 如果不在的話就是"0"，必為"X0"
            dp[1] = 1 
        for i in range(2,len(s)+1):
            if s[i-1:i] in alphaN:
                dp[i] += dp[i-1]
            if s[i-2:i] in alphaN:
                dp[i] += dp[i-2]
        # print(dp)
        return dp[-1]

以上為兩天的練習，感謝大家