齐卫鹏的博客

数据结构学习笔记 - 07 集合

发表于 2020-12-03 更新于 2023-10-16

介绍

对于集合来说，主要涉及增、查、删的操作，不涉及改的操作。

集合的应用，比如词汇量统计，客户统计等。

集合分为有序集合与无序集合；二分搜索树实现的集合，包括 Java 中的 TreeSet 使用红黑树实现，都是有序集合，因为这个集合中的元素是有序排列的。

但是很多时候可能使用集合不会使用到集合的有序性，那么性能更好的无序集合就更适合。这里使用链表实现的集合虽然也是无序的，但是性能不好，但是如果使用哈希表实现，性能就很好了。

实现

定义集合的接口：

public interface Set<E> {

    /**
     * 添加元素 e
     */
    void add(E e);

    /**
     * 删除元素 e
     */
    void remove(E e);

    /**
     * 查看集合是否包含元素 e
     */
    boolean contains(E e);

    /**
     * 查看集合中元素的数量
     */
    int getSize();

    /**
     * 查看当前集合是否为空。
     */
    boolean isEmpty();
}

使用二分搜索树实现的集合：

public class BSTSet<E extends Comparable<E>> implements Set<E> {
    private BST<E> bst;

    public BSTSet() {
        bst = new BST<>();
    }

    @Override
    public int getSize() {
        return bst.size();
    }

    @Override
    public boolean isEmpty() {
        return bst.isEmpty();
    }

    @Override
    public void add(E e) {
        bst.add(e);
    }

    @Override
    public boolean contains(E e) {
        return bst.contains(e);
    }

    @Override
    public void remove(E e) {
        bst.remove(e);
    }
}

使用链表实现的集合：

public class LinkedListSet<E> implements Set<E> {

    private LinkedList<E> linkedList;

    public LinkedListSet() {
        linkedList = new LinkedList<>();
    }

    @Override
    public int getSize() {
        return linkedList.getSize();
    }

    @Override
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

    @Override
    public boolean contains(E e) {
        return linkedList.contains(e);
    }

    @Override
    public void add(E e) {
        if (!linkedList.contains(e)) {
            linkedList.addFirst(e);
        }
    }

    @Override
    public void remove(E e) {
        linkedList.removeElements(e);
    }
}

分析

	链表集合	二分搜索树集合（平均）	二分搜索树集合（最差）
增 add	O(n)	O(logn)	O(n)
查 contains	O(n)	O(logn)	O(n)
删 remove	O(n)	O(logn)	O(n)

对于链表集合来说，本身在链表头增加一个元素或者删除一个元素，都是 O(1) 级别的。但是为了查重，都需要遍历查询一边，链表的查询是 O(n) 级别的，所以最终增删也是 O(n) 级别的。

对于二分搜索树集合，它的增查删其实只是寻找了树的层树，我们用 h 表示。最好的情况，也就是树是满的情况下层数和元素数的关系是 2^h - 1 = n，h = log(n + 1) (log底是 2)。那么最好情况的复杂度就是 O(logn) 级别的，这其实很接近 O(1) 级别，在数据量大的时候要比 O(n) 好得多。但是对于二分搜索树来说，如果添加元素的时候恰好是从小到大或者相反地插入元素，这棵树就退化成链表了。要解决这个问题，就要使用平衡二叉树。

二分搜索树集合属于有序集合，有序集合都是基于搜索树实现的。如果我们需要使用集合的有序性这一特点，就要考虑使用搜索树来实现。比如有序集合更适合得到集合中的最大元素，最小元素等。

链表集合属于无序集合。无序集合也可以使用哈希表来实现，哈希表实现的集合性能比搜索树实现的更好。

数据结构学习笔记 - 06 二分搜索树

发表于 2020-11-09 更新于 2023-10-16

关于树结构

计算机中的文件夹系统，现实生活中的图书馆、公司组织架构等，都是树结构。

树结构相比线性结构的一大优势就是将查找效率由 O(n) 提升到了 O(lgn)，因为我们往往只需顺着树的一支就能找的我们需要的元素了。

二叉树介绍

二叉树名词：左孩子、右孩子、左子树、右子树、父亲节点、叶子节点；
二叉树具有唯一根节点；
每个节点最多有两个孩子节点；每个节点最多有一个父亲节点；
二叉树具有天然递归性，左子树、右子树都是一个二叉树；
二叉树不一定是满的，一个链表、一个根节点、甚至空都可以看作是一棵二叉树；

二分搜索树介绍

BST 即 Binary Search Tree 二分搜索树。

二分搜索树特点：

首先是一棵二叉树；
二分搜索树每一个节点的值都大于其左子树中所有节点的值，都小于其右子树中所有节点的值。二分搜索树具有顺序性。
所存储的元素必须具有可比较性。
不必是一棵完全二叉树，更不必是满二叉树。


// 这就是一棵二分搜索树。

         41
        /  \
       22  58
      / \    \
     15 40    61

所以，当我们在二分搜索树中查找一个元素的时候，只需从根节点开始比较即可，并不需要对所有元素进行遍历。

二分搜索树的实现

这里这个二分搜索树需要满足泛型，同时，这个类型必须是可比较的，因此，这个类型 E 需要满足 Comparable 这个接口。类似地，可以和 Swift 中的协议做对比。

我们实现的这个二分搜索树不包含重复元素。

public class BST<E extends Comparable<E>> {

    // 在类的内部定义一个二分搜索树的节点类
    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    // 根节点
    private Node root;
    // 元素数量
    private int size;

    public BST() {
        root = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 给树添加新元素。
     */
    public void add(E e) {

        // if (root == null) {
        //     root = new Node(e);
        //     size++;
        // } else {
        //     add(root, e);
        // }

        // 改进后
        root = add(root, e);
    }

    /**
     * 向以 node 为根的二分搜索树中插入元素 E， 递归算法。
     */
    // private void add(Node node, E e) {
    //     if (e.equals(node.e)) {
    //         return;
    //     } else if (e.compareTo(node.e) < 0 && node.left == null) {
    //         node.left = new Node(e);
    //         size++;
    //         return;
    //     } else if (e.compareTo(node.e) > 0 && node.right == null) {
    //         node.right = new Node(e);
    //         size++;
    //         return;
    //     }

    //     if (e.compareTo(node.e) < 0) {
    //         add(node.left, e);
    //     } else {
    //         add(node.right, e);
    //     }
    // }

    /**
     * 改进后的递归函数。
     */
    private Node add(Node node, E e) {

        if (node == null) {
            size++;
            return new Node(e);
        }

        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }

        return node;
    }

