qidao123.com技术社区-IT企服评测·应用市场

标题: 算法刷题记录——LeetCode篇(1.1) [第1~10题] [打印本页]

---

作者: 立山    时间: 2025-4-17 16:47
标题: 算法刷题记录——LeetCode篇(1.1) [第1~10题]
更新时间：2025-03-30

• 算法题解目录汇总：算法刷题记录——题解目录汇总
  
• 技术博客总目录：盘算机技术系列博客——目录页
  

---

1. 两数之和

给定一个整数数组 nums 和一个整数量的值 target，请你在该数组中找出 和为目的值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按恣意次序返回答案。
示例 1：

1. 输入：nums = [2,7,11,15], target = 9
2. 输出：[0,1]

复制代码

  解释：由于 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
  示例 2：

1. 输入：nums = [3,2,4], target = 6
2. 输出：[1,2]

复制代码

示例 3：

1. 输入：nums = [3,3], target = 6
2. 输出：[0,1]

复制代码

提示：

• 2 <= nums.length <= 10^4
  
• -10^9 <= nums <= 10^9
  
• -10^9 <= target <= 10^9
  
• 只会存在一个有用答案
  

进阶：
你可以想出一个时间复杂度小于 O(n^2) 的算法吗？

---

方法：哈希表

使用哈希表存储已遍历元素的值及其索引，对于每个元素 nums，盘算其补数 target - nums。若补数存在于哈希表中，则直接返回两个索引；否则将当前元素存入哈希表，继续遍历。

• 初始化哈希表，键为元素值，值为索引。
  
• 遍历数组，对于每个元素盘算补数。
  
• 检查补数是否存在哈希表中：
  
  
  
  • 存在：返回当前索引和补数的索引。
    
  • 不存在：将当前元素存入哈希表。
    
  
  

代码实现(Java)：

1. class Solution {
2.     public int[] twoSum(int[] nums, int target) {
3.         Map<Integer, Integer> map = new HashMap<>();
4.         for (int i = 0; i < nums.length; i++) {
5.             int complement = target - nums[i];
6.             if (map.containsKey(complement)) {
7.                 return new int[] { map.get(complement), i };
8.             }
9.             map.put(nums[i], i);
10.         }
11.         throw new IllegalArgumentException("No solution found");
12.     }
13. }

复制代码

复杂度分析

• 时间复杂度：O(n)，只需一次遍历数组。
  
• 空间复杂度：O(n)，哈希表存储最多 n 个元素。
  

---

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同情势返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：

1. 输入：l1 = [2,4,3], l2 = [5,6,4]
2. 输出：[7,0,8]

复制代码

  解释：342 + 465 = 807.
  示例 2：

1. 输入：l1 = [0], l2 = [0]
2. 输出：[0]

复制代码

示例 3：

1. 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
2. 输出：[8,9,9,9,0,0,0,1]

复制代码

提示：

• 每个链表中的节点数在范围 [1, 100] 内
  
• 0 <= Node.val <= 9
  
• 题目数据包管列表表示的数字不含前导零
  

---

方法：模仿逐位相加

模仿手工逐位相加的过程，从链表头部（最低位）开始遍历，处理每一位的和及进位。使用哑节点简化链表头部的处理，循环直到所有链表遍历完毕且无进位为止。

• 初始化：
  
  
  
  • 创建哑节点 dummy 和当前指针 current。
    
  • 初始化进位 carry 为 0。
    
  
  
• 遍历链表：
  
  
  
  • 只要任一链表未遍历完或存在进位，继续循环。
    
  • 盘算当前位的总和：sum = val1 + val2 + carry。
    
  • 更新当前节点值和进位。
    
  
  
• 处理剩余节点和进位：
  
  
  
  • 若链表遍历完毕，对应值取 0。
    
  • 若终极进位非零，添加新节点。
    
  
  

代码实现(Java)：

1. class Solution {
2.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
3.         ListNode dummy = new ListNode(0);
4.         ListNode current = dummy;
5.         int carry = 0;
6.         while (l1 != null || l2 != null || carry != 0) {
7.             int val1 = (l1 != null) ? l1.val : 0;
8.             int val2 = (l2 != null) ? l2.val : 0;
9.             int sum = val1 + val2 + carry;
10.             carry = sum / 10;
11.             current.next = new ListNode(sum % 10);
12.             current = current.next;
13.             if (l1 != null) l1 = l1.next;
14.             if (l2 != null) l2 = l2.next;
15.         }
16.         return dummy.next;
17.     }
18. }

