一、查找最大公共前缀
1.思路
- 首先检查字符串数组是否为空或长度为0，如果是，则返回空字符串。
- 初始化前缀为数组的第一个字符串。
- 遍历数组中的每个字符串，逐个字符比较前缀与当前字符串，如果不匹配，则缩短前缀长度，直到找到匹配或前缀为空。
- 返回最终的前缀
2.代码实现
public class MaxCommonPrefix {
/**
* 查找字符串数组中的最大公共前缀
*
* @param strs 字符串数组
* @return 最大公共前缀
*/
public static String findLongestCommonPrefix(String[] strs) {
// 如果字符串数组为空或长度为0，返回空字符串
if (strs == null || strs.length == 0) {
return "";
}
// 初始化前缀为数组的第一个字符串
String prefix = strs[0];
// 遍历数组中的每个字符串
for (int i = 1; i < strs.length; i++) {
// 当前字符串与前缀逐个字符比较
while (strs[i].indexOf(prefix) != 0) {
// 如果不匹配，缩短前缀长度
prefix = prefix.substring(0, prefix.length() - 1);
// 如果前缀已经为空，则直接返回空字符串
if (prefix.isEmpty()) {
return "";
}
}
}
// 返回最终的前缀
return prefix;
}
public static void main(String[] args) {
// 测试用例
String[] strs = {"flower", "flow", "flight"};
System.out.println(findLongestCommonPrefix(strs)); // 输出: "fl"
}
}二、 两个升序链表合并
1.思路
- 创建一个哑节点作为合并后链表的头节点。
- 使用两个指针分别指向两个链表的头节点。
- 比较两个指针所指向的节点值，将较小的节点接到合并后链表的末尾，并移动该指针。
- 当其中一个指针为空时，将另一个链表的剩余部分接到合并后链表的末尾。
- 返回合并后链表的头节点（哑节点的下一个节点）。
2.代码实现
public class ListNodeMerger {
// 链表节点定义
static class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
/**
* 合并两个升序链表
*
* @param l1 第一个链表
* @param l2 第二个链表
* @return 合并后的链表
*/
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 创建一个哑节点作为合并后链表的头节点
ListNode dummyHead = new ListNode(0);
// 创建一个指针用于遍历合并后链表
ListNode current = dummyHead;
// 当两个链表都不为空时
while (l1 != null && l2 != null) {
// 比较两个链表节点的值
if (l1.val <= l2.val) {
// 将较小值的节点接到合并后链表的末尾
current.next = l1;
// 移动第一个链表的指针
l1 = l1.next;
} else {
// 将较大值的节点接到合并后链表的末尾
current.next = l2;
// 移动第二个链表的指针
l2 = l2.next;
}
// 移动合并后链表的指针
current = current.next;
}
// 将剩余链表接到合并后链表的末尾
if (l1 != null) {
current.next = l1;
}
if (l2 != null) {
current.next = l2;
}
// 返回合并后链表的头节点（哑节点的下一个节点）
return dummyHead.next;
}
public static void main(String[] args) {
// 测试用例
ListNode l1 = new ListNode(1);
l1.next = new ListNode(2);
l1.next.next = new ListNode(4);
ListNode l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(4);
ListNode mergedList = mergeTwoLists(l1, l2);
// 输出合并后的链表
while (mergedList != null) {
System.out.print(mergedList.val + " ");
mergedList = mergedList.next;
}
// 输出: 1 1 2 3 4 4
}
}三、 回收算法
1.思路
- 创建两个列表，一个用于模拟堆内存（存放对象），一个用于存放被标记的对象。
- 分配对象时，将其添加到堆内存中。
- 标记对象时，将其添加到标记列表中。
- 清除时，遍历堆内存，将未被标记的对象保留到新的堆内存中，并清空标记列表。
2.代码实现
import java.util.ArrayList;
import java.util.List;
public class GarbageCollector {
// 模拟堆内存
private List<Object> heap = new ArrayList<>();
// 存放被标记的对象
private List<Object> marked = new ArrayList<>();
/**
* 分配对象到堆内存中
*
* @param obj 要分配的对象
*/
public void allocate(Object obj) {
heap.add(obj);
}
/**
* 标记对象
*
* @param obj 要标记的对象
*/
public void mark(Object obj) {
marked.add(obj);
}
/**
* 清除未被标记的对象
*/
public void sweep() {
// 新的堆内存，用于存放未被标记的对象
List<Object> newHeap = new ArrayList<>();
// 遍历堆内存中的每个对象
for (Object obj : heap) {
// 如果对象未被标记，则保留到新的堆内存中
if (!marked.contains(obj)) {
newHeap.add(obj);
}
}
// 更新堆内存为新的堆内存
heap = newHeap;
// 清空标记列表
marked.clear();
}
/**
* 获取当前堆内存中的对象
*
* @return 堆内存中的对象列表
*/
public List<Object> getHeap() {
return heap;
}
public static void main(String[] args) {
// 测试用例
GarbageCollector gc = new GarbageCollector();
gc.allocate(new Object("Object1"));
gc.allocate(new Object("Object2"));
gc.mark(gc.getHeap().get(0)); // 标记第一个对象
gc.sweep(); // 清除未被标记的对象
// 输出剩余的堆内存对象
for (Object obj : gc.getHeap()) {
System.out.println(obj);
}
// 输出: Object1（因为Object1被标记了，所以未被清除）
}
}四、 封装方法实现查找数组中重复的数字及重复的次数
1.思路
- 使用一个哈希表来记录每个数字出现的次数。
- 遍历数组，更新哈希表中每个数字的出现次数。
- 遍历哈希表，找出出现次数大于1的数字及其次数。
2.代码实现
import java.util.HashMap;
import java.util.Map;
public class FindDuplicateNumbers {
/**
* 查找数组中重复的数字及重复的次数
* @param nums 输入数组
* @return 包含重复数字及次数的映射
*/
public static Map<Integer, Integer> findDuplicates(int[] nums) {
Map<Integer, Integer> countMap = new HashMap<>();
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1); // 统计每个数字的出现次数
}
Map<Integer, Integer> duplicates = new HashMap<>();
for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
if (entry.getValue() > 1) {
duplicates.put(entry.getKey(), entry.getValue()); // 只保留重复的数字及次数
}
}
return duplicates;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 2, 1, 5, 6, 5};
Map<Integer, Integer> duplicates = findDuplicates(nums);
System.out.println(" 重复的数字及次数: " + duplicates); // 输出: 重复的数字及次数: {1=2, 2=2, 5=2}
}
}五、 封装方法实现整型list去除重复元素并输出
1.代码实现
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class RemoveDuplicatesFromList {
/**
* 去除整型列表中的重复元素
* @param list 输入的整型列表
* @return 去重后的整型列表
*/
public static List<Integer> removeDuplicates(List<Integer> list) {
if (list == null || list.isEmpty()) {
return list; // 如果输入列表为空或为null，直接返回
}
Set<Integer> set = new HashSet<>(); // 使用HashSet来去重
List<Integer> result = new ArrayList<>(); // 存储去重后的结果
for (Integer number : list) {
if (set.add(number)) { // 如果set中没有该元素，则添加到结果列表中
result.add(number);
}
}
return result; // 返回去重后的列表
}
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(2);
list.add(1);
list.add(5);
list.add(6);
list.add(5);
List<Integer> uniqueList = removeDuplicates(list);
System.out.println(" 去重后的列表: " + uniqueList); // 输出去重后的列表
}
}