数据结构与算法（二）

1 时间复杂度、空间复杂度、排序算法和二分法

• 内容：
  • 评估算法优劣的核心指标
  • 时间复杂度、空间复杂度、估算方式、意义
  • 常数时间的操作
  • 选择排序、冒泡排序、插入排序
  • 最优解
  • 对数器
  • 二分法

1.1 简单的排序算法

• 选择排序

• 冒泡排序

• 插入排序

1.2 二分查找

• 有序数组中找到num

• 有序数组中找到>=num最左的位置

• 有序数组中找到<=num最右的位置

• 局部最小值问题，定义何为局部最小值：
  • arr[0] < arr[1]，0位置是局部最小；
  • arr[N-1] < arr[N-2]，N-1位置是局部最小；
    arr[i-1] > arr[i] < arr[i+1]，i位置是局部最小；
  • 给定一个数组arr，已知任何两个相邻的数都不相等，找到随便一个局部最小位置返回

2 异或运算、进一步认识对数器的重要性

• 内容：
  • 异或运算的性质
  • 异或运算的题目

2.1 不用额外变量交换两个数的值

a = a ^ b;
b = a ^ b;
a = a ^ b;

2.2 不用额外变量交换数组中两个数的值

public static void swap (int[] arr, int i, int j) {arr[i]  = arr[i] ^ arr[j];arr[j]  = arr[i] ^ arr[j];arr[i]  = arr[i] ^ arr[j];
}

2.3 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数

• arr数组中，只有一种数出现奇数次

public static void printOddTimesNum1(int[] arr) {int ans = 0;for (int x : arr) ans ^= x;System.out.println(ans);
}

2.4 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数

怎么把一个int类型的数 x，提取出二进制中最右侧的1?

x & (~x + 1) 等价于 x & (-x)

public static void printOddTimesNum2(int[] arr) {int eor = 0;for (int i = 0; i < arr.length; i++) {eor ^= arr[i];}// a 和 b是两种数// eor != 0// eor最右侧的1，提取出来// eor :     00110010110111000// rightOne :00000000000001000int rightOne = eor & (-eor); // 提取出最右的1int onlyOne = 0; // eor'for (int i = 0 ; i < arr.length;i++) {//  arr[1] =  111100011110000// rightOne=  000000000010000if ((arr[i] & rightOne) != 0) {onlyOne ^= arr[i];}}System.out.println(onlyOne + " " + (eor ^ onlyOne));
}

2.5 一个数组中有一种数出现K次，其他数都出现了M次

• 已知M > 1，K < M，找到出现了K次的数，要求额外空间复杂度O(1)，时间复杂度O(N)

// 对数器 for test
public static int test(int[] arr, int k, int m) {Map<Integer, Integer> counter = new HashMap<>();for (int x : arr) {counter.compute(x, (key, v) -> v == null ? 1 : v + 1);}for (Integer num : counter.keySet()) {if (counter.get(num) == k) {return num;}}return -1;
}

public static int onlyKTimes(int[] arr, int k, int m) {int intBits = 32;int[] bitCounter = new int[intBits];// bitCounter[0]: 0 位置的1出现了几个// bitCounter[i]: i 位置的1出现了几个for (int x : arr) {for (int i = 0; i < intBits; i++) {//          if (((x >> i) & 1) != 0) {//             bitCounter[i] += 1;//          }bitCounter[i] += (x >> i) & 1;}}int ans = 0;for (int i = 0; i < intBits; i++) {if (bitCounter[i] % m != 0) {// 在第i位上有1ans |= (1 << i);}}return ans;
}

题目变一下，如果能找到出现K次的数，就返回该数；如果找不到，返回-1。

public static int onlyKTimes(int[] arr, int k, int m) {int intBits = 32;int[] bitCounter = new int[intBits];// bitCounter[0]: 0 位置的1出现了几个// bitCounter[i]: i 位置的1出现了几个for (int x : arr) {for (int i = 0; i < intBits; i++) {//				if (((x >> i) & 1) != 0) {//					bitCounter[i] += 1;//				}bitCounter[i] += (x >> i) & 1;}}int ans = 0;for (int i = 0; i < intBits; i++) {//			if (bitCounter[i] % m != 0) {//				// 在第i位上有1//				ans |= (1 << i);//			}// 题目变一下，如果能找到出现K次的数，就返回该数；如果找不到，返回-1。if (bitCounter[i] % m == 0) continue;if (bitCounter[i] % m == k) ans |= (1 << i);else return -1;}// 边界处理if (ans == 0) {int cnt = 0;for (int x : arr) {if (x == 0) cnt++;}if (cnt != k) return -1;}return ans;
}