    /**
     * 查看二分搜索树中是否包含元素 e
     */
    public boolean contains(E e) {
        return contains(root, e);
    }

    /**
     * 私有的递归方法。
     */
    private boolean contains(Node node, E e) {

        if (node == null) {
            return false;
        }

        if (e.compareTo(node.e) == 0) {
            return true;
        } else if (e.compareTo(node.e) < 0) {
            return contains(node.left, e);
        } else {
            return contains(node.right, e);
        }
    }

    /**
     * 二分搜索树的前序遍历。
     * 前序遍历就是先访问节点，然后访问左右子树。
     */
    public void preOrder() {
        preOrder(root);
    }

    /**
     * 二分搜索树前序遍历私有递归方法。
     */
    private void preOrder(Node node) {

        if (node == null) {
            return;
        }

        System.out.println(node.e);

        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 非递归写法的前序遍历。
     */
    public void preOrderNR() {
        Stack<Node> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.println(cur.e);

            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
    }

    /**
     * 二分搜索树的中序遍历。中序遍历最重要的特点就是，它就是元素从小到大的排序。
     * 中序遍历就是先遍历左子树，再遍历根节点，再遍历右子树。
     */
    public void inOrder() {
        inOrder(root);
    }

    /**
     * 中序遍历递归方法。
     */
    private void inOrder(Node node) {
        if (node == null) {
            return;
        }

        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

    /**
     * 二分搜索树的后序遍历。
     * 后序遍历就是先遍历左右子树，再遍历根节点。
     * 后序遍历的一个应用是为二分搜索树释放内存。
     */
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }

        inOrder(node.left);
        inOrder(node.right);
        System.out.println(node.e);
    }

    /**
     * 层序遍历。顾名思义，就是从跟节点开始一层一层遍历，每层从左到右。
     * 层序遍历一般使用非递归的算法完成，需要使用队列。这也是队列的一个不错的应用。
     * 
     * 前序遍历、中序遍历、后序遍历都是深度优先遍历，而层序遍历是广度优先遍历。
     */
    public void levelOrder() {
        Queue<Node> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty()) {
            Node cur = q.remove();
            System.out.println(cur.e);

            if (cur.left != null) {
                q.add(cur.left);
            }

            if (cur.right != null) {
                q.add(cur.right);
            }
        }
    }

    /**
     * 寻找二分搜索树的最小元素。
     */
    public E minimum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty");
        }

        return minimum(root).e;
    }

    private Node minimum(Node node) {

        if (node.left == null) {
            return node;
        }

        return minimum(node.left);
    }

    /**
     * 寻找二分搜索树的最大元素。
     */
    public E maximum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty.");
        }

        return maximum(root).e;
    }

    private Node maximum(Node node) {

        if (node.right == null) {
            return node;
        }

        return maximum(node.right);
    }

    /**
     * 从二分搜索树中删除最小值所在的节点，返回最小值。
     * 注意点就是，如果最小值所在节点还存在右子树的话，需要把右子树的根节点接到该节点的位置。
     */
    public E removeMin() {
        E ret = minimum();

        root = removeMin(root);

        return ret;
    }

    /**
     * 删除以 node 为根的二分搜索树的最小节点，并返回删除节点后新的二分搜索树的根
     */
    private Node removeMin(Node node) {

        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }

    /**
     * 从二分搜索树中删除最大值所在的节点，返回最大值。
     * 注意点就是，如果最大值所在节点还存在左子树的话，需要把左子树的根节点接到该节点的位置。
     */
    public E removeMax() {
        E ret = maximum();

        root = removeMax(root);

        return ret;
    }

    /**
     * 删除以 node 为根的二分搜索树的最大节点，并返回删除节点后新的二分搜索树的根
     */
    private Node removeMax(Node node) {

        if (node.right == null) {

            // Java 里类的赋值是完全拷贝？
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }

        node.right = removeMin(node.right);
        return node;
    }

    /**
     * 从二分搜索树中删除元素为 e 的节点。
     */
    public void remove(E e) {
        root = remove(root, e);
    }

    private Node remove(Node node, E e) {
        if (node == null) {
            return null;
        }

        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            return node;
        } else {
            // 待删除节点右子树为空
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }

            // 待删除节点右子树为空
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }

            // 待删除节点左右子树均不为空
            // 找到比待删除节点大的最小节点，即待删除节点右子树的最小节点，也就是这个节点的后继（相应也有前驱的概念）。
            // 用这个节点顶替待删除节点的位置。
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;

            return successor;
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

        generateBSTString(root, 0, res);
        return res.toString();
    }

    // 生成以 node 为根节点，深度为 depth 的描述二叉树的字符串。
    private void generateBSTString(Node node, int depth, StringBuilder res) {

        if (node == null) {
            res.append(generateDepthString(depth) + "null\n");
            return;
        }

        res.append(generateDepthString(depth) + node.e + "\n");
        generateBSTString(node.left, depth + 1, res);
        generateBSTString(node.right, depth + 1, res);
    }

    private String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();

        for (int i = 0; i < depth; i++) {
            res.append("--");
        }

        return res.toString();
    }
}

二分搜索树的遍历

前序遍历：先根节点，再左右子树。非递归可使用栈辅助实现。
中序遍历：先左子树、再根节点、再右子树。中序遍历正好元素从小到大的排序顺序。
后序遍历：先左右子树，再根节点。应用场景是内存释放，必须先把孩子节点释放才能释放该节点本身。
层序遍历：从根节点开始一层一层遍历。非递归可使用队列辅助实现。

数据结构学习笔记 - 05 链表

发表于 2020-11-07 更新于 2023-10-16

介绍

之前学习的动态数组、栈、队列底层都是依托于静态数组，通过 resize 解决容量问题。
链表是最简单的动态数据结构。
优点：真正的动态，不需要处理固定容量的问题。
缺点：丧失了随机访问的能力（这也是数组的优点）。
Java 中 java.util.LinkedList 这个链表类底层使用双向循环链表实现。
链表如果看作一个抽象的数据结构，也可以使用数组来实现。只需要将指向下一个节点的指针改存为数组的某的位置的索引。

复杂度

链表各个操作时间复杂度：

addLast(e)     O(n)
addFirst(e)    O(1)
add(e)         O(n)
 
removeLast(e)  O(n)
removeFirst(e) O(1)
remove(e)      O(n)

set(index, e)  O(n)

