chenyuxiang0425

Markdown    4 hrs          ███████████████▌░░░░░  74.1%
Python      1 hr 12 mins   ████▋░░░░░░░░░░░░░░░░  22.5%
Other       10 mins        ▋░░░░░░░░░░░░░░░░░░░░   3.2%
CSV         0 secs         ░░░░░░░░░░░░░░░░░░░░░   0.2%

chenyuxiang0425

#伪代码：

Dijkstra(G, s):
    while not every vertex has been visited:
        visit(unmarked vertex v for which distTo(v) is minimized)

visit(v):
    mark(v)
    for each edge e of s:
        relax(e)          # 这一步是对访问的节点的每个 edge 进行计算

chenyuxiang0425

/**
 * 求两个非负整数的最大公约数
 * @param p    非负整数
 * @param q    非负整数
 */
public static int gcd(int p, int q) {
    if (q == 0) return p;
    int r = p % q;
    return gcd(q,r);
}

chenyuxiang0425

public class BinarySearch {
  /**
   * 查找排序数组中值等于 key 的 index
   * @param key    目标值
   * @param a      排序数组
   * @return       值等于 key 时的 index，若找不到则为 -1
   */
  public static int rank(int key, int[] a) {
    int lo = 0;
    int hi = a.length - 1;

chenyuxiang0425

/*
* 求一个数的平方根
* @param c: 数
* @return 该数的平方根
*/
public static double sqrt(double c) {
 double err = 1e-15; //  误差因子
 double t = c;       //  随便猜一个近似值 t
 while (Math.abs(t - c/t) > err * t) {
   t = (c/t + t) / 2.0; 

chenyuxiang0425

• 算术表达式求值

算术表达式求值，(1+(2+3)*(4+5))

• 用两个栈，一个保存运算符，一个保存操作数
• 将操作数压入操作数栈
• 将运算符压入运算符栈
• 忽略左括号
• 遇到右括号，弹出一个运算符，弹出所需要的操作数，并将运算符和操作数运算的结果压入操作数栈

计算实例

chenyuxiang0425

import java.util.Arrays;

public class UnionFind {
    private int[] intSet;
    /* Creates a UnionFind data structure holding n vertices. Initially, all
       vertices are in disjoint sets. */
    public UnionFind(int n) {
        intSet = new int[n];
        Arrays.fill(intSet, -1);
    }

chenyuxiang0425

public class MergeSort {
    
    private static int[] aux;  // 辅助数组

    /*
     * 自底而上归并排序法对 a 数组的元素进行排序
     * @param a 原数组
     * @effect a 数组中的所有元素变为升序
     */
    public static void mergeSortDownToUp(int[] a) {

chenyuxiang0425

收集一些元素,从N个元素中找到M个最大或最小元素

优先队列 MAXPQ

• 两个重要操作： 删除最大元素delMax()和插入元素insert

二叉堆实现优先级队列

• 二叉堆的每个元素要大于两个特定位置的元素
  • k 的上一层是 k/2, k 的下一层是 2k、2k+1 (a[0] 作为哨兵节点可以简化这个的实现)
  • 两个帮助方法，上浮swim(int k),下沉sink(int k)
• 上浮实现： while 反复比较 k 和 k/2 的大小

chenyuxiang0425

class BinarySearch {
	/*
   * 在已排序数组中找到 key 的 index,如果找不到则返回小于 key 的个数
   * @param a 已排序数组
   * @param key 目标值
   */

	public static int binarySearchRecursion(int[] a,int key) {
		return binarySearchRecursionHelper(a,key,0,a.length-1);
	}