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

思路都在注释里，就是bfs层序遍历

```java
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> averages = new ArrayList<>(); //答案数组 
        if (root == null) {  //特判
            return averages; 
        }

        Queue<TreeNode> queue = new LinkedList<>(); //bfs队列
        queue.offer(root); //根结点入队

        while (!queue.isEmpty()) {
              int levelSize = queue.size();
              double sum = 0;
              for (int i = 0; i < levelSize; i++) {  //入队并计算
                  TreeNode node = queue.poll();
                  sum += node.val;
                  if (node.left != null) {
                      queue.offer(node.left);
                  }
                  if (node.right != null) {
                      queue.offer(node.right);
                  }
              }
              averages.add(sum / levelSize);
          }

        return averages;

    }
}
```

![image.png](/static/img/d3473bc81fc37facd3b1aa2349f259e0.image.webp)
```java
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
                 int lenA = 0, lenB = 0;
         ListNode tempA = headA, tempB = headB;

         // 计算两个链表的长度
         while (tempA != null) {
              lenA++;
               tempA = tempA.next;
           }
         while (tempB != null) {
              lenB++;
               tempB = tempB.next;
           }

         // 对齐链表
         tempA = headA;
         tempB = headB;
         if (lenA > lenB) {
              for (int i = 0; i < lenA - lenB; i++) {
                   tempA = tempA.next;
               }
           } else {
               for (int i = 0; i < lenB - lenA; i++) {
                   tempB = tempB.next;
               }
           }

         // 遍历链表，找到相交节点
         while (tempA != null && tempB != null) {
               if (tempA == tempB) {
                   return tempA;
               }
               tempA = tempA.next;
               tempB = tempB.next;
           }

         return null;
       

    }
}
```

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

```java
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root.left,root.right);
    }

    private boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val)
        && isMirror(t1.right, t2.left)
        && isMirror(t1.left, t2.right);
    }

}
```


今日刷题


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

```java
public class Solution {
    public int garbageCollection(String[] garbage, int[] travel) {
         int[] lastPos = new int[]{-1,-1,-1}; // 记录每种垃圾最后出现的位置
         int[] time = new int[4]; // 记录每种垃圾收拾所需的时间
         int count = 0;
         // 遍历垃圾数组，记录每种垃圾最后出现的位置
         for (int i = 0; i < garbage.length; i++) {
              for (int j = 0; j < garbage[i].length(); j++) {
                  char c = garbage[i].charAt(j);
                  if (c == 'M') {
                      lastPos[0] = i;
                      count++;
                      //time[0] += travel[i];
                  } else if (c == 'P') {
                      lastPos[1] = i;
                      count++;
                      //time[1] += travel[i];
                  } else if (c == 'G') {
                      lastPos[2] = i;
                      count++;
                      //time[2] += travel[i];
                  }
              }
          }

          //System.out.println(lastPos[2]); -1,2,3

         // 计算收拾每种垃圾所需的时间
         for (int i = 0; i < 3; i++) {
              if (lastPos[i] > 0) {
                for(int j = 0; j < lastPos[i];j++) {
                    time[i]=time[i]+ travel[j];
                }
                System.out.println(time[2]);
                //time[i] += lastPos[i] * travel[lastPos[i] - 1];
              }
          }

          // 返回收拾所有垃圾所需的时间
          return time[0] + time[1] + time[2] + count;
      }

   
}

```


![image.png](/static/img/0cc71f152e21312bda305d1e57577b06.image.webp)
```java
public class Solution {
    private int minDiff = Integer.MAX_VALUE;
    private Integer prevVal = null;

    public int getMinimumDifference(TreeNode root) {
         inorder(root);
         return minDiff;
     }

    private void inorder(TreeNode node) {
         if (node == null) {
              return;
          }
          inorder(node.left); // 左子树
          if (prevVal != null) {
              minDiff = Math.min(minDiff, node.val - prevVal);
          }
          prevVal = node.val; // 更新前一个节点的值
          inorder(node.right); // 右子树
     }
}



```


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

```java
public class Solution {
    public boolean isValidBST(TreeNode root) {
         return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
      }

    private boolean isValidBST(TreeNode node, long lower, long upper) {
         if (node == null) {
              return true;
           }
           // 当前节点的值必须在lower和upper之间
         if (node.val <= lower || node.val >= upper) {
              return false;
           }
           // 递归验证左子树和右子树
         return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
      }
}

```


算法题常遇到一些字符串操作，记住这些API就能更快码出来，以下是一些常用的字符串处理函数：

### 分割字符串

- `split(String regex)`: 使用正则表达式作为分隔符来分割字符串。
- `split(String regex, int limit)`: 与`split(String regex)`类似，但限制了分割后的数组大小。

### 匹配字符串

- `matches(String regex)`: 判断字符串是否匹配给定的正则表达式。
- `contains(CharSequence s)`: 判断字符串是否包含指定的子字符串。

### 组合字符串

- `concat(String str)`: 将指定字符串连接到当前字符串的末尾。
- `join(CharSequence delimiter, CharSequence... elements)`: 使用指定的分隔符连接一系列元素。