get(index)     O(n)
contains(e)    O(n)

也就是说，对于链表来说，增删改查全是 O(n) 级别的。

但是需要注意，如果只是对链表头进行操作，那么不管是增删还是查，都是 O(1) 级别的。

链表的复杂度主要是花费在查找节点上，而具体删除或者插入的操作是很方便的，这点和数组不同，数组体现在查找特别快，但是删除或者插入比较麻烦。

链表的增删改查操作可以尝试使用递归实现。

链表的实现

public class LinkedList<E> {

    /**
     * Node
     * 链表的节点，设置为一个内部的私有类，只在链表类内部可以访问到。
     */
    private class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    // 第一个节点，即链表的头。对于链表来说，我们只跟踪链表的头，并没有跟踪链表的尾巴。
    // 这一点和数组不同，数组我们往往设计一个变量去跟踪数组的尾部。
    // 为了添加元素的统一，我们在真正的 head 前放置一个虚拟头节点。
    // private Node head;
    private Node dummyHead;
    // 元素个数。
    int size;

    public LinkedList() {
        // head = null;
        dummyHead = new Node();
        size = 0;
    }

    /**
     * 获取链表中元素的个数。
     */
    public int getSize() {
        return size;
    }

    /**
     * 链表是否为空。
     * 
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 在链表的指定 index 位置插入新的元素 e
     * 这个操作在链表中是一个不常用操作，主要是练习使用。
     */
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }

        // 如果为填表头添加元素需要特殊处理，那么我们可以使用为链表设立虚拟头节点的方式解决。
        // if (index == 0 ) {
        //     addFirst(e);
        // } else {
        //     Node prev = head;
        //     for (int i = 0; i < index - 1; i++) {
        //         prev = prev.next;
        //     }

        //     // Node node = new Node(e);
        //     // node.next = prev.next;
        //     // prev.next = node;
        //     prev.next = new Node(e, prev.next);

        //     size++;
        // }

        // 因为虚拟头节点的添加，我们不再需要 if-else
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        prev.next = new Node(e, prev.next);
        size++;
    }

    /**
     * 为链表头添加一个节点。
     * 对于链表来讲，在头部添加一个节点是最容易的。
     */
    public void addFirst(E e) {
        // Node node = new Node(e, head);
        // head = node;

        // size++;
        add(0, e);
    }

    /**
     * 在链表末尾添加元素。
     */
    public void addLast(E e) {
        add(size, e);
    }

    /**
     * 获得链表 index 位置的元素。
     * 这也不是一个常用操作，仅作练习使用。
     */
    public E get(int index) {

        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Get failed. Illegal index.");
        }

        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        return cur.e;
    }

    public E getFirst() {
        return get(0);
    }

    public E getLast() {
        return get(size - 1);
    }

    /**
     * 更新 index 位置的元素。
     * 不常用操作，练习使用。
     */
    public void set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Set failed. Illegal index.");
        }

        Node cur = dummyHead.next;

        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        cur.e = e;
    }

    /**
     * 查找链表中是否有元素 e
     */
    public boolean contains(E e) {

        Node cur = dummyHead.next;

        // for (int i = 0; i < size; i++) {
        //     if (cur.e.equals(e)) {
        //         return true;
        //     }
        //      cur = cur.next;
        // }
        // return false;

        while (cur != null) {
            if (cur.e.equals(e)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 删除指定 index 位置的元素，并返回所删除的元素。
     * 不常用操作，练习使用。
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Remove failed. Illegal index.");
        }

        Node prev = dummyHead;

        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        Node delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
        size--;

        return delNode.e;
    }

    public E removeFirst() {
        return remove(0);
    }

    public E removeLast() {
        return remove(size - 1);
    }

    // 从链表中删除元素 e
    public void removeElements(E e) {

        Node prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.e.equals(e)) {
                break;
            }
            prev = prev.next;
        }

        if (prev.next != null) {
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
        }
    }

    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();

        Node cur = dummyHead.next;
        while (cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }

        res.append("NULL");

        return res.toString();
    }
}

数据结构学习笔记 - 04 队列

发表于 2020-11-05 更新于 2023-10-16

介绍

队列的的操作也是数组的子集，不同的是，队列只能从一端（队尾）添加元素，只能从另一端（队首）取出元素。

队列实现

将队列定义为一个接口：

public interface Queue<E> {

    /**
     * 入队。
     * 
     * @param e 入队的元素。
     */
    void enqueue(E e);

    /**
     * 出队。
     * 
     * @return 出队的元素。
     */
    E dequeue();

    /**
     * 获得队首元素。
     * 
     * @return 队首的元素。
     */
    E getFront();

    /**
     * 获得队列中元素的个数。
     * 
     * @return 元素的个数。
     */
    int getSize();

    /**
     * 查看队列是否为空。
     * 
     * @return 队列是否为空。
     */
    boolean isEmpty();
}

使用动态数组实现队列：

/**
 * ArrayQueue
 * 
 * 类似栈的实现，这里也使用动态数组对队列进行一个实现。
 * 
 * 这个队列中的五个方法复杂度：
 * void enqueue(E)     O(1) 均摊
 * E dequeue()         O(n)
 * E getFront()        O(1)
 * int getSize()       O(1)
 * boolean isEmpty()   O(1)
 * 
 * 可以看到，数组实现的队列最大问题就是出队的复杂度是 O(n)
 */
public class ArrayQueue<E> implements Queue<E> {

    private Array<E> array;

    public ArrayQueue(int capacity) {
        array = new Array<>(capacity);
    }

    public ArrayQueue() {
        array = new Array<>();
    }

    /**
     * 队列的元素个数。
     */
    @Override
    public int getSize() {
        return array.getSize();
    }

    /**
     * 队列元素是否为空。
     */
    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    /**
     * 查看实现这个队列的这个动态数组当前的容积。
     */
    public int getCapacity() {
        return array.getCapacity();
    }

    /**
     * 入队。
     */
    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

    /**
     * 出队。
     */
    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    /**
     * 获取队首元素。
     */
    @Override
    public E getFront() {
        return array.getFirst();
    }

    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        res.append("front [");

        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize() - 1) {
                res.append(", ");
            }
        }

        res.append("] tail");

        return res.toString();
    }
}

使用循环队列解决数组队列出队复杂度高的问题：

