第一首先是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();
     }
}
```

第三是接雨水

![image.png](/static/img/418e41a203ef96554d51c250badaeee6.image.webp)

```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;
      }


}

```





手撸三板斧

调大模型api



![image.png](/static/img/8cdc1c2fc7ee8b45429045af3fe288db.image.webp)


很简单，哈希一下

进阶

```java
public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        
        Map<Character, Integer> charCount = new HashMap<>();
        
        // 遍历第一个字符串，统计每个字符出现的次数
        for (int i = 0; i < s.length(); i++) {
            charCount.put(s.charAt(i), charCount.getOrDefault(s.charAt(i), 0) + 1);
        }
        
        // 遍历第二个字符串，减去对应字符的计数
        for (int i = 0; i < t.length(); i++) {
            charCount.put(t.charAt(i), charCount.getOrDefault(t.charAt(i), 0) - 1);
        }
        
        // 检查HashMap中的所有值是否都为0
        for (int count : charCount.values()) {
            if (count != 0) {
                return false;
            }
        }
        
        return true;
    }
}
```


![image.png](/static/img/1780035a62451d8b046334f941269c46.image.webp)

也是哈希，很简单的思路

```java
public class Solution {
    public int longestPalindrome(String s) {
        int[] count = new int[54]; // 26个小写字母 + 26个大写字母 + 2个额外空间
        int result = 0;
        boolean hasOdd = false;

        // 统计每个字母出现的次数
        for (char c : s.toCharArray()) {
            int index = c >= 'a' ? c - 'a' : c - 'A' + 26;
            count[index]++;
        }

        // 计算最长回文串的长度
        for (int i = 0; i < count.length; i++) {
            if (count[i] % 2 == 0) {
                result += count[i];
            } else {
                result += count[i] - 1; // 出现奇数次的字母，取偶数次
                hasOdd = true;
            }
        }

        // 如果有出现奇数次的字母，结果加1
        if (hasOdd) {
            result++;
        }

        return result;
    }
}
```

![image.png](/static/img/e60dbd0709d5e8aefb8e41cdf4d1377f.image.webp)

```java
public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> duplicates = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != nums[nums[i] - 1]) {
                // 交换 nums[i] 和 nums[nums[i] - 1]
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }
        // 找出出现两次的整数
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                duplicates.add(nums[i]);
            }
        }
        return duplicates;
    }
}
```

![image.png](/static/img/a1a220d70219ea16aa0d1b93075bb152.image.webp)


```java
import java.util.Random;

public class Solution {
    private int[] nums;
    private Random rand;

    public Solution(int[] nums) {
        this.nums = nums;
        this.rand = new Random();
    }

    public int pick(int target) {
        int count = 0;
        int result = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                count++; // 遇到目标值的次数
                // 以1/count的概率选择当前索引
                if (rand.nextInt(count) == 0) {
                    result = i;
                }
            }
        }
        return result;
    }
}

/////
class Solution {
    Map<Integer, List<Integer>> pos;
    Random random;

    public Solution(int[] nums) {
        pos = new HashMap<Integer, List<Integer>>();
        random = new Random();
        for (int i = 0; i < nums.length; ++i) {
            pos.putIfAbsent(nums[i], new ArrayList<Integer>());
            pos.get(nums[i]).add(i);
        }
    }

    public int pick(int target) {
        List<Integer> indices = pos.get(target);
        return indices.get(random.nextInt(indices.size()));
    }
}



```


![image.png](/static/img/a6974a3a1887abb5b08698e09177df83.image.webp)

```java
public class Solution {
    public String[] findWords(String[] words) {
        // 创建三个集合，分别代表键盘上的三行
        Set<Character> row1 = new HashSet<>();
        Set<Character> row2 = new HashSet<>();
        Set<Character> row3 = new HashSet<>();
        // 初始化三行的字符集合
        String row1Chars = "qwertyuiop";
        String row2Chars = "asdfghjkl";
        String row3Chars = "zxcvbnm";
        for (char c : row1Chars.toCharArray()) {
            row1.add(c);
        }
        for (char c : row2Chars.toCharArray()) {
            row2.add(c);
        }
        for (char c : row3Chars.toCharArray()) {
            row3.add(c);
        }

        // 创建一个列表来存储结果
        List<String> result = new ArrayList<>();

        // 遍历每个单词
        for (String word : words) {
            // 将单词转换为小写，以便比较
            String lowerCaseWord = word.toLowerCase();
            // 检查单词中的每个字符是否都在同一行
            boolean isOnSameRow1 = true;
            boolean isOnSameRow2 = true;
            boolean isOnSameRow3 = true;
            for (char c : lowerCaseWord.toCharArray()) {
                if (!row1.contains(c)) {
                    isOnSameRow1 = false;
         
                }
                if (!row2.contains(c)) {
                    isOnSameRow2 = false;
       
                }
                if (!row3.contains(c)) {
                    isOnSameRow3 = false;
         
                }
               
            }
            // 如果单词中的所有字符都在同一行，则添加到结果列表中
            if (isOnSameRow1 || isOnSameRow2 || isOnSameRow3) {
                result.add(word);
            }
        }

        // 将结果列表转换为数组并返回
        return result.toArray(new String[0]);
    }
}

