Android学习总结之算法篇五（字符串）

字符串求回笔墨串数目

1. public class CountPalindromicSubstrings {
2.     /**
3.      * 此方法用于计算字符串中回文子串的数量
4.      * @param s 输入的字符串
5.      * @return 回文子串的数量
6.      */
7.     public static int countSubstrings(String s) {
8.         // 若输入字符串为空或长度为 0，直接返回 0
9.         if (s == null || s.length() == 0) {
10.             return 0;
11.         }
12.         // 用于记录回文子串的数量
13.         int count = 0;
14.         // 获取字符串的长度
15.         int n = s.length();
16.         // 遍历字符串中的每个字符
17.         for (int i = 0; i < n; i++) {
18.             // 以单个字符为中心进行扩展，统计以该字符为中心的回文子串数量
19.             count += expandAroundCenter(s, i, i);
20.             // 以两个相邻字符为中心进行扩展，统计以这两个相邻字符为中心的回文子串数量
21.             count += expandAroundCenter(s, i, i + 1);
22.         }
23.         return count;
24.     }
26.     /**
27.      * 以给定的左右索引为中心向两边扩展，计算以该中心的回文子串数量
28.      * @param s 输入的字符串
29.      * @param left 左索引
30.      * @param right 右索引
31.      * @return 以该中心的回文子串数量
32.      */
33.     private static int expandAroundCenter(String s, int left, int right) {
34.         // 用于记录以该中心的回文子串数量
35.         int count = 0;
36.         // 当左右索引在字符串范围内，并且对应字符相等时，继续扩展
37.         while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
38.             // 每找到一个回文子串，数量加 1
39.             count++;
40.             // 左索引向左移动一位
41.             left--;
42.             // 右索引向右移动一位
43.             right++;
44.         }
45.         return count;
46.     }
48.     public static void main(String[] args) {
49.         // 定义一个示例字符串
50.         String s = "abc";
51.         // 调用 countSubstrings 方法计算回文子串的数量，并输出结果
52.         System.out.println("回文子串的数目是: " + countSubstrings(s));
53.     }
54. }   

复制代码

字符串转整数（atoi）

题目：输入一个表示整数的字符串，转换成整数并输出。需处理正负号、溢出（返回 INT_MAX 或 INT_MIN）、非法字符（遇到非数字字符停止转换）。

1. // 该类用于将字符串转换为整数，模拟实现 Java 中的字符串转整数功能
2. public class StringToInteger {
3.     // 此方法将输入的字符串 s 转换为整数
4.     public int myAtoi(String s) {
5.         // 获取输入字符串的长度
6.         int len = s.length();
7.         // 若字符串长度为 0，即空字符串，直接返回 0
8.         if (len == 0) return 0;
10.         // 步骤 1: 去除字符串开头的空白字符
11.         // 初始化索引，用于遍历字符串
12.         int index = 0;
13.         // 当索引未越界且当前字符为空白字符时，索引向后移动
14.         while (index < len && s.charAt(index) == ' ') {
15.             index++;
16.         }
18.         // 步骤 2: 处理字符串中的符号位
19.         // 初始化符号，默认为正号
20.         int sign = 1;
21.         // 若索引未越界且当前字符为正号或负号
22.         if (index < len && (s.charAt(index) == '+' || s.charAt(index) == '-')) {
23.             // 若为负号，将符号设为 -1；若为正号，符号保持为 1
24.             sign = (s.charAt(index) == '-') ? -1 : 1;
25.             // 索引向后移动一位
26.             index++;
27.         }
29.         // 步骤 3: 把字符串中的数字部分转换为整数，同时处理可能的溢出情况
30.         // 用 long 类型存储结果，避免在转换过程中出现整数溢出
31.         long result = 0;
32.         // 当索引未越界且当前字符为数字时
33.         while (index < len && Character.isDigit(s.charAt(index))) {
34.             // 把当前字符转换为对应的数字
35.             int digit = s.charAt(index) - '0';
36.             // 把当前数字添加到结果中
37.             result = result * 10 + digit;
39.             // 检查是否发生正溢出
40.             if (sign == 1 && result > Integer.MAX_VALUE) {
41.                 // 若发生正溢出，返回整数的最大值
42.                 return Integer.MAX_VALUE;
43.             }
44.             // 检查是否发生负溢出
45.             if (sign == -1 && result > -(long)Integer.MIN_VALUE) {
46.                 // 若发生负溢出，返回整数的最小值
47.                 return Integer.MIN_VALUE;
48.             }
49.             // 索引向后移动一位
50.             index++;
51.         }
52.         // 把最终结果乘以符号，并转换为 int 类型返回
53.         return (int)(result * sign);
54.     }
56.     public static void main(String[] args) {
57.         // 创建 StringToInteger 类的实例
58.         StringToInteger solution = new StringToInteger();
59.         // 测试不同的输入字符串，并打印转换后的整数结果
60.         System.out.println(solution.myAtoi("42"));         // 输出 42
61.         System.out.println(solution.myAtoi("-42"));        // 输出 -42
62.         System.out.println(solution.myAtoi("4193 with words")); // 输出 4193
63.         System.out.println(solution.myAtoi("words and 987")); // 输出 0（遇到非数字字符则停止转换）
64.         System.out.println(solution.myAtoi("-91283472332")); // 输出 -2147483648（整数的最小值，处理了溢出情况）
65.     }
66. }

