BinaryTree
- 判断一颗二叉树是否是有效的二叉搜索树
- 有思路,但是不多…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class 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数字是负的那我们就进行选择双指针之和为正的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50class 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;
}
}
- 先排序,进行数组去重,将指针指向去重后的元素,然后使用双指针进行求和,如果k数字是负的那我们就进行选择双指针之和为正的
今日基础学习
当谈论Java中实现List接口的类时,通常指的是一些常见的类,它们都是java.util包中的一部分。这些类都实现了List接口,这意味着它们都提供了有序的、可重复的元素集合,并且可以通过索引访问元素。以下是其中几个类:
ArrayList:
实现了可调整大小的动态数组。
通过数组实现,支持随机访问。
非线程安全,适用于单线程环境。
1 | List<String> arrayList = new ArrayList<>(); |
LinkedList:
实现了双向链表。
对于频繁的插入和删除操作,性能比ArrayList好。
同样支持随机访问,但效率相对较低。
1 | List<String> linkedList = new LinkedList<>(); |
Stack:
继承自Vector类,实现了堆栈数据结构。
提供了后进先出(LIFO)的操作。
由于Vector是线程安全的,Stack也是线程安全的。
1 | Stack<String> stack = new Stack<>(); |
Vector:
实现了可调整大小的动态数组。
与ArrayList类似,但是是线程安全的。
由于线程安全的开销,通常在性能要求较低的场景中使用。
1 | List<String> vector = new Vector<>(); |
CopyOnWriteArrayList:
实现了可调整大小的动态数组。
写操作时会创建一个新的数组,读操作不需要加锁。
适用于读多写少的场景,因为写操作的开销比较大。
1 | List<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>(); |
这些类都提供了一些常用的方法,如添加元素、删除元素、获取元素等。选择使用哪个类取决于你的具体需求和性能考虑。如果需要在多线程环境中使用,可能需要考虑线程安全性。
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Comment
WalineFacebook Comments