LeetCode 字符串与整数刷题笔记

目录：LeetCode 索引

1 无重复字符的最长子串（LeetCode 3）

给定一个字符串，找出其中不含有重复字符的最长子串的长度。

输入 "abcabcbb" → 3（”abc”）
输入 "bbbbb" → 1（”b”）
输入 "pwwkew" → 3（”wke”，注意”pwke”是子序列不是子串）

知识点

滑动窗口：两个指针表示窗口左右边界，根据条件调整左边界；
哈希表：字符作为 key、字符下标作为 value，快速定位左边界需要跳转的位置。

算法（以 Python 讲解）

初始化字符到下标字典 charToIndex、窗口起始 start/终止 end、maxLength；
end 未达到终点时迭代；
若 end 指向的字符在字典中，更新 start = max(start, index + 1)（取较大者防止 start 左滑。如它 abba：b 连续出现两次，若直接取 index+1 会让 start 左移，导致误判长度）；
更新 maxLength = max(maxLength, end - start + 1)；
存储当前字符下标；end + 1。

        
      
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charToIndex = dict()
        start = 0
        end = 0
        lengthOfString = len(s)
        maxLength = 0
        while(end < lengthOfString):
            char = s[end]
            index = charToIndex.get(char)
            # @note 这里的坑：若 index 为 0，`if (index)` 不会进入分支，
            # 必须显式与 None 比较（或用 `if char in charToIndex`）
            if (index != None):
                # 取较大者，防止 start 向左滑动（例：abba）
                start = max(start, index + 1)

            charToIndex[char] = end
            maxLength = max(maxLength, end - start + 1)
            end += 1

        return maxLength

Java 版

        
      
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        // map 存放字符在字符串 s 中对应的下标
        Map<Character, Integer> map = new HashMap<>();
        for (int j = 0, i = 0; j < n; j++) {
            char c = s.charAt(j);
            // 窗口包含当前字符时，左边界移到相同字符下一位置和 i 中更靠右的位置，防止 i 左移
            if (map.containsKey(c)) {
                i = Math.max(map.get(c), i);
            }
            ans = Math.max(ans, j - i + 1);
            // value 存 j+1：出现重复时 i 直接跳到上个相同字符的下个位置，if 中无需再 +1
            map.put(c, j + 1);
        }
        return ans;
    }
}

C 版

        
      
#include <string.h>

int lengthOfLongestSubstring(char * s){
    int maxLength = 0;
    int start = 0;   // 指向最长子串头部
    int end = 0;     // 指向最长子串尾部
    int map[128] = {-1};   // 假设字符全部为 ASCII；存字符对应下标+1
    int len = strlen(s);
    while(end < len) {
        char c = *(s + end);
        int index = map[c];
        if (index != -1)
            start = (start > index) ? start : index;

        int currentLength = end - start + 1;
        maxLength = maxLength > currentLength ? maxLength : currentLength;

        map[c] = end + 1;   // 存下个位置，更新 start 时无需再 +1
        end += 1;
    }
    return maxLength;
}

2 整数反转（LeetCode 7）

给出一个 32 位有符号整数，将每位上的数字反转；溢出则返回 0。

输入 123 → 321；输入 -123 → -321；输入 120 → 21。

知识点

整数拆解：x % 10 取出最低位，x // 10 去掉最低位；
32 位有符号整数范围 [-(2<<30), (2<<30)-1]（1 << 31 == 2 << 30）；
Python3 中负数 % 10 的结果与 Java 不同（Python 结果与除数符号一致），因此先转为正数再处理；
溢出判断：计算 res*10 + last_digit 前判断——正数溢出条件：
- res > max_int / 10
- res == max_int / 10 and last_digit > max_int % 10 负数同理（注意负数下界比正数多 1）。

Python3 版（先取正）

        
      
class Solution:
    def reverse(self, x: int) -> int:
        is_nagtive = False
        if x < 0:
            is_nagtive = True
            x = -x

        max_int = (1 << 31) - 1
        one_int_ten_max_int = max_int / 10
        last_digit_of_max_int = max_int % 10

        res = 0
        while(x != 0):
            last_dight = x % 10
            # 在赋值前判断 res*10 与 res*10+last_dight 是否可能溢出
            if res > one_int_ten_max_int or (res == one_int_ten_max_int and last_dight > last_digit_of_max_int):
                return 0
            elif res < -one_int_ten_max_int or (res == -one_int_ten_max_int and res < -last_digit_of_max_int - 1):
                return 0

            res = res * 10 + last_dight
            x = x // 10

        if is_nagtive:
            res = -res
        return res

C 版（直接判断 INT_MIN/INT_MAX）

        
      
int reverse(int x){
    int y = 0;
    int pop;
    int one_tenth_max = INT_MAX / 10;
    int one_tenth_min = INT_MIN / 10;
    while(x){
        pop = x % 10;
        if (y > one_tenth_max || (y == one_tenth_max && pop > 7))
            return 0;
        if (y < one_tenth_min || (y == one_tenth_min && pop < -8))
            return 0;
        y = y * 10 + pop;
        x /= 10;
    }
    return y;
}

3 字符串转换整数 atoi（LeetCode 8）

实现将字符串转换成 32 位有符号整数的 myAtoi(string s)，处理前导空格、正负号、数字前缀、越界截断，无法转换返回 0。

        
      
class Solution:
    def myAtoi(self, s: str) -> int:
        s = s.lstrip()
        if not s:
            return 0
        sign = 1
        i = 0
        if s[0] in '+-':
            if s[0] == '-':
                sign = -1
            i = 1
        res = 0
        INT_MAX = (1 << 31) - 1
        INT_MIN = -(1 << 31)
        while i < len(s) and s[i].isdigit():
            res = res * 10 + int(s[i])
            i += 1
        res *= sign
        if res > INT_MAX:
            return INT_MAX
        if res < INT_MIN:
            return INT_MIN
        return res

4 回文数（LeetCode 9）

判断一个整数是否是回文数（如 121 → true，-121 → false，10 → false）。

        
      
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x % 10 == 0 and x != 0):
            return False
        reverted = 0
        while x > reverted:
            reverted = reverted * 10 + x % 10
            x //= 10
        # 偶数位：x == reverted；奇数位：reverted // 10 去掉中间位
        return x == reverted or x == reverted // 10

不转字符串，只反转后半段数字，与前半段比较，避免整体反转溢出。

阅读 — · 全站 —