复制代码

字符串全排列

题目：输入一个字符串（含重复字符），打印所有字符排列（不重复输出）。
算法：回溯法，递归互换字符位置生成排列，使用Set去重（或在递归时跳过重复字符）。

1. import java.util.ArrayList;
2. import java.util.HashSet;
3. import java.util.List;
4. import java.util.Set;
6. // 该类用于生成字符串的所有不重复排列
7. public class StringPermutation {
8.     // 用于存储最终生成的所有排列结果
9.     private List<String> result = new ArrayList<>();
10.     // 存储输入字符串转换后的字符数组
11.     private char[] chars;
13.     // 生成字符串 s 的所有不重复排列
14.     public List<String> permutation(String s) {
15.         // 将输入的字符串转换为字符数组，方便后续操作
16.         chars = s.toCharArray();
17.         // 调用回溯函数，从索引 0 开始生成排列
18.         backtrack(0);
19.         // 返回存储所有排列结果的列表
20.         return result;
21.     }
23.     // 回溯函数，用于生成排列
24.     private void backtrack(int index) {
25.         // 当索引等于字符数组的长度时，说明已经生成了一个完整的排列
26.         if (index == chars.length) {
27.             // 将当前字符数组转换为字符串，并添加到结果列表中
28.             result.add(new String(chars));
29.             // 递归终止，返回上一层
30.             return;
31.         }
32.         // 使用 Set 记录已经交换过的字符，避免生成重复的排列
33.         Set<Character> used = new HashSet<>();
34.         // 从当前索引开始，遍历字符数组
35.         for (int i = index; i < chars.length; i++) {
36.             // 如果当前字符已经在 Set 中，说明已经交换过，跳过该字符
37.             if (used.contains(chars[i])) continue;
38.             // 将当前字符添加到 Set 中，表示已经使用过
39.             used.add(chars[i]);
40.             // 交换当前索引和 i 索引位置的字符
41.             swap(index, i);
42.             // 递归调用回溯函数，处理下一个索引位置
43.             backtrack(index + 1);
44.             // 回溯操作，恢复交换前的状态，以便尝试其他排列
45.             swap(index, i);
46.         }
47.     }
49.     // 交换字符数组中两个位置的字符
50.     private void swap(int i, int j) {
51.         // 临时存储 i 位置的字符
52.         char temp = chars[i];
53.         // 将 j 位置的字符赋值给 i 位置
54.         chars[i] = chars[j];
55.         // 将临时存储的字符赋值给 j 位置
56.         chars[j] = temp;
57.     }
59.     public static void main(String[] args) {
60.         // 创建 StringPermutation 类的实例
61.         StringPermutation solution = new StringPermutation();
62.         // 测试输入字符串 "abc"，并打印生成的所有排列
63.         System.out.println(solution.permutation("abc"));
64.         // 测试输入字符串 "aab"，并打印生成的所有不重复排列
65.         System.out.println(solution.permutation("aab"));
66.     }
67. }

复制代码

复杂度分析：

