笔试准备

基本知识

数据结构

栈

• Java

  Stack<Integer> s1 = new Stack<Integer>();
  Stack<Integer> s2 = new Stack<Integer>();
  s1.push(x);
  s2.push(x);
  int p1 = s1.peek();
  int p2 = s2.peek();
  System.out.println(p1 == p2);
  System.out.println(s1.peek() == s2.peek());

  序号	方法描述
  1	boolean empty() 测试堆栈是否为空。
  2	Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。
  3	Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。
  4	Object push(Object element) 把项压入堆栈顶部。
  5	int search(Object element) 返回对象在堆栈中的位置，以 1 为基数。

• C++

  stack<int> st;
  st.push(1), a =  st.top(), st.pop(), st.size(), st.empty();

• Python

  一般我会用数组

  st = []
  st.append(1)
  st.pop()
  len(st)
  if st:
      print("st不为空")
  else:
      print("st为空")

队列

其实一般说到队列，我们更多的时候会想到Queue，但是Java中做了很多封装，常用的如LinkedList，C++则可以用dequeue或者queue

• Java

  LinkedList<String> sites = new LinkedList<String>();

  方法	描述
  public boolean add(E e)	链表末尾添加元素，返回是否成功，成功为 true，失败为 false。
  public void add(int index, E element)	向指定位置插入元素。
  public boolean addAll(Collection c)	将一个集合的所有元素添加到链表后面，返回是否成功，成功为 true，失败为 false。
  public boolean addAll(int index, Collection c)	将一个集合的所有元素添加到链表的指定位置后面，返回是否成功，成功为 true，失败为 false。
  public void addFirst(E e)	元素添加到头部。
  public void addLast(E e)	元素添加到尾部。
  public boolean offer(E e)	向链表末尾添加元素，返回是否成功，成功为 true，失败为 false。
  public boolean offerFirst(E e)	头部插入元素，返回是否成功，成功为 true，失败为 false。
  public boolean offerLast(E e)	尾部插入元素，返回是否成功，成功为 true，失败为 false。
  public void clear()	清空链表。
  public E removeFirst()	删除并返回第一个元素。
  public E removeLast()	删除并返回最后一个元素。
  public boolean remove(Object o)	删除某一元素，返回是否成功，成功为 true，失败为 false。
  public E remove(int index)	删除指定位置的元素。
  public E poll()	删除并返回第一个元素。
  public E remove()	删除并返回第一个元素。
  public boolean contains(Object o)	判断是否含有某一元素。
  public E get(int index)	返回指定位置的元素。
  public E getFirst()	返回第一个元素。
  public E getLast()	返回最后一个元素。
  public int indexOf(Object o)	查找指定元素从前往后第一次出现的索引。
  public int lastIndexOf(Object o)	查找指定元素最后一次出现的索引。
  public E peek()	返回第一个元素。
  public E element()	返回第一个元素。
  public E peekFirst()	返回头部元素。
  public E peekLast()	返回尾部元素。
  public E set(int index, E element)	设置指定位置的元素。
  public Object clone()	克隆该列表。
  public Iterator descendingIterator()	返回倒序迭代器。
  public int size()	返回链表元素个数。
  public ListIterator listIterator(int index)	返回从指定位置开始到末尾的迭代器。
  public Object[] toArray()	返回一个由链表元素组成的数组。
  public T[] toArray(T[] a)	返回一个由链表元素转换类型而成的数组。

• C++

  queue<int> qu;
  dequeue<int> dequ;

  方法	双端队列
  push(int x)	pop_back()
  pop()	pop_front()
  size()	push_back()
  empty()	push_front
  	insert(int index, int val)
  	erase(int index)

• Python

  引用模块Queueimport Queue

  Queue.qsize() 返回队列的大小
  Queue.empty() 如果队列为空，返回True,反之False
  Queue.full() 如果队列满了，返回True,反之False，Queue.full 与 maxsize 大小对应
  Queue.get([block[, timeout]])获取队列，timeout等待时间
  Queue.get_nowait() 相当于Queue.get(False)，非阻塞方法
  Queue.put(item) 写入队列，timeout等待时间
  Queue.task_done() 在完成一项工作之后，Queue.task_done()函数向任务已经完成的队列发送一个信号。每个get()调用得到一个任务，接下来task_done()调用告诉队列该任务已经处理完毕。
  Queue.join() 实际上意味着等到队列为空，再执行别的操作

链表

• Java：略
• C++：略
• Python：略

树&图

