2024.3.21 晚 20:00 前，突然出名单，鼠鼠擦线居然进了复试，遂马上准备材料和上机考。

由于来不及了，所以打算直接把真题过一遍。

感谢 Pobz 老哥提供的机考回忆。

1. 二叉树相同子结构判断

LeetCode 原题链接

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool check(TreeNode* A, TreeNode* B) {
      // 都存在 ---> 看值
      if (A && B) {
        if (A->val == B->val) {
          // 值相等，看孩子
          return check(A->left, B->left) && check(A->right, B->right);
        } else {
          return false;
        }
      } else {
        if (!A && B) {
          return false;
        } else {
          return true;
        }
      }
    }

    bool dfs(TreeNode* A, TreeNode* B) {
        if (!A || !B) {
            return false;
        }
        // 如果满足值相等，可能是匹配的子树 ---> 彻底检查
        if (A->val == B->val && check(A, B)) {
          return true;
        }
        // 如果当前顶点与 B 的 root 不满足 ---> 遍历孩子寻找机会
        return dfs(A->left, B) || dfs(A->right, B);
    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        return dfs(A, B);
    }
};

2. 打地鼠

Acwing 原题链接

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 1e5 + 10;
int n, upper_limit;
int x[N];

int main() {
    cin >> n >> upper_limit;

    for (int i = 0; i < n; ++ i) {
        cin >> x[i];
    }

    sort(x, x + n);

    int res = 0;
    int last_value = x[0];
    for (int i = 1; i < n; ++ i) {
        // 差距不小于给定的数
        if (x[i] - last_value >= upper_limit) {
            ++ res;
            last_value = x[i];
        }
    }

    cout << ++ res << endl;

    return 0;
}

// 1 2 4 5 7 8

3. 675. 为高尔夫比赛砍树

LeetCode 原题链接

代码

class Solution {
private:
  int tree_nums;

  struct meta_info {
    int height;
    int _x, _y;
    bool operator<(const meta_info &o) {
      return height < o.height;
    }
  } trees[2505];

  // 向上、下、左、右四个方向之一移动一个单位
  int dx[4] = {0, 0, -1, 1};
  int dy[4] = {1, -1, 0, 0};

  using pii = pair<int, int>;
#define x first
#define y second
  vector<vector<int>> m_forest;

  int m, n;

public:
  int bfs_find_road(pii current, pii dst) {
    if (current == dst) {
      return 0;
    }

    queue<pii> q;
    bool visit[55][55] = {false};

    int length = 0;
    q.emplace(current);
    visit[current.x][current.y] = true;


    while (!q.empty()) {
      int sz = q.size();
      ++ length;

      // 把同一路径长度下所有的点都走一遍
      while (sz --) {
        auto head = q.front();
        q.pop();

        // 考察周围四个
        for (int i = 0; i < 4; ++ i) {
          auto next_x = head.x + dx[i];
          auto next_y = head.y + dy[i];
          // 是合法的下一个单元格
          if (next_x >= 0 && next_x < m && next_y >= 0 && next_y < n) {
            // 达到了目的地
            if (dst.x == next_x && dst.y == next_y) {
              return length;
            }

            // 访问过了
            if (visit[next_x][next_y]) {
              continue;
            }

            visit[next_x][next_y] = true;

            // 不是目的地
            if (m_forest[next_x][next_y] == 0) {
              // 0 -> 是障碍
              continue;
            } else {
              // 1 -> 是平地
              q.emplace(make_pair(next_x, next_y));
            }
          }
        }
      }
    }

    return -1;
  }

  int cutOffTree(vector<vector<int>>& forest) {
    m = forest.size(), n = forest[0].size();
    m_forest = forest;
    //将所有的合法树存储起来
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        //0障碍，1地面，其他是树
        if (forest[i][j] > 1) {
          trees[tree_nums ++] = {forest[i][j], i, j};
        }
      }
    }

    // 找到一条唯一路径（没有两棵树的高度是相同的）
    // 必然存在一个严格单调递增的序列
    sort(trees, trees + tree_nums);

    // 路径长度求和
    int ans = 0;

    // 查找从当前顶点到下一个顶点的最短路径
    pii current = {0, 0};
    for (int i = 0; i < tree_nums; ++ i) {
      auto tree = trees[i];
      pii next = make_pair(tree._x, tree._y);
      int res = bfs_find_road(current, next);
      if (res == -1) {
        return -1;
      }
      // cout << res << endl;
      // cout << next.x << " " << next.y << " ok!" << endl; 
      ans += res;
      current = next;
    }

    return ans;
  }
};

// 2 3 4
// 0 0 5
// 8 7 6