• 时间复杂度：O (n×n!)，n 为字符串长度。每个位置有 n, n-1, ..., 1 种可能，统共有 n! 种排列，每次生成排列需 O (n) 时间复制字符数组。
  
• 空间复杂度：O (n)，递归栈深度为 n，存储排列的空间为 n!×n（均匀环境可视为 O (n!)）。
  

找最小的 k 个数

题目：从 n 个数中找到最小的 k 个数（k≤n）。
算法：使用最大堆（优先队列）维护 k 个元素，堆顶是当前 k 个数中的最大值。遍历数组时，若当前数小于堆顶，则替换堆顶，包管堆中始终是最小的 k 个数。

1. import java.util.ArrayList;
2. import java.util.List;
3. import java.util.PriorityQueue;
5. // 该类用于找出数组中最小的 k 个数
6. public class SmallestKNumbers {
7.     // 该方法用于从数组 arr 中找出最小的 k 个数
8.     public List<Integer> getLeastNumbers(int[] arr, int k) {
9.         // 用于存储最终找到的最小的 k 个数
10.         List<Integer> result = new ArrayList<>();
11.         // 如果 k 为 0，说明不需要找最小的数，直接返回空列表
12.         if (k == 0) return result;
14.         // 使用优先队列来实现最大堆。
15.         // PriorityQueue 默认是最小堆，通过传入 (a, b) -> b - a 这个逆序比较器，将其转换为最大堆
16.         PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
18.         // 遍历数组中的每个元素
19.         for (int num : arr) {
20.             // 如果最大堆中的元素数量小于 k，直接将当前元素添加到最大堆中
21.             if (maxHeap.size() < k) {
22.                 maxHeap.offer(num);
23.             } else if (num < maxHeap.peek()) {
24.                 // 如果最大堆已经有 k 个元素，且当前元素比堆顶元素（堆中的最大值）小
25.                 // 则移除堆顶元素，将当前元素添加到堆中
26.                 maxHeap.poll();
27.                 maxHeap.offer(num);
28.             }
29.         }
31.         // 遍历最大堆，将堆中的元素依次添加到结果列表中
32.         while (!maxHeap.isEmpty()) {
33.             result.add(maxHeap.poll());
34.         }
36.         // 返回存储最小的 k 个数的列表
37.         return result;
38.     }
40.     public static void main(String[] args) {
41.         // 创建 SmallestKNumbers 类的实例
42.         SmallestKNumbers solution = new SmallestKNumbers();
43.         // 定义一个测试数组
44.         int[] arr = {3, 2, 1, 5, 6, 4};
45.         // 调用 getLeastNumbers 方法找出数组中最小的 2 个数，并打印结果
46.         System.out.println(solution.getLeastNumbers(arr, 2));
47.         // 结果可能是 [1, 2]，由于堆结构不保证元素的顺序，实际输出顺序可能不同，可后续排序
48.     }
49. }

复制代码

优化说明：

• 若需要效果排序，可在最后对列表排序：result.sort((a,b)->a-b);。
  
• 复杂度分析：
  
  
  
  • 时间复杂度：O (n log k)，每个元素入堆和出堆操作均为 O (log k)，共 n 次操作。
    
  • 空间复杂度：O (k)，堆中存储 k 个元素。
    
  
  

其他方法对比：

• 排序法：先排序数组，取前 k 个。时间复杂度 O (n log n)，实用于 n 较小的环境。
  
• 快速选择（雷同快排分区）：均匀时间复杂度 O (n)，但最坏环境 O (n²)，且不实用于海量数据（需修改原数组）。
  

环形链表总集

