目錄

13. 羅馬數(shù)字轉(zhuǎn)整數(shù) Roman to Integer? ★

14. 最長公共前綴 Longest Common Prefix??★

15. 三數(shù)之和 3Sum??★★★

🌟?每日一練刷題專欄?🌟

Golang每日一練 專欄

Python每日一練 專欄

C/C++每日一練 專欄

Java每日一練 專欄

---

13. 羅馬數(shù)字轉(zhuǎn)整數(shù) Roman to Integer

羅馬數(shù)字包含以下七種字符:?I，?V，?X，?L，C，D?和?M。

字符          數(shù)值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 羅馬數(shù)字?2?寫做?II?，即為兩個并列的 1 。12?寫做?XII?，即為?X?+?II?。?27?寫做??XXVII, 即為?XX?+?V?+?II?。

通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。但也存在特例，例如 4 不寫做?IIII，而是?IV。數(shù)字 1 在數(shù)字 5 的左邊，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 。同樣地，數(shù)字 9 表示為?IX。這個特殊的規(guī)則只適用于以下六種情況：

• I?可以放在?V?(5) 和?X?(10) 的左邊，來表示 4 和 9。
• X?可以放在?L?(50) 和?C?(100) 的左邊，來表示 40 和?90。?
• C?可以放在?D?(500) 和?M?(1000) 的左邊，來表示?400 和?900。

給定一個羅馬數(shù)字，將其轉(zhuǎn)換成整數(shù)。

示例?1:

輸入:?s = "III"
輸出: 3

示例?2:

輸入:?s = "IV"
輸出: 4

示例?3:

輸入:?s = "IX"
輸出: 9

示例?4:

輸入:?s = "LVIII"
輸出: 58
解釋: L = 50, V= 5, III = 3.

示例?5:

輸入:?s = "MCMXCIV"
輸出: 1994
解釋: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

• 1 <= s.length <= 15
• s?僅含字符?('I', 'V', 'X', 'L', 'C', 'D', 'M')
• 題目數(shù)據(jù)保證?s?是一個有效的羅馬數(shù)字，且表示整數(shù)在范圍?[1, 3999]?內(nèi)
• 題目所給測試用例皆符合羅馬數(shù)字書寫規(guī)則，不會出現(xiàn)跨位等情況。
• IL 和 IM 這樣的例子并不符合題目要求，49 應該寫作 XLIX，999 應該寫作 CMXCIX 。
• 關于羅馬數(shù)字的詳盡書寫規(guī)則，可以參考 羅馬數(shù)字(鏈接略)?。?

代碼：

package mainimport ("fmt"
)var roman = map[string]int{"I": 1,"V": 5,"X": 10,"L": 50,"C": 100,"D": 500,"M": 1000}func romanToInt(s string) int {if s == "" {return 0}num, lastint, total := 0, 0, 0for i := 0; i < len(s); i++ {char := s[len(s)-(i+1) : len(s)-i]num = roman[char]if num < lastint {total = total - num} else {total = total + num}lastint = num}return total
}func main() {fmt.Println(romanToInt("IX"))fmt.Println(romanToInt("LVIII"))fmt.Println(romanToInt("MCMXCIV"))}

輸出：

9
58
1994

---

14. 最長公共前綴 Longest Common Prefix

編寫一個函數(shù)來查找字符串數(shù)組中的最長公共前綴。

如果不存在公共前綴，返回空字符串?""。

示例 1：

輸入：strs = ["flower","flow","flight"]
輸出："fl"

示例 2：

輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i]?僅由小寫英文字母組成

代碼：

package mainimport ("fmt""strings"
)func longestCommonPrefix(strs []string) string {if len(strs) == 0 {return ""}prefix := strs[0]for i := 1; i < len(strs); i++ {for !strings.HasPrefix(strs[i], prefix) {prefix = prefix[:len(prefix)-1]if prefix == "" {return ""}}}return prefix
}func main() {fmt.Println(longestCommonPrefix([]string{"flower", "flow", "flight"}))fmt.Println(longestCommonPrefix([]string{"dog", "racecar", "car"}))}

輸出：

fl

說明：

將第一個字符串作為公共前綴的初始值，從第二個字符串開始依次與公共前綴進行比較。
如果當前字符串不是以公共前綴開頭，則將公共前綴縮短一個字符，繼續(xù)比較。
如果公共前綴已經(jīng)為空，則說明不存在公共前綴，返回空字符串。

---

15. 三數(shù)之和 3Sum

給你一個包含?n?個整數(shù)的數(shù)組?nums，判斷?nums?中是否存在三個元素?a,b,c，使得?a + b + c =?0？請你找出所有和為?0?且不重復的三元組。

注意：答案中不可以包含重復的三元組。

示例 1：

輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]

示例 2：

輸入：nums = []
輸出：[]

示例 3：

輸入：nums = [0]
輸出：[]

提示：

• 0 <= nums.length <= 3000
• -10^5?<= nums[i] <= 10^5

代碼1：

package mainimport ("fmt""sort"
)func threeSum(nums []int) [][]int {sort.Ints(nums) // 先將數(shù)組排序res := [][]int{}for i := 0; i < len(nums)-2; i++ {if i > 0 && nums[i] == nums[i-1] { // 跳過重復的元素continue}l, r := i+1, len(nums)-1 // 雙指針for l < r {sum := nums[i] + nums[l] + nums[r]if sum == 0 {res = append(res, []int{nums[i], nums[l], nums[r]})for l < r && nums[l] == nums[l+1] { // 跳過重復的元素l++}for l < r && nums[r] == nums[r-1] { // 跳過重復的元素r--}l++r--} else if sum < 0 {l++} else {r--}}}return res
}func main() {fmt.Println(threeSum([]int{-1, 0, 1, 2, -1, -4}))fmt.Println(threeSum([]int{}))fmt.Println(threeSum([]int{0}))}

代碼2：?

package mainimport ("fmt""sort"
)func threeSum(nums []int) [][]int {sort.Ints(nums) // 先將數(shù)組排序n := len(nums)res := [][]int{}for i := 0; i < n; i++ {if i > 0 && nums[i] == nums[i-1] { // 去重continue}k := n - 1target := -nums[i]for j := i + 1; j < n; j++ {if j > i+1 && nums[j] == nums[j-1] { // 去重continue}for j < k && nums[j]+nums[k] > target { // 雙指針k--}if j == k {break}if nums[j]+nums[k] == target {res = append(res, []int{nums[i], nums[j], nums[k]})}}}return res
}func main() {nums := []int{-1, 0, 1, 2, -1, -4}fmt.Println(threeSum(nums))fmt.Println(threeSum([]int{}))fmt.Println(threeSum([]int{0}))}

輸出：

[[-1 -1 2] [-1 0 1]]
[]
[]

---

🌟?每日一練刷題專欄?🌟

??持續(xù)，努力奮斗做強刷題搬運工！

👍?點贊，你的認可是我堅持的動力！?

🌟?收藏，你的青睞是我努力的方向！?

??評論，你的意見是我進步的財富！??

	Golang每日一練 專欄
	Python每日一練 專欄
	C/C++每日一練 專欄
	Java每日一練 專欄