目录

1、杨辉三角（数组，动态规划）

选项代码

2、电话号码的字母组合（哈希表，字符串）

选项代码

3、验证回文串（双指针，字符串）

选项代码

1、杨辉三角（数组，动态规划）

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5

输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1

输出: [[1]]

提示:

• 1 <= numRows <= 30

选项代码：

from typing import List
class Solution:def generate(self, numRows: int) -> List[List[int]]:if numRows == 0:return []if numRows == 1:return [[1]]if numRows == 2:return [[1], [1, 1]]result = [[1], [1, 1]] + [[] for i in range(numRows - 2)]for i in range(2, numRows):for j in range(i + 1):if j == 0 or j == i:result[i].append(1)else:result[i].append(result[i - 1][j - 1] + result[i - 1][j])return result
if __name__ == "__main__":s = Solution()print (s.generate( numRows = 5))

2、电话号码的字母组合（哈希表，字符串）

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

选项代码：

from typing import List
class Solution:def letterCombinations(self, digits: str) -> List[str]:letters = [[],[],['a', 'b', 'c'],['d', 'e', 'f'],['g', 'h', 'i'],['j', 'k', 'l'],['m', 'n', 'o'],['p', 'q', 'r', 's'],['t', 'u', 'v'],['w', 'x', 'y', 'z'],]combinations = []i = 0for d in digits:letter = letters[int(d)]if i == 0:for l in letter:combinations.append([l])else:added = []for c in combinations:j = 0origin_c = []origin_c += cfor l in letter:if j == 0:c.append(l)else:new_c = []new_c += origin_cnew_c.append(l)added.append(new_c)j += 1combinations += addedi += 1output = []for c in combinations:output.append(''.join(c))return output
# %%
s = Solution()
print(s.letterCombinations(digits = "23"))

3、验证回文串（双指针，字符串）

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"

输出: true

解释："amanaplanacanalpanama" 是回文串

示例 2:

输入: "race a car"

输出: false

解释："raceacar" 不是回文串

提示：

• 1 <= s.length <= 2 * 105
• 字符串 s 由 ASCII 字符组成

选项代码：

class Solution(object):def isPalindrome(self, s):""":type s: str:rtype: bool"""i = 0j = len(s) - 1while i < j:if s[i].isalnum() and s[j].isalnum():if s[i].upper() == s[j].upper():i += 1j -= 1else:return Falseelse:if not s[i].isalnum():i += 1if not s[j].isalnum():j -= 1return True
# %%
s = Solution()
print(s.isPalindrome("A man, a plan, a canal: Panama"))