/**
 * LoopQueue
 * 数组队列的问题在于，出队的时间复杂度过高，导致如果队列元素特别多的情况下，出队就比较耗时。
 * 循环队列可以解决这一问题。
 * 
 * 这个队列中的五个方法复杂度：
 * void enqueue(E)     O(1) 均摊
 * E dequeue()         O(1) 均摊
 * E getFront()        O(1)
 * int getSize()       O(1)
 * boolean isEmpty()   O(1)
 */
public class LoopQueue<E> implements Queue<E> {
    private E[] data;
    private int front, tail;
    private int size;

    @SuppressWarnings("unchecked")
    public LoopQueue(int capacity) {

        // 创建的数组容量比用户期望的多一个，因为循环队列中，我们会有意识的浪费掉一个空间。
        // 因为我们通常认为 front == tail 的时候是队列为空，对于循环队列，我们如果不让出一个空间，那么这个表达式也有可能是队列元素占满的情况。
        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue() {
        this(10);
    }

    /**
     * 循环队列创建的数组中，我们会有意识地浪费掉一个空间。
     * 
     * @return
     */
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * 循环队列使用 front == tail 来判断元素为空，这也是为什么创建数组需要多一个空间。
     */
    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    /**
     * 获得队列元素的个数。
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 入队。
     */
    @Override
    public void enqueue(E e) {

        // 判断队列是否满了
        if ((tail + 1) % data.length == front) {
            resize(getCapacity() * 2);
        }

        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }

    /**
     * 出队。
     */
    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;

        // 缩容。
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }

        return ret;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty.");
        }
        return data[front];
    }

    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];

        // 第一种遍历循环队列的所有元素的方式。
        for (int i = 0; i < size; i++) {
            // 当扩容或者缩容的时候，原本 front 不为 0 的队列被重新规整为 front 为 0 的队列了
            newData[i] = data[(i + front) % data.length];
        }

        data = newData;
        front = 0;
        tail = size;
    }

    /**
     * 打印该类的显示字符串。
     */
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("QUeue: size = %d, capacity = %d\n", size, getCapacity()));
        res.append("front [");

        // 第二种遍历循环队列中所有元素的方式。
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            res.append(data[i]);
            if ((i + 1) % data.length != tail) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }
}

使用链表实现队列：

/**
 * LinkedListQueue
 * 
 * 这里我们使用链表实现队列。
 * 由于队列需要从一端添加，另一端删除，对于链表来说，我们需要给它先添加一个 tail 标记，类似 head 标记那样，这样我们从末尾添加元素就也是 O(1)
 * 级别的了。
 * 但是有一个问题是，即使添加了 tail 标记，在从尾部删除一个元素的时候，我们无法快速找到 tail 之前的那个节点。
 * 
 * 所以合理的设计队列的方式就是，从尾部只负责添加元素，在链表的头部负责删除元素，也就是出队。
 * 
 * 这里我们设计的链表就不使用 dummyHead 了，但是要注意链表为空的情况。
 */
public class LinkedListQueue<E> implements Queue<E> {

    private class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        // public Node() {
        //     this(null);
        // }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node head, tail;
    private int size;

    public LinkedListQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void enqueue(E e) {
        if (tail == null) {
            tail = new Node(e);
            head = tail;
        } else {
            tail.next = new Node(e);
            tail = tail.next;
        }
        size++;
    }

    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        }

        Node retNode = head;
        head = head.next;
        retNode.next = null;
        if (head == null) {
            tail = null;
        }
        size--;
        return retNode.e;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty.");
        }

        return head.e;
    }

    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();
        res.append("Queue: front ");

        Node cur = head;
        while (cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }

        res.append("NULL tail");

        return res.toString();
    }
}

数据结构学习笔记 - 03 栈

发表于 2020-11-05 更新于 2023-10-16

介绍

栈对应的操作是数组的子集。

对于栈的理解，其实它就是一个数组，只不过只能从一端添加元素，也只能从这一端删除元素。

栈是一种后进先出的数据结构（LIFO）。

栈的应用

编辑器中的 Undo 操作，通常就是使用一个栈来维护的。
程序调用的系统栈。比如我们执行 A 函数，执行到第 2 行后其调用了 B 函数，那么 A 函数执行就暂停，开始调用 B 函数，此时就有一个栈来维护这个调用过程，类似 A2 就被 push 到栈里，记录 A 函数当前执行到第 2 行。类似的 B3 也可能被 push 到栈中去执行 C 函数，C 函数执行完了继续执行 B，那么栈就会执行一个 pop 操作。通过栈顶的记录，计算机就找到了继续执行哪个函数以及执行到哪里了。
编辑器中的括号匹配。

栈的实现

使用 Java 进行实现。我们将栈定义为一个接口。

public interface Stack<E> {

    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();
}

数组栈（使用之前实现的动态数组结构）：

/**
 * ArrayStack
 * 
 * 这个类基于我们自己实现的动态数组来实现「栈」这个接口。
 * 
 * 这个栈中的五个方法复杂度：
 * void push(E)        O(1) 均摊
 * E pop()             O(1) 均摊
 * E peek()            O(1)
 * int getSize()       O(1)
 * boolean isEmpty()   O(1)
 * 
 */
public class ArrayStack<E> implements Stack<E> {

    private Array<E> array;

    public ArrayStack(int capacity) {
        array = new Array<>(capacity);
    }

    public ArrayStack() {
        array = new Array<>();
    }

    /**
     * 栈的元素个数。
     */
    @Override
    public int getSize() {
        return array.getSize();
    }

    /**
     * 栈元素是否为空。
     */
    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    /**
     * 查看实现这个栈的这个动态数组当前的容积。
     * 这个方法不是栈特有的，因此栈接口没有定义这个方法，但是我们是使用数组实现的这个栈，可以有这个方法供用户查看。
     */
    public int getCapacity() {
        return array.getCapacity();
    }

    /**
     * 入栈。
     */
    @Override
    public void push(E e) {
        array.addLast(e);
    }

    /**
     * 出栈。
     */
    @Override
    public E pop() {
        return array.removeLast();
    }

    /**
     * 查看栈顶元素。
     */
    @Override
    public E peek() {
        return array.getLast();
    }

    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();
        res.append("Stack: ");
        res.append('[');

        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize() - 1) {
                res.append(", ");
            }
        }

        res.append("] top");

        return res.toString();
    }
}

链表栈（会使用之后实现的链表结构）：

/**
 * LinkedListStack
 * 使用链表来实现一个栈的数据结构。
 * 
 * 这个栈中的五个方法复杂度：
 * void push(E)        O(1)
 * E pop()             O(1)
 * E peek()            O(1)
 * int getSize()       O(1)
 * boolean isEmpty()   O(1)
 * 
 */
