左程云算法课笔记

认识复杂度和简单排序算法

• 异或运算

  无进位的二进制加法

  $N \bigoplus 0 = N, N \bigoplus N = 0$

排序算法实现

简单选择排序算法

---

认识O(NlogN)的排序

归并排序

• 小和问题

  问题描述：

  在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

  题解：

/**
 * @brief 小和问题
 * 
 * 将小和问题转化为找某数字 num 右侧有多少更大的数字，num 对应的小和就是 num * cnt。
 * 在归并排序的基础上，合并数组时查找右侧比左侧大的数字个数，当前left对应数字的小和为 (right - j + 1) * nums[j]
 */
class Solution {
public:
    int smallSum(vector<int>& nums) {
        int len = nums.size();
        if(len == 0 || len == 1) {
            return 0;
        }

        return process(nums, 0, len - 1);
    }

    // 计算左侧数组、右侧数组和合并时产生的小和
    int process(vector<int>& nums, int left, int right) {
        if(left == right) {
            return 0;
        }

        int mid = left + ((right - left) >> 1);     // 要有括号，否则因为运算符优先级问题会出错
        return process(nums, left, mid) + process(nums, mid + 1, right) + merge(nums, left, mid, right);
    }

    // 合并数组，并计算小和
    int merge(vector<int>& nums, int left, int mid, int right) {
        vector<int> tmp;
        int i = left, j = mid + 1;
        int small_sum = 0;

        while(i <= mid && j <= right) {            
                small_sum += nums[i] < nums[j] ? (right - j + 1) * nums[i] : 0;
                tmp.emplace_back(nums[i] < nums[j] ? nums[i++] : nums[j++]);
        }

        while(i <= mid) {
            tmp.emplace_back(nums[i++]);
        }

        while(j <= right) {
            tmp.emplace_back(nums[j++]);
        }

        for(int i = 0; i < tmp.size(); i++) {
            nums[left++] = tmp[i];
        }

        return small_sum;
    }
};

• 逆序对问题

  问题描述：

  在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对。

  题解：

class Solution {
public:
    int inversionPair(vector<int>& nums) {
        if(nums.size() < 2) {
            return 0;
        }

        return process(nums, 0, nums.size() - 1);
    }

    int process(vector<int>& nums, int left, int right) {
        if(left == right) {
            return 0;
        }

        int mid = left + ((right - left) >> 1);
        return process(nums, left, mid) + process(nums, mid + 1, right) + merge(nums, left, mid, right);
    }

    int merge(vector<int>& nums, int left, int mid, int right) {
        vector<int> tmp;
        int l = left, r = mid + 1;
        int cnt = 0;

        while(l <= mid && r <= right) {
            cnt += nums[l] <= nums[r] ? 0 : mid - l + 1;
            tmp.emplace_back(nums[l] <= nums[r] ? nums[l++] : nums[r++]);
        }

        while(l <= mid) {
            tmp.emplace_back(nums[l++]);
        }

        while(r <= right) {
            tmp.emplace_back(nums[r++]);
        }

        for(int i = 0; i < tmp.size(); i++) {
            nums[left++] = tmp[i];
        }

        return cnt;
    }
};

快速排序

• 荷兰国旗问题

  • 第一种：K值有且仅有一个

    问题描述

    给定一个整数数组，给定一个值K（K只有一个），这个值在原数组中一定存在，要求把数组中小于等于K的元素放到数组的左边，大于K的元素放到数组的右边，最终返回一个整数数组。

    题解

    数组分为两个区域：小于等于区、大于区

    分两种情况：

    • nums[i] ≤ target：交换nums[i]与小于等于区域的下一个数值，小于等于区域右扩，i++
    • nums[i] > target：i++

void sortNums(vector<int>& nums， int target) {
    int len = nums.size();
    int left = -1, right = len;
    int i = 0;
    
    while(i < right) {
        if(nums[i] <= target) {
            swap(nums[++left], nums[i++]);
        } else {
            i++;
        }
    }
}

