算法分类与总结

二进制相关

  1. 获取最接近n的2的整数次幂(用于HashMap扩容)
    思路：n–的目的是为了num等于2的整数次幂的时候结果正确,下面的多次右移是为了保证最高位1的后面全部是1,返回n+1;
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // 给定一个非负整数num,返回离num最近的(大于等于)2的某次方
    public static final int tableSizeFor(int n) {
        n--;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : n + 1;
    }
    总结：要拿到一个数的2的整数次幂，首先将这个数转化为2进制，离他最近的二进制数就是他最高位1左移一位，后面全部补0;
    获得技巧：通过多次右移可以拿到最高位1后面全部是1的数;

贪心算法相关

  1. 一个数组中只有两种字符’G’和’B’，可以让所有的G都放在左侧，所有的B都放在右侧，或者可以让所有的G都放在右侧，所有的B都放在左侧，但是只能在相邻字符之间进行交换操作，请问请问至少需要交换几次。
    思路：保证数组中碰到的第一个G放在第0位，第二个G放在第1位，以此类推，最终得到所有的G在左，B在右;
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public static int minSteps(String s) {
        if (s == null || s.equals("")) {
            return 0;
        }
        char[] str = s.toCharArray();
        int step1 = 0;
        int step2 = 0;
        int gi = 0;
        int bi = 0;
        for (int i = 0; i < str.length; i++) {
            if (str[i] == 'G') {
                step1 += i - (gi++);
            } else {
                step2 += i - (bi++);
            }
        }
        return Math.min(step1, step2);
    }

动态规划相关

算法技巧收集

  1. 判断一个数是否是偶数： n & 1 != 0
  2. n /2 —> n >> 1
  3. 二叉树由于没有指向父节点的指针，构造每个节点的父节点map
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    HashMap<Node, Node> parents = new HashMap<>();
    parents.put(root, null);
    createParentMap(root, parents);

    public static void createParentMap(Node cur, HashMap<Node, Node> parents) {
    	if (cur == null) {
    		return;
    	}
    	if (cur.left != null) {
    		parents.put(cur.left, cur);
    		createParentMap(cur.left, parents);
    	}
    	if (cur.right != null) {
    		parents.put(cur.right, cur);
    		createParentMap(cur.right, parents);
    	}
    }