复制代码

  哑节点：简化链表头节点的处理，避免空指针题目。
循环条件：覆盖两链表长度差别及存在终极进位的环境。
进位处理：每位盘算后更新进位，并在循环结束时检查是否必要添加新节点。
  复杂度分析

• 时间复杂度：O(max(m, n))，其中 m 和 n 为两链表长度。
  
• 空间复杂度：O(1)（不计效果链表）。
  

---

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

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

1. 输入: s = "abcabcbb"
2. 输出: 3

复制代码

  解释: 由于无重复字符的最长子串是 “abc”，以是其长度为 3。
  示例 2:

1. 输入: s = "bbbbb"
2. 输出: 1

复制代码

  解释: 由于无重复字符的最长子串是 “b”，以是其长度为 1。
  示例 3:

1. 输入: s = "pwwkew"
2. 输出: 3

复制代码

  解释: 由于无重复字符的最长子串是 “wke”，以是其长度为 3。请留意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
  提示：

• 0 <= s.length <= 5 * 10^4
  
• s 由英文字母、数字、符号和空格组成
  

---

方法一：滑动窗口（哈希表记录字符末了出现的位置）

使用哈希表来记录每个字符末了一次出现的位置。当遇到重复字符时，直接将左指针移动到重复字符的下一个位置，确保窗口内无重复字符。
代码实现(Java)：

1. class Solution {
2.     public int lengthOfLongestSubstring(String s) {
3.         Map<Character, Integer> map = new HashMap<>();
4.         int maxLen = 0;
5.         int left = 0;
6.         for (int right = 0; right < s.length(); right++) {
7.             char c = s.charAt(right);
8.             if (map.containsKey(c) && map.get(c) >= left) {
9.                 left = map.get(c) + 1;
10.             }
11.             map.put(c, right);
12.             maxLen = Math.max(maxLen, right - left + 1);
13.         }
14.         return maxLen;
15.     }
16. }

复制代码

---

方法二：滑动窗口（哈希聚集维护当前窗口）

使用哈希聚集来维护当前窗口中的字符。当遇到重复字符时，渐渐移动左指针并移除字符，直到重复字符被移出聚集。
代码实现(Java)：

1. class Solution {
2.     public int lengthOfLongestSubstring(String s) {
3.         Set<Character> set = new HashSet<>();
4.         int maxLen = 0;
5.         int left = 0;
6.         for (int right = 0; right < s.length(); right++) {
7.             char c = s.charAt(right);
8.             while (set.contains(c)) {
9.                 set.remove(s.charAt(left));
10.                 left++;
11.             }
12.             set.add(c);
13.             maxLen = Math.max(maxLen, right - left + 1);
14.         }
15.         return maxLen;
16.     }
17. }

复制代码

---

方法三：数组优化（记录字符索引）

使用数组代替哈希表来记录字符的末了出现位置，提升访问速度。假设字符集为ASCII，数组大小设为128。
代码实现(Java)：

1. class Solution {
2.     public int lengthOfLongestSubstring(String s) {
3.         int[] index = new int[128];
4.         Arrays.fill(index, -1);
5.         int maxLen = 0;
6.         int left = 0;
7.         for (int right = 0; right < s.length(); right++) {
8.             char c = s.charAt(right);
9.             if (index[c] >= left) {
10.                 left = index[c] + 1;
11.             }
12.             index[c] = right;
13.             maxLen = Math.max(maxLen, right - left + 1);
14.         }
15.         return maxLen;
16.     }
17. }

复制代码

---

对比总结

• 滑动窗口（哈希表）：使用哈希表存储字符及其末了一次出现的位置。当右指针遇到重复字符时，直接调整左指针到重复字符的下一位，确保窗口内无重复。
  
• 滑动窗口（哈希聚集）：使用聚集生存当前窗口的字符。右指针移动时，若遇到重复字符，则不断移动左指针并移除字符，直到重复字符被移出聚集。
  
• 数组优化：针对ASCII字符集，用数组替代哈希表，记录字符的末了出现位置。访问数组比哈希表更快，提升效率。
  