### 替换字符串

- `replace(CharSequence target, CharSequence replacement)`: 将字符串中所有出现的指定字符序列替换为另一个字符序列。
- `replaceAll(String regex, String replacement)`: 使用正则表达式替换所有匹配的子字符串。

### 转换大小写

- `toLowerCase()`: 将字符串中的所有字符都转换为小写。
- `toUpperCase()`: 将字符串中的所有字符都转换为大写。

### 去除空白

- `trim()`: 去除字符串两端的空白字符。
- `strip()`: Java 11新增的方法，去除字符串两端的空白字符。

### 比较字符串

- `equals(Object anotherObject)`: 比较当前字符串与另一个对象是否相等。
- `equalsIgnoreCase(String anotherString)`: 与`equals(Object anotherObject)`类似，但忽略大小写。

### 搜索子字符串

- `indexOf(String str)`: 返回指定子字符串在此字符串中第一次出现处的索引。
- `lastIndexOf(String str)`: 返回指定子字符串在此字符串中最后一次出现处的索引。

### 提取子字符串

- `substring(int beginIndex)`: 返回一个新的字符串，它是此字符串的一个子字符串。
- `substring(int beginIndex, int endIndex)`: 返回一个新的字符串，它是此字符串的一个子字符串。

### 字符串与字节数组转换

- `getBytes()`: 将字符串转换为字节数组。
- `new String(byte[] bytes, int offset, int length)`: 使用指定的字节数组构造一个新的字符串。

### 其他常用方法

- `length()`: 返回字符串的长度。
- `isEmpty()`: 判断字符串是否为空。
- `charAt(int index)`: 返回指定索引处的字符。
- `contains(CharSequence s)`: 判断字符串是否包含指定的子字符串。



以下是代码示例：
```java
public class StringExample {
    public static void main(String[] args) {
        String str = "Hello, World!";

        // 分割字符串
        String[] parts = str.split(", ");
        System.out.println("分割字符串: " + String.join(" ", parts));

        // 匹配字符串
        boolean matches = str.matches(".*World.*");
        System.out.println("匹配字符串: " + matches);

        // 组合字符串
        String combined = str.concat(" How are you?");
        System.out.println("组合字符串: " + combined);

        // 替换字符串
        String replaced = str.replace("World", "Java");
        System.out.println("替换字符串: " + replaced);

        // 转换大小写
        String lower = str.toLowerCase();
        String upper = str.toUpperCase();
        System.out.println("转换大小写: " + lower + " | " + upper);

        // 去除空白
        String trimmed = str.trim();
        System.out.println("去除空白: " + trimmed);

        // 比较字符串
        boolean equals = str.equals("Hello, World!");
        boolean equalsIgnoreCase = str.equalsIgnoreCase("hello, world!");
        System.out.println("比较字符串: " + equals + " | " + equalsIgnoreCase);

        // 搜索子字符串
        int index = str.indexOf("World");
        System.out.println("搜索子字符串: " + index);

        // 提取子字符串
        String subStr = str.substring(7, 12);
        System.out.println("提取子字符串: " + subStr);

        // 字符串与字节数组转换
        byte[] bytes = str.getBytes();
        String fromBytes = new String(bytes);
        System.out.println("字符串与字节数组转换: " + fromBytes);
    }
}
```



Java String操作

比较版本，字符串处理

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

```java
class Solution {
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\."); //按.分割
        String[] v2 = version2.split("\\.");
        int len1 = v1.length;
        int len2 = v2.length;
        int maxLen = Math.max(len1, len2); //选出最大长度

        for (int i = 0; i < maxLen; i++) { //开始比较
            int num1 = i < len1 ? Integer.parseInt(v1[i]) : 0;
            int num2 = i < len2 ? Integer.parseInt(v2[i]) : 0;
            if (num1 != num2) {
                return num1 > num2 ? 1 : -1;
            }
        }
        return 0;
    }

}
```

合并区间

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


```java
class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
             return new int[0][2];
         }

         // 按照区间的起始位置排序
         Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

         List<int[]> merged = new ArrayList<>();
         for (int[] interval : intervals) {
             // 如果列表为空，或者当前区间的起始位置大于前一个区间的结束位置，直接添加
             if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                 merged.add(interval);
             } else {
                 // 否则，合并区间
                 merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
             }
         }

         // 将List转换为数组
         return merged.toArray(new int[merged.size()][]);

    }
}
```

峰值

要找到数组中的峰值元素，可以使用二分查找算法。由于峰值元素的定义是其值严格大于左右相邻值的元素，我们可以利用这个特性来缩小搜索范围。

![image.png](/static/img/e23185bbf28e8103a823644565eec373.image.webp)
```java
class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
              int mid = left + (right - left) / 2;
              if (nums[mid] > nums[mid + 1]) {
                  right = mid;
               } else {
                  left = mid + 1;
               }
        }

         return left; // 或者 right，因为 left == right

    }
}
```



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


}

```



