【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) {
        // 判断输入数组是否为空或长度为0
        if (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;
    }


}