- 第二种：K有多个

  参考leetcode75题：75. 颜色分类

  **问题描述**

  给定一个整数数组，给定一个值K，这个值在原数组中一定存在且有多个，要求把数组中小于K的元素放到数组的左边，大于K的元素放到数组的右边，等于K的元素放到数组的中间，最终返回一个整数数组，其中只有两个值，分别是等于K的数组部分的左右两个下标值。

  

  **题解**

  数组分为三个区域：`小于区`、`等于区`、`大于区`

  分三种情况：

  - `nums[i] < target`：交换`nums[i]`与`小于区的下一个数值`，小于区右扩，i++
  - `nums[i] > target`：交换`nums[i]`与`大于区的前一个数值`，大于区左括，i不变
  - `nums[i] == target`：i++

void sortNums(vector<int>& nums， int target) {
    int len = nums.size();
    int left = -1, right = len;
    int i = 0;
    
    while(i < right) {
        if(nums[i] < target) {
            swap(nums[++left], nums[i++]);
        } else if(nums[i] > target) {
            swap(nums[--right], nums[i]);
        } else {
            i++;
        }
    }
}

• 快排实现

  912. 排序数组
  • 方式一：将最后一个数字作为pivot，每次先从右向左找小于pivot的值，再从左向右找大于pivot的值，直至左右指针相遇

