目錄
10.?正則表達(dá)式匹配?Regular Expression Matching????????
11. 盛最多水的容器 Container with most water??????
12. 整數(shù)轉(zhuǎn)羅馬數(shù)字 Integer to Roman??????
???每日一練刷題專欄???
Golang每日一練 專欄
Python每日一練 專欄
C/C++每日一練 專欄
Java每日一練 專欄
10.?正則表達(dá)式匹配?Regular Expression Matching
給你一個(gè)字符串?s?和一個(gè)字符規(guī)律?p，請(qǐng)你來實(shí)現(xiàn)一個(gè)支持?'.'?和?'*'?的正則表達(dá)式匹配。
-
'.'?匹配任意單個(gè)字符 -
'*'?匹配零個(gè)或多個(gè)前面的那一個(gè)元素
所謂匹配，是要涵蓋?整個(gè)?字符串?s的，而不是部分字符串。
示例 1：
輸入：s = "aa", p = "a" 輸出：false 解釋："a" 無法匹配 "aa" 整個(gè)字符串。
示例 2:
輸入：s = "aa", p = "a*" 輸出：true 解釋：因?yàn)?'*' 代表可以匹配零個(gè)或多個(gè)前面的那一個(gè)元素, 在這里前面的元素就是 'a'。因此，字符串 "aa" 可被視為 'a' 重復(fù)了一次。
示例?3：
輸入：s = "ab", p = ".*" 輸出：true 解釋：".*" 表示可匹配零個(gè)或多個(gè)（'*'）任意字符（'.'）。
提示：
1 <= s.length?<= 201 <= p.length?<= 30-
s?只包含從?a-z?的小寫字母。 -
p?只包含從?a-z?的小寫字母，以及字符?.?和?*。 - 保證每次出現(xiàn)字符?
*?時(shí)，前面都匹配到有效的字符
代碼：
package main
import (
"fmt"
)
func isMatch(s string, p string) bool {
sLen, pLen := len(s), len(p)
dp := make([][]bool, sLen+1)
for i := 0; i <= sLen; i++ {
dp[i] = make([]bool, pLen+1)
}
dp[0][0] = true
for i := 0; i <= sLen; i++ {
for j := 1; j <= pLen; j++ {
if p[j-1] == '*' {
dp[i][j] = dp[i][j-2]
if match(s, p, i, j-1) {
dp[i][j] = dp[i][j] || dp[i-1][j]
}
} else {
if match(s, p, i, j) {
dp[i][j] = dp[i-1][j-1]
}
}
}
}
return dp[sLen][pLen]
}
func match(s, p string, i, j int) bool {
if i == 0 {
return false
}
if p[j-1] == '.' {
return true
}
return s[i-1] == p[j-1]
}
func main() {
fmt.Println(isMatch("aa", "a"))
fmt.Println(isMatch("aa", "a*"))
fmt.Println(isMatch("ab", ".*"))
}
輸出：
false
true
true
說明：
動(dòng)態(tài)規(guī)劃，定義一個(gè)二維數(shù)組dp，dp[i][j]表示s的前i個(gè)字符和p的前j個(gè)字符是否匹配。
11. 盛最多水的容器 Container with most water
給定一個(gè)長度為?n?的整數(shù)數(shù)組?height?。有?n?條垂線，第?i?條線的兩個(gè)端點(diǎn)是?(i, 0)?和?(i, height[i])?。
找出其中的兩條線，使得它們與?x?軸共同構(gòu)成的容器可以容納最多的水。
返回容器可以儲(chǔ)存的最大水量。
說明：你不能傾斜容器。
示例 1：
輸入：[1,8,6,2,5,4,8,3,7] 輸出：49 解釋：圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為?49。
示例 2：
輸入：height = [1,1] 輸出：1
提示：
n == height.length2 <= n <= 10^50 <= height[i] <= 10^4
代碼：
package main
import (
"fmt"
)
func maxArea(height []int) int {
max, start, end := 0, 0, len(height)-1
for start < end {
width := end - start
high := 0
if height[start] < height[end] {
high = height[start]
start++
} else {
high = height[end]
end--
}
temp := width * high
if temp > max {
max = temp
}
}
return max
}
func main() {
fmt.Println(maxArea([]int{1, 8, 6, 2, 5, 4, 8, 3, 7}))
fmt.Println(maxArea([]int{1, 1}))
}
輸出：
49
1
說明：
雙指針，定義兩個(gè)指針 start 和 end，分別指向數(shù)組的頭和尾。初始時(shí)，它們之間的距離就是數(shù)組的長度。然后，以較小的高度為準(zhǔn)，計(jì)算兩個(gè)指針圍成的面積，并更新最大面積。接著，將較小高度的指針向中間移動(dòng)。
12. 整數(shù)轉(zhuǎn)羅馬數(shù)字 Integer to Roman?
羅馬數(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?，即為兩個(gè)并列的 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。這個(gè)特殊的規(guī)則只適用于以下六種情況：
-
I?可以放在?V?(5) 和?X?(10) 的左邊，來表示 4 和 9。 -
X?可以放在?L?(50) 和?C?(100) 的左邊，來表示 40 和?90。? -
C?可以放在?D?(500) 和?M?(1000) 的左邊，來表示?400 和?900。
給你一個(gè)整數(shù)，將其轉(zhuǎn)為羅馬數(shù)字。
示例?1:
輸入:?num = 3 輸出: "III"
示例?2:
輸入:?num = 4 輸出: "IV"
示例?3:
輸入:?num = 9 輸出: "IX"
示例?4:
輸入:?num = 58 輸出: "LVIII" 解釋: L = 50, V = 5, III = 3.
示例?5:
輸入:?num = 1994 輸出: "MCMXCIV" 解釋: M = 1000, CM = 900, XC = 90, IV = 4.
提示：
1 <= num <= 3999
代碼：
package main
import (
"fmt"
)
func intToRoman(num int) string {
values := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
symbols := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
var roman string
for i := 0; i < len(values); i++ {
for values[i] <= num {
num -= values[i]
roman += symbols[i]
}
}
return roman
}
func main() {
fmt.Println(intToRoman(9))
fmt.Println(intToRoman(58))
fmt.Println(intToRoman(1994))
}輸出：
IX
LVIII
MCMXCIV
???每日一練刷題專欄???
??持續(xù)，努力奮斗做強(qiáng)刷題搬運(yùn)工！
???點(diǎn)贊，你的認(rèn)可是我堅(jiān)持的動(dòng)力！?
???收藏，你的青睞是我努力的方向！?文章來源：http://www.zghlxwxcb.cn/news/detail-402429.html
??評(píng)論，你的意見是我進(jìn)步的財(cái)富！??文章來源地址http://www.zghlxwxcb.cn/news/detail-402429.html
 |
Golang每日一練 專欄 |
 ? |
Python每日一練 專欄 |
 ? |
C/C++每日一練 專欄 |
 ? |
Java每日一練 專欄 |
到了這里，關(guān)于Golang每日一練(leetDay0004)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