3 单双链表、栈和队列、递归和Master公式、哈希表和有序表的使用和性能

• 内容：
  • 单链表、双链表
  • 栈、队列
  • 递归的物理实质
  • 评估递归复杂度的Master公式
  • 哈希表的使用和性能
  • 有序表的使用和性能

3.1 反转单链表、反转双链表

• 反转单链表

• 反转双链表

3.2 在链表中删除指定值的所有节点

public static Node removeValue(Node head, int num) {// head来到第一个不需要删的位置while (head != null) {if (head.val != num) break;head = head.next;}// 1 ) head == null// 2 ) head != nullNode pre = head;Node cur = head;while (cur != null) {if (cur.val == num) pre.next = cur.next;else pre = cur;cur = cur.next;}return head;
}

3.3 用双链表实现栈和队列

• 基于之前实现的双端队列 MyDeque 实现

public static class MyStack<T> {private MyDeque<T> queue;public MyStack() {queue = new MyDeque<>();}public void push(T value) {queue.pushHead(value);}public T pop() {return queue.pollHead();}public boolean isEmpty() {return queue.isEmpty();}
}public static class MyQueue<T> {private MyDeque<T> queue;public MyQueue() {queue = new MyDeque<>();}public void push(T value) {queue.pushHead(value);}public T poll() {return queue.pollTail();}public boolean isEmpty() {return queue.isEmpty();}
}

3.4 用环形数组实现栈和队列

public static class MyQueue {private int[] items;private int head;private int tail;private int size;private final int capacity;public MyQueue(int capacity) {this.items = new int[capacity];this.head = 0;this.tail = 0;this.size = 0;this.capacity = capacity;}public void push(int val) {if (isFull()) throw new RuntimeException("queue is full");size++;items[head] = val;head = resetOffset(head);}public int pop() {if (isEmpty()) throw new RuntimeException("queue is empty");size--;int item = items[tail];tail = resetOffset(tail);return item;}public boolean isEmpty() {return size == 0;}public boolean isFull() {return size == capacity;}private int resetOffset(int idx) {return idx < capacity - 1 ? idx + 1 : 0;} 
}

3.5 实现有getMin功能的栈

public static class MinStack {// 定义两个栈：一个数据栈(用于正常存放数据)、一个最小栈(用于存放栈中的最小值)private Stack<Integer> dataStack;private Stack<Integer> minStack;public MinStack() {dataStack = new Stack<>();minStack = new Stack<>();}public void push(int newVal) {dataStack.push(newVal);// 每次push新值时，同时维护最小栈minStack// minStack如果为空，则直接放进去；如果不为空，则比较当前栈顶最小值和新值，取小的minStack.push(minStack.isEmpty() ? newVal : Math.min(newVal, minStack.peek()));}public int pop() {if (dataStack.isEmpty()) throw new RuntimeException("MinStack is Empty");int val = dataStack.pop();// 每次pop时，比较是否是栈顶的最小值，如果是，则minStack也需要出栈if (val == minStack.peek()) minStack.pop();return val;}public int getMin() {if (minStack.isEmpty()) throw new RuntimeException("MinStack is Empty");return minStack.peek();}
}

3.6 两个栈实现队列

public static class StackQueue<T> {// 定义两个栈：一个push栈(作为队列头部加数据)、一个pop栈(作为队列尾部取数据)private Stack<T> pushStack;private Stack<T> popStack;public StackQueue() {this.pushStack = new Stack<>();this.popStack = new Stack<>();}public void add(T val) {pushStack.push(val);// 每次添加数据时，同时维护pop栈popStack// popStack为空时，才将pushStack中的数据导入到popStackrebalance();}public T remove() {if (isEmpty()) throw new RuntimeException("StackQueue is empty");// 每次移除数据时，同时维护pop栈popStackrebalance();return popStack.pop();}public T peek() {if (isEmpty()) throw new RuntimeException("StackQueue is empty");// 每次查看数据时，同时维护pop栈popStackrebalance();return popStack.peek();}private void rebalance() {if (!popStack.isEmpty()) return;while (!pushStack.isEmpty()) popStack.push(pushStack.pop());}private boolean isEmpty() {return popStack.isEmpty() && pushStack.isEmpty();}
}

3.7 两个队列实现栈

public static class QueueStack<T> {// 定义两个队列：一个用于入栈、出栈，一个用于来回倒数据private Queue<T> queue;private Queue<T> help;public QueueStack() {this.queue = new LinkedList<>();this.help = new LinkedList<