三种方法均包管了线性时间复杂度（O(n)），其中数组优化方法在常数时间使用上更优。

---

4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：

1. 输入：nums1 = [1,3], nums2 = [2]
2. 输出：2.00000

复制代码

  解释：合并数组 = [1,2,3] ，中位数 2
  示例 2：

1. 输入：nums1 = [1,2], nums2 = [3,4]
2. 输出：2.50000

复制代码

  解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
  提示：

• nums1.length == m
  
• nums2.length == n
  
• 0 <= m <= 1000
  
• 0 <= n <= 1000
  
• 1 <= m + n <= 2000
  
• -10^6 <= nums1, nums2 <= 10^6
  

---

方法：二分查找法

将题目转化为寻找两个有序数组的第k小元素，通过递归二分扫除元素实现。

• 中位数转换：
  
  
  
  • 将中位数题目转化为寻找第k小元素题目，奇数找中心数，偶数找中心两个数的平均值
    
  
  
• 递归二分扫除：
  
  
  
  • 每次比力两个数组的第k/2个元素（现实取有用长度防止越界）
    
  • 扫除较小值所在数组的前k/2元素（或全部剩余元素）
    
  • 递归处理剩余部门，直到k=1时直接取较小值
    
  
  
• 界限处理：
  
  
  
  • 当某个数组起始位置越界时，直接从另一数组取对应元素
    
  • 有用步长盘算确保不会越界访问数组
    
  
  

代码实现(Java)：

1. class Solution {
2.     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
3.         int total = nums1.length + nums2.length;
4.         if (total % 2 == 1) {
5.             return findKth(nums1, nums2, 0, 0, total / 2 + 1);
6.         } else {
7.             int left = findKth(nums1, nums2, 0, 0, total / 2);
8.             int right = findKth(nums1, nums2, 0, 0, total / 2 + 1);
9.             return (left + right) / 2.0;
10.         }
11.     }
12.   
13.     private int findKth(int[] A, int[] B, int aStart, int bStart, int k) {
14.         if (aStart >= A.length) return B[bStart + k - 1];
15.         if (bStart >= B.length) return A[aStart + k - 1];
16.         if (k == 1) return Math.min(A[aStart], B[bStart]);
17.       
18.         // 计算有效步长（防止越界）
19.         int aStep = Math.min(k / 2, A.length - aStart);
20.         int bStep = Math.min(k / 2, B.length - bStart);
21.         int aIndex = aStart + aStep - 1;
22.         int bIndex = bStart + bStep - 1;
23.       
24.         // 比较并排除较小值的区间
25.         if (A[aIndex] <= B[bIndex]) {
26.             return findKth(A, B, aStart + aStep, bStart, k - aStep);
27.         } else {
28.             return findKth(A, B, aStart, bStart + bStep, k - bStep);
29.         }
30.     }
31. }

复制代码

复杂度分析

• 时间复杂度为O(log(m+n))，每次递归减少k值约一半。
  

---

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：

1. 输入：s = "babad"
2. 输出："bab"

复制代码

  解释：“aba” 同样是符合题意的答案。
  示例 2：

1. 输入：s = "cbbd"
2. 输出："bb"

复制代码

提示：

• 1 <= s.length <= 1000
  
• s 仅由数字和英文字母组成
  

---

方法一：动态规划

• 使用二维数组 dp[j] 记录子串 s[i...j] 是否为回文。
  
• 通过状态转移方程 dp[j] = (s == s[j]) && dp[i+1][j-1] 递推盘算所有子串的回文性，同时记录最长回文。
  

代码实现(Java)：

1. class Solution {
2.     public String longestPalindrome(String s) {
3.         int n = s.length();
4.         if (n < 2) return s;
5.       
6.         boolean[][] dp = new boolean[n][n];
7.         int maxLen = 1, start = 0;
8.       
9.         // 初始化所有长度为1的子串为回文
10.         for (int i = 0; i < n; i++) dp[i][i] = true;
11.       
12.         // 递推计算所有子串
13.         for (int j = 1; j < n; j++) {
14.             for (int i = 0; i < j; i++) {
15.                 if (s.charAt(i) != s.charAt(j)) {
16.                     dp[i][j] = false;
17.                 } else {
18.                     if (j - i < 3) { // 长度<=3时无需检查内部子串
19.                         dp[i][j] = true;
20.                     } else {
21.                         dp[i][j] = dp[i+1][j-1];
22.                     }
23.                 }
24.               
25.                 // 更新最长回文
26.                 if (dp[i][j] && j - i + 1 > maxLen) {
27.                     maxLen = j - i + 1;
28.                     start = i;
29.                 }
30.             }
31.         }
32.         return s.substring(start, start + maxLen);
33.     }
34. }