1. // 定义链表节点类，每个节点包含一个整数值和一个指向下一个节点的引用
2. class ListNode {
3.     int val;
4.     ListNode next;
5.     // 构造函数，用于初始化节点的值
6.     ListNode(int x) {
7.         val = x;
8.         next = null;
9.     }
10. }
12. public class CircularLinkedListAlgorithms {
13.     /**
14.      * 判断链表是否有环
15.      * @param head 链表的头节点
16.      * @return 如果链表有环返回 true，否则返回 false
17.      */
18.     public static boolean hasCycle(ListNode head) {
19.         // 若链表为空或者只有一个节点，不可能存在环，直接返回 false
20.         if (head == null || head.next == null) {
21.             return false;
22.         }
23.         // 慢指针，每次移动一步
24.         ListNode slow = head;
25.         // 快指针，每次移动两步
26.         ListNode fast = head;
27.         // 当快指针和其下一个节点都不为空时，继续循环
28.         while (fast != null && fast.next != null) {
29.             // 慢指针移动一步
30.             slow = slow.next;
31.             // 快指针移动两步
32.             fast = fast.next.next;
33.             // 如果慢指针和快指针相遇，说明链表存在环
34.             if (slow == fast) {
35.                 return true;
36.             }
37.         }
38.         // 快指针到达链表末尾，说明链表不存在环
39.         return false;
40.     }
42.     /**
43.      * 找到环形链表的入环点
44.      * @param head 链表的头节点
45.      * @return 入环点的节点，如果链表无环则返回 null
46.      */
47.     public static ListNode detectCycle(ListNode head) {
48.         // 若链表为空或者只有一个节点，不可能存在环，直接返回 null
49.         if (head == null || head.next == null) {
50.             return null;
51.         }
52.         // 慢指针，每次移动一步
53.         ListNode slow = head;
54.         // 快指针，每次移动两步
55.         ListNode fast = head;
56.         // 标记链表是否有环
57.         boolean hasCycle = false;
58.         // 当快指针和其下一个节点都不为空时，继续循环
59.         while (fast != null && fast.next != null) {
60.             // 慢指针移动一步
61.             slow = slow.next;
62.             // 快指针移动两步
63.             fast = fast.next.next;
64.             // 如果慢指针和快指针相遇，说明链表存在环
65.             if (slow == fast) {
66.                 hasCycle = true;
67.                 break;
68.             }
69.         }
70.         // 如果链表无环，返回 null
71.         if (!hasCycle) {
72.             return null;
73.         }
74.         // 慢指针重新指向头节点
75.         slow = head;
76.         // 慢指针和快指针同时移动一步，直到它们相遇，相遇点即为入环点
77.         while (slow != fast) {
78.             slow = slow.next;
79.             fast = fast.next;
80.         }
81.         return slow;
82.     }
84.     /**
85.      * 计算环形链表的环长度
86.      * @param head 链表的头节点
87.      * @return 环的长度，如果链表无环则返回 0
88.      */
89.     public static int cycleLength(ListNode head) {
90.         // 若链表为空或者只有一个节点，不可能存在环，直接返回 0
91.         if (head == null || head.next == null) {
92.             return 0;
93.         }
94.         // 慢指针，每次移动一步
95.         ListNode slow = head;
96.         // 快指针，每次移动两步
97.         ListNode fast = head;
98.         // 标记链表是否有环
99.         boolean hasCycle = false;
100.         // 当快指针和其下一个节点都不为空时，继续循环
101.         while (fast != null && fast.next != null) {
102.             // 慢指针移动一步
103.             slow = slow.next;
104.             // 快指针移动两步
105.             fast = fast.next.next;
106.             // 如果慢指针和快指针相遇，说明链表存在环
107.             if (slow == fast) {
108.                 hasCycle = true;
109.                 break;
110.             }
111.         }
112.         // 如果链表无环，返回 0
113.         if (!hasCycle) {
114.             return 0;
115.         }
116.         // 初始化环的长度为 1
117.         int length = 1;
118.         // 快指针移动一步
119.         fast = fast.next;
120.         // 快指针继续移动，直到再次和慢指针相遇，记录移动的步数
121.         while (slow != fast) {
122.             fast = fast.next;
123.             length++;
124.         }
125.         return length;
126.     }
128.     public static void main(String[] args) {
129.         // 构建一个有环的链表示例
130.         ListNode node1 = new ListNode(1);
131.         ListNode node2 = new ListNode(2);
132.         ListNode node3 = new ListNode(3);
133.         ListNode node4 = new ListNode(4);
134.         node1.next = node2;
135.         node2.next = node3;
136.         node3.next = node4;
137.         node4.next = node2; // 形成环
139.         // 调用 hasCycle 方法判断链表是否有环并输出结果
140.         System.out.println("链表是否有环: " + hasCycle(node1));
141.         // 调用 detectCycle 方法找到入环点
142.         ListNode entryPoint = detectCycle(node1);
143.         if (entryPoint != null) {
144.             // 若有入环点，输出入环点的值
145.             System.out.println("入环点的值: " + entryPoint.val);
146.         } else {
147.             // 若没有入环点，输出提示信息
148.             System.out.println("没有入环点");
149.         }
150.         // 调用 cycleLength 方法计算环的长度并输出结果
151.         System.out.println("环的长度: " + cycleLength(node1));
152.     }
153. }   

