11.字符串

# 01.有效的括号

20.有效的括号 (opens new window)

# 事例1
输入：s = "()[]{}"
输出：true
# 事例2
输入：s = "(]"
输出：false

1
2
3
4
5
6

# 1.1 python

如果是左括号直接入栈，如果右边括号判断栈顶是否时对应左括号
如果左右括号匹配栈顶出栈，最终判断是否栈为空

class Solution:
    def isValid(self, s):
        d = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        stack = []
        for ch in s:
            if ch in d:                   # 如果字符串是 右边括号判断栈顶是否时对应左括号
                if not stack or stack[-1] != d[ch]:
                    return False
                stack.pop()              # 如果 左右括号匹配 栈顶出栈
            else:
                stack.append(ch)         # 如果是左侧括号，直接入栈
        return not stack

if __name__== "__main__":
    print(Solution().isValid("([]{})"))  # True
    print(Solution().isValid("([(])"))  # False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 02.回文数

9.回文数 (opens new window)
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数例如，121 是回文，而 123 不是

输入：x = 121
输出：true
输入：x = -121
输出：false

1
2
3
4

# 1、python

class Solution:
    def huiwen(self, x):
        x = str(x)
        l, r = 0, len(x) - 1
        while l < r and x[l] == x[r]:
            l = l + 1
            r = r - 1
        # 跳出循环 l == r 证明为奇数回文， x[l] == x[r]为偶数回文，否则不是回文
        return l == r or x[l] == x[r]

print( Solution().huiwen(121) )      # True

1
2
3
4
5
6
7
8
9
10
11

# 03.去除重复字母

316.去除重复字母 (opens new window)
- 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次
- 需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）
1081.不同字符的最小子序列 (opens new window)
- 返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次

输入：s = "bcabc"
输出："abc"

输入：s = "cbacdcbc"
输出："acdb"

1
2
3
4
5

# 1、python

使用字典 dic_cnt 统计字符串出现次数
使用stack存储去重的字符串（字符顺序字典序最小：栈顶大于0 当前更小当前更新栈顶）

class Solution:
    def smallestSubsequence(self, s):
        dic_cnt = {}                  # {'c': 4, 'b': 2, 'a': 1, 'd': 1}
        for c in s:
            dic_cnt[c] = dic_cnt.get(c, 0) + 1
        
        set_ = set()
        stack = []                    # 用栈来构建结果
        for c in s:
            dic_cnt[c] -= 1           # 更新字符出现次数
            if c in set_:             # 如果字符已经在栈中，跳过
                continue

            # 字符顺序字典序最小： 栈顶大于0 当前更小 当前更新栈顶
            while stack and c < stack[-1] and dic_cnt[stack[-1]] > 0:
                set_.remove(stack.pop())
            stack.append(c)                   # 将当前字符加入栈和集合
            set_.add(c)

        return ''.join(stack)                 # 拼接栈中的字符生成结果字符串

print( Solution().smallestSubsequence("cbacdcbc") )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 04.最长公共前缀

14.最长公共前缀 (opens new window)
编写一个函数来查找字符串数组中的最长公共前缀
如果不存在公共前缀，返回空字符串 ""

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

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀

1
2
3
4
5
6

# 1、python

标签：链表
当字符串数组长度为 0 时则公共前缀为空，直接返回
令最长公共前缀 ans 的值为第一个字符串，进行初始化
遍历后面的字符串，依次将其与 ans 进行比较，两两找出公共前缀，最终结果即为最长公共前缀
如果查找过程中出现了 ans 为空的情况，则公共前缀不存在直接返回
时间复杂度：O(s)，s 为所有字符串的长度之和

def longest(strs):
    p0 = strs[0]                      # 令最长公共前缀 ans 的值为第一个字符串，进行初始化
    for i in range(1,len(strs)):
        j = 0
        # 遍历后面的字符串，依次将其与 ans 进行比较，两两找出公共前缀，最终结果即为最长公共前缀
        while j < len(p0) and j < len(strs[i]):
            if p0[j] != strs[i][j]:
                break
            j = j+1
        if j == 0:                   # 如果查找过程中出现了 ans 为空的情况，则公共前缀不存在直接返回
            return ""
        p0 = strs[0][:j]
    return p0

strs = ["flower","flow","flight"]
print( longest(strs) )    # fl

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 05.找出字符串中第一个匹配项的下标

28.找出字符串中第一个匹配项的下标 (opens new window)
给定一个 haystack 字符串和一个 needle字符串
在 haystack 字符串中找出needle字符串出现的第一个位置 (从0开始)
如果不存在，则返回 -1