public class LinkedListStack<E> implements Stack<E> {
    private LinkedList<E> list;

    public LinkedListStack() {
        list = new LinkedList<>();
    }

    @Override
    public int getSize() {
        return list.getSize();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public void push(E e) {
        list.addFirst(e);
    }

    @Override
    public E pop() {
        return list.removeFirst();
    }

    @Override
    public E peek() {
        return list.getFirst();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

        res.append("Stack: top ");
        res.append(list);
        return res.toString();
    }
}

数据结构学习笔记 - 02 数组

发表于 2020-10-25 更新于 2023-10-16

介绍

数组最大的优点是可以快速查询，如 scores[2]；
数组最好应用于 “索引有语意” 的情况；

复杂度

操作	复杂度
增	O(n)
删	O(n)
改	已知索引 O(1) 未知索引 O(n)
查	已知索引 O(1) 未知索引 O(n)
`addLast(e)`	O(1)
`addFirst(e)`	O(n)
`add(index, e)`	O(n)
`removeLast(e)`	O(1)
`removeFirst(e)`	O(n)
`remove(index, e)`	O(n)
`resize`	O(1) （均摊复杂度）

静态数组

数组简单来讲就是将一组数据码成一排进行存放。内存中，会开辟一个连续的区间存放数组。一旦创建，数组的容量是固定的。

不同语言对数组的实现会略有不同：

语言	实现	类型	元素	可变
Java	`E[]（E 表示类型，如 int）`	引用类型	指定类型	容量不可变，元素可变
Objective-C	`NSArray`	引用类型	对象类型	容量不可变，元素可变
Swift	`Array`	值类型	指定类型	容量和元素均不可变

首先，三种语言的数组容量都是不可变的，这也是静态数组的特点，空间一旦开辟，就固定了；其次，对于元素的类型，Objective-C 是只要是对象即可，因此对元素类型的限制较小，而其他两种语言要求元素必须为指定的类型；最后，Swift 的数组使用值类型，而另外两种采用引用类型，这也使得 Swift 数组创建后，元素就无法做更改了。

动态数组的实现

动态数组使用静态数组实现，它必须要有的几个成员变量：

E[] data：使用一个静态数组作为容器来存放元素；
int capacity: 当前数组的容量，可以使用 data.length 表示；
int size：当前数组存放元素的个数；

使用 Java 实现：

public class Array<E> {

    // 使用一个静态数组来存放元素，也就是当前数组的容量。
    private E[] data;
    // 数组中存放元素的个数。
    private int size;

    /**
     * 构造函数。
     * 
     * @param capacity 数组初始容量。
     */
    @SuppressWarnings("unchecked")
    public Array(int capacity) {
        data = (E[]) new Object[capacity];
        size = 0;
    }

    /**
     * 无需传入数组容量的构造函数。默认初始容量为 10。
     */
    public Array() {
        this(10);
    }

    /**
     * 通过一个静态数组构造动态数组。
     * 如：Array<Integer> arr = new Array<>(new Integer[]{3, 1, 2});
     * 
     * @param arr 静态数组。
     */
    @SuppressWarnings("unchecked")
    public Array(E[] arr) {
        data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
        size = arr.length;
    }

    /**
     * 获取数组的容量。
     * 
     * @return 数组的容量。
     */
    public int getCapacity() {
        return data.length;
    }

    /**
     * 获取数组中元素的个数。
     * 
     * @return 数组中元素的个数。
     */
    public int getSize() {
        return size;
    }

    /**
     * 数组是否为空。
     * 
     * @return 数组是否为空。
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 在指定索引添加一个元素。
     * 时间复杂度最大为 O(n)，最小为 O(1)。总体计算应该算出各个可能性的期望复杂度，最终是 O(n/2)，由于常数忽略，所以还是 O(n)。
     * 
     * @param index
     * @param e
     */
    public void add(int index, E e) {
        // 索引必须合法
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
        }

        if (size == data.length) {
            // 修改前，如果数组已经满了，则无法添加新元素，抛出异常。
            // throw new IllegalArgumentException("Add failed. Array is full.");
            // 修改后，如果数组已经满了，则不再抛出异常，而是容量翻倍。
            resize(2 * data.length);
        }

        // 将索引后面的元素依次向后挪动一个位置，应该从最后一个元素开始挪起。
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }

        data[index] = e;
        size++;
    }

    /**
     * 向数组末尾添加元素。
     * 时间复杂度 O(1)，因为算法运行时间和输入数据规模无关，是一个常数，也就是和数组元素个数无关。
     * 
     * @param e 元素。
     */
    public void addLast(E e) {
        // 尾部添加一个元素可以调用 add 方法。
        add(size, e);
        // // 如果数组已经满了，则无法添加新元素，抛出异常。
        // if (size == data.length) {
        // throw new IllegalArgumentException("AddLast failed. Array is full.");
        // }
        // data[size] = e;
        // size++;
    }

    /**
     * 在数组开头插入一个元素。
     * 时间复杂度 O(n)，因为需要向后挪动 n 个元素，数组中所有内容都要向后挪动。
     * 
     * @param e 插入的元素。
     */
    public void addFirst(E e) {
        add(0, e);
    }

    /**
     * 获取某个元素。
     * 时间复杂度 O(1)。
     * 
     * @param index 索引。
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        }

        return data[index];
    }

    /**
     * 获取数组最后一个元素。
     */
    public E getLast() {
        return get(size - 1);
    }

    /**
     * 获取数组第一个元素。
     */
    public E getFirst() {
        return get(0);
    }

    /**
     * 修改 index 索引位置的元素为 e。
     * 时间复杂度 O(1)。这也是数组最大的优势，支持随机访问，知道索引的情况下改元素超快。
     * 
     * @param index 索引。
     * @param e     新设置的元素。
     */
    public void set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Set failed. Index is illegal.");
        }

        data[index] = e;
    }

    /**
     * 查找数组中是否包含某个元素。
     * 时间复杂度 O(n)。
     */
    public boolean contains(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 查找元素 e 所在的第一个索引，如果不存在该元素，则返回 -1。
     * 时间复杂度 O(n)。
     */
    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 从数组中删除指定索引的元素，并将其返回。
     * 时间复杂度 O(n)
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Remove failed. Index is Illegal.");
        }

        E ret = data[index];

        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        data[size] = null; // 可写可不写，写的话可以优化一点点内存。loitering objects != memory leak

        // 缩容采取 lazy 的策略，元素变为 1/4 时再进行缩容。
        // 这样的目的是防止复杂度震荡。
        if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }

        return ret;
    }

    /**
     * 删除第一个元素。
     * 时间复杂度 O(n)
     * 
     * @return 删除的元素。
     */
    public E removeFirst() {
        return remove(0);
    }

    /**
     * 删除最后一个元素。
     * 时间复杂度 O(1)
     * 
     * @return 删除的元素。
     */
    public E removeLast() {
        return remove(size - 1);
    }

    /**
     * 如果数组包含元素 e，则删除第一个 e。
     * 
     * @param e
     */
    public void removeElement(E e) {
        int index = find(e);
        if (index != -1) {
            remove(index);
        }
    }

    /**
     * 交换数组中指定两个索引的元素
     */
    public void swap(int i, int j) {
        if (i < 0 || i >= size || j < 0 || j >= size) {
            throw new IllegalArgumentException("Index is illegal.");
        }

        E t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    /**
     * 改变数组容量。
     * 
     * 对于该算法复杂度的分析，最合适的应该是均摊复杂度分析，而不应该使用最坏的情况。因为 resize 操作是不可能每次添加元素都触发的。
     * 由于不是每次操作都触发，则这次的耗时可以分摊到每一次操作中。
     * 使用均摊复杂度分析的复杂度是 O(1) 级别的
     * 
     * 但是，如果我们正好在扩容和缩容的边界反复交替调用 addLast 和 removeLast 的话，复杂度就一直是 O(n) 级别的，这叫做复杂度震荡。
     * 为了防止复杂度震荡，我们可以在缩容的时候采取 lazy 的策略，即元素个数到 1/2 容量时先不要锁容，而等到更小，比如 1/4 的时候再进行。
     * 
     * @param newCapacity 需要变更的容量。
     */
    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) {

        if (newCapacity < size) {
            throw new IllegalArgumentException("New capacity is Illegal.");
        }

        E[] newData = (E[]) new Object[newCapacity];

        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        res.append('[');
        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if (i != size - 1) {
                res.append(", ");
            }
        }
        res.append(']');
        return res.toString();
    }
}

总结：

对于增删操作，最好的情况是 O(1) 即增删在尾部，最差的情况是 O(n) 即增删在首位，平均还是 O(n)；
对于数组越界的处理，我们都选择抛出异常使程序中断，而不是采取返回空等温和的做法；
改变数组的 resize 操作的复杂度分析需要使用均摊复杂度分析，最终该操作的复杂度是 O(1) 级别；
rezize 操作为避免复杂度震荡，缩容操作采用了延迟的策略；

数据结构学习笔记 - 01 介绍

发表于 2020-10-24 更新于 2023-10-16

数据结构的分类

线性结构：数组、栈、队列、链表、哈希表……
树结构：二叉树、二分搜索树、AVL、红黑树、Treap、Splay、堆、Trie、线段树、K-D 树、并查集、霍夫曼树……
图结构：邻接矩阵、邻接表。

数据结构的应用

数据库中大量使用各种树结构（如 AVL、红黑树、Treap、伸展树、B 树等）以及哈希表等；
操作系统中会有系统栈、优先队列（堆）；
霍夫曼树用于文件压缩算法；
微软实习生，通讯录联系人很多时，查找联系人变慢，使用 Trie 查找就会非常好；
图论算法：
- DFS（深度优先遍历）使用栈
- BFS（广度优先遍历）使用队列

简单的关于时间复杂度分析

O(1), O(n), O(lgn), O(nlogn), O(n^2)
简单的说，大O描述的是算法的运行时间和输入数据之间的关系；

本次学习涉及的数据结构

数组
栈
队列
链表
二分搜索树
堆
线段树
Trie
并查集
AVL
红黑树
哈希表

Homebrew 使用简介

发表于 2020-10-10 更新于 2023-10-16

环境变量

系统在加载 ~/.zshrc（macOS Catalina 之前是 ~/.bash_profile）之前还会加载：

/etc/profile
/etc/paths（系统默认指定的一系列 PATH）

使用命令 vi /etc/paths 查看，内容如下：

/usr/local/bin
/usr/bin
/bin
/usr/sbin
/sbin

输入 echo $PATH 可以查看当前的 PATH，会显示 /usr/local/bin:/usr/bin:/bin:/usr/sbin:/sbin:/Library/Apple/usr/bin（最后一个暂不知从哪里加载），可以看到，系统默认就是按照这样的顺序依次从这几个目录中读取的，也就是说，/usr/local/bin 目前是系统最优先读取的路径。

如果在 ~/.zshrc 设置就会优先从该文件的 PATH 加载，因为 ~/.zshrc 是后被系统加载的。

Homebrew 原理

macOS 自带的软件默认是放在 /usr/bin 路径下的，如在该目录可以找到系统自带的 git、gem 等。而 /usr/bin 路径在系统的读取顺序上是低于 /usr/local/bin 路径的。

Homebrew 就是利用了系统更优先读取 /usr/local/bin 的特点，先把包安装到同路径的 Cellar 文件夹下，然后使用软链接的方式，在 bin 文件夹下创建软链接，这样系统就可以优先找到 brew 安装的包了。

Homebrew 安装

安装 Homebrew：

1	$ /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install.sh)"

它是使用系统自带的 ruby 进行安装的。

使用 brew 去可以安装 python、git、java 等等。虽然系统都默认提供了这些，但是版本往往不是最新的，我们也不建议使用 sudo 去更新修改系统的内容。于是完全可以使用 brew 去重新安装维护一套，更新也更方便更安全。这样基本就可以不再使用系统默认提供的一些包了。

安装某些软件时候，处于避免冲突的考虑，brew 不会自动在 /usr/local/bin/ 下创建软链接（如 ruby）。解决方法有两种：一是在 ~/.bash_profile 下为新安装的添加环境变量；二是手动在 /usr/local/bin/ 下创建软链接（推荐），如输入命令 ln -s /usr/local/Cellar/ruby/2.6.3/bin/ruby /usr/local/bin/ruby，就可以把已经使用 brew 安装好的 ruby 在/usr/local/bin/ 下创建软链接。

Homebrew 使用

常用命令：

$ brew list // 安装的软件列表

$ brew install <name> // 安装某个包

$ brew uninstall <name> // 卸载安装的软件

$ brew update // 更新 Homebrew 本身

$ brew outdated 查看过期软件

$ brew upgrade <formula> // 更新指定软件