将树和图放在一起讲，因为他们之间最大的区别就在于有环和无环（或者有向和无向，毕竟树的本质就是有向无环图），而在程序算法设计中，对于其数据信息，我个人一般会用数组或者结构体来存储，只有在使用的时候才会具体区分其是数还是图。因为平时C++用的比较多，但是投的是Java岗，所以这里给出Java的一些实现方式（以后会把C++的各种算法模板放上来）

• Java

  链式向前星

  import java.util.Arrays;
  
  public class Tree {
      private final int N = 10005;
      private Node[] edge = new Node[N << 1];
      private int[] head = new int[N];
      private boolean[] vis = new boolean[N];
      private int cnt = 0;
  
      private static class Node {
          int to, next;
      }
  
      public Tree() {
          Arrays.fill(head, -1);
          Arrays.fill(vis, false);
      }
  
      public void add(int u, int v) {
          edge[cnt] = new Node(); // 注意初始化
          edge[cnt].to = v;
          edge[cnt].next = head[u];
          head[u] = cnt++;
      }
  
      public void dfs(int u, int depth) {
  
          for (int i = head[u]; ~i != 0; i = edge[i].next) {
              int v = edge[i].to;
              if (!vis[v]) {
                  vis[v] = true;
                  System.out.printf("From %d to %d, depth: %d%n", u, v, depth);
                  dfs(v, depth + 1);
                  vis[v] = false;
              }
          }
      }
  
      public static void main(String[] args) {
          int a = -1;
          System.out.println(~a == 0);
          Tree tree = new Tree();
          for (int i = 0; i < 10; ++i) tree.add(i / 2, i + 1);
          tree.dfs(0, 0);
      }
  }

• C++

• Python

常用算法

字符串处理

模式匹配：KMP算法

先从最朴素的算法开始

public static int simple(String source, String target) {
    char[] s = source.toCharArray();
    char[] t = target.toCharArray();
    int i = 0; // 主串的位置
    int j = 0; // 模式串的位置
    while (i < s.length && j < t.length) {
        if (s[i] == t[j]) { // 当两个字符相同，就比较下一个
            i++;
            j++;
        } else {
            i = i - j + 1; // 一旦不匹配，i后退
            j = 0; // j归0
        }
    }
    if (j == t.length) {
        return i - j;
    } else {
        return -1;
    }
}

这里的问题是如果source长这样：”xxxxxxxaaabc”，target=”abc”，那么当target[0]匹配不到source[0]时，target[0]会去匹配source[1]，但事实上source[1]和source[0]相等（都是’x’），甚至之后的好多字符都是’x’，无法匹配target[0]，那么我们能不能直接”跳“到与target[0]匹配的位置呢？又该如何跳呢？

可以肯定的是，我们需要一个数组来保存每个soure中每一个下标对应的跳跃位置；但事实是，这个数组和source并没有关系，我们需要的是target对应的跳跃数组，将其命名为next，下面给出next的获取方式，以便讲解

// 最前面的k个字符和j之前的最后k个字符是一样的。
public static int[] getNext(String target) {
    char[] t = target.toCharArray();
    int[] next = new int[target.length()];
    next[0] = -1;
    int j = 0;
    int k = -1;
    while (j < t.length - 1) {
        if (k == -1 || t[j] == t[k]) {
            next[++j] = ++k;
        } else {
            k = next[k];
        }
    }
    return next;
}

依然使用上述例子，我们假设source=’abaabxxaaabc==abaababc==’，target=’abaababc’，底纹是为了方便观看

==abaab==xxaaabcabaababc

==abaab==abc

对于这前五个字符串，当第六个字符不匹配的时候，此时j=5，表示next数组的下一个值的位置，k=4，而此时t[5]为’a’，t[4]为’x’，我们发现，如果按照朴素的算法来，那么跳跃的格子数将为1（事实上朴素的暴力算法next数组全为1），但是对于字符串’abaab’，其前缀和后缀的最大匹配长度为2，即我们可以直接将target的头与第四个字符对齐，也就是

==abaab==xxaaabcabaababc

  ==abaab==abc

这样正好相当于跳了两个格子，剩下的正常匹配即可

public static int KMP(String source, String target) {
    char[] s = source.toCharArray();
    char[] t = target.toCharArray();
    int i = 0; // 主串的位置
    int j = 0; // 模式串的位置
    int[] next = getNext(target);
    while (i < s.length && j < t.length) {
        if (j == -1 || s[i] == t[j]) { // 当j为-1时，要移动的是i，当然j也要归0
            i++;
            j++;
        } else {
            // i不需要回溯了
            // i = i - j + 1;
            j = next[j]; // j回到指定位置
        }
    }
    if (j == t.length) {
        return i - j;
    } else {
        return -1;
    }
}

