这周力扣做了很多题，准备把hot100写完就放一下，转投洛谷。

数据结构实验课

week9-1 哈夫曼树

给定n个叶节点的权值，请建立哈夫曼树，并求出每个叶节点的路径长与权值乘积之和。

路径长指叶节点到根节点的长度。

输入

第一行包括一个正整数，叶节点个数n (1 <= n <= 100)。

第二行包括 n 个用空格隔开的正整数w_i (1 <= w_i <= 100)，代表n个叶节点的权值。

输出

输出一个数字，叶节点的路径长与权值乘积之和。

思路与答案

• 霍夫曼树

我们要算的其实就是带权路径长度（Weighted Path Length of Tree，WPL），可以在构造时就算出。维护一个最小堆，取出两个最小值，合并（相加）后即为当前 WPL，接着将合并的值插入最小堆直到最小堆的大小为 1。在合并过程中，早入树的值会被重复相加自身的深度次，所以最后最小堆剩下的元素就是 WPL。

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> pq;

    for (int i = 0; i < n; ++i) {
        int w;
        cin >> w;
        pq.push(w);
    }

    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }

    int result = 0;
    while (pq.size() > 1) {
        int a = pq.top();
        pq.pop();
        int b = pq.top();
        pq.pop();
        int sum = a + b;
        result += sum;
        pq.push(sum);
    }

    cout << result << endl;
    return 0;
}

week9-2 二叉树的遍历

有一个 n(n≤1000000) 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 n），建立一棵二叉树（根节点的编号为 1），如果是叶子结点，则输入 0 0。

建好树这棵二叉树之后，依次求出它的前序、中序、后序列遍历。

输入

第一行一个整数 n，表示结点数。

之后 n 行，第 i 行两个整数 l、r，分别表示结点 i 的左右子结点编号。若 l=0 则表示无左子结点，r=0 同理。

输出

输出三行，每行 n 个数字，用空格隔开。

第一行是这个二叉树的前序遍历。

第二行是这个二叉树的中序遍历。

第三行是这个二叉树的后序遍历。

思路与解答

没什么好说的，以前没做过这种竞赛风的二叉树，所以一开始就直接创造节点开始构造，不出意料地在 1000000 测试点爆内存了。先给出正解。

我们只需要两个数组来存左节点和右节点。

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

const int MAXN = 1000024;
int left[MAXN];
int right[MAXN];

void preorder(int root) {
    if (!root) return;
    cout << root << " ";
    preorder(left[root]);
    preorder(right[root]);
}

void inorder(int root) {
    if (!root) return;
    inorder(left[root]);
    cout << root << " ";
    inorder(right[root]);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        left[i + 1] = l;
        right[i + 1] = r;
    }

    preorder(1);
    cout << endl;

    inorder(1);
    cout << endl;

    int root = 1;
    int prev = 0;
    stack<int> stk;
    vector<int> post;

    while (root != 0 || !stk.empty()) {
        while (root != 0) {
            stk.push(root);
            root = left[root];
            prev = root;
        }

        root = stk.top();
        int r = right[root];

        if (r != 0 && prev != r) {
            root = r;
        } else {
            post.push_back(root);
            stk.pop();
            prev = root;
            root = 0;
        }
    }

    for (int val : post) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

力扣

42. 接雨水

名题了，早有耳闻，确是上周才做。

思路

我还是更喜欢动态规划的做法。开两个数组分别记录每根柱子$i$左右侧最大高度的最小值，该最小值即为水位，再用水位减去柱子高度$height[i]$即可。

如何求leftmax[]和rightmax[]呢？用dp的思路。其实这里的dp很简单，就是从左往右（从右往左）扫描一遍记录最大值。

答案

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> leftmax(n, 0);
        vector<int> rightmax(n, 0);
        leftmax[0] = height[0];
        rightmax[n - 1] = height[n - 1];
        for (int i = 1; i < n; i++) {
            leftmax[i] = max(leftmax[i - 1], height[i]);
        }
        for (int i = n - 2; i >= 0; i--) {
            rightmax[i] = max(rightmax[i + 1], height[i]);
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int water = min(leftmax[i], rightmax[i]) - height[i];
            sum += water;
        }
        return sum;
    }
};

