【4】阿里面试题整理

[1]. 介绍一下数据库死锁

数据库死锁是指两个或多个事务，由于互相请求对方持有的资源而造成的互相等待的状态，导致它们都无法继续执行。

死锁会导致事务阻塞，系统性能下降甚至应用崩溃。

比如：事务T1持有资源R1并等待R2，事务T2持有R2并等待R1，这就形成了一个循环等待，导致死锁。

[2]. 手撕：快排

public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high);quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex + 1, high);}}// 分区函数，以最左边的元素为基准元素private static int partition(int[] arr, int low, int high) {int pivot = arr[low];  // 选择最左边的元素作为基准int i = low;    // i 指向小于基准的区域的末尾，初始指向最左边for (int j = low + 1; j <= high; j++) { // j从low+1 开始遍历if (arr[j] < pivot) {i++;swap(arr, i, j); // 将小于基准的元素交换到左侧}}swap(arr, low, i); // 将基准元素交换到正确的位置return i;           // 返回基准元素的索引}// 交换数组中两个元素private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}

[3]. 手撕：二叉树的中序遍历

public class InorderTraversal {// 定义二叉树节点static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;this.left = null;this.right = null;}}// 中序遍历public static void inorderTraversal(TreeNode root) {if (root != null) {inorderTraversal(root.left);   // 遍历左子树System.out.print(root.val + " ");  // 访问根节点inorderTraversal(root.right);  // 遍历右子树}}
}

[4]. 手撕：最大子数组和

public class MaxSubarraySum {public static int maxSubArray(int[] nums) {// 判断输入数组是否为空或长度为0if (nums == null || nums.length == 0) {return 0; // 空数组或 null 返回0}// 记录全局最大子数组和int maxGlobalSum = nums[0];// 记录以当前元素结尾的最大子数组和int maxCurrentSum = nums[0];// 遍历数组，从第二个元素开始for (int i = 1; i < nums.length; i++) {// 更新以当前元素结尾的最大子数组和// 取当前元素值与当前元素加上以前一个元素结尾的最大子数组和中的较大值maxCurrentSum = Math.max(nums[i], maxCurrentSum + nums[i]);// 更新全局最大子数组和// 取全局最大子数组和与以当前元素结尾的最大子数组和中的较大值maxGlobalSum = Math.max(maxGlobalSum, maxCurrentSum);}// 返回全局最大子数组和return maxGlobalSum;}}