```


今日刷题

用nohup启动进程挂了，发现前几天nohup启动的进程挂了

原因如下，nohup启动后按cltr c退出，当前会话被关闭，对应子进程被回收

正确做法，启动后按任意键退出

吐槽一下
```shell

(base) wangwf@wangwf:~/UserFile/zjj2022/etakeaway/houduan$ docker ps
permission denied while trying to connect to the Docker daemon socket at unix:///var/run/docker.sock: Get "http://%2Fvar%2Frun%2Fdocker.sock/v1.24/containers/json": dial unix /var/run/docker.sock: connect: permission denied
(base) wangwf@wangwf:~/UserFile/zjj2022/etakeaway/houduan$ sudo docker ps
CONTAINER ID   IMAGE           COMMAND                   CREATED         STATUS          PORTS                                           NAMES
08606289b1ba   etake           "java -jar Order_foo…"   7 seconds ago   Up 6 seconds    0.0.0.0:8000->8000/tcp, :::8000->8000/tcp       etakeaway
58bd7d1ef5c2   ollama/ollama   "/bin/ollama serve"       2 days ago      Up 12 minutes   0.0.0.0:11435->11434/tcp, :::11435->11434/tcp   ollama
(base) wangwf@wangwf:~/UserFile/zjj2022/etakeaway/houduan$ cd files/

```
研究生学长真无语，不管服务器，docker都没配好，nvidia驱动也不装，无奈自己只有访问权，重启都不行



nohup后台进程挂了

在Java的`ThreadPoolExecutor`中，如果线程池的`workQueue`已满，并且线程池中的线程数量已经达到`maximumPoolSize`，那么新提交的任务将被拒绝。默认情况下，`ThreadPoolExecutor`提供了四种预定义的拒绝策略：

1. **AbortPolicy**：这是默认的拒绝策略。如果任务被拒绝，它会抛出一个`RejectedExecutionException`异常。

2. **CallerRunsPolicy**：如果任务被拒绝，它会由调用`execute`方法的线程直接执行。

3. **DiscardPolicy**：如果任务被拒绝，它会被静默地丢弃，不会有任何通知。

4. **DiscardOldestPolicy**：如果任务被拒绝，线程池会丢弃`workQueue`中最旧的任务（即最早提交的任务），然后尝试重新执行当前任务。

如果你想要实现自己的丢弃策略，你可以通过实现`RejectedExecutionHandler`接口来定义自己的行为。以下是一个简单的自定义丢弃策略的示例，它将丢弃新提交的任务：

```java
import java.util.concurrent.*;

public class DiscardTaskPolicy implements RejectedExecutionHandler {
    @Override
    public void rejectedExecution(Runnable r, ThreadPoolExecutor executor) {
        // 丢弃新提交的任务
    }
}
```

然后，你可以将这个自定义的拒绝策略传递给`ThreadPoolExecutor`的构造函数：

```java
import java.util.concurrent.*;