# 示例 1:
输入: haystack  = "hello", needle = "ll"
输出: 2

# 示例 2:
输入: haystack  = "aaaaa", needleneedle = "bba"
输出: -1

1
2
3
4
5
6
7

# 1、python

暴力破解

def strStr(haystack, needle):
    L, n = len(needle), len(haystack)  # L短字符串长度，n长字符串长度
    for start in range(n - L + 1):
        if haystack[start: start + L] == needle:
            return start
    return -1

print( strStr( 'hello', 'll' ) )    # 2

1
2
3
4
5
6
7
8

# 06.反转字符串中的单词 III

557.反转字符串中的单词 III (opens new window)
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序

输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

1
2

# 1、python

利用栈的先进后出的结构很容易做到字符反转
但一串英文单词中，单词的个数总是比空格的字数多一个，在处理的时候很不方便
- 我们不妨在原字符串末尾补充一个空格，让每一小节都变成“单词+空格”
- 遇见空格就是我们判断出栈的前提条件
- 于是我们只要利用切片返回第一个字符后面的string就可以了

def reverseWords(s):
    stack = []                # 使用列表模拟栈
    new_s = ""                # new_s 新字符串
    s = s + " "               # 原字符串末尾补充一个空格，让每一小节都变成“单词+空格”
    for i in s:
        stack.append(i)       # 只要没有遇到空格就依次进栈
        if i == " ":          # 如果遇到空格依次出栈，这样就实现了反转
            while(stack):
                new_s += stack.pop()
    return new_s[1:]

print( reverseWords( "I love you" ) )  # I evol uoy

1
2
3
4
5
6
7
8
9
10
11
12

# 07.二进制求和

67.二进制求和 (opens new window)
给你两个二进制字符串，返回它们的和（用二进制表示）
输入为非空字符串且只包含数字 1 和 0

输入: a = "11", b = "1"
输出: "100"
输入: a = "1010", b = "1011"
输出: "10101"

1
2
3
4

# 1、python

def addBin(num1,num2):
	i,j = len(num1)-1, len(num2)-1     # 设定 i，j 两指针分别指向 num1，num2 尾部
	carry = 0                          # 两数相加进位为0
	ret = ''                           # 结果
	while i >= 0 or j>=0:
		n1 = int(num1[i]) if i>=0 else 0
		n2 = int(num2[j]) if j>=0 else 0
		tmp = n1 + n2 + carry
		ret = str(tmp%2) + ret             # 取余 就是当前位的值，并加入字符串右面
		carry = tmp // 2                   # 井位
		i,j = i-1,j-1                      # 指针向右移动一位
	if carry:                            # 如果循环结束还存在井位，在头部添加进位 1
		ret = '1' + ret
	return ret

print( addBin('11','10') )   # '101' =》 5
# '11' =》3   '10' =》2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 08.最长回文串

409.最长回文串 (opens new window)
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串
在构造过程中，请注意区分大小写比如 "Aa" 不能当做一个回文字符串

输入:  "abccccdd
输出:  7
解释:  我们可以构造的最长的回文串是"dccaccd", 它的长度是 7

1
2
3

# 1、python

如果字符已经在集合中出现，就移除它，否则添加进去
len(s) - len(odd_chars)计算的是可以形成的最长偶数长度的回文
如果集合中还有字符，那么可以再在中间添加一个字符构成奇数长度的回文

def longestStr(s):
    # 使用集合来记录字符的奇数次出现
    odd_chars = set()
    for char in s:
        if char in odd_chars:
            odd_chars.remove(char)
        else:
            odd_chars.add(char)
    
    # 如果有奇数字符，那么我们可以在回文的中心添加一个字符
    return len(s) - len(odd_chars) + (1 if odd_chars else 0)

# 示例用法
s = 'abcccccdd'
print(longestStr(s))  # 输出: 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 09.字符串压缩

面试题 01.06. 字符串压缩 (opens new window)
字符串压缩，利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能
若“压缩”后的字符串没有变短，则返回原先的字符串
你可以假设字符串中只包含大小写英文字母（a至z）

 输入："aabcccccaaa"
 输出："a2b1c5a3"

 输入："abbccd"
 输出："abbccd"
 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长

1
2
3
4
5
6

# 1、python

