Java口试黄金宝典16
1. 各种排序算法的时间复杂度和空间复杂度冒泡排序
[*]界说：
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再须要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢 “浮” 到数列的顶端。
[*]要点：
[*]每一轮比较都会将最大（或最小）的元素 “浮” 到数列的末尾。
[*]比较相邻的元素，如果顺序错误就把它们交换过来。
[*]时间复杂度：
[*]最好环境：O(n)。当数列已经有序时，只需遍历一次，不须要进行交换操纵。
[*]最坏环境宁静均环境：O(n2)。因为须要进行两层嵌套循环，对于长度为 n 的数列，比较次数约为 n(n−1)/2。
[*]空间复杂度：O(1)。只须要常数级的额外空间，用于交换元素时的临时变量。
[*]应用：
可以通过设置标记位来优化冒泡排序。当某一轮没有发生交换时，说明数列已经有序，提前结束排序。以下是优化后的代码示例：
java
public class OptimizedBubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr > arr) {
// 交换 arr 和 arr
int temp = arr;
arr = arr;
arr = temp;
swapped = true;
}
}
// 如果没有发生交换，说明数组已经有序
if (!swapped) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
选择排序
[*]界说：
选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部元素均排序完毕。
[*]要点：
[*]每次选择最小（或最大）的元素进行交换。
[*]从未排序序列中找到最小（或最大）元素，与未排序序列的第一个元素交换。
[*]时间复杂度：最好、最坏宁静均环境都是 O(n2)。因为无论数列初始状态如何，都须要进行两层嵌套循环来选择最小（或最大）元素。
[*]空间复杂度：O(1)。只须要常数级的额外空间，用于交换元素时的临时变量。
[*]应用：
可以考虑使用堆来优化选择排序，即堆排序。堆排序使用堆这种数据结构，将选择最小（或最大）元素的时间复杂度从 O(n) 降低到 O(logn)。
插入排序
[*]界说：
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
[*]要点：
[*]逐渐构建有序序列。
[*]将未排序数据插入到已排序序列的合适位置。
[*]时间复杂度：
[*]最好环境：O(n)。当数列已经有序时，只需遍历一次，不须要进行插入操纵。
[*]最坏环境宁静均环境：O(n2)。因为在最坏环境下，每次插入都须要将元素移动到序列的最前面。
[*]空间复杂度：O(1)。只须要常数级的额外空间，用于临时存储待插入的元素。
[*]应用：
可以使用二分查找来优化插入排序中查找插入位置的过程。二分查找可以将查找插入位置的时间复杂度从 O(n) 降低到 O(logn)。以下是使用二分查找优化后的插入排序代码示例：
java
public class BinaryInsertionSort {
public static void binaryInsertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr;
int left = 0;
int right = i - 1;
// 使用二分查找找到插入位置
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr > key) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// 移动元素
for (int j = i - 1; j >= left; j--) {
arr = arr;
}
// 插入元素
arr = key;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
binaryInsertionSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
快速排序
[*]界说：
快速排序是一种分治的排序算法。它选择一个基准值，将数组分为两部门，使得左边部门的全部元素都小于等于基准值，右边部门的全部元素都大于等于基准值，然后分别对左右两部门递归地进行排序。
[*]要点：
[*]选择合适的基准值是关键。
[*]分区操纵将数组分为两部门。
[*]时间复杂度：
[*]最好环境宁静均环境：O(nlogn)。每次分区都能将数组大抵分成两部门，递归深度为 logn，每层须要 O(n) 的时间进行分区操纵。
[*]最坏环境：O(n2)。当基准值选择不当，如数组已经有序时，每次分区只能将数组分成一个元素和其他元素两部门，递归深度为 n。
[*]空间复杂度：
[*]平均环境：O(logn)。递归调用栈的深度平均为 logn。
[*]最坏环境：O(n)。当递归深度到达 n 时，栈空间的使用量为 O(n)。
[*]应用：
可以接纳随机选择基准值、三数取中等方法来避免最坏环境的发生。随机选择基准值可以使最坏环境发生的概率降低；三数取中是指选择数组的第一个元素、中心元素和最后一个元素中的中位数作为基准值。
归并排序
[*]界说：
归并排序是接纳分治法的一个非常典型的应用。它将数组分成两个子数组，分别对两个子数组进行排序，然后将排好序的子数组归并成一个最终的有序数组。
[*]要点：
[*]分治思想，将大问题分解为小问题。
[*]归并操纵是关键，须要将两个有序子数组归并成一个有序数组。
[*]时间复杂度：最好、最坏宁静均环境都是 O(nlogn)。因为每次将数组分成两部门，递归深度为 logn，每层须要 O(n) 的时间进行归并操纵。
[*]空间复杂度：O(n)。须要额外的空间来归并子数组，用于临时存储归并后的结果。
[*]应用：
可以接纳迭代的方式实现归并排序，避免递归调用栈的开销。迭代实现的归并排序从最小的子数组开始归并，渐渐扩大归并的范围。
堆排序
[*]界说：
堆排序使用堆这种数据结构，先将数组构建成一个最大堆（或最小堆），然后依次将堆顶元素与数组末尾元素交换，并调解堆，直到整个数组有序。
[*]要点：
[*]堆的构建和调解操纵。
[*]最大堆（或最小堆）的性子：每个节点的值都大于（或小于）其子节点的值。
[*]时间复杂度：最好、最坏宁静均环境都是 O(nlogn)。构建堆的时间复杂度为 O(n)，每次调解堆的时间复杂度为 O(logn)，须要进行 n 次调解。
[*]空间复杂度：O(1)。只须要常数级的额外空间，用于交换元素时的临时变量。
[*]应用：
堆排序可以用于解决一些与优先队列干系的问题，如找出数组中的前 k 大（或小）的元素。
2. Dijkstra (求最短路径)
[*]界说
Dijkstra 算法是一种贪默算法，用于求解带权有向图或无向图中单个源点到其他全部顶点的最短路径。它的根本思想是：从源点开始，渐渐扩展到距离源点近来的顶点，更新这些顶点到源点的最短距离，直到全部顶点都被访问过。
[*]要点
[*]使用一个优先队列（最小堆）来存储待处理的顶点，优先处理距离源点近来的顶点。
[*]维护一个距离数组，纪录每个顶点到源点的最短距离。
[*]标记已访问的顶点，避免重复处理。
代码示例
java
import java.util.*;
class Dijkstra {
static final int INF = Integer.MAX_VALUE;
public static int[] dijkstra(int[][] graph, int src) {
int n = graph.length;
int[] dist = new int;
boolean[] visited = new boolean;
Arrays.fill(dist, INF);
dist = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a - b);
pq.offer(new int[]{src, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int u = curr;
if (visited) continue;
visited = true;
for (int v = 0; v < n; v++) {
if (!visited && graph != 0 && dist != INF && dist + graph < dist) {
dist = dist + graph;
pq.offer(new int[]{v, dist});
}
}
}
return dist;
}
public static void main(String[] args) {
int[][] graph = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
int[] dist = dijkstra(graph, 0);
for (int i = 0; i < dist.length; i++) {
System.out.println("Shortest distance from source to vertex " + i + " is " + dist);
}
}
}
[*]应用
[*]Dijkstra 算法不能处理负权边，如果图中存在负权边，可以使用 Bellman - Ford 算法。Bellman - Ford 算法通过多次松弛操纵来更新顶点的最短距离，可以处理负权边，但时间复杂度较高，为 O(VE)，其中 V 是顶点数，E 是边数。
[*]可以使用邻接表来优化图的存储，镌汰空间复杂度。邻接表只存储图中的非零边，对于稀疏图可以节流大量的空间。
3. 如何找出旋转数组的某个数
[*]界说
旋转数组是将一个有序数组在某个点进行旋转得到的。可以使用二分查找来找出目标数。通过比较中心元素和数组两端元素的大小关系，判断目标数大概存在的区间。
[*]要点
[*]确定旋转点的位置，判断数组哪一部门是有序的。
[*]根据目标数与有序部门的范围关系，缩小查找区间。
代码示例
java
public class SearchInRotatedSortedArray {
public static int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums == target) {
return mid;
}
if (nums <= nums) {
if (target >= nums && target < nums) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (target > nums && target <= nums) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
public static void main(String[] args) {
int[] nums = {4, 5, 6, 7, 0, 1, 2};
int target = 0;
int index = search(nums, target);
System.out.println("Index of target: " + index);
}
}
[*]应用
[*]可以处理数组中存在重复元素的环境，此时须要对二分查找的条件进行适当调解。当中心元素与数组两端元素相称时，无法确定哪一部门是有序的，须要将左右指针同时移动一位。
[*]可以进一步拓展到找出旋转点的位置。通过比较中心元素和其相邻元素的大小关系，判断旋转点在左半部门还是右半部门。
4. 什么是哲学家问题
[*]界说
哲学家问题是一个经典的并发编程问题，形貌了多个哲学家围坐在圆桌旁，每个哲学家之间有一根筷子，哲学家瓜代进行思考和进餐。进餐时须要同时拿起左右两根筷子，否则会挨饿。该问题主要探讨如何避免死锁和资源竞争。
[*]要点
[*]死锁的产生条件：
[*]互斥：资源不能被多个历程同时使用。
[*]占有并等待：历程已经占有了至少一个资源，又在等待其他资源。
[*]不可抢占：资源只能由占有它的历程自愿释放，不能被其他历程强行抢占。
[*]循环等待：多个历程形成一个循环，每个历程都在等待下一个历程所占有的资源。
[*]解决死锁的方法：破坏死锁的产生条件。
[*]解决方法示例
[*]破坏循环等待：可以给筷子编号，规定哲学家必须先拿起编号较小的筷子，再拿起编号较大的筷子。这样可以避免循环等待的环境发生。
[*]资源分级：可以引入一个服务员，只有当服务员允许时，哲学家才能拿起筷子。服务员可以控制资源的分配，避免死锁的发生。
[*]应用
哲学家问题可以推广到更一样寻常的资源竞争问题，如多个线程对多个共享资源的竞争。在实际开发中，须要根据具体环境选择合适的解决方法来避免死锁和资源竞争。
5. 如何求最大连续子序列和
[*]界说
可以使用动态规划的思想来解决该问题。界说一个数组 dp，其中 dp 表现以第 i 个元素结尾的最大连续子序列和。状态转移方程为 dp = max(dp + nums, nums)。
[*]要点
[*]维护一个当前最大连续子序列和和一个全局最大连续子序列和。
[*]遍历数组，更新当前最大连续子序列和和全局最大连续子序列和。
代码示例
java
public class MaximumSubarray {
public static int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int;
dp = nums;
int maxSum = dp;
for (int i = 1; i < n; i++) {
dp = Math.max(dp + nums, nums);
maxSum = Math.max(maxSum, dp);
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int maxSum = maxSubArray(nums);
System.out.println("Maximum subarray sum: " + maxSum);
}
}
[*]应用
[*]可以优化空间复杂度，只使用常数级的额外空间。因为 dp 只与 dp 有关，可以使用一个变量来代替 dp 数组。以下是优化后的代码示例：
java
public class MaximumSubarrayOptimized {
public static int maxSubArray(int[] nums) {
int n = nums.length;
int currentSum = nums;
int maxSum = nums;
for (int i = 1; i < n; i++) {
currentSum = Math.max(currentSum + nums, nums);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int maxSum = maxSubArray(nums);
System.out.println("Maximum subarray sum: " + maxSum);
}
}
2. 可以拓展到二维数组，求最大子矩阵和。可以通过枚举矩阵的上下边界，将二维问题转化为一维问题，然后使用一维最大连续子序列和的方法来求解。
6. 如何最左前缀匹配
[*]界说
最左前缀匹配通常用于数据库的索引优化。在数据库中，当查询条件使用了索引的最左前缀时，可以使用索引来加速查询。例如，对于复合索引 (col1, col2, col3)，查询条件 WHERE col1 = 'value1' AND col2 = 'value2' 可以使用该索引进行最左前缀匹配。
[*]要点
[*]索引的顺序很紧张，要确保查询条件按照索引的顺序使用。
[*]当查询条件不满意最左前缀时，大概无法使用索引。
[*]应用
[*]在实际开发中，要根据业务需求合理计划索引，避免创建过多的索引导致性能下降。过多的索引会增加数据库的维护成本，同时也会影响插入、更新和删除操纵的性能。
[*]可以使用数据库的查询分析工具来分析查询语句是否使用了最左前缀匹配。例如，在 MySQL 中可以使用 EXPLAIN 语句来检察查询的执行筹划，判断是否使用了索引。
7. 如何实现单链表反转并输出
[*]界说
可以使用迭代或递归的方法来反转单链表。迭代方法通过遍历链表，依次改变节点的指针方向；递归方法则是先递归地反转后续节点，再调解当前节点的指针方向。
[*]要点
[*]迭代方法：须要维护三个指针：前一个节点、当前节点和下一个节点。
[*]递归方法：须要注意递归的终止条件和指针的调解。
代码示例（迭代）
java
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class ReverseLinkedList {
public static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
public static void printList(ListNode head) {
ListNode curr = head;
while (curr != null) {
System.out.print(curr.val + " ");
curr = curr.next;
}
System.out.println();
}
public static void main(String[] args) {
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);
}
}
代码示例（递归）
java
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class ReverseLinkedListRecursive {
public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
public static void printList(ListNode head) {
ListNode curr = head;
while (curr != null) {
System.out.print(curr.val + " ");
curr = curr.next;
}
System.out.println();
}
public static void main(String[] args) {
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);
}
}
[*]应用
[*]可以考虑反转链表的一部门。可以通过指定反转的起始位置和结束位置，只反转链表的这一部门。
[*]可以使用递归方法实现链表反转，递归方法的代码更加简洁，但须要注意递归深度大概会导致栈溢出。
8. 如何找到非排序数组中未出现的第一个正整数
[*]界说
可以使用数组本身作为哈希表来解决该问题。起首将数组中全部小于等于 0 或大于数组长度的数置为一个特殊值（如数组长度加 1），然后遍历数组，将出现过的正整数对应的数组位置的元素置为负数，最后再次遍历数组，找到第一个正数所在的位置，该位置加 1 就是未出现的第一个正整数。
[*]要点
[*]使用数组的索引来标记正整数的出现环境。
[*]处理数组中小于等于 0 或大于数组长度的数。
代码示例
java
public class FirstMissingPositive {
public static int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
if (nums <= 0 || nums > n) {
nums = n + 1;
}
}
for (int i = 0; i < n; i++) {
int num = Math.abs(nums);
if (num <= n) {
nums = -Math.abs(nums);
}
}
for (int i = 0; i < n; i++) {
if (nums > 0) {
return i + 1;
}
}
return n + 1;
}
public static void main(String[] args) {
int[] nums = {3, 4, -1, 1};
int firstMissing = firstMissingPositive(nums);
System.out.println("First missing positive: " + firstMissing);
}
}
[*]应用
[*]可以考虑使用哈希表来解决该问题，但空间复杂度会变为 O(n)。使用哈希表可以更直观地纪录正整数的出现环境，但须要额外的空间。
[*]可以拓展随处理包罗负数和 0 的数组。可以先将负数和 0 过滤掉，然后再使用上述方法。
9. 在 0 到 n 这 n + 1 个数中取 n 个数，如何找到缺少的那个
[*]界说
可以使用求和公式或异或运算来解决该问题。求和公式方法是先盘算 0 到 n 的和，再减去数组中全部元素的和，得到的差值就是缺少的数；异或运算方法是将 0 到 n 的全部数与数组中的全部数进行异或运算，最闭幕果就是缺少的数。
[*]要点
[*]求和公式方法：须要注意大概会出现整数溢出的问题。可以使用长整型来避免溢出。
[*]异或运算方法：使用了异或的性子：a ^ a = 0，a ^ 0 = a。
代码示例（异或运算）
java
public class MissingNumber {
public static int missingNumber(int[] nums) {
int n = nums.length;
int xor = 0;
for (int i = 0; i < n; i++) {
xor ^= nums;
}
for (int i = 0; i <= n; i++) {
xor ^= i;
}
return xor;
}
public static void main(String[] args) {
int[] nums = {3, 0, 1};
int missing = missingNumber(nums);
System.out.println("Missing number: " + missing);
}
}
[*]应用
[*]可以考虑数组中元素大概重复的环境，此时须要使用其他方法。可以使用哈希表来纪录每个元素的出现次数，然后找出出现次数为 0 的元素。
[*]可以拓展到多维数组或其他数据结构。须要根据具体环境选择合适的方法。
10. 链表中如何判断有环路
[*]界说
可以使用快慢指针的方法来判断链表中是否有环路。快指针每次移动两步，慢指针每次移动一步，如果链表中有环路，快指针最终会追上慢指针。
[*]要点
[*]初始化快慢指针都指向链表头。
[*]循环移动快慢指针，直到快指针到达链表末尾或快慢指针相遇。
代码示例
java
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class LinkedListCycle {
public static boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
public static void main(String[] args) {
ListNode head = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
head.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2;
boolean hasCycle = hasCycle(head);
System.out.println("Linked list has cycle: " + hasCycle);
}
}
[*]应用
[*]可以进一步找出环路的入口节点。当快慢指针相遇时，将其中一个指针重新指向链表头，然后两个指针都以步长 1 移动，再次相遇的节点就是环路的入口节点。
[*]可以考虑使用哈希表来判断链表中是否有环路，但空间复杂度会变为 O(n)。使用哈希表可以纪录每个节点是否被访问过，如果某个节点被再次访问，则说明链表中有环路。
友谊提示：本文已经整理成文档，可以到如下链接免积分下载阅读
https://download.csdn.net/download/ylfhpy/90535485
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]