學習使用工具
劍指Offer http://itmyhome.com/sword-means-offer/sword-means-offer.pdf
LeetCode的劍指Offer題庫 https://leetcode.cn/problemset/all/
劍指 Offer 17. 打印從1到最大的n位數(shù)
輸入數(shù)字 n蛛蒙，按順序打印出從 1 到最大的 n 位十進制數(shù)责循。比如輸入 3贷帮，則打印出 1氨鹏、2、3 一直到最大的 3 位數(shù) 999反镇。
示例 1:
輸入: n = 1
輸出: [1,2,3,4,5,6,7,8,9]
說明：
- 用返回一個整數(shù)列表來代替打印
- n 為正整數(shù)
解法：
啊這題竟然不考大數(shù)問題屑柔？很驚詫买乃，秒了。
def printNumbers(self, n: int) -> List[int]:
max = 0
for i in range(n):
max *= 10
max += 9
return list(range(1, max + 1))
翻了下原書蝙搔，確實是要考大數(shù)問題的缕溉，這里記錄一下。原書問題如下：
題目：輸入數(shù)字n吃型，按順序打印出從1最大的n位十進制數(shù)证鸥。比如輸入3，則打印出1勤晚、2枉层、3一直到最大的3位數(shù)即999。
這里的實際思路應當使用字符串去模擬數(shù)字進行打印而規(guī)避發(fā)生大數(shù)溢出的問題赐写。原書提供的全排列思路：
如果我們在數(shù)字前面補0的話鸟蜡，就會發(fā)現(xiàn)n位所有十進制數(shù)其實就是n個從0到9的全排列。也就是說挺邀，我們把數(shù)字的每一位都從0到9排列一遍揉忘，就得到了所有的十進制數(shù)。只是我們在打印的時候端铛，數(shù)字排在前面的0我們不打印出來罷了泣矛。
全排列用遞歸很容易表達，數(shù)字的每1位都可能是0~9中的一個數(shù)禾蚕，然后設(shè)置下一位您朽。遞歸結(jié)束的條件是我們已經(jīng)設(shè)置了數(shù)字的最后1位。
代碼實現(xiàn)（使用C/C++）：
void Print1ToMaxOfNDigits(int n){
if(n <= 0)
return;
char* number = new char[n + 1] ;
number[n] = '\0';
for(int i=0;i<10;++i)
number[0] = i + '0';
Print1ToMaxOfNDigitsRecursively (number, n, 0) ;
delete[] number;
}
void Print1ToMaxOfNDigitsRecursively (char* number, int length, int index){
if(index == length 一1)
PrintNumber (number) ;
return;
}
for(int i=0;i<10;++i)
number [index + 1] = i + '0';
Print1ToMaxOfNDigitsRecursively(number, length, index + 1) ;
}
}
劍指 Offer 18. 刪除鏈表的節(jié)點
給定單向鏈表的頭指針和一個要刪除的節(jié)點的值换淆，定義一個函數(shù)刪除該節(jié)點虚倒。返回刪除后的鏈表的頭節(jié)點。
注意：此題對比原題有改動
示例 1:
輸入: head = [4,5,1,9], val = 5
輸出: [4,1,9]
解釋: 給定你鏈表中值為 5 的第二個節(jié)點产舞，那么在調(diào)用了你的函數(shù)之后，該鏈表應變?yōu)?4 -> 1 -> 9.
示例 2:
輸入: head = [4,5,1,9], val = 1
輸出: [4,5,9]
解釋: 給定你鏈表中值為 1 的第三個節(jié)點菠剩，那么在調(diào)用了你的函數(shù)之后易猫，該鏈表應變?yōu)?4 -> 5 -> 9.
說明：
題目保證鏈表中節(jié)點的值互不相同
若使用 C 或 C++ 語言拦惋，你不需要
free或delete被刪除的節(jié)點
解法：
比較簡單，先判空溯壶，如果頭結(jié)點就是要刪除的節(jié)點則直接返回頭節(jié)點的下一個節(jié)點即可凉馆。如果不是就搜索，刪除特定節(jié)點后返回初始頭結(jié)點攘已。
def deleteNode(self, head: ListNode, val: int) -> ListNode:
if not head:
return None
if head.val == val:
return head.next
else:
temp = head
while(temp.next):
if not temp.next.val == val:
temp = temp.next
else:
temp.next = temp.next.next
break
return head
這里再翻一下原書：
題目:給定單向鏈表的頭指針和一個結(jié)點指針炮赦，定義一個函數(shù)在0(1)時間刪除該結(jié)點。
這也是一個很簡單的題样勃，只要將節(jié)點的next節(jié)點覆蓋此節(jié)點即可吠勘，不再贅述。
劍指 Offer 19. 正則表達式匹配
請實現(xiàn)一個函數(shù)用來匹配包含'. '和'*'的正則表達式峡眶。模式中的字符'.'表示任意一個字符剧防，而'*'表示它前面的字符可以出現(xiàn)任意次（含0次）。在本題中辫樱，匹配是指字符串的所有字符匹配整個模式峭拘。例如，字符串"aaa"與模式"a.a"和"ab*ac*a"匹配狮暑，但與"aa.a"和"ab*a"均不匹配鸡挠。
示例 1:
輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個字符串。
示例 2:
輸入:
s = "aa"
p = "a*"
輸出: true
解釋: 因為 '*' 代表可以匹配零個或多個前面的那一個元素, 在這里前面的元素就是 'a'搬男。因此拣展，字符串 "aa" 可被視為 'a' 重復了一次。
示例 3:
輸入:
s = "ab"
p = ".*"
輸出: true
解釋: ".*" 表示可匹配零個或多個（'*'）任意字符（'.'）止后。
示例 4:
輸入:
s = "aab"
p = "c*a*b"
輸出: true
解釋: 因為 '*' 表示零個或多個瞎惫，這里 'c' 為 0 個, 'a' 被重復一次。因此可以匹配字符串 "aab"译株。
示例 5:
輸入:
s = "mississippi"
p = "mis*is*p*."
輸出: false
-
s可能為空瓜喇，且只包含從a-z的小寫字母。 -
p可能為空歉糜，且只包含從a-z的小寫字母以及字符.和*乘寒，無連續(xù)的'*'。
解法：
我做錯了什么要在大晚上刷到正則表達式匹配題匪补？Offer消失術(shù)Ｉ⌒痢！
class Solution {
public boolean isMatch(String s, String p) {
return s.matches(p);
}
}
好吧夯缺，我除了硬配想不出來蚤氏！要考慮的情況又太多了真真不好寫。讀了下答案踊兜，正經(jīng)寫的話用動態(tài)規(guī)劃竿滨，不過條件轉(zhuǎn)移方程不是很好寫，官方又寫的很難懂，這里就記錄一個不寫狀態(tài)轉(zhuǎn)移方程于游、純記錄狀態(tài)的吧毁葱。
作者：Krahets
來源：力扣（LeetCode）
用 dp[i][j]表示 s 的前 i 個字符與 i 中的前 j 個字符是否能夠匹配。
- 當
p[j - 1] = '*'時贰剥，dp[i][j]在當以下任一情況為true時等于true：-
dp[i][j - 2]： 即將字符組合p[j - 2] *看作出現(xiàn)0次時倾剿，能否匹配； -
dp[i - 1][j]且s[i - 1] = p[j - 2]: 即讓字符p[j - 2]多出現(xiàn)1次時蚌成，能否匹配前痘； -
dp[i - 1][j]且p[j - 2] = '.': 即讓字符.多出現(xiàn) 1 次時，能否匹配笑陈；
-
- 當
p[j - 1] != '*'時际度，dp[i][j]在當以下任一情況為true時等于true：-
dp[i - 1][j - 1]且s[i - 1] = p[j - 1]： 即讓字符p[j - 1]多出現(xiàn)一次時，能否匹配涵妥； -
dp[i - 1][j - 1]且p[j - 1] = '.'： 即將字符.看作字符s[i - 1]時乖菱，能否匹配；
-
初始值：需要先初始化 dp 矩陣首行蓬网，以避免狀態(tài)轉(zhuǎn)移時索引越界窒所。
dp[0][0] = ture-
dp[0][j] = dp[0][j - 2]且p[j - 1] = '*'： 首行s為空字符串，因此當p的偶數(shù)位為*時才能夠匹配（即讓p的奇數(shù)位出現(xiàn)0次帆锋，保持p是空字符串）吵取。因此，循環(huán)遍歷字符串p锯厢，步長為2（即只看偶數(shù)位）皮官。
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s) + 1, len(p) + 1
dp = [[False] * n for _ in range(m)]
dp[0][0] = True
for j in range(2, n, 2):
dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i][j - 2] or dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.') \
if p[j - 1] == '*' else \
dp[i - 1][j - 1] and (p[j - 1] == '.' or s[i - 1] == p[j - 1])
return dp[-1][-1]
劍指 Offer 20. 表示數(shù)值的字符串
請實現(xiàn)一個函數(shù)用來判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）。
數(shù)值（按順序）可以分成以下幾個部分：
- 若干空格
- 一個 小數(shù) 或者 整數(shù)
- （可選）一個
'e'或'E'实辑，后面跟著一個 整數(shù) - 若干空格
小數(shù)（按順序）可以分成以下幾個部分：
- （可選）一個符號字符（
'+'或'-'） - 下述格式之一：
- 至少一位數(shù)字捺氢，后面跟著一個點
'.' - 至少一位數(shù)字，后面跟著一個點
'.'剪撬，后面再跟著至少一位數(shù)字 - 一個點
'.'摄乒，后面跟著至少一位數(shù)字
- 至少一位數(shù)字捺氢，后面跟著一個點
整數(shù)（按順序）可以分成以下幾個部分：
- （可選）一個符號字符（
'+'或'-'） - 至少一位數(shù)字
部分數(shù)值列舉如下：
["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
部分非數(shù)值列舉如下：
["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]
示例 1：
輸入：s = "0"
輸出：true
示例 2：
輸入：s = "e"
輸出：false
示例 3：
輸入：s = "."
輸出：false
示例 4：
輸入：s = " .1 "
輸出：true
提示：
1 <= s.length <= 20s僅含英文字母（大寫和小寫），數(shù)字（0-9）残黑，加號'+'馍佑，減號'-'，空格' '或者點'.'梨水。
解法：
出這題的人拭荤，你食不食油餅？就真面向用例編程是吧疫诽，不要太過分了舅世！
收錄兩個個人覺得挺不錯的非面向用例編程辦法笼恰，一個是嘗試轉(zhuǎn)float，成功則Ture歇终，失敗則False；另一個是正則逼龟。
def isNumber(self, s: str) -> bool:
try:
float(s)
return True
except ValueError:
return False
public boolean isNumber(String s) {
return s.trim().matches("[+-]?((\\d+(\\.\\d+)?)|(\\.\\d+)|(\\d+\\.))([eE][+-]?\\d+)?");
}
官方給的解答竟然是有限狀態(tài)自動機评凝！這誰想得到，雖然我學過形式語言與自動機但我真想不到（用的太少了）腺律。
但是用自動機解題確實很方便奕短，編碼思路簡單也不用和if-else搏斗，主要是前期分析花時間匀钧。這里收錄一下官方題解：
import需要的庫：from enum import Enum
輸入字符：
數(shù)字
e
小數(shù)點
符號
空格
不符合條件的非法輸入
Chartype = Enum("Chartype", [
"CHAR_NUMBER",
"CHAR_EXP",
"CHAR_POINT",
"CHAR_SIGN",
"CHAR_SPACE",
"CHAR_ILLEGAL"
])
def toChartype(ch: str) -> Chartype:
if ch.isdigit():
return Chartype.CHAR_NUMBER
elif ch.lower() == "e":
return Chartype.CHAR_EXP
elif ch == ".":
return Chartype.CHAR_POINT
elif ch == "+" or ch == "-":
return Chartype.CHAR_SIGN
elif ch == " ":
return Chartype.CHAR_SPACE
else:
return Chartype.CHAR_ILLEGAL
狀態(tài)集合：
起始的空格
符號位
整數(shù)部分
左側(cè)有整數(shù)的小數(shù)點
左側(cè)無整數(shù)的小數(shù)點
小數(shù)部分
字符 e
指數(shù)部分的符號位
指數(shù)部分的整數(shù)部分
末尾的空格
State = Enum("State", [
"STATE_INITIAL",
"STATE_INT_SIGN",
"STATE_INTEGER",
"STATE_POINT",
"STATE_POINT_WITHOUT_INT",
"STATE_FRACTION",
"STATE_EXP",
"STATE_EXP_SIGN",
"STATE_EXP_NUMBER",
"STATE_END"
])
狀態(tài)轉(zhuǎn)移規(guī)則：
transfer = {
State.STATE_INITIAL: {
Chartype.CHAR_SPACE: State.STATE_INITIAL,
Chartype.CHAR_NUMBER: State.STATE_INTEGER,
Chartype.CHAR_POINT: State.STATE_POINT_WITHOUT_INT,
Chartype.CHAR_SIGN: State.STATE_INT_SIGN
},
State.STATE_INT_SIGN: {
Chartype.CHAR_NUMBER: State.STATE_INTEGER,
Chartype.CHAR_POINT: State.STATE_POINT_WITHOUT_INT
},
State.STATE_INTEGER: {
Chartype.CHAR_NUMBER: State.STATE_INTEGER,
Chartype.CHAR_EXP: State.STATE_EXP,
Chartype.CHAR_POINT: State.STATE_POINT,
Chartype.CHAR_SPACE: State.STATE_END
},
State.STATE_POINT: {
Chartype.CHAR_NUMBER: State.STATE_FRACTION,
Chartype.CHAR_EXP: State.STATE_EXP,
Chartype.CHAR_SPACE: State.STATE_END
},
State.STATE_POINT_WITHOUT_INT: {
Chartype.CHAR_NUMBER: State.STATE_FRACTION
},
State.STATE_FRACTION: {
Chartype.CHAR_NUMBER: State.STATE_FRACTION,
Chartype.CHAR_EXP: State.STATE_EXP,
Chartype.CHAR_SPACE: State.STATE_END
},
State.STATE_EXP: {
Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER,
Chartype.CHAR_SIGN: State.STATE_EXP_SIGN
},
State.STATE_EXP_SIGN: {
Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER
},
State.STATE_EXP_NUMBER: {
Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER,
Chartype.CHAR_SPACE: State.STATE_END
},
State.STATE_END: {
Chartype.CHAR_SPACE: State.STATE_END
},
}
運行：
st = State.STATE_INITIAL
for ch in s:
typ = toChartype(ch)
if typ not in transfer[st]:
return False
st = transfer[st][typ]
return st in [State.STATE_INTEGER, State.STATE_POINT, State.STATE_FRACTION, State.STATE_EXP_NUMBER, State.STATE_END]