我们从左往右遍历字符串，用 ch记录当前要压缩的字符，cnt记录 ch出现的次数
如果当前枚举到的字符 s[i]等于ch，我们就更新 cnt的计数，即 cnt = cnt + 1
否则我们按题目要求将 ch以及cnt 更新到答案字符串ans 里，即 ans = ans + ch + cnt,完成对 ch字符的压缩
随后更新 ch为 s[i]，cnt 为 1，表示将压缩的字符更改为 s[i]
在遍历结束之后，我们就得到了压缩后的字符串ans，并将其长度与原串长度进行比较
如果长度没有变短，则返回原串，否则返回压缩后的字符串

def compressString(S):
    ch = S[0]      # ch记录当前要压缩的字符
    ans = ''       # ans拼接新字符串
    cnt = 0        # cnt记录 ch出现的次数
    for c in S:
        if c == ch:        # 当前枚举到的字符 s[i]等于ch，就加一
            cnt += 1
        else:              # 否则我们按题目要求将 ch以及cnt 更新到答案字符串ans 里
            ans += ch + str(cnt)  # `ans = ans + ch + cnt`,完成对 ch字符的压缩
            ch = c
            cnt = 1
    ans += ch + str(cnt)   # 跳出for循环后更新最后一部分
    return ans if len(ans) < len(S) else S

s = "aabcccccaaa"
print( compressString(s) )  # a2b1c5a3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 10.反转字符串

# 1、python

'''第一种：使用字符串切片'''
s = 'Hello World'
print(s[::-1])  # dlroW olleH

'''第二种：使用列表的reverse方法'''
l = list(s)
l.reverse()
print( "".join(l) )   # dlroW olleH

'''第三种：使用reduce'''
from functools import reduce
result = reduce(lambda x,y:y+x,s)
print( result )      # dlroW olleH

1
2
3
4
5
6
7
8
9
10
11
12
13

# 2、golang

package main

func Reverse(s string) string {
	news := []rune(s)
	for l, r := 0, len(news)-1; l < r; l, r = l+1, r-1 {
		news[l], news[r] = news[r], news[l]
	}
	return string(news)
}