void quickSort(vector<int>& array, int left, int right) {
    if(array.size() == 0) {
        return;
    }
 
    if(left < right) {
        int pivot = array[left];
        int low = left, high = right;
        while(low < high) {
            while(array[high] >= pivot && low < high) {
                high--;
            }
            array[low] = array[high];
            
            while(array[low] <= pivot && low < high) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = pivot;
        
        quickSort(array, left, low - 1);
        quickSort(array, low + 1, right);
    }
}

- 方式二：利用荷兰国旗问题的第二种方式，partition时将数据分为小于、等于、大于三部分

class Solution {
private:
    vector<int> partition(vector<int>& nums, int L, int R) {
        // 将nums[R]作为基准值，即对nums[L...R-1]做partition
        int less = L - 1, more = R;
        while(L < more) {
            if(nums[L] < nums[R]) {
                swap(nums[L++], nums[++less]);
            } else if(nums[L] > nums[R]){
                swap(nums[L], nums[--more]);
            } else {
                L++;
            }
        }
        swap(nums[more], nums[R]);
        return vector<int>{less + 1, more};
    }

    // 随机选择一个数值作为基准值，并交换到最后一个位置
    vector<int> randomized_partition(vector<int>& nums, int L, int R) {
        int p = rand() % (R - L + 1) + L;
        swap(nums[p], nums[R]);
        return partition(nums, L, R);
    }

    void randomized_quicksort(vector<int>& nums, int L, int R) {
        if(L < R) {
            vector<int> equal_scope = randomized_partition(nums, L, R);
            randomized_quicksort(nums, L, equal_scope[0] - 1);
            randomized_quicksort(nums, equal_scope[1] + 1, R);
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        srand((int)time(NULL));
        randomized_quicksort(nums, 0, nums.size() - 1);
        return nums;
    }
};

堆排

912. 排序数组

• 基础代码

  堆排代码：堆排

• 堆排扩展

  题目：已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。

  题解：以k+1大小的窗口进行滑动，窗口内构造堆结构，每次将最值放到当前窗口的第一个位置，并先后滑动窗口。

class Solution {
public:
    void sort_distance_less_k(vector<int>& nums, int k) {
        // 默认大根堆，需设置比较器使其为小根堆
        priority_queue<int, vector<int>, greater<int>> heap;
        int i = 0;
        for(; i < min((int)nums.size(), k); i++) {
            heap.push(nums[i]);
        }

        int start = 0;
        for(; i < nums.size(); i++) {
            heap.push(nums[i]);
            nums[start++] = heap.top();
            heap.pop();
        }

        while(!heap.empty()) {
            nums[start++] = heap.top();
            heap.pop();
        }
    }
};

基数排序

排序稳定性

不具备稳定性：选择排序，快速排序，堆排序

具备稳定性：冒泡排序，插入排序，归并排序

排序	时间复杂度	空间复杂度	稳定性
选择	O(N2)	O(1)	不稳定
冒泡	O(N2)	O(1)	稳定
插入	O(N2)	O(1)	稳定
归并	O(N*logN)	O(N)	稳定
快排	O(N*logN)	O(logN)	不稳定
堆排	O(N*logN)	O(1)	不稳定

链表

链表中环的入口节点

双链表的第一个公共节点

160. 相交链表

公共节点说明此后的节点为两个链表的公共部分，因为每个节点的next唯一且相同。并且由于next唯一，所以**有环则环必在链表尾部**。



1. 判断是否有环，loop1表示链1的环入口节点，loop2表示链2的环入口节点。若没有环则为空。
2. 根据环的有无进行分类：
    - 都没有环

        较长的链表指针走两个链表的长度差值步，两个链表指针同时后移，直至相同节点或节点为空。前者即第一个公共节点，后者即没有公共节点。
    - 一个有环，一个无环

        必然没有公共节点。
    - 两个都有环
        - `loop1 == loop2`，同一个环的入口节点：将`loop1`视作链表的终止，即转化为两个链表都没有环的操作
        - `loop1 ≠ loop2`
            - 某个入口节点在环上

                遍历环，若找到另一个入口节点则为该情况，结果为`loop1`或`loop2`均可，否则表示不相交，没有公共节点
            - 不相交

                遍历环，没有另一个入口节点，则没有公共节点

二叉树

二叉树的遍历算法

二叉树的树的应用

判断是否是BST

用long避免测试样例为-2147483648时出错

// 递归
class Solution {
public:
    long preValue = LONG_MIN;

    bool isValidBST(TreeNode* root) {
        if(root == nullptr) return true;
        if(!isValidBST(root->left)) return false;
        if(root->val <= preValue)   return false;
        preValue = root->val;
        return isValidBST(root->right);
    }
};

// 边界值（指针）
class Solution {
public:
    bool isValidBST(TreeNode* root, TreeNode* min, TreeNode* max) {
        if(!root)   return true;
        if(min && root->val <= min->val)    return false;
        if(max && root->val >= max->val)    return false;
        return isValidBST(root->left, min, root) && isValidBST(root->right, root, max);
    }

    bool isValidBST(TreeNode* root) {
        return isValidBST(root, nullptr, nullptr);
    }
};

// 边界值（long类型）
class Solution {
public:
    bool isValidBST(TreeNode* root, long min, long max) {
        if(!root)   return true;
        if(root->val <= min || root->val >= max)    return false;
        return isValidBST(root->left, min, root->val) && isValidBST(root->right, root->val, max);
    }

    bool isValidBST(TreeNode* root) {
        return isValidBST(root, LONG_MIN, LONG_MAX);
    }
};

// 中序遍历
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> S;
        long long preValue = LONG_MIN;

        while(!S.empty() || root) {
            while(root) {
                S.push(root);
                root = root->left;
            }

            root = S.top();
            S.pop();
            if(root->val <= preValue) {
                return false;
            }
            preValue = root->val;
            root = root->right;
        }

        return true;
    }
};

判断是否是完全二叉树

层次遍历，标记左孩子是否出现空的情况

public class isCBT {
    public  static boolean isCBT(Node head){
        if(head==null){
            return true;
        }
        //利用队列来遍历二叉树
        LinkedList<Node> queue = new LinkedList<Node>();
        boolean flag =false;
        Node l = null;
        Node r = null;
        queue.add(head);
        while(!queue.isEmpty()){
            head = queue.poll();
            l=head.left;
            r=head.right;
            if(flag&&((l!=null||r!=null)||(l==null&&r!=null)){
                return false;
            }
            if(l!=null){
                queue.add(l);
            }
            if(r!=null){
                queue.add(r);
                if(l == null||r==null){
                    flag = true;
                }
            }
        }
    }
}

判断是否是满二叉树

![](https://secure2.wostatic.cn/static/s15HuSJudU7E5ejTZmBFQD/image.png)

判断是否是平衡二叉树

两个节点的最低公共祖先节点

236. 二叉树的最近公共祖先



限制：o1和o2一定属于树

方法一：map+set

首先遍历二叉树记录所有节点的父节点（记根节点的父节点为自身），再依次记录o1、o2的所有到根节点路径上的节点，比较两个集合，找到共同路径的最后一个节点。



方法二：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q) {
            return root;
        }

