数据结构与算法（二）

数据结构与算法（二）

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;
1
2
3

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];
}
1
2
3
4
5
6

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

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

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

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 :00000000000001000
    int rightOne = eor & (-eor); // 提取出最右的1

    int onlyOne = 0; // eor'
    for (int i = 0 ; i < arr.length;i++) {
   
        //  arr[1] =  111100011110000
        // rightOne=  000000000010000
        if ((arr[i] & rightOne) != 0) {
   
            onlyOne ^= arr[i];
        }
    }
    System.out.println(onlyOne + " " + (eor ^ onlyOne));
}
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

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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);
        }
    }
    return ans;
}
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

题目变一下，如果能找到出现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;
}
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

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 != null
    Node pre = head;
    Node cur = head;
    while (cur != null) {
   
        if (cur.val == num) pre.next = cur.next;
        else pre = cur;
        cur = cur.next;
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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();
    }
}
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

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;
    } 
}
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

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();
    }
}
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

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中的数据导入到popStack
        rebalance();
    }
    public T remove() {
   
        if (isEmpty()) throw new RuntimeException("StackQueue is empty");
        // 每次移除数据时，同时维护pop栈popStack
        rebalance();
        return popStack.pop();
    }
    public T peek() {
   
        if (isEmpty()) throw new RuntimeException("StackQueue is empty");
        // 每次查看数据时，同时维护pop栈popStack
        rebalance();
        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();
    }
}
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

3.7 两个队列实现栈

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