func main() {
	println(Reverse("Hello, Wrold")) // dlorW ,olleH
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 11.统计单词次数

统计指定文件中单词出现数量，并找到出现次数最多的前五个

import re
def wordCount(path,n):
	d = {}
	with open(path, encoding="utf-8") as f:
		data = f.read()
		# words = ['version', '3', 'services', .... ]
		words = [s.lower() for s in re.findall("\w+", data)]
		for word in words:
			d[word] = d.get(word, 0) + 1
	return sorted(d.items(), key=lambda item: item[1], reverse=True)[:n]

if __name__ == '__main__':
	pt = r'C:\tmp\drf_demo\book\models.py'
	most_common_5 = wordCount(pt,5)
	print(most_common_5)  # [('mysql', 5), ('root', 3), ('db', 3), ('environment', 2), ('3306', 2)]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 12.无重复字符的最长子串

3.无重复字符的最长子串 (opens new window)
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度
- 以(a)bcabcbb 开始的最长字符串为 (abc)abcbb；
- 以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb
- 以 ab(c)abcbb开始的最长字符串为ab(cab)cbb

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3

1
2
3

# 1、python

我们定义一个左右指针，初始化都指向0位置
右指针每次从左指针位置向右滑动，当出现重复值时结束while循环并重新计算最大值

def longestSubstring(s):
	set_ = set()           # 哈希集合，记录每个字符是否出现过
	n = len(s)
	res = 0                # 记录最大子串长度
	for l in range(n):
		r = l
		while r < n and s[r] not in set_:       # 字符串遍历完成或者出现重复字符串结束
			set_.add(s[r])
			r += 1                              # 不断地移动右指针
		set_ = set()
		res = max(res, r - l)
	return res

print(longestSubstring("abcabcbb"))  # 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 13.最长回文子串

5.最长回文子串 (opens new window)
给你一个字符串 s，找到 s 中最长的回文子串

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案

1
2
3

# 1、python

本题最容易想到的一种方法应该就是 中心扩散法
从每一个位置出发，向两边扩散即可，遇到不是回文的时候结束

class Solution:
    def subscript(self, s, l, r):
        # 左指针大于等于0，右指针小于字符串长度，并且左右对称位置“值”相等，就继续循环
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return l + 1, r - 1

    def longestString(self, s):
        start, end = 0, 0                      # 最开始，初始化左右位置都为 0号位置
        for i in range(len(s)):
            l1, r1 = self.subscript(s, i, i)   # 第一个字符串找左右下标
            l2, r2 = self.subscript(s, i, i + 1)   # 第二个字符串找左右下标
            if r1 - l1 > end - start:
                start, end = l1, r1
            if r2 - l2 > end - start:
                start, end = l2, r2
        return s[start: end + 1]

print(Solution().longestString('babad'))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 14.最长有效括号

32.最长有效括号 (opens new window)

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

1
2
3
4
5
6
7

# 1、python dp

使用一个栈来记录索引，初始时我们将 -1 压入栈中，这可以帮助我们处理最开始的有效子串
遍历字符串s中的每一个字符：
- 如果字符是 '('，我们将它的索引压入栈中
- 如果字符是 ')'，我们弹出栈顶的元素如果此时栈为空，说明没有匹配的 '('，我们将当前索引压入栈中
- 如果栈不为空，我们计算当前有效括号的长度，即当前索引减去栈顶元素的索引，并更新最大长度
遍历结束后，最大长度即为最长有效括号的长度

class Solution:
    def longestValidParentheses(self, s):
        stack = [-1]                    # 栈初始存入 -1 以便计算长度
        max_len = 0

        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()            # stack为空 证明 当栈顶只有一个元素时出现了右括号，必然不符合要求[-1,)]
                if not stack:
                    stack.append(i)     # 如果栈为空，压入当前索引
                else:
                    max_len = max(max_len, i - stack[-1])  # 计算最大长度

        return max_len

print(Solution().longestValidParentheses("(()"))     # 输出：2
print(Solution().longestValidParentheses(")()())"))  # 输出：4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 15.括号生成

22.括号生成 (opens new window)
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合
1 <= n <= 8

# 输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
# 输入：n = 1
输出：["()"]

1
2
3
4

# 1、python回溯

时间复杂度 O(4^n / √n)
空间复杂度：O(C(n) * n) 其中 C(n) 是 Catalan 数

class Solution:
    def generateParenthesis(self, n):
        res = []                  # 存储所有有效的括号组合
        def dfs(s, l, r):
            if len(s) == n * 2:   # 长度达到 2n 时加入结果列表
                res.append(s)
                return
            if l < n:             # 如果左括号数量小于 n
                dfs(s + '(', l + 1, r)
            # 如果右括号数量大于左括号数量肯定不符合，不进入循环即可
            if r < l:
                dfs(s + ')', l, r + 1)

        dfs('', 0, 0)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 16.字符串转换整数 (atoi)

8.字符串转换整数 (atoi) (opens new window)
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数
跳过前导空格：忽略字符串开头的所有空格
处理符号：检查是否有符号字符（+ 或 -），并记录结果的符号
读取数字：从当前位置开始读取数字字符，并转换为整数
处理溢出：确保结果不会超出 32 位有符号整数的范围

# 1、python

class Solution:
    def myAtoi(self, s):
        i = 0
        while i < len(s) and s[i] == ' ':               #1.跳过前导空格
            i += 1

        if i < len(s) and (s[i] == '+' or s[i] == '-'): #2.处理符号
            sign = -1 if s[i] == '-' else 1
            i += 1
        else:
            sign = 1

        res = 0
        while i < len(s) and s[i].isdigit():            #3.读取数字
            digit = int(s[i])
            if res > (2 ** 31 - 1 - digit) // 10:       # 检查是否会溢出
                return 2 ** 31 - 1 if sign == 1 else -2 ** 31

            res = res * 10 + digit
            i += 1

        return res * sign

print( Solution().myAtoi("   -123") )  # -123

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 17.字符串解码

394.字符串解码 (opens new window)
给定一个经过编码的字符串，返回它解码后的字符串
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次
你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入

输入：s = "3[a]2[bc]"
输出："aaabcbc"

输入：s = "3[a2[c]]"
输出："accaccacc"

1
2
3
4
5

# 1、python

栈存储 [(cur_str, cur_num)] 代指 [当前的解析字符串, 解析字符数量]
当遇到 ] 时出栈，这时 cur_str变量才是 当前的解析字符串
以a2[c]为例，当遍历到 ] 此时栈[('a', 2)]
- 此时 print(c, stack, cur_str) 输出] [('a', 2)] c
- [('a', 2)] c = a + c * 2 = acc

