【Q13】

Roman numerals are represented by seven different symbols:?I,?V,?X,?L,?C,?D?and?M.

Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000

For example,?two is written as?II?in Roman numeral, just two one's added together. Twelve is written as,?XII, which is simply?X?+?II. The number twenty seven is written as?XXVII, which is?XX?+?V?+?II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not?IIII. Instead, the number four is written as?IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as?IX. There are six instances where subtraction is used:

• I?can be placed before?V?(5) and?X?(10) to make 4 and 9.?
• X?can be placed before?L?(50) and?C?(100) to make 40 and 90.?
• C?can be placed before?D?(500) and?M?(1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input:?"III" Output: 3

Example 2:

Input:?"IV" Output: 4

Example 3:

Input:?"IX" Output: 9

Example 4:

Input:?"LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3.

Example 5:

Input:?"MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

解法：從高位至低位倒序遍歷，遇到遇到I/X/C時判斷此時數值，若此時數值大于5/50/500，則對數值依次減去1/10/100,其余情況下加上對應數字即可。
class Solution:def romanToInt(self, s):""":type s: str:rtype: int"""op = 0for x in reversed(s):if x=='I':op += 1 if op<5 else -1elif x=='V':op += 5elif x=='X':op += 10 if op<50 else -10elif x=='L':op += 50elif x=='C':op += 100 if op<500 else -100elif x=='D':op += 500else:op += 1000return op

?

【Q14】

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string?"".

Example 1:

Input: ["flower","flow","flight"] Output: "fl"

Example 2:

Input: ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters?a-z.

?

解法：先找到最短的字符串，以此為基準。遍歷整個字符串數組，取每個單詞依次與該最短字符串比較。

class Solution:def longestCommonPrefix(self, strs):""":type strs: List[str]:rtype: str"""if len(strs)==0:return ""shortestStr = min(strs,key=len) # find shortest string in the listfor i in range(len(shortestStr)):for s in strs:if s[i]!=shortestStr[i]:return shortestStr[:i]return shortestStr

?

【Q15】

Given an array?nums?of?n?integers, are there elements?a,?b,?c?in?nums?such that?a?+?b?+?c?= 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],A solution set is: [[-1, 0, 1],[-1, -1, 2] ] 解法：先固定一個數A，則任務變成尋找數組里的另外兩個數，使得這兩個數的和Target=0-A，此時問題變成2Sum問題。需要注意的是可能存在數組內有重復元素的問題，此時可通過while語句直接跳過重復元素。
class Solution:def threeSum(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""nums.sort()N = len(nums)result = []for k in range(N):if k>0 and nums[k]==nums[k-1]:continuetarget = 0-nums[k]i,j = k+1,N-1while i<j:if nums[i]+nums[j]==target:result.append([nums[k],nums[i],nums[j]])i += 1j -= 1while i<j and nums[i]==nums[i-1]:i += 1elif nums[i]+nums[j]<target:i += 1else:j -= 1return result

?

?

轉載于:https://www.cnblogs.com/YunyiGuang/p/10351374.html

總結

以上是生活随笔為你收集整理的【LeetCode算法题库】Day5：Roman to Integer Longest Common Prefix 3Sum的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。