第一首先是LRU

用哈希表和链表可以实现，java的话用LinkedHaskMap可以解决

java

第二是快速排序

以最后一个元素为基准元素

java
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[high];
         int i = (low - 1); // 指向比基准小的元素的最后一个位置

         for (int j = low; j < high; j++) {
             // 如果当前元素小于或等于基准
             if (arr[j] <= pivot) {
                 i++;

                 // 交换 arr[i] 和 arr[j]
                swap(arr,i,j);
             }
         }

         // 交换 arr[i+1] 和 arr[high]（或基准）
        swap(arr,i+1,high);

         // 返回分区的下标
         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 = {10, 7, 8, 9, 1, 5};
         int n = arr.length;

         System.out.println("Original array:");
         printArray(arr);

         quickSort(arr, 0, n - 1);

         System.out.println("Sorted array:");
         printArray(arr);
     }

     private static void printArray(int[] arr) {
         for (int value : arr) {
             System.out.print(value + " ");
         }
         System.out.println();
     }
}

第三是接雨水

java
public class Solution {
    public int trap(int[] height) {
         if (height == null || height.length == 0) {
             return 0;
          }

         int n = height.length;
         int[] leftMax = new int[n];
         int[] rightMax = new int[n];

         // 计算每个柱子左边最高的柱子高度
         leftMax[0] = height[0];
         for (int i = 1; i < n; i++) {
              leftMax[i] = Math.max(leftMax[i - 1], height[i]);
          }

          // 计算每个柱子右边最高的柱子高度
         rightMax[n - 1] = height[n - 1];
          for (int i = n - 2; i >= 0; i--) {
              rightMax[i] = Math.max(rightMax[i + 1], height[i]);
          }

          // 计算能接的雨水量
         int trappedWater = 0;
          for (int i = 0; i < n; i++) {
              int water = Math.min(leftMax[i], rightMax[i]) - height[i];
              if (water > 0) {
                  trappedWater += water;
              }
          }

          return trappedWater;
      }


}