1. 引言
在程序开发中，数据结构和算法是非常重要的基础知识。掌握了数据结构和算法，可以帮助我们优化和提升程序的效率，同时也能够解决一些复杂的问题。在Java中，也提供了一些内置的数据结构和算法，比如ArrayList、LinkedList、HashMap等。本篇博客将介绍一些常见的数据结构和算法，并通过实战练习加深理解。
2. 数据结构练习
2.1 数组
数组是一种在内存中连续存储相同类型数据的数据结构。在Java中，数组可以通过索引访问或修改其中的元素。
练习题1
给定一个整数数组，编写一个函数来判断数组中是否存在重复元素。
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (set.contains(num)) {
return true;
}
set.add(num);
}
return false;
}
2.2 链表
链表是一种非连续存储的数据结构，每个节点都包含指向下一个节点的指针。在Java中，可以通过链表实现各种常见的数据结构，如队列、栈等。
练习题2
给定一个链表，判断链表中是否有环。
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
2.3 栈
栈是一种后进先出（LIFO）的数据结构。在Java中，可以使用Stack类实现栈的功能。
练习题3
给定一个只包含 '(' 和 ')' 的字符串，编写一个函数来检查字符串是否有效。
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
return false;
}
}
}
return stack.isEmpty();
}
2.4 队列
队列是一种先进先出（FIFO）的数据结构。在Java中，可以使用LinkedList类的add()和remove()方法实现队列的功能。
练习题4
给定一个数组，和一个大小固定的滑动窗口，请找出所有滑动窗口里的最大值。
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || k <= 0 || nums.length < k) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (!deque.isEmpty() && deque.peekFirst() == i - k) {
deque.pollFirst();
}
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.addLast(i);
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
3. 算法练习
3.1 排序算法
排序算法是将一组数据按照某种顺序进行排列的算法。常见的排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序等。
练习题5
给定一个整数数组，请编写一个函数将数组排序。
public void sortArray(int[] nums) {
quickSort(nums, 0, nums.length - 1);
}
private void quickSort(int[] nums, int low, int high) {
if (low < high) {
int pivot = partition(nums, low, high);
quickSort(nums, low, pivot - 1);
quickSort(nums, pivot + 1, high);
}
}
private int partition(int[] nums, int low, int high) {
int pivot = nums[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (nums[j] < pivot) {
i++;
swap(nums, i, j);
}
}
swap(nums, i + 1, high);
return i + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
3.2 查找算法
查找算法是在一组数据中查找指定元素的算法。常见的查找算法有线性查找、二分查找、哈希查找等。
练习题6
给定一个有序数组和一个目标值，请编写一个函数，在数组中查找目标值，并返回其索引。
public int search(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
4. 总结
通过上面的实战练习，我们对Java中常见的数据结构和算法有了更深入的了解。在实际开发中，根据问题的特点选择合适的数据结构和算法，可以提高代码的效率和可读性。因此，我们要多加练习和思考，并且不断学习和探索更高级的数据结构和算法。
本文来自极简博客，作者：梦幻星辰，转载请注明原文链接：Java 数据结构与算法实战练习
