BinaryTree

• 判断一颗二叉树是否是有效的二叉搜索树
  • 有思路,但是不多…

    class Solution {
      public boolean isValidBST(TreeNode root) {
          // 调用辅助函数，初始时上界和下界为 null，表示没有限制
          return helper(root, null, null);
      }
    
      public boolean helper(TreeNode root, Integer lower, Integer upper) {
          // 如果当前节点为空，返回 true
          if (root == null) return true;
    
          // 如果当前节点的值不在上下界之间，返回 false
          if (lower != null && root.val <= lower) return false;
          if (upper != null && root.val >= upper) return false;
    
          // 递归地判断左右子树，更新上下界
          return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
          //第一遍想的太局部了,想成了,只需要单调的递归左右子树就可以了 但是会遇到下面这种情况
          //        5
          //       / \
          //      4   6
          //         / \
          //        3   7
      }
    }

• 三数之和
  • 先排序,进行数组去重,将指针指向去重后的元素,然后使用双指针进行求和,如果k数字是负的那我们就进行选择双指针之和为正的

    class Solution {
      public List<List<Integer>> threeSum(int[] nums) {
          List<List<Integer>> ans = new ArrayList<>();
          // 检查数组是否为空或长度小于3
          if (nums == null || nums.length < 3) {
              return ans;
          }
          // 对数组进行排序
          Arrays.sort(nums);
          // 遍历数组中的每个元素，将其作为第一个元素
          for (int i = 0; i < nums.length - 2; i++) {
              // 跳过相同的元素，避免重复的结果
              if (i > 0 && nums[i] == nums[i - 1]) {
                  continue;
              }
              // 使用双指针法找到剩余两个元素
              int left = i + 1; // 左指针
              int right = nums.length - 1; // 右指针
              int target = -nums[i]; // 目标和
              while (left < right) {
                  int sum = nums[left] + nums[right]; // 当前和
                  if (sum == target) { // 找到一个三元组
                      // 对三元组进行排序，保证非降序
                      List<Integer> triplet = new ArrayList<>();
                      triplet.add(nums[i]);
                      triplet.add(nums[left]);
                      triplet.add(nums[right]);
                      Collections.sort(triplet);
                      // 添加到结果列表中
                      ans.add(triplet);
                      // 跳过相同的元素，避免重复的结果
                      while (left < right && nums[left] == nums[left + 1]) {
                          left++;
                      }
                      while (left < right && nums[right] == nums[right - 1]) {
                          right--;
                      }
                      // 移动左右指针，继续寻找
                      left++;
                      right--;
                  } else if (sum < target) { // 当前和小于目标和，需要增大左指针
                      left++;
                  } else { // 当前和大于目标和，需要减小右指针
                      right--;
                  }
              }
          }
          return ans;
      }
    }

今日基础学习
当谈论Java中实现List接口的类时，通常指的是一些常见的类，它们都是java.util包中的一部分。这些类都实现了List接口，这意味着它们都提供了有序的、可重复的元素集合，并且可以通过索引访问元素。以下是其中几个类：

ArrayList:
实现了可调整大小的动态数组。
通过数组实现，支持随机访问。
非线程安全，适用于单线程环境。

List<String> arrayList = new ArrayList<>();

LinkedList:
实现了双向链表。
对于频繁的插入和删除操作，性能比ArrayList好。
同样支持随机访问，但效率相对较低。

List<String> linkedList = new LinkedList<>();

Stack:
继承自Vector类，实现了堆栈数据结构。
提供了后进先出（LIFO）的操作。
由于Vector是线程安全的，Stack也是线程安全的。

Stack<String> stack = new Stack<>();

Vector:
实现了可调整大小的动态数组。
与ArrayList类似，但是是线程安全的。
由于线程安全的开销，通常在性能要求较低的场景中使用。

List<String> vector = new Vector<>();

CopyOnWriteArrayList:
实现了可调整大小的动态数组。
写操作时会创建一个新的数组，读操作不需要加锁。
适用于读多写少的场景，因为写操作的开销比较大。

List<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>();

这些类都提供了一些常用的方法，如添加元素、删除元素、获取元素等。选择使用哪个类取决于你的具体需求和性能考虑。如果需要在多线程环境中使用，可能需要考虑线程安全性。