复制代码

复杂度分析:

• 时间复杂度：O(n²)，双重循环遍历所有子串。
  
• 空间复杂度：O(n²)，存储动态规划表。
  

---

方法二：中心扩展法

遍历每个可能的回文中心（单个字符或相邻字符对），向两侧扩展直到不满足回文条件。记录扩展过程中的最长回文。
代码实现(Java)：

1. class Solution {
2.     public String longestPalindrome(String s) {
3.         if (s == null || s.length() < 1) return "";
4.         int start = 0, end = 0;
5.       
6.         for (int i = 0; i < s.length(); i++) {
7.             int len1 = expand(s, i, i);    // 奇数长度
8.             int len2 = expand(s, i, i+1);  // 偶数长度
9.             int maxLen = Math.max(len1, len2);
10.          
11.             if (maxLen > end - start) {
12.                 start = i - (maxLen - 1) / 2;
13.                 end = i + maxLen / 2;
14.             }
15.         }
16.         return s.substring(start, end + 1);
17.     }
18.   
19.     private int expand(String s, int left, int right) {
20.         while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
21.             left--;
22.             right++;
23.         }
24.         return right - left - 1; // 实际回文长度
25.     }
26. }

复制代码

复杂度分析:

• 时间复杂度：O(n²)，遍历 2n-1 个中心点，每个扩展最多 O(n) 次。
  
• 空间复杂度：O(1)，无需额外存储。
  

---

方法三：BFS 层序扩展

将每个可能的回文中心（长度1或2）加入队列，逐层向两侧扩展。每次扩展后更新最长回文，使用队列避免重复处理。
代码实现(Java)：

1. class Solution {
2.     public String longestPalindrome(String s) {
3.         int n = s.length();
4.         if (n == 0) return "";
5.       
6.         Queue<int[]> queue = new LinkedList<>();
7.         boolean[][] visited = new boolean[n][n];
8.         int maxLen = 1, start = 0;
9.       
10.         // 初始化长度为1和2的回文
11.         for (int i = 0; i < n; i++) {
12.             queue.offer(new int[]{i, i});
13.             visited[i][i] = true;
14.             if (i < n-1 && s.charAt(i) == s.charAt(i+1)) {
15.                 queue.offer(new int[]{i, i+1});
16.                 visited[i][i+1] = true;
17.                 maxLen = 2;
18.                 start = i;
19.             }
20.         }
21.       
22.         // BFS扩展
23.         while (!queue.isEmpty()) {
24.             int[] pos = queue.poll();
25.             int l = pos[0], r = pos[1];
26.          
27.             // 向两侧扩展
28.             int nl = l - 1, nr = r + 1;
29.             if (nl >= 0 && nr < n && s.charAt(nl) == s.charAt(nr) && !visited[nl][nr]) {
30.                 visited[nl][nr] = true;
31.                 queue.offer(new int[]{nl, nr});
32.                 if (nr - nl + 1 > maxLen) {
33.                     maxLen = nr - nl + 1;
34.                     start = nl;
35.                 }
36.             }
37.         }
38.         return s.substring(start, start + maxLen);
39.     }
40. }

复制代码

复杂度分析:

• 时间复杂度：O(n²)，每个子串最多处理一次。
  
• 空间复杂度：O(n²)，存储队列和访问标记。
  

---

方法四：Manacher 算法（最优解）

通过插入特别字符（如 #）将字符串同一为奇数长度，使用对称性快速盘算每个中心的最长回文半径，避免重复盘算。
代码实现(Java)：