def decodeString(s):
    stack = []            # 存储左右括号 和临时结果 [('b', 3), ('a', 2)]
    cur_str = ''          # 存储当前的解析字符串
    cur_num = 0           # 解析字符数量

    for c in s:
        print(c, stack, cur_str)
        if c.isdigit():
            cur_num = cur_num * 10 + int(c)          # 获取字符数
        elif c == '[':
            stack.append((cur_str, cur_num))         # 左括号 [('b', 3), ('a', 2)]
            cur_str = ''                             # 重置当前字符串
            cur_num = 0                              # 重置数量
        elif c == ']':
            last_str, num = stack.pop()              # 遇到右括号时，弹出上一个字符串和数字
            cur_str = last_str + cur_str * num       # 重复当前字符串 num 次并与上一个字符串拼接
        else:
            cur_str += c                             # 普通字符直接拼接到当前字符串

    return cur_str


print(decodeString("b3[a2[c]]"))  # 输出: "baccaccacc" （b acc acc acc）
"""
b [] 
3 [] b
[ [] b
a [('b', 3)] 
2 [('b', 3)] a
[ [('b', 3)] a
c [('b', 3), ('a', 2)] 
] [('b', 3), ('a', 2)] c     # 遇到第一个 ] 出栈 "('a', 2)] c" =  a + c * 2 = acc 
] [('b', 3)] acc             # 遇到第二个 ] 出栈 "[('b', 3)] acc" =  b + accc * 3 = baccaccacc
"""

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 18.单词拆分

139.单词拆分 (opens new window)
给你一个字符串 s 和一个字符串列表 wordDict 作为字典如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成

1
2
3

# 1、python dp

状态定义：dp[i] 表示字符串 s 中从位置 0 到位置 i-1 的子串是否可以通过字典 wordDict 完全拆分
状态转移方程：if dp[j] and s[j:i] in set_
- 满足 dp[j] 为 True 且 s[j:i] 在字典 wordDict 中
初始状态：dp[0] = True，表示空字符串可以被拆分

class Solution:
    def wordBreak(self, s, wordDict):
        set_ = set(wordDict)              # 转换为集合，{'pen', 'apple'}
        dp = [False] * (len(s) + 1)
        dp[0] = True                      # 空字符串可以被拼接

        for i in range(1, len(s) + 1):
            for j in range(i):                     # 检查 s[0:j] 中是否存在为True的肯能
                if dp[j] and s[j:i] in set_:       # 检查 dp[j] 是否为 True 且 s[j:i] 是否在字典中
                    dp[i] = True
                    break
        return dp[len(s)]
        # dp = [True, False, False, False, False, True, False, False, True, False, False, False, False, True]

print( Solution().wordBreak( "applepenapple", ["apple", "pen"]) )   # True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

最终：dp = [True, False, False, False, False, True, False, False, True, False, False, False, False, True]

# s = "applepenapple", wordDict = ["apple", "pen"]
dp[5] = True  # 因为 `"apple"` 在字典中
dp[8] = True  # 因为 `"pen"` 在字典中，且 dp[5] 为 True
dp[13] = True # 因为 `"apple"` 在字典中，且 `dp[8]` 为 `True`
# 最终，`dp[13]` 为 `True`，因此可以拼接出 `s`

1
2
3
4
5

# 19.移掉K位数字

402.移掉 K 位数字 (opens new window)
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小
请你以字符串形式返回这个最小的数字

输入：num = "10200", k = 1
输出："200"
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零

输入：num = "1432219", k = 3
输出："1219"

1
2
3
4
5
6

# 1、python

遍历每个数字时，我们将其与栈顶数字比较
如果栈顶数字大于当前数字，并且我们还有机会移除数字（k > 0），则移除栈顶数字
这个过程确保我们逐步构建的数字尽可能小

class Solution:
    def removeKdigits(self, num, k):
        stack = []
        for digit in num:                                       # 构建单调递增的数字串
            while k > 0 and stack and stack[-1] > digit:        # k>0保证最多移除k个数
                stack.pop()
                k -= 1
            stack.append(digit)
        # 最终 stack = ['0', '0', '2', '2', '1', '9'], 移除首位1 和 43这三个字符
        finalStack = stack[:-k] if k else stack          # 如果 K > 0，删除末尾的 K 个字符
        return "".join(finalStack).lstrip('0') or "0"    # 抹去前导零，如果最终结果为空，则返回 "0"

print( Solution().removeKdigits("100224319", 3)) # 2219

1
2
3
4
5
6
7
8
9
10
11
12
13

# 20.基本计算器

224.基本计算器 (opens new window)
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值
s 由数字+-()空格 组成
'+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
'-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
输入中不存在两个连续的操作符

# 1、python