public class Main {
    public static void main(String[] args) {
        // 创建自定义的丢弃策略实例
        RejectedExecutionHandler handler = new DiscardTaskPolicy();

        // 创建线程池，指定自定义的丢弃策略
        ThreadPoolExecutor executor = new ThreadPoolExecutor(
            1, // corePoolSize
            2, // maximumPoolSize
            10, // keepAliveTime
            TimeUnit.SECONDS,
            new ArrayBlockingQueue<>(1), // workQueue
            Executors.defaultThreadFactory(), // threadFactory
            handler // 指定自定义的丢弃策略
        );

        // 提交任务到线程池
        executor.execute(() -> {
            System.out.println("Task is running");
        });

        // 关闭线程池
        executor.shutdown();
    }
}
```

在这个例子中，我们创建了一个`ThreadPoolExecutor`实例，并将自定义的丢弃策略`handler`传递给它。当线程池无法执行新任务时，它将调用`handler`的`rejectedExecution`方法，而这个方法中没有任何操作，因此新提交的任务将被丢弃。

我们主要来探究一下默认的四种拒绝策略是怎么实现的

分析一下对应的源码



### DiscardPolicy

```java
/**
 * A handler for tasks that cannot be executed by a {@code ThreadPoolExecutor}.
 */
public static class DiscardPolicy implements RejectedExecutionHandler {
    /**
     * Creates a {@code DiscardPolicy}.
     */
    public DiscardPolicy() { }

    /**
     * Does nothing, which has the effect of discarding task r.
     * @param r the runnable task requested to be executed
     * @param e the executor attempting to execute this task
     */
    public void rejectedExecution(Runnable r, ThreadPoolExecutor e) {
    }
}
```

在`rejectedExecution`方法中，`DiscardPolicy`没有执行任何操作，因此当任务被拒绝时，它不会被添加到队列中，也不会被其他线程执行。这个方法的实现非常简单，只是空方法体。




### AbortPolicy

`AbortPolicy`是默认的拒绝策略。当任务被拒绝时，它会抛出一个`RejectedExecutionException`异常。

```java
public static class AbortPolicy implements RejectedExecutionHandler {
    /**
     * Creates an {@code AbortPolicy}.
     */
    public AbortPolicy() { }

    /**
     * Always throws RejectedExecutionException.
     *
     * @param r the runnable task requested to be executed
     * @param e the executor attempting to execute this task
     * @throws RejectedExecutionException always
     */
    public void rejectedExecution(Runnable r, ThreadPoolExecutor e) {
        throw new RejectedExecutionException("Task " + r.toString() +
                                             " rejected from " +
                                             e.toString());
    }
}
```

在`rejectedExecution`方法中，`AbortPolicy`直接抛出了一个`RejectedExecutionException`异常，这个异常会被提交任务的线程捕获，通常会导致应用程序的执行流程中断。

### CallerRunsPolicy

`CallerRunsPolicy`在任务被拒绝时，会由提交任务的线程直接执行该任务。

```java
public static class CallerRunsPolicy implements RejectedExecutionHandler {
    /**
     * Creates a {@code CallerRunsPolicy}.
     */
    public CallerRunsPolicy() { }

    /**
     * Executes task r in the caller's thread, unless the executor
     * has been shut down, in which case the task is discarded.
     *
     * @param r the runnable task requested to be executed
     * @param e the executor attempting to execute this task
     */
    public void rejectedExecution(Runnable r, ThreadPoolExecutor e) {
        if (!e.isShutdown()) {
            r.run();
        }
    }
}
```

在`rejectedExecution`方法中，如果线程池没有被关闭，`CallerRunsPolicy`会调用任务的`run`方法，这样任务就会在调用`execute`方法的线程中执行。

### DiscardOldestPolicy

`DiscardOldestPolicy`在任务被拒绝时，会丢弃`workQueue`中最旧的任务（即最早提交的任务），然后尝试重新执行当前任务。

```java
public static class DiscardOldestPolicy implements RejectedExecutionHandler {
    /**
     * Creates a {@code DiscardOldestPolicy} for the given executor.
     */
    public DiscardOldestPolicy() { }

    /**
     * Obtains and ignores the next task that the executor
     * would otherwise execute, if one is immediately available,
     * and then retries execution of task r, unless the executor
     * is shut down, in which case task r is instead discarded.
     *
     * @param r the runnable task requested to be executed
     * @param e the executor attempting to execute this task
     */
    public void rejectedExecution(Runnable r, ThreadPoolExecutor e) {
        if (!e.isShutdown()) {
            e.getQueue().poll();
            e.execute(r);
        }
    }
}
```

在`rejectedExecution`方法中，`DiscardOldestPolicy`首先尝试从`workQueue`中移除最旧的任务，然后重新执行当前任务。如果`workQueue`为空或者线程池被关闭，当前任务将被丢弃。


