算法与数据结构基础概览

算法基础

1. 在评估一段包含多个操作的代码时，主要关注最耗时的操作。
2. 时间复杂度分析：
   1. 对于固定次数的操作（如1次、2次、3次...），其时间复杂度为O(1)。
   2. 对于与输入规模成线性关系的操作（如n次、2n次、3n次...），其时间复杂度为O(n)。
3. 常见递归算法的时间复杂度：
   1. 二分查找的时间复杂度为O(log n)。
   2. 二叉树遍历的时间复杂度为O(n)。
   3. 简单排序（如冒泡排序）的时间复杂度为O(n^2)。
   4. 高效排序算法（如快速排序、归并排序）的时间复杂度为O(n log n)。

数组与链表

数组

1. 数组是一段连续的内存空间，可以通过索引直接访问任何元素。
2. 访问数组中任一元素的时间复杂度为O(1)。
3. 为了保持数组元素在内存中的连续性，插入或删除操作的时间复杂度为O(n)。

链表

1. 链表分为单向链表和双向链表。
2. 在链表中插入或删除元素的时间复杂度为O(1)，但查找元素需要遍历链表，因此时间复杂度为O(n)。

链表操作实例

// 反转单链表
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}


// 两两交换链表中的节点
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
ListNode first = prev.next;
ListNode secOnd= prev.next.next;
first.next = second.next;
second.next = first;
prev.next = second;
prev = first;
}
return dummy.next;
}

// 判断链表是否有环
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;
}

// 查找链表环的起始节点
public ListNode detectCycle(ListNode head) {
Set set = new HashSet<>();
while (head != null) {
if (!set.add(head)) return head;
head = head.next;
}
return null;
}

// K个一组反转链表
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null) return null;
// Check if there are at least k nodes left in the linked list
ListNode w = head;
for (int i = 0; i if (w == null) return head;
w = w.next;
}
// Reverse k nodes
ListNode prev = null;
ListNode curr = head;
for (int i = 0; i ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
// Connect the reversed part with the rest of the list
if (w != null) head.next = reverseKGroup(w, k);
return prev;
}

栈与队列

1. 栈是一种后进先出的数据结构，类似于一个底部封闭的桶。
2. 队列是一种先进先出的数据结构，类似于一个没有底部的管道，元素只能从前端进入，后端出去。
3. 优先队列（Priority Queue）：
   1. 元素按优先级顺序出队。
   2. 通常使用堆（如二叉堆、多项式堆、斐波那契堆）或二叉搜索树实现。
   3. 堆是一种高效的优先队列实现方式，支持高效的插入、删除和合并操作。

// 使用栈实现队列
public class MyQueue {
private Stack s1 = new Stack<>();
private Stack s2 = new Stack<>();

public void push(int x) {
s1.push(x);
}

public int pop() {
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
return s2.pop();
}

public int peek() {
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
return s2.peek();
}

public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}

// 使用队列实现栈
public class MyStack {
private LinkedList queue = new LinkedList<>();

public void push(int x) {
queue.add(x);
for (int i = 1; i queue.add(queue.remove());
}
}

public int pop() {
return queue.remove();
}

public int top() {
return queue.peek();
}

public boolean empty() {
return queue.isEmpty();
}
}

流式数据处理

寻找流式数据中的第K大元素

1. 使用快速排序对前K个元素进行排序，时间复杂度为O(K log K)。
2. 使用优先队列对元素进行管理，时间复杂度为O(log K)。
3. 在大量数据中寻找第K大元素的方法：
   1. 方法1：保存K个元素并排序，每次新元素加入时重新排序，总时间复杂度为O(N K log K)。
   2. 方法2：使用优先队列，保持队列中始终有K个元素，新元素与队列中最小元素比较，若更大则替换，总时间复杂度为O(N log K)。
4. 优先队列相比快速排序能显著降低时间复杂度。

// 实现寻找流式数据中的第K大元素
public class KthLargest {
private PriorityQueue minHeap;
private int k;

public KthLargest(int k, int[] nums) {
this.k = k;
this.minHeap = new PriorityQueue<>(k);
for (int num : nums) {
add(num);
}
}

public int add(int val) {
if (minHeap.size() minHeap.offer(val);
} else if (val > minHeap.peek()) {
minHeap.poll();
minHeap.offer(val);
}
return minHeap.peek();
}
}