用栈存储括号外的运算结果和符号（栈中这种 3+4+5+6 会直接算出结果存储到cur_res中）
遍历字符串，字符串根据字符串下面四种情况匹配：(+-)
① ( ：计算cur_res结果并将结果入栈，同时cur_res=0 sign=+
② 数字：计算cur_num当前数字（可能有多位）
③ +-: 计算cur_res 并设置sign=char cur_num=0
④ ): 遇到右括号证明匹配到了一个完整左右括号，出栈计算结果

class Solution:
    def calculate(self, s):
        stack = []                # 用栈存储括号外的运算结果和符号
        cur_res = 0               # 当前计算的累积结果
        cur_num = 0               # 当前正在处理的数字
        sign_map = {"+": 1, "-": -1}  # 使用字典来映射符号
        sign = "+"                # 当前符号，初始为 "+"

        for char in s:
            if char == '(':         # 1）入栈 计算cur_res结果 并将结果入栈
                stack.append(cur_res)                   # 将当前结果入栈保存
                stack.append(sign)
                cur_res = 0
                sign = "+"
            elif char.isdigit():    # 2）计算cur_num当前数字（可能有多位）
                cur_num = cur_num * 10 + int(char)  # 处理多位数字的情况
                
            elif char in sign_map:  # 3）计算cur_res
                cur_res += sign_map[sign] * cur_num     # 将当前数字和符号累加到结果中
                sign = char                             # 直接存储当前符号，稍后处理
                cur_num = 0

                
            elif char == ')':       # 4）出栈 括号内最后一个数字 + 累加栈顶值
                cur_res += sign_map[sign] * cur_num     # 处理括号内最后一个数字
                sign = stack.pop()
                # 将括号内结果乘以栈中的符号，并累加栈中的结果
                cur_res = stack.pop() + sign_map[sign] * cur_res
                cur_num = 0
            print(f"{char}\t{stack}\t{cur_res}")        # 打印当前字符、栈和累积结果

        return cur_res + sign_map[sign] * cur_num       # 10

print(Solution().calculate("(1+(2+(3+4+5+6)))"))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

推演 "(1+(2+(3+4+5+6)))"

# print(f"{char}\t{stack}\t{cur_res}")
(	[0, '+']	0
1	[0, '+']	0
+	[0, '+']	1
(	[0, '+', 1, '+']	0
2	[0, '+', 1, '+']	0
+	[0, '+', 1, '+']	2
(	[0, '+', 1, '+', 2, '+']	0
3	[0, '+', 1, '+', 2, '+']	0
+	[0, '+', 1, '+', 2, '+']	3   # cur_res=3
4	[0, '+', 1, '+', 2, '+']	3
+	[0, '+', 1, '+', 2, '+']	7   # cur_res = cur_res+4 = 7
5	[0, '+', 1, '+', 2, '+']	7
+	[0, '+', 1, '+', 2, '+']	12  # cur_res = cur_res+5 = 12
6	[0, '+', 1, '+', 2, '+']	12
)	[0, '+', 1, '+']	20
)	[0, '+']	21
)	[]	21

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 21.36进制加法

36进制加法 (opens new window) 头条补充题
36进制由0-9，a-z，共36个字符表示
要求按照加法规则计算出任意两个36进制正整数的和，如1b + 2x = 48 （解释：47+105=152）
要求：不允许使用先将36进制数字整体转为10进制，相加后再转回为36进制的做法

# 1、python

使用两个字典，char_to_value 用于将字符映射到其对应的数值，value_to_char 用于将数值映射回字符
根据上面转换，计算方法和正常字符串相加基本一致，逐位相加 即可
处理进位和结果反转：
- 当循环结束时，可能会有一个进位剩余，如果有进位，我们会继续处理它
- 由于计算结果是从低位到高位生成的，最终需要将 res 列表反转并转换为字符串

class Solution:
    def __init__(self):
        #字符串转数字： {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5
        self.char_to_value = {ch: i for i, ch in enumerate("0123456789abcdefghijklmnopqrstuvwxyz")}
        #数字转字符串： 'u', 31: 'v', 32: 'w', 33: 'x', 34: 'y', 35: 'z'}
        self.value_to_char = {i: ch for i, ch in enumerate("0123456789abcdefghijklmnopqrstuvwxyz")}

    def addStrings(self, num1, num2):
        res = []
        i, j, carry = len(num1) - 1, len(num2) - 1, 0        # i 和 j 指向两个字符串的末尾，carry 表示进位

        while i >= 0 or j >= 0 or carry:
            # 取出当前位的字符并转换为数值
            n1 = self.char_to_value[num1[i]] if i >= 0 else 0
            n2 = self.char_to_value[num2[j]] if j >= 0 else 0
            tmp = n1 + n2 + carry                           # 计算当前位的和，包括进位
            res.append(self.value_to_char[tmp % 36])        # 当前位的值为 tmp % 36，找到对应的字符
            carry = tmp // 36                               # 更新进位值
            i -= 1
            j -= 1

        res.reverse()                 # 将结果列表反转并转换为字符串
        return ''.join(res)