1. class Solution {
2.     public String longestPalindrome(String s) {
3.         StringBuilder sb = new StringBuilder("^#");
4.         for (char c : s.toCharArray()) {
5.             sb.append(c).append('#');
6.         }
7.         sb.append('$');
8.         String T = sb.toString();
9.       
10.         int n = T.length();
11.         int[] P = new int[n];
12.         int C = 0, R = 0;
13.       
14.         for (int i = 1; i < n-1; i++) {
15.             int mirror = 2 * C - i;
16.             if (i < R) P[i] = Math.min(R - i, P[mirror]);
17.          
18.             // 扩展回文
19.             while (T.charAt(i + P[i] + 1) == T.charAt(i - P[i] - 1)) {
20.                 P[i]++;
21.             }
22.          
23.             // 更新中心和右边界
24.             if (i + P[i] > R) {
25.                 C = i;
26.                 R = i + P[i];
27.             }
28.         }
29.       
30.         // 找出最大回文
31.         int maxLen = 0, center = 0;
32.         for (int i = 1; i < n-1; i++) {
33.             if (P[i] > maxLen) {
34.                 maxLen = P[i];
35.                 center = i;
36.             }
37.         }
38.         int start = (center - maxLen) / 2;
39.         return s.substring(start, start + maxLen);
40.     }
41. }

复制代码

复杂度分析:

• 时间复杂度：O(n)，线性时间处理。
  
• 空间复杂度：O(n)，存储变换后的字符串和回文半径数组。
  

---

对比总结

方法优劣势动态规划逻辑直观，但空间占用较高中心扩展法空间最优，代码轻便BFS 扩展类似中心扩展，但需额外空间记录状态Manacher 算法线性时间，但实现复杂，适用于极大输入

---

6. Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
好比输入字符串为 "AYPALISHIRING" 行数为 3 时，排列如下：

1. P   A   H   N
2. A P L S I I G
3. Y   I   R

复制代码

之后，你的输出必要从左往右逐行读取，产生出一个新的字符串，好比："AHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1：

1. 输入：s = "PAYPALISHIRING", numRows = 3
2. 输出："PAHNAPLSIIGYIR"

复制代码

示例 2：

1. 输入：s = "PAYPALISHIRING", numRows = 4
2. 输出："PINALSIGYAHRPI"

复制代码

  解释：如下所示。

1. P     I    N
2. A   L S  I G
3. Y A   H R
4. P     I

复制代码

示例 3：

1. 输入：s = "A", numRows = 1
2. 输出："A"

复制代码

提示：

• 1 <= s.length <= 1000
  
• s 由英文字母（小写和大写）、',' 和 '.' 组成
  
• 1 <= numRows <= 1000
  

---

方法一：数学规律法（按行访问）

通过观察Z字形排列的规律，直接盘算每一行字符在原字符串中的位置并按次序拼接。

• 周期盘算：每个Z字形周期的长度为 2 * numRows - 2。
  
• 按行处理：对于每一行，字符的位置分为主列（垂直列）和斜列（对角线列）。主列的位置为 j + i，斜列的位置为 j + cycle - i，其中 j 为周期的起始索引。
  
• 界限处理：第一行和末了一行没有斜列，中心行必要处理斜列的位置，确保不越界。
  

代码实现(Java)：

1. class Solution {
2.     public String convert(String s, int numRows) {
3.         if (numRows == 1) {
4.             return s;
5.         }
6.       
7.         StringBuilder result = new StringBuilder();
8.         int cycle = 2 * numRows - 2;
9.       
10.         for (int i = 0; i < numRows; i++) {
11.             for (int j = 0; j + i < s.length(); j += cycle) {
12.                 result.append(s.charAt(j + i));
13.                 if (i != 0 && i != numRows - 1) { // 中间行处理斜列
14.                     int secondIndex = j + cycle - i;
15.                     if (secondIndex < s.length()) {
16.                         result.append(s.charAt(secondIndex));
17.                     }
18.                 }
19.             }
20.         }
21.         return result.toString();
22.     }
23. }

复制代码

---

方法二：模仿方向法（按行添补）

通过模仿字符的排列过程，按方向逐行添补字符，末了合并所有行的字符。

• 方向模仿：使用方向变量控制字符添补的行移动方向，到达界限时反转方向。
  
• 逐行添补：根据当前方向将字符添加到对应行，末了合并所有行得到效果。
  

代码实现(Java)：

