大厂高频数据结构和算法题
怎么判断两个链表是否相交？怎么优化？（字节跳动、货拉拉）
判断两个链表是否相交可以采用多种方法。
一种方法是使用双指针。首先分别遍历两个链表，得到两个链表的长度。然后让长链表的指针先走两个链表长度差的步数。之后，同时移动两个链表的指针，每次比较两个指针是否指向相同的节点。如果指向相同节点，那么这两个链表相交；如果直到指针都走到链表末尾还没有相同节点，那么这两个链表不相交。
// ListNode 定义
static class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public boolean isIntersect(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return false;
}
// 1. 计算两个链表的长度
int lenA = getLength(headA);
int lenB = getLength(headB);
// 2. 让较长的链表先走一段距离，使得两个链表剩余部分长度相同
while (lenA > lenB) {
headA = headA.next;
lenA--;
}
while (lenB > lenA) {
headB = headB.next;
lenB--;
}
// 3. 同时遍历两个链表，检查是否相交
while (headA != null && headB != null) {
if (headA == headB) {
return true; // 相交
}
headA = headA.next;
headB = headB.next;
}
return false; // 不相交
}
// 计算链表的长度
private int getLength(ListNode head) {
int length = 0;
while (head != null) {
length++;
head = head.next;
}
return length;
}
例如，有链表 A 长度为 m，链表 B 长度为 n（假设 m > n）。先让链表 A 的指针先走 m - n 步，然后同时移动 A 和 B 的指针。这种方法的时间复杂度是 O (m + n)，因为需要遍历两个链表来获取长度，然后再同时遍历一部分。
优化的方法可以是使用哈希表。遍历一个链表，将链表中的节点存入哈希表。然后遍历另一个链表，每次检查节点是否在哈希表中。如果在，那么两个链表相交；如果遍历完第二个链表都没有发现相同节点，那么两个链表不相交。这种方法的时间复杂度也是 O (m + n)，但是在平均情况下，哈希表的查找速度很快，可以更快地判断是否相交。
import java.util.HashSet;
public class Solution2 {
// ListNode 定义
static class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public boolean isIntersect(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return false;
}
// 使用哈希集合来存储链表A的所有节点
HashSet<ListNode> nodeSet = new HashSet<>();
// 遍历链表A并将所有节点添加到哈希集合中
ListNode currA = headA;
while (currA != null) {
nodeSet.add(currA);
currA = currA.next;
}
// 遍历链表B，并检查是否存在与链表A中的节点相同的节点
ListNode currB = headB;
while (currB != null) {
if (nodeSet.contains(currB)) {
return true; // 相交
}
currB = currB.next;
}
return false; // 不相交
}
public static void main(String[] args) {
// 创建测试用例
ListNode headA = new ListNode(1);
headA.next = new ListNode(2);
headA.next.next = new ListNode(3);
headA.next.next.next = new ListNode(4);
headA.next.next.next.next = new ListNode(5);
ListNode headB = new ListNode(6);
headB.next = new ListNode(7);
headB.next.next = headA.next.next; // 相交节点是节点 3
Solution2 solution = new Solution2();
System.out.println(solution.isIntersect(headA, headB)); // 输出 true
}
}
手撕冒泡排序（美团）
在面试时，很多公司面试时要手撕冒泡排序，根据这来考察面试者基本功。
冒泡排序（Bubble Sort）是一种简单的排序算法。它通过重复遍历待排序的列表，比较相邻元素并交换它们的位置，直到整个列表排序完成。每次遍历都会把当前未排序部分的最大值“冒泡”到数组的最后。
思路：
- 从数组的第一个元素开始，逐个比较相邻的元素。
- 如果当前元素大于下一个元素，交换它们的位置。
- 每一轮遍历后，最大的元素会被“冒泡”到数组的末尾。
- 每次遍历的长度逐渐减少，因为已经排序好的元素已经“浮到”数组的末尾。
- 直到没有需要交换的元素时，排序完成。
冒泡排序的优化：
- 如果在某次遍历中没有进行交换，说明数组已经是有序的，可以提前结束排序，避免不必要的遍历。
时间复杂度：
- 最坏情况下，时间复杂度为 O(n^2)，即当数组是逆序时。
- 最好情况下（当数组已经是有序的），时间复杂度为 O(n)，因为只会进行一次遍历且没有发生任何交换。
空间复杂度：
- O(1)，因为该算法是原地排序，不需要额外的空间。
Java 完整代码实现：
public class BubbleSort {
public static void main(String[] args) {
// 测试数组
int[] arr = {5, 2, 9, 1, 5, 6};
// 调用冒泡排序
bubbleSort(arr);
// 打印排序后的数组
System.out.println("Sorted array:");
for (int num : arr) {
System.out.print(num + " ");
}
}
// 冒泡排序方法
public static void bubbleSort(int[] arr) {
int n = arr.length;
// 外层循环控制排序的轮数
for (int i = 0; i < n - 1; i++) {
boolean swapped = false; // 标记是否发生了交换
// 内层循环进行相邻元素比较和交换
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果没有发生交换，说明数组已经有序，提前结束
if (!swapped) {
break;
}
}
}
}
代码解释：
- 主方法 (
main)：初始化一个整数数组并调用bubbleSort方法进行排序。排序后打印数组。 - 冒泡排序方法 (
bubbleSort)：- 外层循环控制排序的轮次，每一轮确保将最大的元素“冒泡”到末尾。
- 内层循环执行相邻元素的比较和交换。如果当前元素比下一个元素大，则交换。
swapped是一个标记，用来检查在某一轮遍历中是否发生了交换。如果某轮没有交换，说明数组已经是有序的，可以提前结束排序。
手撕快速排序（作业帮）
快速排序是面试时考察最多的排序算法。快速排序（Quick Sort）是一种常用的排序算法，采用分治法（Divide and Conquer）进行排序。其基本思路是通过选择一个基准元素（pivot），将待排序的数组分成两部分，一部分所有元素都小于基准元素，另一部分所有元素都大于基准元素。然后递归地对这两部分继续进行排序，最终达到排序整个数组的效果。
快速排序的步骤：
- 选择基准元素：选择数组中的一个元素作为基准元素（常见的选择有第一个元素、最后一个元素、随机选择等）。
- 分区操作：将数组分成两部分，小于基准的放左边，大于基准的放右边。基准元素最终的位置已经确定。
- 递归排序：对基准元素左侧和右侧的子数组进行递归调用快速排序，直到子数组的大小为1或0，排序完成。
时间复杂度：
- 最佳情况：
O(n log n)，发生在每次分割时都能平衡地分成两部分。 - 最坏情况：
O(n^2)，当数组已经有序或反向有序时，每次选择的基准元素都可能是最小或最大的元素，从而导致不均匀的分割。 - 平均情况：
O(n log n)，在大多数情况下，快速排序的时间复杂度表现良好。
空间复杂度：
- 快速排序是原地排序，只需要
O(log n)的栈空间来存储递归调用的状态。 - 空间复杂度主要取决于递归的深度，最坏情况下是
O(n)，但平均情况下是O(log n)。
快速排序的Java实现代码：
public class QuickSort {
// 主函数：调用快速排序
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSortHelper(arr, 0, arr.length - 1);
}
// 快速排序的核心递归函数
private static void quickSortHelper(int[] arr, int left, int right) {
if (left < right) {
// 分区操作，返回基准元素的正确位置
int pivotIndex = partition(arr, left, right);
// 递归对基准元素左侧和右侧的子数组排序
quickSortHelper(arr, left, pivotIndex - 1);
quickSortHelper(arr, pivotIndex + 1, right);
}
}
// 分区操作，返回基准元素的最终位置
private static int partition(int[] arr, int left, int right) {
// 选择最右边的元素作为基准元素
int pivot = arr[right];
int i = left - 1; // i 指向比基准小的元素区域的最后一个元素
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
// 交换 arr[i + 1] 和 arr[j]
i++;
swap(arr, i, j);
}
}
// 将基准元素放到正确位置
swap(arr, i + 1, right);
return i + 1; // 返回基准元素的索引
}
// 交换数组中两个元素的位置
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 主函数入口，打印排序后的结果
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 6, 3, 2};
System.out.println("Original array: ");
printArray(arr);
quickSort(arr);
System.out.println("Sorted array: ");
printArray(arr);
}
// 打印数组的辅助函数
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
手撕堆排序（美团）
堆排序（Heap Sort）是一种基于比较的排序算法，利用堆这种数据结构来实现排序。堆是一种完全二叉树，通常用数组来表示。堆排序分为两个步骤：构建最大堆和不断将堆顶元素与末尾元素交换，再进行堆调整。
思路：
- 构建最大堆：首先要将数组转化为一个最大堆。最大堆的特点是父节点的值大于等于其左右子节点的值。通过调整从最后一个非叶子节点开始，向上调整整个堆。
- 堆排序过程：
- 将堆顶元素（最大值）与堆的最后一个元素交换。
- 然后将堆的大小减1，调用堆调整操作（heapify）恢复堆的性质，继续重复上述过程，直到堆的大小为1。
时间复杂度：
- 构建堆：O(n)。
- 从最后一个非叶子节点开始调整，每次调整的时间是 O(log n)，一共进行 n/2 次调整，因此时间复杂度是 O(n)。
- 堆排序过程：每次需要调整堆结构，进行 n 次交换，每次调整堆的时间复杂度是 O(log n)，所以堆排序的时间复杂度是 O(n log n)。
空间复杂度：
- 堆排序是原地排序算法，它不需要额外的空间来存储数据。时间复杂度是 O(1)。
Java代码实现：
public class HeapSort {
// 堆化操作，维护堆的性质
public static void heapify(int[] arr, int n, int i) {
int largest = i; // 初始化父节点为最大值
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点比父节点大
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点比父节点大
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是父节点，交换并继续堆化
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// 递归堆化
heapify(arr, n, largest);
}
}
// 堆排序
public static void heapSort(int[] arr) {
int n = arr.length;
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 一个个地把最大元素移动到数组末尾
for (int i = n - 1; i >= 1; i--) {
// 将当前堆的根节点与末尾元素交换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 调整堆
heapify(arr, i, 0);
}
}
// 输出数组
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
// 主函数
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("Original array:");
printArray(arr);
heapSort(arr);
System.out.println("Sorted array:");
printArray(arr);
}
}
手撕归并排序（美团）
归并排序的思路：
- 分解（Divide）：将待排序的数组分成两半，递归地对这两半分别进行归并排序。
- 解决（Conquer）：对分解出的子数组继续进行排序，直到每个子数组只有一个元素（因为一个元素自然是有序的）。
- 合并（Combine）：将排序后的子数组合并成一个有序的大数组。合并是归并排序的核心步骤。
归并排序的时间复杂度与空间复杂度：
- 时间复杂度：
- 归并排序的时间复杂度是 O(nlogn)，无论是最坏情况、最佳情况还是平均情况。这里的 n 是待排序元素的数量，logn 是因为每次递归将数组分成两半，直到数组大小为1。
- 每一层递归的合并操作是线性时间复杂度O(n)，递归深度是logn，所以总的时间复杂度是 O(nlogn)。
- 空间复杂度：
- 归并排序需要额外的空间来存储合并过程中的中间结果，空间复杂度为O(n)。
- 在递归调用过程中，每次递归调用栈的深度是logn，但归并过程中需要额外的存储空间来存储中间的合并结果，所以总空间复杂度是 O(n)。
归并排序的Java实现：
public class MergeSort {
// 归并排序函数
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 调用辅助函数进行递归排序
mergeSortHelper(arr, 0, arr.length - 1);
}
// 递归的归并排序方法
private static void mergeSortHelper(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // 防止溢出
mergeSortHelper(arr, left, mid); // 排序左半部分
mergeSortHelper(arr, mid + 1, right); // 排序右半部分
merge(arr, left, mid, right); // 合并两部分
}
}
// 合并两个有序子数组
private static void merge(int[] arr, int left, int mid, int right) {
// 创建临时数组存储合并结果
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
// 合并两个有序子数组
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 如果左半部分有剩余元素，直接复制到temp数组
while (i <= mid) {
temp[k++] = arr[i++];
}
// 如果右半部分有剩余元素，直接复制到temp数组
while (j <= right) {
temp[k++] = arr[j++];
}
// 将临时数组的内容拷贝回原数组
System.arraycopy(temp, 0, arr, left, temp.length);
}
// 测试归并排序
public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10};
System.out.println("排序前: ");
printArray(arr);
mergeSort(arr);
System.out.println("排序后: ");
printArray(arr);
}
// 打印数组
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
手撕二分查找(VIVO)
二分查找是一种在有序数组中查找特定元素的高效算法。其基本思路是通过逐步缩小查找范围来找到目标元素。每次将查找范围的中间元素与目标元素进行比较，根据比较结果决定继续查找左半部分还是右半部分。
二分查找的实现思路：
- 输入：一个有序数组
arr和一个目标值target。 - 初始化：设置两个指针，
left和right，分别指向数组的左右两端（即left = 0，right = arr.length - 1）。 - 循环查找：
- 计算中间位置
mid = left + (right - left) / 2。 - 如果
arr[mid] == target，则找到了目标值，返回mid（即元素的索引）。 - 如果
arr[mid] < target，说明目标值可能在右半部分，将left移动到mid + 1。 - 如果
arr[mid] > target，说明目标值可能在左半部分，将right移动到mid - 1。
- 计算中间位置
- 退出条件：如果
left超过了right，说明数组中没有目标元素，返回-1。
时间复杂度与空间复杂度分析：
- 时间复杂度：O(log n)，每次查找将问题的规模减少一半，因此时间复杂度为对数级别。
- 空间复杂度：O(1)，使用常数空间，只需要几个额外的变量（
left、right和mid）来存储指针，没有使用额外的空间。
Java 完整代码实现：
public class BinarySearch {
// 二分查找函数
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
// 进行二分查找
while (left <= right) {
// 计算中间索引
int mid = left + (right - left) / 2;
// 检查中间元素是否为目标值
if (arr[mid] == target) {
return mid; // 找到目标，返回其索引
}
// 如果目标值大于中间元素，则调整搜索范围为右半部分
if (arr[mid] < target) {
left = mid + 1;
}
// 如果目标值小于中间元素，则调整搜索范围为左半部分
else {
right = mid - 1;
}
}
// 目标值不存在于数组中，返回 -1
return -1;
}
// 主函数，用于测试
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int target = 7;
// 调用二分查找方法
int result = binarySearch(arr, target);
if (result != -1) {
System.out.println("目标元素 " + target + " 在数组中的索引是: " + result);
} else {
System.out.println("目标元素 " + target + " 不在数组中");
}
}
}
海量数据找出前K大（新浪）
对于海量数据找出前 K大元素，可以使用最小堆的方法，以下是 Java 实现：
import java.util.PriorityQueue;
public class TopK {
public static int[] findTopK(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
for (int num : nums) {
if (minHeap.size() < k) {
minHeap.offer(num);
} else if (num > minHeap.peek()) {
minHeap.poll();
minHeap.offer(num);
}
}
int[] result = new int[k];
int i = 0;
while (!minHeap.isEmpty()) {
result[i++] = minHeap.poll();
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 10, 5, 20, 15, 8, 30, 25, 12, 18, 22};
int k = 3;
int[] topK = findTopK(nums, k);
for (int num : topK) {
System.out.print(num + " ");
}
}
}
代码解释：
- 首先创建一个大小为
k的最小堆（优先队列）。 - 遍历数组，如果堆的大小小于
k，将元素添加到堆中；如果元素大于堆顶元素，先弹出堆顶元素，再将该元素添加到堆中。 - 最终堆中存储的就是前
k大的元素。
以上代码和方法能够有效地解决相应的链表和海量数据问题，通过合理利用数据结构和算法，可以提高程序的性能和准确性。
字符串的全排列（要求去重）（字节跳动）
在面试中，字符串的全排列问题是一个经典的面试题，要求生成一个字符串的所有全排列，且去重。这个问题可以通过回溯法（Backtracking）来实现，同时利用一个 HashSet 来避免重复的排列。
- 问题理解
给定一个字符串，要求输出该字符串的所有可能的排列（排列需要去重），并且考虑到字符串可能包含重复字符，结果中的排列也应该去重。
- 思路分析
使用回溯法生成所有可能的排列。回溯法的核心思想是递归地交换字符，在每一层递归中交换一个字符到当前位置，并继续处理剩下的部分。为了避免重复的排列，可以在递归过程中使用一个 HashSet 来记录已经生成的排列。
步骤：
- 排序：首先对字符串进行排序，可以帮助我们提前跳过重复字符。例如，如果字符串是 "AAB"，排序后是 "AAB"，这样我们可以确保在递归过程中只处理一遍相同的字符。
- 回溯法生成排列：在递归中，每次交换一个字符到当前位置，然后递归处理剩余部分。
- 在交换字符时，检查该字符是否已经在当前位置的前面出现过，如果出现过则跳过。
- 去重：为了避免重复的排列结果，我们可以使用一个
HashSet来记录所有已生成的排列（字符串形式）。 - 时间复杂度和空间复杂度
- 时间复杂度：生成排列的总数是
n!，其中n是字符串的长度。每次递归交换的时间复杂度是 O(n)，因此总体时间复杂度为O(n * n!)。 - 空间复杂度：空间复杂度主要由递归栈和存储结果的集合组成。递归栈的深度最大为
n，存储结果的集合最多保存n!个排列，因此空间复杂度为O(n * n!)。
- Java代码实现
import java.util.*;
public class Solution {
public List<String> permuteUnique(String s) {
// 用一个列表保存结果
List<String> result = new ArrayList<>();
// 将字符串转换为字符数组并排序，排序后有助于去重
char[] chars = s.toCharArray();
Arrays.sort(chars);
// 结果集合，用来存储去重后的排列
Set<String> set = new HashSet<>();
// 通过回溯法生成排列
backtrack(chars, 0, result, set);
// 将集合转换为列表返回
return new ArrayList<>(set);
}
private void backtrack(char[] chars, int index, List<String> result, Set<String> set) {
// 当到达字符数组的最后一位时，生成一个排列
if (index == chars.length) {
String permutation = new String(chars);
set.add(permutation); // 将当前排列加入结果集合
return;
}
// 遍历每个字符
for (int i = index; i < chars.length; i++) {
// 如果当前字符和前一个字符相同，跳过（避免重复排列）
if (i > index && chars[i] == chars[i - 1]) {
continue;
}
// 交换字符
swap(chars, i, index);
// 递归处理
backtrack(chars, index + 1, result, set);
// 回溯，恢复交换前的状态
swap(chars, i, index);
}
}
// 辅助函数：交换字符数组中的两个字符
private void swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "AAB";
List<String> result = solution.permuteUnique(s);
for (String str : result) {
System.out.println(str);
}
}
}
求一个字符串中最长不重复子串的长度（字节跳动）
这是一个常见的面试题，要求找到字符串中最长的不重复子串的长度。我们可以使用 滑动窗口 和 哈希集合 的方法来有效地解决这个问题。
思路：
- 滑动窗口：我们通过维护一个窗口来追踪当前不重复的子串。窗口的左边和右边分别由两个指针表示，我们通过右指针来扩展窗口，左指针则会根据需要收缩窗口。
- 哈希集合：为了高效检查一个字符是否已经在当前窗口中，我们可以使用哈希集合来存储窗口中的字符。
- 当我们遇到重复字符时，左指针会移动到重复字符之后的位置，确保窗口内的字符不重复。
具体步骤：
- 初始化一个空的哈希集合，用于存储当前窗口内的字符。
- 使用两个指针：
left和right。right用于扩展窗口，left用于收缩窗口。 - 如果当前字符（
s[right]）不在哈希集合中，表示没有重复字符，将其加入集合，并更新最大长度。 - 如果当前字符已经在集合中，移动
left指针，直到窗口中的字符没有重复。 - 每次移动
right指针时，更新当前窗口的最大长度。
时间复杂度：
- 时间复杂度是 O(n)，其中
n是字符串的长度。因为每个字符最多只会被访问两次（一次通过右指针，另一次通过左指针）。
空间复杂度：
- 空间复杂度是 O(min(n, m))，其中
n是字符串的长度，m是字符集的大小（对于英语字符集而言，m通常是常数 256）。
Java 代码实现：
import java.util.HashSet;
public class LongestUniqueSubstring {
public static int lengthOfLongestSubstring(String s) {
// 用一个哈希集合来记录当前窗口内的字符
HashSet<Character> set = new HashSet<>();
int left = 0; // 滑动窗口的左指针
int maxLength = 0; // 记录最长子串的长度
// 遍历字符串
for (int right = 0; right < s.length(); right++) {
// 当右指针指向的字符已经在集合中，收缩窗口
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++;
}
// 将当前字符加入集合
set.add(s.charAt(right));
// 更新最大长度
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
public static void main(String[] args) {
String s = "abcabcbb";
System.out.println("The length of the longest substring without repeating characters is: "
+ lengthOfLongestSubstring(s)); // Output: 3 ("abc")
}
}
反转字符串的单词：如何在原字符串上翻转字符串（如将 "i am student" 翻转为 "student am i"），要求空间复杂度为 O (1)？（字节跳动、美团、滴滴）
要在空间复杂度为 O (1) 的情况下翻转原字符串，可以通过多次翻转子串来实现。
首先，将整个字符串进行翻转。例如，对于字符串 "i am student"，翻转后得到 "tneduts ma i"。可以通过双指针的方法来实现，一个指针指向字符串的开头，另一个指针指向字符串的末尾，然后交换两个指针所指向的字符，并且向中间移动指针，直到两个指针相遇。
接着，对每个单词进行翻转。在翻转后的字符串 "tneduts ma i" 中，我们需要将单词翻转回正确的顺序。可以通过再次使用双指针的方式，找到每个单词的开始和结束位置，然后对每个单词进行翻转。例如，找到第一个单词的开始位置是 0，结束位置是 6（索引从 0 开始），将这个单词 "tneduts" 翻转回 "student"。
以下是一个简单的 Java 实现代码：
class StringReverser {
public static void reverseString(char[] s) {
int left = 0;
int right = s.length - 1;
// 翻转整个字符串
while (left < right) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
int start = 0;
for (int i = 0; i <= s.length; i++) {
if (i == s.length || s[i] == ' ') {
int end = i - 1;
// 翻转每个单词
while (start < end) {
char tempWord = s[start];
s[start] = s[end];
s[end] = tempWord;
start++;
end--;
}
start = i + 1;
}
}
}
}
可以通过以下方式调用这个方法：
public class Main {
public static void main(String[] args) {
char[] str = "i am student".toCharArray();
StringReverser.reverseString(str);
System.out.println(new String(str));
}
}
这样就可以在原字符串上，以空间复杂度为 O (1) 的方式翻转字符串。这种方法主要是巧妙地利用了字符数组的原地操作，通过多次双指针的交换来达到翻转的目的。
压缩字符串题wsssgkeghh 变为 w3sgkeg2h（云从科技）
对于将类似 “wsssgkeghh” 这样的字符串压缩为 “w3sgkeg2h” 的问题，我们可以通过遍历字符串并统计连续出现相同字符的个数来实现。以下是一种常见的解决思路和具体的实现步骤。
首先，我们可以使用双指针的方法来处理字符串。定义两个指针，一个指针（我们暂且称为慢指针）用于标记当前正在处理的字符分组的起始位置，另一个指针（快指针）用于向前遍历字符串，去发现连续相同字符的范围。
例如，对于输入的字符串 “wsssgkeghh”，一开始慢指针和快指针都指向第一个字符‘w’。然后快指针开始向后移动，当快指针指向的字符和慢指针指向的字符不同时，就意味着一个连续相同字符的分组结束了。在这个过程中，我们可以通过计算快指针和慢指针的位置差来得到这个字符连续出现的次数。
以 “wsssgkeghh” 为例，快指针从‘w’开始移动，当遇到第二个‘s’时，发现与起始的‘w’不同了，此时快指针和慢指针的位置差为 1（因为只出现了 1 次‘w’），由于只出现了 1 次，我们不需要对‘w’进行压缩，直接将‘w’添加到结果字符串中即可。
接着，快指针继续移动，当遇到‘g’时，意味着连续的‘s’字符分组结束了，此时快指针和慢指针的位置差为 3，说明‘s’连续出现了 3 次，我们就把‘w’和 “3s” 添加到结果字符串中（这里先添加‘w’是因为前面已经判断过它属于上一个不同的字符分组了）。
然后，继续这个过程，对于后面的 “keghh” 部分，同理，当遇到不同字符时统计前面连续字符出现的次数并添加到结果字符串中，像遇到第二个‘h’时，‘h’连续出现了 2 次，就把 “eg2h” 添加到结果字符串中。
以下是使用 Java 语言实现的代码示例：
public class StringCompression {
public static String compressString(String input) {
if (input == null || input.length() == 0) {
return input;
}
StringBuilder result = new StringBuilder();
int slow = 0;
int fast = 0;
while (fast < input.length()) {
while (fast < input.length() && input.charAt(fast) == input.charAt(slow)) {
fast++;
}
int count = fast - slow;
if (count > 1) {
result.append(count);
}
result.append(input.charAt(slow));
slow = fast;
}
return result.toString();
}
public static void main(String[] args) {
String input = "wsssgkeghh";
String compressed = compressString(input);
System.out.println(compressed);
}
}
单链表反转（贝壳）
单链表反转是常见的面试题目之一，下面是关于如何反转一个单链表的思路、时间和空间复杂度分析以及完整的 Java 代码实现。
思路
单链表反转的关键在于改变每个节点的指向，使得原来指向下一个节点的指针指向前一个节点。为了做到这一点，我们可以通过迭代的方式来逐个调整节点的指针。
具体步骤：
- 初始化三个指针：
prev：指向前一个节点，初始化为null。curr：指向当前节点，初始化为链表的头节点。next：指向当前节点的下一个节点，初始化为null。
- 遍历链表：
- 每次保存
curr的下一个节点 (next = curr.next)。 - 将当前节点的
next指向prev（反转指向）。 - 将
prev移动到curr，将curr移动到next，继续遍历。
- 每次保存
- 完成遍历后，****
prev会指向新链表的头节点。
时间复杂度
- 时间复杂度：O(n)，其中 n 是链表的长度。我们需要遍历一次整个链表。
- 空间复杂度：O(1)，我们只用了常数空间来存储指针，不需要额外的空间。
Java 完整代码实现
public class Solution {
// 定义链表节点
static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
// 反转链表的函数
public static ListNode reverseList(ListNode head) {
ListNode prev = null; // 初始化前一个节点为null
ListNode curr = head; // 当前节点从头节点开始
while (curr != null) {
ListNode next = curr.next; // 保存下一个节点
curr.next = prev; // 反转当前节点的指针
prev = curr; // 前一个节点移动到当前节点
curr = next; // 当前节点移动到下一个节点
}
return prev; // prev最终会是新的头节点
}
// 打印链表的辅助函数
public static void printList(ListNode head) {
ListNode curr = head;
while (curr != null) {
System.out.print(curr.val + " -> ");
curr = curr.next;
}
System.out.println("null");
}
public static void main(String[] args) {
// 创建一个链表：1 -> 2 -> 3 -> 4 -> 5 -> null
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
// 打印原链表
System.out.println("Original list:");
printList(head);
// 反转链表
ListNode reversedHead = reverseList(head);
// 打印反转后的链表
System.out.println("Reversed list:");
printList(reversedHead);
}
}
反转链表中前 K 个节点
反转链表中前 K 个节点的问题可以通过以下步骤来解决：
- 反转链表的前 K 个节点。
- 保持链表的剩余部分不变。
- 调整链表中的指针，使得原链表的结构恢复正确。
假设我们有一个链表节点 ListNode，它定义如下：
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
解题思路：
- 链表结构：
- 我们有一个单链表，定义为
ListNode类型。每个节点包含一个值val和指向下一个节点的指针next。 - 目标是反转链表中前
k个节点，并对每一组长度为k的节点进行反转，直到链表遍历完。
- 我们有一个单链表，定义为
- 关键步骤：
- 判断当前段是否满
k个节点： 在反转之前，我们必须确认当前的节点数是否足够k个。如果不足，直接跳过该段，保持原链表顺序。 - 反转当前
k个节点： 如果当前段正好有k个节点，我们就进行反转。 - 连接反转后的链表： 反转后的链表需要和之前的链表正确连接，以保证链表结构的完整性。
- 判断当前段是否满
- 具体步骤：
- 维护一个
dummy虚拟节点，它的next指针指向链表头。这样可以避免链表头部的特殊情况处理，使得头节点的反转与其他节点反转保持一致。 - 使用
prevGroupEnd指针来标记上一个反转段的最后一个节点，它在反转完成后需要连接到当前反转段的最后一个节点。 - 对每一组长度为
k的节点进行反转。具体做法是使用prev和curr两个指针，通过迭代的方式完成每组的反转。 - 完成一组反转后，更新
prevGroupEnd和head，继续处理下一组。
- 维护一个
- 终止条件：
- 当链表遍历完，或者剩下的节点不足
k个时，停止反转操作。
- 当链表遍历完，或者剩下的节点不足
package com.zg.suppledata.utils;
public class ReverseNodes {
public ListNode reverseKGroup(ListNode head, int k) {
// 如果链表为空或 k 为 1，直接返回头节点
if (head == null || k == 1) return head;
// 虚拟头节点，方便处理边界情况
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prevGroupEnd = dummy; // prevGroupEnd: 反转前一组的最后一个节点
// 遍历链表，逐组反转
while (head != null) {
// 找到当前组的最后一个节点
ListNode groupEnd = head;
int count = 1;
while (groupEnd != null && count < k) {
groupEnd = groupEnd.next;
count++;
}
// 如果当前组的节点数不足 K 个，则不需要反转
if (groupEnd == null) break;
// 暂存下一个组的起始节点
ListNode nextGroupStart = groupEnd.next;
// 断开当前组的链接，开始反转
ListNode prev = nextGroupStart;
ListNode curr = head;
while (curr != nextGroupStart) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
// 连接当前反转后的组
prevGroupEnd.next = groupEnd;
head.next = nextGroupStart;
// 更新 prevGroupEnd 和 head
prevGroupEnd = head;
head = nextGroupStart;
}
return dummy.next; // 返回新的头节点
}
// 辅助方法：打印链表
public void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
ReverseNodes solution = new ReverseNodes();
// 创建一个链表 1 -> 2 -> 3 -> 4 -> 5
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
int k = 3;
// 输出原链表
System.out.print("Original List: ");
solution.printList(head);
// 调用反转链表前 K 个节点的方法
ListNode newHead = solution.reverseKGroup(head, k);
// 输出反转后的链表
System.out.print("List after reversing first " + k + " nodes: ");
solution.printList(newHead);
}
}
链表判环，找入口（新浪）
以下是判断链表是否有环以及找出环入口的 Java 代码：
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
public class LinkedListCycle {
// 判断链表是否有环
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head;
while (fast!= null && fast.next!= null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
// 找出环的入口
public ListNode findCycleEntry(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
boolean hasCycle = false;
while (fast!= null && fast.next!= null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
hasCycle = true;
break;
}
}
if (!hasCycle) {
return null;
}
slow = head;
while (slow!= fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
public static void main(String[] args) {
// 创建一个有环的链表
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node3;
LinkedListCycle solution = new LinkedListCycle();
boolean hasCycle = solution.hasCycle(node1);
System.out.println("是否有环: " + hasCycle);
ListNode entry = solution.findCycleEntry(node1);
if (entry!= null) {
System.out.println("环的入口节点值: " + entry.val);
} else {
System.out.println("无环");
}
}
}
代码解释：
- 判断是否有环：使用快慢指针，快指针每次走两步，慢指针每次走一步，如果它们相遇，说明有环。
- 找出环入口：当判断出有环后，将慢指针重新指向头节点，然后快慢指针同时以相同速度移动，再次相遇的节点就是环的入口。
删除字符串中的字符。
要删除字符串中的字符，可以有多种实现思路和方法，以下是一些常见的做法。
一种是基于遍历和重新构建字符串的方式。
假设我们要删除的是给定字符串中的某个特定字符或者某些特定字符集合。可以通过循环遍历原字符串的每一个字符，在遍历过程中，判断当前字符是否是要删除的字符，如果不是，就将其添加到一个新的字符串或者字符数组（后续可以转换为字符串）中。
例如，在 Java 中，可以这样写代码实现删除指定字符的功能：
public String deleteChar(String s, char target) {
StringBuilder result = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i)!= target) {
result.append(s.charAt(i));
}
}
return result.toString();
}
这里通过 StringBuilder 来构建新的字符串，遍历原字符串 s，当遇到字符不等于要删除的目标字符 target 时，就将其添加到 StringBuilder 中，最后返回构建好的新字符串，就实现了删除指定字符的功能。
求数组的全排列（VIVO）
思路：
要获取一个数组的全排列，我们可以利用回溯算法。具体来说，回溯算法通过递归的方式逐步生成排列，在每一步都将一个元素加入排列中，然后在下一步递归中排除已选元素，回溯的时候撤销选择，尝试其他可能。
步骤：
- 递归生成排列：
- 使用一个辅助数组来记录当前的排列。
- 对于每个位置，我们尝试填充每一个可能的元素，并递归地填充后续的位置。
- 使用回溯的方式，在完成一个排列后，撤回当前选择，继续尝试其他可能性。
- 交换元素：
- 通过交换数组中的元素来生成排列，而不是额外使用空间存储状态。这样可以减少空间复杂度。
时间复杂度：
- 生成全排列的时间复杂度是 O(n!)，因为每个元素都需要和其他元素交换一遍，排列的总数为 n!。
空间复杂度：
- 空间复杂度是 O(n)，因为递归调用栈的深度是 n（每次递归深度为数组的长度），且我们只需要常数空间来交换数组元素。
Java 代码实现：
import java.util.ArrayList;
import java.util.List;
public class Permutations {
// 主函数，返回所有的全排列
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, new ArrayList<>(), result, new boolean[nums.length]);
return result;
}
// 回溯函数，生成排列
private void backtrack(int[] nums, List<Integer> current, List<List<Integer>> result, boolean[] used) {
// 当当前排列的长度等于nums的长度时，说明找到了一个全排列
if (current.size() == nums.length) {
result.add(new ArrayList<>(current));
return;
}
// 遍历nums数组中的每个元素
for (int i = 0; i < nums.length; i++) {
// 如果该元素已经被使用过，则跳过
if (used[i]) continue;
// 做选择，标记当前元素为已使用
used[i] = true;
current.add(nums[i]);
// 递归生成剩余的排列
backtrack(nums, current, result, used);
// 撤销选择，回溯
used[i] = false;
current.remove(current.size() - 1);
}
}
// 测试主函数
public static void main(String[] args) {
Permutations solution = new Permutations();
int[] nums = {1, 2, 3};
List<List<Integer>> result = solution.permute(nums);
// 打印结果
for (List<Integer> perm : result) {
System.out.println(perm);
}
}
}
合并两个有序数组或有序链表（字节跳动、货拉拉）
思路：
- 双指针法：我们使用两个指针分别指向两个数组的起始位置。
- 比较大小：每次比较两个数组当前指针指向的元素，将较小的元素加入到结果数组中，并移动对应的指针。
- 处理剩余元素：当其中一个数组的所有元素都被合并到结果数组中时，另一个数组剩余的元素直接追加到结果数组中。
关键点：
- 如果两个数组的长度分别为
n和m，那么合并的时间复杂度是O(n + m)，因为每个元素只会被处理一次。 - 空间复杂度是
O(n + m)，因为我们需要一个新的数组来存储结果。
时间复杂度：
- 时间复杂度：
O(n + m)，其中n和m分别是两个数组的长度。我们需要遍历两个数组的每个元素一次。
空间复杂度：
- 空间复杂度：
O(n + m)，因为我们需要一个新的数组来存储合并后的结果。
合并两个有序数组Java代码实现：
public class MergeSortedArrays {
// 合并两个有序数组
public static int[] merge(int[] arr1, int[] arr2) {
// 创建一个新数组，大小为两个数组之和
int n = arr1.length;
int m = arr2.length;
int[] result = new int[n + m];
int i = 0, j = 0, k = 0;
// 合并两个数组，直到有一个数组遍历完
while (i < n && j < m) {
if (arr1[i] <= arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}
// 将剩余元素添加到结果数组中
while (i < n) {
result[k++] = arr1[i++];
}
while (j < m) {
result[k++] = arr2[j++];
}
return result;
}
public static void main(String[] args) {
int[] arr1 = {1, 3, 5, 7};
int[] arr2 = {2, 4, 6, 8};
int[] mergedArray = merge(arr1, arr2);
// 打印合并后的数组
System.out.print("Merged array: ");
for (int num : mergedArray) {
System.out.print(num + " ");
}
}
}
合并两个有序链表Java代码实现：
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class MergeSortedListNodes {
// Definition for singly-linked list.
// 合并两个有序链表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 创建一个虚拟头节点，简化链表操作
ListNode dummy = new ListNode(0);
ListNode current = dummy;
// 遍历两个链表，直到其中一个链表为空
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;
}
// 如果 l1 还有剩余节点，直接连接到合并链表的尾部
if (l1 != null) {
current.next = l1;
} else if (l2 != null) {
current.next = l2;
}
// 返回合并后的链表，跳过虚拟头节点
return dummy.next;
}
// 辅助方法：打印链表
public void printList(ListNode head) {
ListNode current = head;
while (current != null) {
System.out.print(current.val + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
MergeSortedListNodes solution = new MergeSortedListNodes();
// 创建两个有序链表 l1 和 l2
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 = solution.mergeTwoLists(l1, l2);
// 打印合并后的链表
solution.printList(mergedList);
}
}
输出 2 到 N 之间的全部（VIVO）
在面试时，要求输出 2 到 N 之间的所有素数是一个经典的问题，通常会考察应聘者对算法和时间空间复杂度的理解。下面是思路的详细解释，以及 Java 代码实现。
思路
- 素数定义：素数是大于1的自然数，且仅能被1和自身整除。
- 方法选择：
- 最直接的解法是对于每个数字
i，判断它是否为素数。这个判断过程是通过检查i是否能被小于等于i的所有整数整除来完成。显然，时间复杂度较高。 - 更高效的方法是 埃拉托斯特尼筛法（Sieve of Eratosthenes）。该方法的思想是：从2开始，将所有2的倍数标记为非素数，然后依次处理3、4、5等，直到处理到 √N 为止。这个方法能够有效减少判断素数的次数。
- 最直接的解法是对于每个数字
时间复杂度和空间复杂度分析
- 埃拉托斯特尼筛法的时间复杂度：
- 时间复杂度是
O(N log log N)，这个复杂度是通过逐步标记每个合数来实现的，比暴力方法要高效得多。
- 时间复杂度是
- 空间复杂度：
- 空间复杂度是
O(N)，因为我们需要一个大小为 N 的布尔数组来存储每个数是否是素数。
- 空间复杂度是
Java 实现（埃拉托斯特尼筛法）
import java.util.ArrayList;
import java.util.List;
public class PrimeNumbers {
// 埃拉托斯特尼筛法：输出2到N之间的素数
public static List<Integer> sieveOfEratosthenes(int N) {
// 布尔数组，true表示该数是素数，false表示该数不是素数
boolean[] isPrime = new boolean[N + 1];
// 初始时，所有数字都假设为素数
for (int i = 2; i <= N; i++) {
isPrime[i] = true;
}
// 从2开始，标记所有合数
for (int i = 2; i * i <= N; i++) {
if (isPrime[i]) {
// 如果i是素数，将i的所有倍数标记为非素数
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
// 收集所有素数
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= N; i++) {
if (isPrime[i]) {
primes.add(i);
}
}
return primes;
}
public static void main(String[] args) {
int N = 50; // 可以根据需要修改N的值
List<Integer> primes = sieveOfEratosthenes(N);
// 输出素数
System.out.println("2到" + N + "之间的素数：");
for (int prime : primes) {
System.out.print(prime + " ");
}
}
}