print(Solution().addStrings("1b", "2x"))  # 输出："48"
print(Solution().addStrings("1234", "123"))  # 输出："1357"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 22.编辑距离

72.编辑距离 (opens new window)
给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

1
2
3
4
5
6

# 1、python `dp`

初始化边界条件

如果 word1 为空字符串（即 i = 0），则需要将 word2 的前 j 个字符全部插入进去，所需的操作数为 j，即 dp[0][j] = j
如果 word2 为空字符串（即 j = 0），则需要将 word1 的前 i 个字符全部删除，所需的操作数为 i，即 dp[i][0] = i

对于任意的 dp[i][j]，我们有以下几种情况：

字符相等 (word1[i-1] == word2[j-1]):
- 如果 word1 和 word2 的当前字符相同，则不需要额外的操作，因此 dp[i][j] = dp[i-1][j-1]
字符不相等 (word1[i-1] != word2[j-1]):
- 删除操作：从 word1 中删除一个字符，即 dp[i][j] = dp[i-1][j] + 1
- 插入操作：在 word1 中插入一个字符，即 dp[i][j] = dp[i][j-1] + 1
- 替换操作：将 word1 中的一个字符替换为 word2 的字符，即 dp[i][j] = dp[i-1][j-1] + 1

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    
    # 初始化 dp 数组
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 边界条件
    for i in range(1, m + 1):
        dp[i][0] = i  # word1 前 i 个字符转换为空字符串的操作数
    for j in range(1, n + 1):
        dp[0][j] = j  # 空字符串转换为 word2 前 j 个字符的操作数
    
    # 填充 dp 表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i][j - 1] + 1,  # 插入
                               dp[i - 1][j] + 1,  # 删除
                               dp[i - 1][j - 1] + 1)  # 替换
    
    # 返回最终结果
    return dp[m][n]

# 测试用例
word1 = "horse"
word2 = "ros"
print(minDistance(word1, word2))  # 输出：3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

推演 word1 = "sun"，word2 = "satur"

0）初始化数组
- 第一行 0 1 2 3 4 5 表示word1 为空字符串（即 i = 0），则需要将 word2 的前 j 个字符全部插入进去，所需的操作数为 j
- 第一列 0 1 2 3 表示 word2 为空字符串（即 j = 0），则需要将 word1 的前 i 个字符全部删除，所需的操作数为 i

word1 \ word2    ""   s   a   t   u   r
""               0    1   2   3   4   5
s                1    ?   ?   ?   ?   ?
u                2    ?   ?   ?   ?   ?
n                3    ?   ?   ?   ?   ?

1
2
3
4
5

1）word1[i - 1] == word2[j - 1] 每次比较都当做最后一个字符串比较，按照下面逻辑

            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]   # 不变
            else:
                dp[i][j] = min(dp[i][j - 1] + 1,  # 插入
                               dp[i - 1][j] + 1,  # 删除
                               dp[i - 1][j - 1] + 1)  # 替换

1
2
3
4
5
6

#1）计算 dp[1][1]  word1[0] = s 和 word2[0] = s 相等，不需要任何操作
dp[1][1] = dp[0][0] = 0 

# 计算 dp[1][2]  word1[0] = s 和 word2[1] = a 不相等
dp[1][2] = min(
	dp[1][0] + 1,   # 插入(左)
  dp[0][1] + 1,   # 删除（上）
  dp[0][1] + 1,   # 替换（对角）
)
dp[1][2] = min(
	dp[1][0] + 1 = 0 + 1 = 1
  dp[0][1] + 1 = 3 + 1 = 3
  dp[0][1] + 1 = 1 + 1 = 2
)
# 最终 dp[1][2] = 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

word1 \ word2    ""   s   a   t   u   r
""               0    1   2   3   4   5
s                1    0   1   ?   ?   ?
u                2    ?   ?   ?   ?   ?
n                3    ?   ?   ?   ?   ?

1
2
3
4
5

# 23.套餐内商品的排列顺序

LCR 157.套餐内商品的排列顺序 (opens new window)
- 店铺将用于组成套餐的商品记作字符串 goods，其中 goods[i] 表示对应商品请返回该套餐内所含商品的全部排列方式
- 返回结果 无顺序要求，但不能含有重复的元素
字符串的排列 (opens new window)
输入一个字符串，打印出该字符串中字符的所有排列

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