$ brew pin <formula> 指定某软件保持在当前版本不被更新

$ brew unpin <formula> 取消某软件保持在当前版本

$ brew --cache 查看 Homebrew 缓存目录

// cask 相关

$ brew cask install <name> // 使用 cask 安装软件

$ brew list --cask // 使用 cask 命令安装的应用列表

$ brew cask uninstall <name> // 卸载使用 cask 命令安装的应用

$ brew cask search <name> // 查找

避免 Homebrew 自动更新：在 ~/.zshrc 文件中写入 export HOMEBREW_NO_AUTO_UPDATE=true。

安装 homebrew-cask-upgrade 方便 cask 应用更新：

$ brew tap buo/cask-upgrade // 安装

$ brew cu -a // 更新所有

$ brew cu <name> -a 更新指定

如何部署 Hexo 博客

发表于 2020-10-10 更新于 2023-10-16

假期时候花了点时间将博客迁移到了 Hexo，下面记录一些部署流程。

安装

安装 node：

1	$ brew install node

安装 Hexo：

1	$ npm install hexo-cli -g

新建博客项目：

1
2
3

$ hexo init <folder>
$ cd <folder>
$ npm install

之后这个文件夹可以通过 Git 进行管理并托管 GitHub。

配置

配置文件

配置 _config.yml 文件：

url: https://qiweipeng.github.io

deploy:
  type: git
  repository: git@github.com:qiweipeng/qiweipeng.github.io.git
  branch: master

要保证 GitHub 已经配置了 SSH，之后命令行进行部署就很方便。

安装主题

安装 next 主题：

1 2	$ cd <folder> $ git clone https://github.com/theme-next/hexo-theme-next themes/next

之后修改 _config.yml 文件更换主题

1	theme: next

CNAME

markdown 文件放在 source/_posts 文件夹下，如果绑定域名，CNAME 文件放在 source 文件夹下。

发布流程

$ hexo new "My New Post" // 创建新的 markdown 文件

$ hexo server // 本地部署

$ hexo g // 生成

$ hexo d // 部署

图床

因为域名备案的原因，不想再用七牛云的图床了，打算直接在 GitHub 上建一个仓库作为图床。

创建 qiweipeng/images 仓库。设置中打开 GitHub Pages，Custom domain 设置为 image.qiweipeng.com，打开 HTTPS。同时 GoDaddy 设置 CNAME，值 image 指向 qiweipeng.github.io。

之后安装 PicGo 进行图片的上传。打开[上传前重命名]和[时间戳重命名]。设置 GitHub 图床：

图 - 4: PicGo 中 GitHub 图床设置

其中需要配置 Personal access tokens，命名如 Weipeng's MacBook Pro - PicGo，打开的权限：

repo

Mac 电脑的个人配置

发表于 2020-10-09 更新于 2023-10-16

本文记录自己新装电脑后的软件安装和个性化配置，以及之后的维护。

软件安装

App Store

1Password
Spark
Fantastical
Todoist
Notability
MindNode
Drafts
Reeder
Xcode
Sequel Ace
Wechat
QQ
Pages
Keynote
Numbers
WPS Office
Apple Developer
Swift Playgrounds
CloudMounter
The Unarchiver
Magnet
Bear
Amphetamine
Petrify
Cleaner for Xcode
quicktype

Homebrew

安装 Homebrew：

1	/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"

使用 Homebrew 安装软件：

1	$ brew install <name>

mysql
git
sqlite
nvm（如果安装多版本 node）
node（如果只安装单版本 node）

使用 brew cask 安装应用：

1	$ brew install --cask <name>

android-studio
google-chrome
~~oracle-jdk~~
openjdk
openjdk@8
appcleaner
iina
pdf-expert
baidunetdisk
imazing
picgo
db-browser-for-sqlite
iterm2
postman
downie
moneywiz
fliqlo
mweb
visual-studio-code
github
notion
dash
sketch
figma
feishu

手动安装

SF Symbols
ClashX
~~trojan-qt5~~

配置和维护

需要激活的 App

MoneyWiz
MWeb
Sketch
PDF Expert
Downie

系统配置

System Preferences

General -> SideBar icon size: Small
General -> Recent items: 5
Desktop & Screen Saver -> Screen Saver: Fliqlo
Desktop & Screen Saver -> Start after: 5 Minutes
Dock -> Position on screen: Left
Dock -> Show recent application in Dock: NO
Notifications: 对所有 App 进行配置
Accessibility -> Pointer Control -> Trackpad Options -> Enable dragging: three finger drag
Security & Privacy -> General -> Requeire passowrd: 5seconds
Security & Privacy -> FileVault: Turn On
Security & Privacy -> Firewall: Turn On
Keyboard -> Text -> Correct spelling automatically: NO
Keyboard -> Input Sources: 增加小鹤双拼
Trackpad: 打开所有手势
Displays -> NightShift: Turn On

Finder

General -> New Finder windows show: qiweipeng
Tags: 添加到 Favorite Tags
SideBar -> Favorites: 仅保留 Applications、Downloads、qiweipeng

Safari

首页 -> Show Frequently Visited: Turn Off
General -> Open "safe" files after downloading: No
Search -> Search engine: Google
Advanced -> Show Develop menu in menu bar: Yes
Extensions: 各个插件具体配置

其它

FaceTime -> Ringtone: Hillside
Message -> Message received sound: Bamboo
所有的系统 App 打开 iCloud 账户同步功能

Homebrew

常用命令：

$ brew list // 安装的软件列表

$ brew install <name> // 安装某个包

$ brew uninstall <name> // 卸载安装的软件

$ brew update // 更新 Homebrew 本身

$ brew outdated 查看过期软件

$ brew upgrade <formula> // 更新指定软件

$ brew pin <formula> 指定某软件保持在当前版本不被更新

$ brew unpin <formula> 取消某软件保持在当前版本

$ brew --cache 查看 Homebrew 缓存目录

// cask 相关

$ brew install --cask <name> // 使用 cask 安装软件

$ brew list --cask // 使用 cask 命令安装的应用列表

$ brew cask uninstall <name> // 卸载使用 cask 命令安装的应用

$ brew cask search <name> // 查找

避免 Homebrew 自动更新：在 ~/.zshrc 文件中写入 export HOMEBREW_NO_AUTO_UPDATE=true。

安装 homebrew-cask-upgrade 方便 cask 应用更新：

$ brew tap buo/cask-upgrade // 安装

$ brew cu -a // 更新所有