排序

复杂度&稳定性概览

归并

 // 注意是左闭右闭
private int[] MergeSort(int[] nums, int left, int right) {
    int mid = left + right >> 1;
    if (left < right) {
        // 左边归并
        MergeSort(nums, left, mid);
        // 右边归并
        MergeSort(nums, mid + 1, right);
        // 合并，最重要的
        merge(nums, left, mid, right);
    }
    return nums;
}
// 仍然是左闭右闭
// 在此之前，nums[left:mid]和nums[mid:right]都已经是有序的了
private void merge(int[] nums, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, cur = 0;
    while (i <= mid && j <= right) {
        // 放相对小的
        if (nums[i] < nums[j]) temp[cur++] = nums[i++];
        else temp[cur++] = nums[j++];
    }
    // 把剩下相对大的放进去
    while (i <= mid) temp[cur++] = nums[i++];
    while (j <= right) temp[cur++] = nums[j++];
    // 然后放到nums中
    for (i = 0; i < temp.length; ++i) nums[i + left] = temp[i];
}

快排

public void QuickSort(int[] nums, int left, int right) {
    if (left >= right) return;
    int key = Partition(nums, left, right);
    QuickSort(nums, left, key - 1);
    QuickSort(nums, key + 1, right);
}

private int Partition(int[] nums, int left, int right) {
    int key = left;//取最左边的元素做key
    while (left < right) {//当左右没有相遇
        while (left < right && nums[right] >= nums[key])//如果右比key小就退出循环
            right--;
        while (left < right && nums[left] <= nums[key])//如果左比key大就退出循环
            left++;
        swap(nums, left, right);//交换左右
    }
    swap(nums, key, left);
    return left;//返回key的位置
}

private void swap(int[] nums, int left, int right) {
    int t = nums[left];
    nums[left] = nums[right];
    nums[right] = t;
}

堆排

原理就是通过构建一个大（小）顶堆，并插入元素，不断调整堆结构的过程。

优化的地方在于，使用数组来构建堆（数据结构中讲过），而C++中我可能会用priority_queue<int>来做，毕竟push然后pop就完事了

public void heapSort(int[] array) {
    if (array == null) return;
    // heap的根节点为0
    int length = array.length;
    // 从非叶节点开始构建大顶堆
    for (int i = length / 2 - 1; i >= 0; --i) {
        // 从第一个非叶子结点从下至上，从右至左调整结构
        // pos/2 表示的是父结点， 再减一则是上一层的最后一个结点
        // 从这里开始是为了初始化大顶堆（注意默认的array是有元素的）
        adjustHeap(array, i, length);
    }
    //2.调整堆结构+交换堆顶元素与末尾元素，此做法相当于把最大值放到末尾，然后就不将末尾元素纳入排序的范围内了，也就等同于"pop"了
    for (int j = length - 1; j > 0; j--) {
        //将堆顶元素与末尾元素进行交换
        swap(array, 0, j);
        //重新对堆进行调整
        adjustHeap(array, 0, j);
    }
}

private void adjustHeap(int[] array, int i, int length) {
    int tmp = array[i];
    // 左递归子节点
    for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
        // 与兄弟结点比较并取大的那一个
        if (k + 1 < length && array[k] < array[k + 1]) {
            k++;
        }
        // 如果子节点大于父节点，将子节点值赋给父节点，且array[i]这个位置相当于被“置空”了
        if (array[k] > tmp) {
            array[i] = array[k];
            i = k;
        } else {
            // 一直找到一个比tmp小的，break掉
            // 这样前一个位置，也就是array[i]一定是比array大且位置已经“置空”了的
            break;
        }
    }
    // 到这里就相当于为tmp找到了他合适的位置了
    array[i] = tmp;
}

计数排序