1
2

排列方案的生成
- 根据字符串排列的特点，考虑深度优先搜索所有排列方案
- 即通过字符交换，先固定第 1 位字符（ n 种情况）
- 再固定第 2 位字符（ n-1 种情况）
- 最后固定第 n 位字符（ 1 种情况）

# 1、python 回溯

class Solution:
    def goodsOrder(self, s):
        res = []
        s = sorted(s)                           # 先排序，方便去重
        def dfs(path, used):
            if len(path) == len(s):
                res.append("".join(path))
                return
            for i in range(len(s)):
                if used[i]:                     # 如果该字符已被使用，跳过
                    continue
                # 如果多个字符相同，只处理最后一个，跳过重复元素
                if i > 0 and s[i] == s[i - 1] and not used[i - 1]:
                    continue
                used[i] = True
                dfs(path + [s[i]], used)
                used[i] = False

        dfs([], [False] * len(s))
        return res

print( Solution().goodsOrder("abc"))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 24.解码方法

91.解码方法 (opens new window)
一条包含字母 A-Z 的消息通过以下映射进行了编码 "1" -> 'A', ``"26" -> 'Z'`
给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数
如果没有合法的方式解码整个字符串，返回 0

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）

1
2
3

# 1、python dp

状态定义：dp[i] 表示以 s[i-1]结尾的子字符串的解码方法总数
状态转移方程：
- 如果s[i-1] != '0'，dp[i] = dp[i - 1]
  - 单独解码当前数字，解码方法和 dp[i - 1] 相等
- 如果 s[i-2:i] ，dp[i] += dp[i-2]
  - 这两个字符组成的数字在 10 到 26 之间，且 s[i-2] != '0'，
  - 则dp[i] 方法总数和 dp[i-2] 相等，但是需要累加上面计算结果所以 dp[i] += dp[i-2]
初始状态：dp[0] = 1 表示空字符串有 1 种解码方法
返回结果：dp[n]，即整个字符串的解码方法总数

class Solution:
    def numDecodings(self, s):
        n = len(s)
        # dp[i] 表示以 s[i-1] 结尾的子字符串的解码方法总数
        dp = [1] + [0] * n            # dp[0] = 1 表示空字符串有 1 种解码方法

        for i in range(1, n + 1):
            # 单独解码，单独解码方法数=dp[i - 1] （'0' 不能独立解码）
            if s[i - 1] != '0':
                dp[i] = dp[i - 1]

            # 如果当前字符和前一个字符形成的数字在 10 到 26 之间，且前一个字符不为 '0'
            # 两个数放一起解码：此时 dp[i] = dp[i - 2] 要顾及上面计算结果，所以累加
            if i > 1 and s[i - 2] != '0' and int(s[i - 2:i]) <= 26:
                dp[i] += dp[i - 2]

        return dp[n]

print( Solution().numDecodings("123") )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

以123为例推演

# 初始化 dp = [1, 0, 0, 0]

# i=1  s[0]='1'，它可以单独解码为 'A'
# dp = [1, 1, 0, 0]
dp[i] = dp[i - 1] => dp[1] += dp[0]  = 1

# i=2  s[1]='2'  它可以单独解码为'B'，并且 s[0:2] = '12' 也可以解码为 'L'
# dp = [1, 1, 2, 0]
因为 s[1] != '0'， 所以 dp[2] = dp[1]， 即 dp[2] = 1  # 单独解码为'B'
因为 10 <= int(s[0:2]) <= 26， 所以 dp[2] += dp[0]，即 dp[2] = 2  # '12' 也可以解码为 'L'

# i=3  s[2]='3'  它可以单独解码为 'C'，并且 s[1:3] = '23' 也可以解码为 'W'
# dp = [1, 1, 2, 3]
因为 s[2] != '0'，所以 dp[3] = dp[2]，即 dp[3] = 2  # 单独解码为 'C'
因为 10 <= int(s[1:3]) <= 26，所以 dp[3] += dp[1]，即 dp[3] = 3  # '23' 也可以解码为 'W'


# dp[3] = 3，表示字符串 "123" 总共有 3 种解码方式：
'1' + '2' + '3' → 'A' + 'B' + 'C'
'12' + '3' → 'L' + 'C'
'1' + '23' → 'A' + 'W'

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

上次更新: 2024/9/27 11:33:57

← 02.数组 21.链表→