652. 寻找重复的子树
# 652. 寻找重复的子树
给定一棵二叉树 root，返回所有重复的子树。 对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。 如果两棵树具有相同的结构和相同的结点值，则它们是重复的。 示例 1：
输入：root = [1,2,3,4,null,2,4,null,null,4]输出：[[2,4],[4]]
示例 2：
输入：root = [2,1,1]输出：[[1]]
示例 3：
输入：root = [2,2,2,3,null,3,null]输出：[[2,3],[3]]
提示：
树中的结点数在 \([1,10^4]\) 范围内。
-200 <= Node.val <= 200
# 题解
emmm, 这是中等题？ 参考官方题解
class Solution {public: vector findDuplicateSubtrees(TreeNode* root) { dfs(root); return {repeat.begin(), repeat.end()}; } ...
滴滴笔试
时间：2022/9/4 19:00~20:40 20 道选择题 两道编程题 第一题：n 个桃子，常数 k，第 i 个重量为 \(a_i\)，使一箱中最重的桃子重量不超过平均重量的 k 倍，求一箱中最多几个桃子。 通过 55%
#include<iostream>#include<vector>#include<algorithm> using namespace std;int main() { int n, k; cin >> n >> k; vector a; vector b; for (int i = 0;i < n;i++) { int t; cin >> t; a.push_back(t); } sort(a.begin(), a.end()); b.push_back(a[0]); for (int i = 1;i < n;i++) { b.push_b ...
小红书笔试
时间：2022/9/1 16:00~18:00 20 道选择题 三道编程题 第一题：输入一个数字序列，及镜像复制次数，求第 k 位的数。
#include<iostreaam>#include<vector>using namespace std;int main() { int n, m; long long k; cin >> n >> m >> k; vector a(2 * n, 0); for (int i = 0;i < n;i++) { int t; cin >> t; a[i] = t; a[2 * n - 1 - i] = t; } k %= (2 * n); cout << a[k - 1] << endl; return 0;}
第二题：输入一个数字序列，每次可对一个值加一或减一，求使序列乘积为 7 的最小操作次数。
#include<i ...
1582. 二进制矩阵中的特殊位置
https://leetcode.cn/problems/special-positions-in-a-binary-matrix/ 给你一个大小为 rows x cols 的矩阵 mat，其中 mat [i][j] 是 0 或 1，请返回 矩阵 mat 中特殊位置的数目 。 特殊位置 定义：如果 mat [i][j] == 1 并且第 i 行和第 j 列中的所有其他元素均为 0（行和列的下标均 从 0 开始 ），则位置 (i, j) 被称为特殊位置。 示例 1：
输入：mat = [[1,0,0], [0,0,1], [1,0,0]]输出：1解释：(1,2) 是一个特殊位置，因为 mat[1][2] == 1 且所处的行和列上所有其他元素都是 0
示例 2：
输入：mat = [[1,0,0], [0,1,0], [0,0,1]]输出：3解释：(0,0), (1,1) 和 (2,2) 都是特殊位置
示例 3：
输入：mat = [[0,0,0,1], [1,0,0,0], [0,1,1,0], [0,0,0,0]]输出：2
示例 4：
输入：mat = [[0,0,0 ...
646. 最长数对链
# 646. 最长数对链
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。 现在，我们定义一种跟随关系，当且仅当 b <c 时，数对 (c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。 示例：
输入：[[1,2], [2,3], [3,4]]输出：2解释：最长的数对链是 [1,2] -> [3,4]
提示：
给出数对的个数在 [1, 1000] 范围内。
# 题解
动态规划
class Solution {public: int findLongestChain(vector<vector<int>>& pairs) { sort(pairs.begin(),pairs.end()); vector dp(pairs.size(),1); for(int i=0;i<pairs.size();i++)&# ...
687. 最长同值路径
https://leetcode.cn/problems/longest-univalue-path/ 给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。 两个节点之间的路径长度 由它们之间的边数表示。 示例 1:
输入：root = [5,4,5,1,1,5]输出：2
示例 2:
输入：root = [1,4,5,4,4,5]输出：2
提示:
树的节点数的范围是 [0, 104]
-1000 <= Node.val <= 1000
树的深度将不超过 1000
# 题解
利用深搜递归获得经过某个父节点得到的最长规定路径，从而得到全局最长规定路径
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), righ ...
深信服笔试
时间：2022/9/1 19:00~21:00 选择题 10 道，不定项 填空题 10 道 编程题三道 一、输入一个长度为 n 的数组及 k，循环比较数组的前两个元素，将较大的一个放在数组首位，将较小的一个放在数组末位，求连续胜利 k 次的数字。
#include<iostream>#include<list>#include<cmath>using namespace std;int main() { list arr; int k; int n = 0; int m = 0; int flag; while (cin >> k) { arr.push_back(k); n++; flag = m; m = max(m, k); } arr.pop_back(); if (k < n - 1) { int flag = 0; int ans = 0; ...
CVTE笔试
时间：2022/8/31 19:00~20:30 不可修改之前做过的题目，白板编程 单多选混杂 20 道 编程题两道 第一题：降序排列输入数据并返回前百分之三十中最小的数。 第二题：输入 IPV4 地址（大于两个），返回子网最大掩码长度（1 的个数最多），使 IP 处于同一子网中。