22. 括号生成

感觉比八皇后难。。。

思路

一开始我想的是递归讨论是这样的

$$()_{n} = ( + ()_{n - 1} + ) \space || \space () + () + ()_{n - 1} \space || \space ()_{n - 1} + ()$$

但是我发现我好像搓不出来（不知道是底力不够还是思路就不对），遂放弃。官解如下：

backtrack函数存当前字符串长，目前有的左括号和右括号的个数，题目要求的括号对数量。

void backtrack(vector<string> &ans, string &cur, int left, int right, int n)

递归终止条件：当字符串长度等于括号数量的两倍时，将字符串添加至答案数组。我们会在下面的操作保证括号是匹配的。

所以分情况讨论。当左括号数量小于总括号对数时，优先往字符串添加左括号，然后递归调用。当右括号小于左括号数量时，就添加右括号，然后递归调用。注意，这两个操作不是if-else关系。

回溯函数如下：

void backtrack(vector<string> &ans, string &cur, int left, int right, int n) {
    if (cur.size() == n * 2) {
        ans.push_back(cur);
        return;
    }
    if (left < n) {
        cur += '(';
        backtrack(ans, cur, left + 1, right, n);
        cur.pop_back();
    }
    if (right < left) {
        cur += ')';
        backtrack(ans, cur, left, right + 1, n);
        cur.pop_back();
    }
}

105. 从前序与中序遍历序列构造二叉树

思路

这题主要就是要清楚前序遍历中序遍历出来的序列的性质。

对于前序遍历$abcdef$，我们可以确定$a$为根节点，后面的子串则可以被分为两个部分，一部分左子树一部分右子树，每个子树性质同上。

对于中序遍历，我们可以确定根节点的左边必定为左子树，右边必定为右子树。至于根节点的寻找则需要借助前序遍历或后序遍历。

我们先用哈希表存下中序遍历出来的数组中每个节点对应数组的位置，方便我们后续定位每个子树的根节点。

int n = preorder.size();
unordered_map<int, int> inmap;
for (int i = 0; i < n; i++) {
    inmap[inorder[i]] = i;
}

然后写构造函数build。根据前面所说的性质，我们只需要传入每个（子）树前序遍历和中序遍历数组的左右端，这样就可以确定（子）树的所有节点以及（子）树大小，然后递归构建左子树和右子树。

TreeNode* build(vector<int> &preorder, vector<int> &inorder, int pl, int pr, int il, int ir) {
    if (pl > pr) return nullptr;
    TreeNode *root = new TreeNode(preorder[pl]);
    int inorder_root = inmap[preorder[pl]];
    int left_tree_size = inorder_root - il;

    root->left = build(preorder, inorder, pl + 1, pl + left_tree_size, il, inorder_root - 1);

    root->right = build(preorder, inorder, pl + left_tree_size + 1, pr, inorder_root + 1, ir);

    return root;
}

114. 二叉树展开为链表

思路

主要是前序遍历时用一个指针prev前驱节点，然后修改前驱节点。只要访问一个节点时，同时将左右节点入栈，就不会造成数据竞争。剩下也没什么好说的。

答案

class Solution {
public:
    void flatten(TreeNode* root) {
        if (root == nullptr) return;
        stack<TreeNode*> stk;
        stk.push(root);
        TreeNode *prev = nullptr;
        while (!stk.empty()) {

            root = stk.top();
            stk.pop();
            if (prev != nullptr) {
                prev->left = nullptr;
                prev->right = root;
            }
            TreeNode *left = root->left;
            TreeNode *right = root->right;
            if (right != nullptr) stk.push(right);
            if (left != nullptr) stk.push(left);

            prev = root;
        }
    }
};

131. 分割回文串