        TreeNode * left = lowestCommonAncestor(root->left, p, q);
        TreeNode * right = lowestCommonAncestor(root->right, p, q);
        
        if (left != nullptr && right != nullptr) {
            return root;
        }

        return left != nullptr ? left : right;
    }
};

找到二叉树一个节点的后继节点

分为两种情况：

- node有右子树：后继节点为右子树的最左节点
- node无右子树：后继节点为next，且当前子树为next的左子树，即要找到`x==x→parent→left`。（若当前节点为最后一个节点，则没有后继节点，也就是说该树不为任何节点的左子树，此时parent为空，即返回空）

class Solution {
public:
    TreeNode* getLeftMost(TreeNode* root) {
        if(root == nullptr) {
            return nullptr;
        }

        while(root->left) {
            root = root->left;
        }

        return root;
    }

    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (root == nullptr || p == nullptr) {
            return nullptr;
        }

        if (p->right != nullptr) {
            return getLeftMost(p->right);
        } else {
            TreeNode* parent = p->parent;
            while (parent != nullptr && parent->left != p) {
                p = parent;
                parent = p->parent;
            }

            return parent;
        }
    }
};

297. 二叉树的序列化与反序列化

递归实现

![](https://secure2.wostatic.cn/static/9s8f2BVaLjYmDZXV1gHpHm/image.png)

折纸问题

每次折纸，增加的折痕符合树形结构，且每个节点的左孩子为凹，右孩子为凸。结果为树的中序遍历顺序。

graph TB
  node1((down))
  node2-1((down))
  node2-2((up))
  node3-1((down))
  node3-2((up))
  node3-3((down))
  node3-4((up))
  
  node1 --- node2-1
  node1 --- node2-2
  node2-1 --- node3-1
  node2-1 --- node3-2
  node2-2 --- node3-3
  node2-2 --- node3-4
  

class FoldPaper {
public:
    void inOrder(vector<string>& res, int n, string direction) {
        if(n == 0) {
            return;
        }
        
        inOrder(res, n - 1, "down");
        res.emplace_back(direction);
        inOrder(res, n - 1, "up");
        
        return;
    }
    
    vector<string> foldPaper(int n) {
        vector<string> res;
        inOrder(res, n, "down");
        return res;
    }
};

图

0：39：27

图结构

class Edge;

class Node {
public:
    int value;
    int in;     // 入度
    int out;    // 出度
    vector<Node> nexts;
    vector<Edge> edges;

    Node() {}
    Node(int value) {
        this->value = value;
        in = 0;
        out = 0;
    }
};

class Edge {
public:
    int weight;
    Node from;
    Node to;

    Edge() {}
    Edge(int weight, Node from, Node to) {
        this->weight = weight;
        this->from = from;
        this->to = to;
    }
};


class Graph {
public:
    unordered_map<int, Node> nodes;
    set<Edge> edges;

    Graph() {}
};

图建立代码

Graph createGraph(vector<vector<int>> matrix) {
    Graph graph = Graph();
    for(int i = 0; i < matrix.size(); i++) {
        int from = matrix[i][0];
        int to = matrix[i][1];
        int weight = matrix[i][2];

        if(!graph.nodes.count(from)) {
            graph.nodes[from] = Node(from);
        }
        if(!graph.nodes.count(to)) {
            graph.nodes[to] = Node(to);
        }

        Node fromNode = graph.nodes[from];
        Node toNode = graph.nodes[to];
        Edge newEdge = Edge(weight, fromNode, toNode);
        fromNode.nexts.emplace_back(toNode);
        fromNode.out++;
        fromNode.edges.emplace_back(newEdge);
        toNode.in++;
    }

    return graph;
}

图的BFS

vector<Node> BFS(Node node) {
    vector<Node> res;
    queue<Node> Q;
    set<Node> S;
    Q.push(node);
    S.insert(node);

    while(!Q.empty()) {
        Node cur = Q.front();
        Q.pop();
        cout << cur.value << endl;
        res.emplace_back(cur);
        for(auto next : cur.nexts) {
            if(!S.count(next)) {
                Q.push(next);
                cout << next.value << " " << Q.size() << endl;
                S.insert(next);
            }
        }
    }

    return res;
}

图的DFS

vector<Node> DFS(Node node) {
    vector<Node> res;
    stack<Node> S;
    set<Node> visited;
    S.push(node);
    visited.insert(node);
    res.emplace_back(node);

    while(!S.empty()) {
        Node cur = S.top();
        S.pop();

        for(auto next : cur.nexts) {
            if(!visited.count(next)) {
                S.push(cur);
                S.push(next);
                visited.insert(next);
                res.emplace_back(next);
                break;
            }
        }
    }
}

拓扑排序

vector<Node> sortedTopology(Graph graph) {
    map<Node, int> inMap;       // 存储 Node 与 入度 的映射
    queue<Node> zeroInQueue;    // 入度为 0 的节点

    // 遍历所有节点，记录节点与入度的对应关系
    for(auto node : graph.nodes) {
        Node cur = node.second;
        inMap[cur] = cur.in;
        if(cur.in == 0) {
            zeroInQueue.push(cur);
        }
    }

    // 先选择入度为0的节点进行删除，再将该节点对应的nexts节点的入度减1，
    // 若出现入度为0的节点，则加到队列中
    vector<Node> res;
    while(!zeroInQueue.empty()) {
        Node node = zeroInQueue.front();
        zeroInQueue.pop();
        res.emplace_back(node);

        for(auto next : node.nexts) {
            inMap[next]--;
            if(inMap[next] == 0) {
                zeroInQueue.push(next);
            }
        }
    }

    return res;
}

最小生成树

Kruskal算法和Prim算法

#### Kruskal算法（加边法）

  将边从小到大排序，依次选择最小的边，若添加边后不形成环则添加，否则不添加

#### Prim算法（加点法）

  ![](https://secure2.wostatic.cn/static/da7uCyvyB7wcDsLFW9dsC6/image.png)

最短路径-Dijkstra算法

适用于权值为非负数的无向图

每次从未选择节点中选择距离最近的节点，更新当前选中的节点到相邻节点的最短距离，并将该节点标记为已选择，重复上述操作。

Node* getMinDistanceAndUnselectedNode(map<Node, int> distanceMap, set<Node> selectedNodes) {
    int minDistance = INT_MAX;
    Node minNode;
    for(auto node : distanceMap) {
        int distance = node.second;
        Node cur = node.first;
        if(distance < minDistance && !selectedNodes.count(cur)) {
            minDistance = distance;
            minNode = cur;
        }
    }
    return &minNode;
}

map<Node, int> dijkstra(Node head) {
    // 从head出发到每个节点的最小距离，若没在表中，表示head到该点的距离为正无穷
    map<Node, int> distanceMap;
    distanceMap[head] = 0;

    set<Node> selectedNodes;
    Node* minNodePointer = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);

    while(minNodePointer) {
        int distance = distanceMap[*minNodePointer];
        for(Edge edge : (*minNodePointer).edges) {
            Node toNode = edge.to;
            if(!selectedNodes.count(toNode)) {
                distanceMap[toNode] = distance + edge.weight;
            }
            distanceMap[toNode] = min(distanceMap[toNode], distance + edge.weight);
        }
        selectedNodes.insert(*minNodePointer);
        minNodePointer = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
    }

    return distanceMap;
}

前缀树

边表示对应字符串的字母，点为空，也可以增加信息，例如pass表示经过该点的字符串数，end表示以该点为结尾的字符串数。

![](https://secure2.wostatic.cn/static/2YAPFnpAFJmWhG1UQGqnNY/image.png)

动态规划

题1

题3