复制代码

有序数组去重

1. public class RemoveDuplicatesSortedArray {
2.     /**
3.      * 此方法用于移除有序数组中的重复元素，使每个元素只出现一次。
4.      * 并返回移除重复元素后数组的新长度。
5.      * 原数组会被修改，新长度之前的元素为去重后的元素。
6.      *
7.      * @param nums 输入的有序整数数组
8.      * @return 去重后数组的新长度
9.      */
10.     public static int removeDuplicates(int[] nums) {
11.         // 如果数组为空，直接返回 0
12.         if (nums == null || nums.length == 0) {
13.             return 0;
14.         }
15.         // 慢指针，指向去重后数组的最后一个位置
16.         int slow = 0;
17.         // 快指针，用于遍历数组
18.         for (int fast = 1; fast < nums.length; fast++) {
19.             // 如果快指针指向的元素和慢指针指向的元素不相等
20.             if (nums[fast] != nums[slow]) {
21.                 // 慢指针向后移动一位
22.                 slow++;
23.                 // 将快指针指向的元素赋值给慢指针当前位置
24.                 nums[slow] = nums[fast];
25.             }
26.         }
27.         // 慢指针的位置加 1 就是去重后数组的长度
28.         return slow + 1;
29.     }
31.     public static void main(String[] args) {
32.         // 定义一个有序数组
33.         int[] nums = {1, 1, 2, 2, 3, 4, 4, 4, 5};
34.         // 调用 removeDuplicates 方法进行去重
35.         int newLength = removeDuplicates(nums);
36.         System.out.println("去重后数组的新长度: " + newLength);
37.         System.out.print("去重后的数组元素: ");
38.         for (int i = 0; i < newLength; i++) {
39.             System.out.print(nums[i] + " ");
40.         }
41.     }
42. }   

复制代码

数组归并区间 

1. import java.util.ArrayList;
2. import java.util.Arrays;
3. import java.util.Comparator;
4. import java.util.List;
6. public class MergeIntervals {
7.     /**
8.      * 合并重叠的区间
9.      * @param intervals 输入的区间数组
10.      * @return 合并后不重叠的区间数组
11.      */
12.     public static int[][] merge(int[][] intervals) {
13.         // 如果输入数组为空或者长度为 0，直接返回空数组
14.         if (intervals == null || intervals.length == 0) {
15.             return new int[0][0];
16.         }
17.         // 按照区间的起始位置进行排序
18.         Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
20.         // 用于存储合并后的区间
21.         List<int[]> merged = new ArrayList<>();
22.         // 取第一个区间作为初始的合并区间
23.         int[] current = intervals[0];
24.         // 遍历剩余的区间
25.         for (int i = 1; i < intervals.length; i++) {
26.             int[] interval = intervals[i];
27.             // 如果当前区间的结束位置大于等于下一个区间的起始位置，说明有重叠
28.             if (current[1] >= interval[0]) {
29.                 // 更新当前区间的结束位置为两个区间结束位置的最大值
30.                 current[1] = Math.max(current[1], interval[1]);
31.             } else {
32.                 // 没有重叠，将当前区间加入到合并列表中
33.                 merged.add(current);
34.                 // 更新当前区间为下一个区间
35.                 current = interval;
36.             }
37.         }
38.         // 将最后一个合并的区间加入到列表中
39.         merged.add(current);
41.         // 将列表转换为二维数组并返回
42.         return merged.toArray(new int[merged.size()][]);
43.     }
45.     public static void main(String[] args) {
46.         int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
47.         int[][] mergedIntervals = merge(intervals);
48.         // 输出合并后的区间
49.         for (int[] interval : mergedIntervals) {
50.             System.out.println(Arrays.toString(interval));
51.         }
52.     }
53. }   

复制代码

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