这里主要讲一种对字符串回文串查找预处理的方法，动态规划的思路。

我们用dfa[][]来表示从$i$到$j$子串是否为回文串。状态转移方程如下

$$dfa(i, j) = \begin{cases} True, & i \geq j \\ dfa(i+1,j−1)∧(s[i]=s[j]), & otherwise \end{cases}$$

然后就开始构建。注意，我们的i和j不从0开始，这是为了方便避免写出繁杂的if-else来规避各种越界问题，也可以避免考虑$i < j$的情况。

string s;
n = s.size();
dfa.assign(n, vector<bool>(n, true));
for (int i = n - 1; i >= 0; i--) {
    for (int j = i + 1; j < n; j++) {
        dfa[i][j] = (s[i] == s[j]) && dfa[i + 1][j - 1];
    }
}
dfs(s, 0);
return ans;

437. 路径总和 III

思路

我们定义节点的 前缀和 为：由根结点到当前结点的路径上所有节点的和。用$prefix[sum]$记录“从根走到当前搜索路径上某个节点时，前缀和 = sum”的出现次数。

我们主要是在深度优先搜索的过程中，通过递归传参获得当前节点前缀和$cur$，然后通过prefix[]获得以该节点为终点，和为targetSum的路径条数$prefix[cur - targetSum]$。然后将该结果写入prefix[]，接着递归左右子树，然后回溯还原。

注意，对于空路径我们也需要保存预先处理一下，此时因为空路径不经过任何节点，因此它的前缀和为 0。

答案

class Solution {
public:
    unordered_map<long long, int> prefix;

    int dfs(TreeNode* root, long long cur, int targetSum) {
        if (root == nullptr)
            return 0;

        int ret = 0;
        cur += root->val;
        if (prefix.count(cur - targetSum))
            ret = prefix[cur - targetSum];

        prefix[cur]++;

        ret += dfs(root->left, cur, targetSum);
        ret += dfs(root->right, cur, targetSum);

        prefix[cur]--;
        return ret;
    }

    int pathSum(TreeNode* root, int targetSum) {
        prefix[0] = 1; // 空路径处理
        return dfs(root, 0, targetSum);
    }
};

4. 寻找两个正序数组的中位数

中位数是中学数学内容，不多阐述。本题其实可以改编为求两个正序数组中的第k大数字。

思路

我们直接撰写int getKthNum(vector<int> &nums1, vector<int> &nums2, int k)

题目要求时间复杂度为$O(\log(m+n))$，加上两数组都是有序的，所以我们基本上只有二分查找的思想了。

我们首先对$k$二分，找到每个数组的第$k / 2 - 1$个数，将他们比较，假设$A[k / 2 - 1] < B[k / 2 - 1]$，那么我们就可以排除$(A[0], A[k / 2 - 1])$之间的数，反之也如此，然后我们就可以更新$k$的值为$k' = k−k/2$。接着循环直到某个数组被全部剔除，然后我们就可以返回另一个数组的第$k'$个值了。还有一种情况终止循环就是当$k' = 1$后，我们直接返回两个数组中的最小值即可。

实现

int getKthNum(vector<int> &nums1, vector<int> &nums2, int k) {
    int m = nums1.size();
    int n = nums2.size();

    int index1 = 0, index2 = 0;

    while (true) {
        if (index1 == m) {
            return nums2[index2 + k - 1];
        }
        if (index2 == n) {
            return nums1[index1 + k - 1];
        }
        if (k == 1) {
            return min(nums1[index1],nums2[index2]);
        }

        int newindex1 = min(index1 + k / 2 - 1, m - 1);
        int newindex2 = min(index2 + k / 2 - 1, n - 1);
        int p1 = nums1[newindex1];
        int p2 = nums2[newindex2];
        if (p1 <= p2) {
            k -= newindex1 - index1 + 1;
            index1 = newindex1 + 1;
        } else {
            k -= newindex2 - index2 + 1;
            index2 = newindex2 + 1;
        }
    }
}