ETH官方钱包

前往
大廳
主題

[LeetCode] 1. TwoSum、13.RomanToIntegar、14.LongestCommonPrefix

テリ君(桃夫模式) | 2023-03-28 16:40:15 | 巴幣 4 | 人氣 238

快一個月沒更新,主要是最近在做網頁作業
另外就是有很多新東西在接觸
最近想要好好裝pytorch先來實作跑資料看看
還有我可能會開始做一些小case
希望可以多累積經驗和賺點小補貼
1.TwoSum
恩很簡單就不多說了
3629 ms (31.25%) / 14.8MB (90.79%)
class Solution:
    def twoSum(self, nums, target):
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return i, j
13. RomanToIntegar
這題其實有很多做法
我一開始是用超:土法煉鋼法
當然超沒效率
56 ms (28.60%) / 13.9MB (19.35%)
class Solution:
    def romanToInt(self, str):
        sum = 0
        temp = str + " "
        for s in range(len(str)):
            if s == len(str) - 1:
                if temp[s] == "I":
                    sum += 1                    
            if s < len(str) - 1:
                if temp[s] == "I" and temp[s + 1] not in ("V", "X"):
                    sum += 1                
            if s >= 1:
                if temp[s] == "X" and temp[s + 1] not in ("L", "C"):
                    if temp[s - 1] == "I":
                        sum += 9                        
                    else:
                        sum += 10                        
                elif temp[s] == "V":
                    if temp[s - 1] == "I":
                        sum += 4                        
                    else:
                        sum += 5                        
                elif temp[s] == "L":
                    if temp[s - 1] == "X":
                        sum += 40                        
                    else:
                        sum += 50                        
                elif temp[s] == "C" and temp[s + 1] not in ("D", "M"):
                    if temp[s - 1] == "X":
                        sum += 90                        
                    else:
                        sum += 100                        
                elif temp[s] == "D":
                    if temp[s - 1] == "C":
                        sum += 400                        
                    else:
                        sum += 500                        
                elif temp[s] == "M":
                    if temp[s - 1] == "C":
                        sum += 900                        
                    else:
                        sum += 1000                        
            else:
                if temp[s] == "X" and temp[s + 1] not in ("L", "C"):
                    sum += 10                    
                elif temp[s] == "V":
                    sum += 5                    
                elif temp[s] == "L" :
                    sum += 50                    
                elif temp[s] == "C" and temp[s + 1] not in ("D", "M"):                    
                    sum += 100                    
                elif temp[s] == "D":                    
                    sum += 500                    
                elif temp[s] == "M":                    
                    sum += 1000                    
                
        return sum

所以就需要想另一個方法
我們如果到著看羅馬數字的話
會發現其實像CM XC 之類的狀況,都是前者小於後者
因此其他狀況都不會有例外
那這樣就可以直接判斷任一區段的數字是否要加減
就不用像土法煉鋼還要看前後和位置
所以就有下面解
range(len(s) - 1, -1, -1)
是指從len(s) - 1 ~ -1 慢慢倒退使得 s[i] 是從後面數過來
51 ms (53.36%) / 13.9MB (63.3%)
class Solution:
    def romanToInt(self, s):
        romans = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        res = 0
        prev = 0
        for i in range(len(s) - 1, -1, -1):
            temp = romans[s[i]]
            if temp < prev:
                res -= temp
            else:
                res += temp

            prev = temp
        
        return res

14. LongestCommonPrefix
待補,等等上課的時候再來做ㄅ
18 ms (77.91%) / 13.6MB (66.39%)
class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        strs.sort()

        first_str = strs[0]
        last_str = strs[-1]
        
        for i, char in enumerate(first_str): #["a","b","c"] -> [(0, "a"), (1, "b"), (2, "c")]
            if char != last_str[i]:
                return first_str[:i]

        return first_str
    

創作回應

Router
加油 我最近也一天一題解每日任務
2023-03-28 16:58:17
テリ君(桃夫模式)
感謝 努力成為初階碼農
2023-03-28 21:26:33

更多創作