主題

[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