$ brew cu <name> -a 更新指定

node

常用命令：

1
2
3

$ npm list // 查看当前目录安装的包

$ npm list -g --depth 0 // 查看本地全局安装过的包

如果需要多版本的 node 则可以通过 brew install nvm 安装 nvm，之后通过 nvm 安装和管理各版本的 node。

nvm

安装流程：

1	brew install nvm

在 .zshrc 中写入：

1 2	export NVM_DIR="$HOME/.nvm" [ -s "/usr/local/opt/nvm/nvm.sh" ] && . "/usr/local/opt/nvm/nvm.sh" # This loads nvm

安装指定版本：

1 2	// 安装 12.16.3 nvm install v12.16.3

查看：

nvm list

如果安装了多个版本，使用如 nvm use v12.16.3 切换到指定版本（重启终端将恢复默认版本），使用如 nvm alias default v12.16.3 设置默认版本。

CocoaPods

安装 CocoaPods：

1	$ sudo gem install cocoapods

CocoaPods 版本更新：首先使用 $ sudo gem install cocoapods 安装最新版本，之后看哪些被更新了($ gem list)，再将旧版本卸载掉，比如 $ sudo gem uninstall cocoapods-core -v 1.9.1。

常用命令：

pod repo // 查看本地关联了哪些仓库源

pod repo update // 本地仓库更新

pod repo update <name> // 更新指定的仓库

Git

参考个人文章《macOS 下 Git 多账号配置，同时管理多个 SSH Key》配置 SSH Key，主要用在 GitHub。

参考个人文章《如何设置 Git 全局忽略 .DS_Store 文件》配置全局忽略文件。

参考个人文章《记录一些 Git 的命令》对 Git 进行配置，如：

// 设置全局的用户名和邮箱
$ git config --global user.name "<name>"
$ git config --global user.email "<email address>"

// 让 Git 输出语句显示颜色
$ git config --global color.ui true

// 给常用 Git 命令设置别名，以快捷输入，这个依然是保存在家目录的 .gitconfig 文件中
$ git config --global alias.st status
$ git config --global alias.co checkout
$ git config --global alias.ci commit
$ git config --global alias.br branch
$ git config --global alias.unstage 'reset HEAD'
$ git config --global alias.last 'log -1'
$ git config --global alias.lg "log --color --graph --pretty=format:'%Cred%h%Creset -%C(yellow)%d%Creset %s %Cgreen(%cr) %C(bold blue)<%an>%Creset' --abbrev-commit"

Java

使用 brew 安装 openjdk 后，需要关注（使用 brew info openjdk 查看）：

For the system Java wrappers to find this JDK, symlink it with
  sudo ln -sfn /usr/local/opt/openjdk/libexec/openjdk.jdk /Library/Java/JavaVirtualMachines/openjdk.jdk

openjdk is keg-only, which means it was not symlinked into /usr/local,
because macOS provides similar software and installing this software in
parallel can cause all kinds of trouble.

If you need to have openjdk first in your PATH, run:
  echo 'export PATH="/usr/local/opt/openjdk/bin:$PATH"' >> ~/.zshrc

For compilers to find openjdk you may need to set:
  export CPPFLAGS="-I/usr/local/opt/openjdk/include"

同样，安装 openjdk@8 后，需要关注（使用 brew info openjdk@8 查看）：

For the system Java wrappers to find this JDK, symlink it with
  sudo ln -sfn /usr/local/opt/openjdk@8/libexec/openjdk.jdk /Library/Java/JavaVirtualMachines/openjdk-8.jdk

openjdk@8 is keg-only, which means it was not symlinked into /usr/local,
because this is an alternate version of another formula.

If you need to have openjdk@8 first in your PATH, run:
  echo 'export PATH="/usr/local/opt/openjdk@8/bin:$PATH"' >> ~/.zshrc

For compilers to find openjdk@8 you may need to set:
  export CPPFLAGS="-I/usr/local/opt/openjdk@8/include"

（这是直接安装 Oracle JDK 时的配置，OpenJDK 也可以做类似配置，或直接在需要时更改 .zshrc 文件中两个版本的声明顺序）如果安装了多个版本的 Java，可在 .zshrc 中写入：

# JDK 8
export JAVA_8_HOME="/Library/Java/JavaVirtualMachines/jdk1.8.0_271.jdk/Contents/Home"
# JDK 15
export JAVA_15_HOME="/Library/Java/JavaVirtualMachines/jdk-15.0.1.jdk/Contents/Home"
# 默认JDK 8
export JAVA_HOME=$JAVA_8_HOME

# alias命令动态切换JDK版本
alias jdk8="export JAVA_HOME=$JAVA_8_HOME"
alias jdk15="export JAVA_HOME=$JAVA_15_HOME"

之后可以使用 jdk8 和 jdk15 切换 java 版本。

Xcode

配置 GitHub

repo
admin:org
admin:public_key
user

代码块

将备份的代码块，即 CodeSnippets 文件夹拖入 ~/Library/Developer/Xcode/UserData 目录内。

偏好设置

Preferences 选中 Behaviors，根据 图 - 1 和 图 - 2 进行设置。

图 - 1: Xcode 偏好设置1

图 - 2: Xcode 偏好设置2

命令行快捷键

创建文件 open_terminal.sh，写入代码：

#!/bin/sh
if [ -n "$XcodeProjectPath" ]; then
    open -a iTerm "$XcodeProjectPath"/..
else
    open -a iTerm "$XcodeWorkspacePath"/..
fi

之后将脚本保存 ~/Local/Scripts/ 目录下，然后在该目录下执行 chmod +x open_terminal.sh 将脚步设为可执行。

打开 Xcode 的 Preferences，选中 Behaviors，新建并命名为 Open Terminal，快捷键设置为 Control + Command + /，路径选择脚本所在路径。

图 - 3: 打开命令行脚本设置

Visual Studio Code

Shift + Command + P 之后找到 Shell Command: Install "code" command in PATH，运行。

登录同步账号：qiweipeng@hotmail.com，登录 Github。

PicGo

打开[上传前重命名]和[时间戳重命名]。

GitHub 图床设置：

图 - 4: PicGo 中 GitHub 图床设置

其中需要配置 Personal access tokens，命名如 Weipeng's MacBook Pro - PicGo，打开的权限：

repo

Trojan

User Rules 配置：

||notion.so
||*.notion.so
||github.com
||*.github.com
||githubusercontent.com
||*.githubusercontent.com
||dribbble.com
||*.dribbble.com