public static void countingSort(int[] array) {
    if (array == null) return;

    int length = array.length;

    int mx = array[0];
    int mn = array[0];
    for (int v : array) {
        mx = Math.max(mx, v);
        mn = Math.min(mn, v);
    }
    // 最大最小元素之间范围[mn, mx]的长度
    int offset = mx - mn + 1;
    int[] count = new int[offset + 1];

    for (int v : array) {
        // 计算当前值的频率，为了方便下面对count进行前缀和，那么这个值将等同于下一个值的开始位置
        count[v - mn + 1]++;
    }
    // 求和是为了方便后面给临时数组赋值
    // 例如：[2,4,4,5,5,5]（就不打乱顺序了） 对应的count数组为：[0,1,2,3] -> [0, 1, 3, 6]，第一个值0代表最小值的开始位置
    // 我们会发现，如果将count数组中的每个值看做下标，其正好是排序的数组aux中每个数对应的末尾
    // 如0的后面的下标是1，最后一个1的后面是3，最后一个2的后面是6
    for (int i = 0; i < offset; i++) {
        count[i + 1] += count[i];
    }
    // 3. 元素按照开始索引分类，用到一个和待排数组一样大临时数组存放数据
    int[] aux = new int[length];
    for (int v : array) {
        // 填充一个数据后，自增，以便相同的数据可以填到下一个空位
        aux[count[v - mn]++] = v;
    }
    // 4. 复制该数组到array中，注意这里使用了Python写法方面阅读，实际使用需要删除`XXX=`
    System.arraycopy(aux, sourcePos=0, array, destinationPos=0, len=length);
}

桶排序

原理有点类似于归并+计数，就是按照一定的规则将数据放到不同index的桶中，然后对所有非空的桶，对他们按照一定的算法进行排序（如归并、快排，甚至是递归的桶排序，注意，如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。），然后再按照index从小到大一个个放入原array中，下面给出一个简单的计算index的规则，知乎上的

private static int toBucketIndex(int value, int maxValue, int length) {
	return (value * length) / (maxValue + 1);
}

样例效果如下：长度为10，maxValue=94，注意这个规则要根据具体的桶的数量来定（如果可以申请很多桶，那么在计算到index过大的时候，可以用LinkedList，与ArrayList 相比，LinkedList 的增加和删除的操作效率更高，而查找和修改的操作效率较低。）

基数排序

在此之前请先读懂计数排序和桶排序

原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

• LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

  • 取得数组中的最大数，并取得位数；
  • arr为原始数组，从最低位开始取每个位组成radix数组；
  • 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

  

  说一下个人理解的原理：对于第i次结束后，第i位（从低位开始）一定是有序的。

  • 例如只有一位数字：[4, 6, 3]

    那么放到对应的桶（分别对应4,6,3）中再按照0-9的顺序拿出来之后变成[3, 4, 6]，即第一位变成有序的了。

  • 若只有两位数字：[910, 20, 45, 43, 61]

    从第一位开始，放到桶中再拿出来变成[910, 20, 61, 43, 45]，我们会发现，若【两个数字，设为a,b】第二位的数字（即十位）是相同的，那么在第一次操作之后，其一定会变成有序的，且即使a==b，a和b的相对位置也不会变（因为先进先出），如同这里的43和45。

    当我们对第二位操作的时候，由于43, 45的相对位置不变，因此不必担心【再次排序可能会打乱其顺序？】的问题，所以再次操作将其拿出来后，会变成[910, 20, 43, 45, 61]，可以发现，所有的二位数都有序了。

    而这里放了一个三位数的意义就在于，说明其并不会影响与之位数不同的数的排序，因为在我们进行第三次操作后，由于其他数的前缀默认添加了0，那么它自然会跑到后面去

  public void LSD(int[] array) {
      int length = array.length;
  
      int mx = Arrays.stream(array).max().getAsInt();
      // 【长度最长的数字】的长度
      int d = Arrays.stream(array).map(s -> String.valueOf(s).length()).max().getAsInt();
      // 0-9正好十个桶
      LinkedList<Integer>[] bucket = (LinkedList<Integer>[]) new LinkedList[10];
      int mod = 1;
      // 从1到d
      for (int i = 1; i <= d; i++) {
          for (int v : array) {
              int index = (v / mod) % 10;
              if (bucket[index] == null) {
                  bucket[index] = new LinkedList<>();
              }
              bucket[index].add(v);
          }
          int count = 0;
          for (int j = 0; j < 10; j++) {
              if (bucket[j] == null) continue;
              for (int v : bucket[j]) {
                  array[count++] = v;
              }
              bucket[j].clear();
          }
          mod *= 10;
      }
  }

• MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序

  • 找出待排序的数组中最大和最小的元素；
  • 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
  • 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
  • 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

  

  知乎上抄的，暂不做翻译了，原地址

  public static void radixSort(int[] array) {
  	if (array == null || array.length <= 1) {
  		return;
  	}
  
  	int length = array.length;
  
  	// 每位数字范围0~9，基为10
  	int radix = 10;
  	int[] aux = new int[length];
  	int[] count = new int[radix + 1];
  	// 以关键字来排序的轮数，由位数最多的数字决定，其余位数少的数字在比较高位时，自动用0进行比较
  	// 将数字转换成字符串，字符串的长度就是数字的位数，字符串最长的那个数字也拥有最多的位数
  	int x = Arrays.stream(array).map(s -> String.valueOf(s).length()).max().getAsInt();
  
  	// 共需要d轮计数排序, 从d = 0开始，说明是从个位开始比较，符合从右到左的顺序
  	for (int d = 0; d < x; d++) {
  		// 1. 计算频率，在需要的数组长度上额外加1
  		for (int i = 0; i < length; i++) {
  			// 使用加1后的索引，有重复的该位置就自增
  			count[digitAt(array[i], d) + 1]++;
  		}
  		// 2. 频率 -> 元素的开始索引
  		for (int i = 0; i < radix; i++) {
  			count[i + 1] += count[i];
  		}
  
  		// 3. 元素按照开始索引分类，用到一个和待排数组一样大临时数组存放数据
  		for (int i = 0; i < length; i++) {
  			// 填充一个数据后，自增，以便相同的数据可以填到下一个空位
  			aux[count[digitAt(array[i], d)]++] = array[i];
  		}
  		// 4. 数据回写
  		for (int i = 0; i < length; i++) {
  			array[i] = aux[i];
  		}
  		// 重置count[]，以便下一轮统计使用
  		for (int i = 0; i < count.length; i++) {
  			count[i] = 0;
  		}
  
  	}
  }
  // 与上面的mod作用相同
  private static int digitAt(int value, int d) {
  	return (value / (int) Math.pow(10, d)) % 10;
  }

选择排序

从0-len，选出最大（小）的元素放到头部，然后在剩下len-1个选，以此类推

public static void selectionSort(int[] array) {
	if (array == null || array.length <= 1) {
		return;
	}

	int length = array.length;

	for (int i = 0; i < length - 1; i++) {
		// 保存最小数的索引
		int minIndex = i;

		for (int j = i + 1; j < length; j++) {
			// 找到最小的数
			if (array[j] < array[minIndex]) {
				minIndex = j;
			}
		}

		// 交换元素位置
		if (i != minIndex) {
			swap(array, minIndex, i);
		}
	}

}

希尔排序

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

public static void shellSort(int[] array) {
	if (array == null || array.length <= 1) {
		return;
	}

	int length = array.length;

	// temp为临时变量，gap增量默认是长度的一半，每次变为之前的一半，直到最终数组有序
	int temp, gap = length / 2;

	while (gap > 0) {
		for (int i = gap; i < length; i++) {
			// 将当前的数与减去增量之后位置的数进行比较，如果大于当前数，将它后移
			temp = array[i];
			int preIndex = i - gap;
			// 有可能分成好多组，所以要用while去寻找每个组中对应i的preIndex中值最大的
			while (preIndex >= 0 && array[preIndex] > temp) {
				array[preIndex + gap] = array[preIndex];
				preIndex -= gap;
			}

			// 将当前数放到空出来的位置
			array[preIndex + gap] = temp;

		}
		gap /= 2; // 实际上这里的2和上面的length / 2都可以将2设为参数，让用户去选择增量gap
	}
}

查找

• 二分查找
• 分块查找
• 二叉查找树：AVL树、红黑树、splag树

分治

• 二分查找就是分治
• 二分答案

操作系统

进程和线程

• 进程（Process）是资源分配的基本单位，线程（Thread）是CPU调度的基本单位。
• 线程将进程的资源分和CPU调度分离开来。 以前进程既是资源分配又是CPU调度的基本单位，后来为了更好的利用高性能的CPU，将资源分配和CPU调度分开。因此，出现了线程。
• 进程和线程的联系： 一个线程只能属于一个进程，一个进程可以拥有多个线程。线程之间共享进程资源。
• 进程和线程的实例： 打开一个QQ，向朋友A发文字消息是一个线程，向朋友B发语音是一个线程，查看QQ空间是一个线程。QQ软件的运行是一个进程，软件中支持不同的操作，需要由线程去完成这些不同的任务。

死锁

同步

中断

内存管理

计算机网络

几种网络协议和模型

软件工程

各种UML图：多画几个例子

其他注意点

• 代码：展现专业素质
• 面向对象编程（不要只用main函数）：用结构化（class或struct）
• 代码规范：命名规则（英文或拼音、驼峰命名）、对齐和缩进
• 阅读代码能力：快速读懂代码
• 写代码的能力：熟悉常用算法模板、一次性0bug

进阶补充

计算几何

• 线性代数：与图像处理相关的一些矩阵变换
• 基础：向量的点乘和叉乘
• 判断：线段相交、点在多边形内部、线段与直线相交、两条之间交点、多边形面积和重心（有一些模板）
• 提高：凸包、半平面交