1. class Solution {
2.     public String convert(String s, int numRows) {
3.         if (numRows == 1) {
4.             return s;
5.         }
6.       
7.         List<StringBuilder> rows = new ArrayList<>();
8.         for (int i = 0; i < numRows; i++) {
9.             rows.add(new StringBuilder());
10.         }
11.       
12.         int currentRow = 0;
13.         int direction = 1; // 1表示向下，-1表示向上
14.       
15.         for (char c : s.toCharArray()) {
16.             rows.get(currentRow).append(c);
17.             currentRow += direction;
18.             // 到达边界时反转方向
19.             if (currentRow == 0 || currentRow == numRows - 1) {
20.                 direction = -direction;
21.             }
22.         }
23.       
24.         StringBuilder result = new StringBuilder();
25.         for (StringBuilder row : rows) {
26.             result.append(row);
27.         }
28.         return result.toString();
29.     }
30. }

复制代码

---

复杂度分析

两种方法的时间复杂度均为 O(n)，其中 n 为字符串长度。数学方法通过直接盘算字符位置更高效，而模仿方法更直观易懂。

---

7. 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部门反转后的效果。
假如反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：

1. 输入：x = 123
2. 输出：321

复制代码

示例 2：

1. 输入：x = -123
2. 输出：-321

复制代码

示例 3：

1. 输入：x = 120
2. 输出：21

复制代码

示例 4：

1. 输入：x = 0
2. 输出：0

复制代码

提示：

• -2^31 <= x <= 2^31 - 1
  

---

方法思路

• 逐位反转：通过循环取出整数的末了一位数字，并构建反转后的数。
  
• 溢出检查：在每次构建新数字前，判断是否会导致溢出。使用整数除法的特性，提前预判乘10后的越界环境。
  
• 符号处理：使用Java负数取余的特性，直接处理负数环境，避免符号转换导致的溢出题目。
  

代码实现(Java)：

1. class Solution {
2.     public int reverse(int x) {
3.         int reversed = 0;
4.         while (x != 0) {
5.             int digit = x % 10;
6.             x /= 10;
7.          
8.             // 检查正数溢出
9.             if (reversed > Integer.MAX_VALUE / 10 || (reversed == Integer.MAX_VALUE / 10 && digit > 7)) {
10.                 return 0;
11.             }
12.             // 检查负数溢出
13.             if (reversed < Integer.MIN_VALUE / 10 || (reversed == Integer.MIN_VALUE / 10 && digit < -8)) {
14.                 return 0;
15.             }
16.          
17.             reversed = reversed * 10 + digit;
18.         }
19.         return reversed;
20.     }
21. }

复制代码

---

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

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。
函数 myAtoi(string s) 的算法如下：

• 空格：读入字符串并丢弃无用的前导空格（" "）
  
• 符号：检查下一个字符（假设还未到字符末端）为 ‘-’ 照旧 ‘+’。假如两者都不存在，则假定效果为正。
  
• 转换：通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的末端。假如没有读取数字，则效果为0。
  
• 舍入：假如整数数超过 32 位有符号整数范围 [−2^31, 2^31 − 1] ，必要截断这个整数，使其保持在这个范围内。具体来说，小于 −2^31 的整数应该被舍入为 −2^31 ，大于 2^31 − 1 的整数应该被舍入为 2^31 − 1 。
  

返回整数作为终极效果。
示例 1：

1. 输入：s = "42"
2. 输出：42

复制代码

  解释：
第 1 步：“42”（当前没有读入字符，由于没有前导空格）
第 2 步：“42”（当前没有读入字符，由于这里不存在 ‘-’ 大概 ‘+’）
第 3 步：“42”（读入 “42”）
  示例 2：

1. 输入：s = " -042"
2. 输出：-42

复制代码

  解释：
第 1 步：" -042"（读入前导空格，但忽视掉）
第 2 步：" -042"（读入 ‘-’ 字符，以是效果应该是负数）
第 3 步：" -042"（读入 “042”，在效果中忽略前导零）
  示例 3：

1. 输入：s = "1337c0d3"
2. 输出：1337

复制代码

  解释：
第 1 步：“1337c0d3”（当前没有读入字符，由于没有前导空格）
第 2 步：“1337c0d3”（当前没有读入字符，由于这里不存在 ‘-’ 大概 ‘+’）
第 3 步：“1337c0d3”（读入 “1337”；由于下一个字符不是一个数字，以是读入停止）
  示例 4：

1. 输入：s = "0-1"
2. 输出：0

复制代码

  解释：
