力扣每日练习3.10

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。 示例 1:

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

解题思路：
1.不含重复字符，可以维护一个这样的哈希表，键为字符，值为出现次数。
2.初始化最长长度、快慢指针为0。
3.设定一个循环，当快指针>=字符串长度时退出：
快指针遍历字符串，不断将当前字符添加进哈希表：若不存在于哈希表，就设其值为1，否则自增1；
检查当前字符的值是不是大于1了，大于就是重复了，这个时候就要将慢指针位置的字符在哈希表里的值-1，重复该过程直到不大于1；
更新最长长度，取最长长度和哈希表长度的最大值（应该直接取前后指针的差值+1）
快指针移动一位。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 初始化哈希表
        _dict = {}
        # 初始化最长长度，慢指针，快指针
        max_len, slow, fast = 0,0,0
        length = len(s)

        # 开始循环
        while fast < length:
            # 如果当前元素不在哈希表中
            if s[fast] not in _dict:
                _dict[s[fast]] = 1
            # 已经在了，加1
            else:
                _dict[s[fast]] += 1

            # 如果当前元素重复
            while _dict[s[fast]] > 1:
                # 减去哈希表的第一个元素的值
                _dict[s[slow]] -= 1
                # 若为0，则删除该元素
                #if _dict[s[slow]] == 0:
                    #del _dict[s[slow]]
                slow += 1
            
            # 更新max_len
            # max_len = max(len(_dict), max_len)
            max_len = max(fast-slow+1, max_len)
            

            fast += 1

        return max_len
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

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1： 输入：s = “babad” 输出：“bab” 解释：“aba” 同样是符合题意的答案。

解题思路：
判断是否回文：最直观的是用sorted函数，你要是倒排出来和原始的一样不就行了，但是这样肯定不对，对于小白来说，自己能想到的直观解法基本都是错的。
正确的判断回文：回文是一个字符串倒着读和正着读都一样，说明是对称结构，只要找到一个中心点，左右是相等的即可。这样就变成找中点，如果回文串是奇数个字符，那中点是一个字符；否则，就是两个字符的空隙，可以将其视作这俩字符。

1.初始化最大长度，最大长度的字符串的开始索引均为0
2.遍历整个字符串，为了考虑到只有一个字符的情况，不能跳过前后末端
3.针对每个可能的中心点，进行扩展。使用中心扩展算法，具体实现是新建一个辅助函数，传入整个字符串、左右指针（初始化为中点）；如果左右指针在字符串区间内，且左右指针的字符相同，则进行扩展；扩展方式，左右指针向左右各增加1，再判断字符是否相同；当超出区间或者不相同时退出，根据左右指针返回回文字符串长度和在整个字符串的起始索引。
这里必须要提的是，回文字符串长度=right-left-1，因为最开始传入的左右指针是中点，肯定是相同的，如果扩展一次后不同了（不用管中间是否相同），左右指针还是移动到了不是回文字符串的外围一个单位，那么回文子串长度就是right-left+1-2。同理，起始索引也变成了left+1。
4.根据奇偶情况获得两种情况下的回文字符串长度和起始索引，与最大长度比较，大于就替换掉，并且最大长度的字符串的开始索引也变为当前起始索引。
5.返回整个字符串的切片，具体是最大长度的字符串的开始索引+最大长度

class Solution:
    def longestPalindrome(self, s: str) -> str:

        def slove(s, left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return right-left-1, left+1

        # 初始化最长子串
        max_len = 0
        start = 0
        for i in range(len(s)):
            # 每次中心点都要初始化
            # 假设是
            # 奇数子串
            len_o, start_o = slove(s, i, i)
            # 偶数子串
            len_a, start_a = slove(s, i, i+1)

            if len_o > max_len:
                max_len = len_o
                start = start_o
            if len_a > max_len:
                max_len = len_a
                start = start_a

        return s[start: start+max_len]

        
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

8. 字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi
函数）。 函数 myAtoi(string s) 的算法如下： 读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。 将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为−231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。 返回整数作为最终结果。 注意： 本题中的空白字符只包括空格字符 ’ ’ 。 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。 示例 1： 输入：s = “42” 输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。 第 1 步：“42”（当前没有读入字符，因为没有前导空格） 第 2
步：“42”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’） 第 3 步：“42”（读入 “42”） 解析得到整数 42 。 由于
“42” 在范围 [-231, 231 - 1] 内，最终结果为 42 。

直观做法：初始化结果字符串、正负符号、单指针。去除前导空格，判断第一个字符是不是正负符号，更新指针和正负符号变量；遍历字符串，不断加入结果，直到指针超过字符串长度或者字符不是数字，就退出；字符不是数字 使用正则判断；最后的结果字符串转整数，与边界比较大小，保留符号边界的。（错误）
解题思路：跟着题目描述的算法走，默认正负符号是正，字符判断是否是数字采用.isdigit()
正确做法：1.初始化结果字符串、正负符号、单指针。去除前导空格。
2.判断第一个字符是不是符号，如果是，则根据符号情况更新正负符号变量，并且指针+1跳过该位置；
3.处理完正负符号后，设置一个while循环，退出条件是指针超过字符串长度或者字符不是数字，在循环内部将当前指针的字符添加进结果字符串；
4.检查结果字符串是否有内容，如果是空字符串，则说明啥数字字符都每一步，直接返回0，至于更改符号，0不用更改；
5.若有内容，则将其转为整数，并*正负符号变量；
6.将得到的整数与左右边界比较，先与右边界比较，如果在右边界之内，那么返回整数值，否则返回右边界；再与左边界比较，如果比左边界还小，则返回左边界，否则返回上次比较的值。这样就保证了一定会被截断。

class Solution:
    def myAtoi(self, s: str) -> int:
        # 删除前空格
        s = s.lstrip()
        # 初始化
        res, sign, index = '', 1, 0
        # 判断正负，跳过符号位置
        if index < len(s) and s[index] in ['+', '-']:
            sign = 1 if s[index] == '+' else -1
            index += 1 
        # 遍历字符，符合要求加入结果
        # 要求是索引位置不是数字或者索引超过字符串长度
        while index < len(s) and s[index].isdigit():
            res += s[index]
            index += 1
        
        # 没有数字字符
        if not res:
            return 0
        # 转数字，加上符号
        res = sign * int(res)
        # 判断是否超过边界，首先对结果和右边界取最小值，如果结果小，那就再和左边界比较最大值，如果左边界较大，则返回左边界
        res = max(min(res, 2**31-1), -2**31)

        return res
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