第 1 步：“0-1” (当前没有读入字符，由于没有前导空格)
第 2 步：“0-1” (当前没有读入字符，由于这里不存在 ‘-’ 大概 ‘+’)
第 3 步：“0-1” (读入 “0”；由于下一个字符不是一个数字，以是读入停止)
  示例 5：

1. 输入：s = "words and 987"
2. 输出：0

复制代码

  解释：
读取在第一个非数字字符“w”处停止。
  提示：

• 0 <= s.length <= 200
  
• s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成
  

---

方法思路

• 去除前导空格：遍历字符串，跳过所有前导空格。
  
• 处理符号：检查符号位，确定正负，并移动索引到符号后的位置。
  
• 逐位转换：读取连续的数字字符，渐渐构建整数。每次添加新数字时检查是否溢出：
  
  
  
  • 正数溢出：效果超过Integer.MAX_VALUE时返回Integer.MAX_VALUE。
    
  • 负数溢出：效果的绝对值超过Integer.MAX_VALUE + 1时返回Integer.MIN_VALUE。
    
  
  
• 返回效果：将终极效果乘以符号，确保在32位整数范围内。
  

代码实现(Java)：

1. class Solution {
2.     public int myAtoi(String s) {
3.         if (s == null || s.isEmpty()) return 0;
5.         int index = 0;
6.         int n = s.length();
7.         int sign = 1;
8.         long result = 0;
10.         // 跳过前导空格
11.         while (index < n && s.charAt(index) == ' ') {
12.             index++;
13.         }
15.         if (index == n) return 0;
17.         // 处理符号
18.         if (s.charAt(index) == '+' || s.charAt(index) == '-') {
19.             sign = s.charAt(index) == '+' ? 1 : -1;
20.             index++;
21.         }
23.         // 转换数字并处理溢出
24.         while (index < n && Character.isDigit(s.charAt(index))) {
25.             int digit = s.charAt(index) - '0';
26.             result = result * 10 + digit;
28.             // 检查正溢出
29.             if (sign == 1 && result > Integer.MAX_VALUE) {
30.                 return Integer.MAX_VALUE;
31.             }
32.             // 检查负溢出
33.             if (sign == -1 && -result < Integer.MIN_VALUE) {
34.                 return Integer.MIN_VALUE;
35.             }
37.             index++;
38.         }
40.         return (int) (sign * result);
41.     }
42. }

复制代码

---

9. 回文数

给你一个整数 x ，假如 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
比方，121 是回文，而 123 不是。
示例 1：

1. 输入：x = 121
2. 输出：true

复制代码

示例 2：

1. 输入：x = -121
2. 输出：false

复制代码

  解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
  示例 3：

1. 输入：x = 10
2. 输出：false

复制代码

  解释：从右向左读, 为 01 。因此它不是一个回文数。
  提示：

• -2^31 <= x <= 2^31 - 1
  

进阶：
你能不将整数转为字符串来办理这个题目吗？

---

方法一：反转整个数字

• 特别环境处理：负数直接返回 false。
  
• 反转整个数字：通过循环取出原数字的每一位，渐渐构建反转后的数字。使用 long 范例存储反转效果以避免溢出。
  
• 比力效果：反转后的数字与原数字相称则为回文数。
  

代码实现(Java)：

1. public boolean isPalindrome(int x) {
2.     if (x < 0) return false;
3.     long reversed = 0;
4.     int original = x;
5.     while (x != 0) {
6.         reversed = reversed * 10 + x % 10;
7.         x /= 10;
8.     }
9.     return reversed == original;
10. }

复制代码

复杂度分析：

• 时间复杂度：O(log n)，其中 n 是输入整数 x 的位数。反转过程必要遍历每一位。
  
• 空间复杂度：O(1)，仅使用常数级别的额外空间。
  

---

方法二：反转一半数字

• 特别环境处理：
  
  
  
  • 负数直接返回 false。
    
  • 末端为 0 的非零数不可能是回文数。
    
  
  
• 反转后半部门：在反转过程中，当反转数大于或等于剩余原数字时停止，此时已处理了一半位数。
  
• 判断回文：
  
  
  
  • 偶数位数：反转数等于剩余原数字。
    
  • 奇数位数：反转数除以 10 后等于剩余原数字（忽略中心位）。
    
  
  

代码实现(Java)：

1. public boolean isPalindrome(int x) {
2.     if (x < 0 || (x % 10 == 0 && x != 0)) return false;
3.     int reversed = 0;
4.     while (x > reversed) {
5.         reversed = reversed * 10 + x % 10;
6.         x /= 10;
7.     }
8.     return x == reversed || x == reversed / 10;
9. }

复制代码

复杂度分析：

• 时间复杂度：O(log n)，最多反转一半位数。
  
• 空间复杂度：O(1)，仅使用常数级别的额外空间。
  

---

10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

• '.' 匹配恣意单个字符
  
• '*' 匹配零个或多个前面的那一个元素
  所谓匹配，是要涵盖 整个 字符串 s 的，而不是部门字符串。
  

示例 1：

1. 输入：s = "aa", p = "a"
2. 输出：false

复制代码

  解释：“a” 无法匹配 “aa” 整个字符串。
  示例 2：

1. 输入：s = "aa", p = "a*"
2. 输出：true

复制代码

  解释：由于 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。
  示例 3：

1. 输入：s = "ab", p = ".*"
2. 输出：true

复制代码

  解释："." 表示可匹配零个或多个（'‘）恣意字符（’.'）。
  提示：

• 1 <= s.length <= 20
  
• 1 <= p.length <= 20
  
• s 只包罗从 a-z 的小写字母。
  
• p 只包罗从 a-z 的小写字母，以及字符 . 和 *。
  
• 包管每次出现字符 * 时，前面都匹配到有用的字符
  

---

方法：动态规划

• 状态界说：
  
  
  
  • dp[j] 表示字符串 s 的前 i 个字符和模式 p 的前 j 个字符是否匹配。
    
  
  
• 界限条件：
  
  
  
  • dp[0][0] = true：空字符串和空模式匹配。
    
  • 处理模式 p 匹配空字符串的环境（如 a*b* 等布局）。
    
  
  
• 状态转移：
  
  
  
  • 当模式字符是 * 时：
    
    
    
    • 匹配0次：忽略当前 * 和前一个字符，状态继续自 dp[j-2]。
      
    • 匹配多次：当前字符需与前一个模式字符匹配，且前序状态 dp[i-1][j] 为真。
      
    
    
  • 平凡字符或.匹配：当前字符必须匹配，且前序状态 dp[i-1][j-1] 为真。
    
  
  

代码实现(Java)：

1. class Solution {
2.     public boolean isMatch(String s, String p) {
3.         int m = s.length(), n = p.length();
4.         boolean[][] dp = new boolean[m + 1][n + 1];
5.         dp[0][0] = true;
7.         // 处理模式串p前j个字符匹配空字符串的情况（如a*b*c*）
8.         for (int j = 1; j <= n; j++) {
9.             if (p.charAt(j - 1) == '*') {
10.                 dp[0][j] = dp[0][j - 2];
11.             }
12.         }
14.         for (int i = 1; i <= m; i++) {
15.             for (int j = 1; j <= n; j++) {
16.                 char sc = s.charAt(i - 1);
17.                 char pc = p.charAt(j - 1);
19.                 if (pc == '*') {
20.                     char prev = p.charAt(j - 2);
21.                     // 匹配0次（跳过当前*和前一个字符）或匹配多次
22.                     boolean matchZero = dp[i][j - 2];
23.                     boolean matchMore = (prev == '.' || prev == sc) && dp[i - 1][j];
24.                     dp[i][j] = matchZero || matchMore;
25.                 } else if (pc == '.' || pc == sc) {
26.                     // 当前字符精确匹配
27.                     dp[i][j] = dp[i - 1][j - 1];
28.                 }
29.                 // 否则保持dp[i][j]为false
30.             }
31.         }
33.         return dp[m][n];
34.     }
35. }

复制代码

复杂度分析

• 时间复杂度：O(m*n)，其中 m 和 n 分别是字符串和模式的长度。
  
• 空间复杂度：O(m*n)，用于存储动态规划表。可优化至 O(n) 使用滚动数组。
  

---

声明
   

• 本文版权归 CSDN 用户 Allen Wurlitzer 所有，遵照CC-BY-SA协议发布，转载请注明出处。
  
• 本文题目泉源 力扣-LeetCode ，著作权归领扣网络所有。贸易转载请联系官方授权，非贸易转载请注明出处。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)

Powered by Discuz! X3.4