LeetCode 每日一题 Day 123-136

1379. 找出克隆二叉树中的相同节点

给你两棵二叉树,原始树 original 和克隆树 cloned,以及一个位于原始树 original 中的目标节点 target。

其中,克隆树 cloned 是原始树 original 的一个 副本 。

请找出在树 cloned 中,与 target 相同 的节点,并返回对该节点的引用(在 C/C++ 等有指针的语言中返回 节点指针,其他语言返回节点本身)。

注意:你 不能 对两棵二叉树,以及 target 节点进行更改。只能 返回对克隆树 cloned 中已有的节点的引用。

示例 1:

在这里插入图片描述

输入: tree = [7,4,3,null,null,6,19], target = 3
输出: 3
解释: 上图画出了树 original 和 cloned。target 节点在树 original 中,用绿色标记。答案是树 cloned 中的黄颜色的节点(其他示例类似)。
示例 2:
在这里插入图片描述

输入: tree = [7], target = 7
输出: 7
示例 3:
在这里插入图片描述

输入: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
输出: 4

提示:

树中节点的数量范围为 [1, 104] 。
同一棵树中,没有值相同的节点。
target 节点是树 original 中的一个节点,并且不会是 null 。

进阶:如果树中允许出现值相同的节点,将如何解答?

递归即可:

/*** 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:TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned,TreeNode* target) {if (original == NULL) {return NULL;}if (original == target) {return cloned;}TreeNode* res = getTargetCopy(original->left, cloned->left, target);if (res != NULL) {return res;}return getTargetCopy(original->right, cloned->right, target);}
};

2192. 有向无环图中一个节点的所有祖先

给你一个正整数 n ,它表示一个 有向无环图 中节点的数目,节点编号为 0 到 n - 1 (包括两者)。

给你一个二维整数数组 edges ,其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边。

请你返回一个数组 answer,其中 answer[i]是第 i 个节点的所有 祖先 ,这些祖先节点 升序 排序。

如果 u 通过一系列边,能够到达 v ,那么我们称节点 u 是节点 v 的 祖先 节点。

示例 1:

在这里插入图片描述

输入:n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
输出:[[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
解释:
上图为输入所对应的图。

  • 节点 0 ,1 和 2 没有任何祖先。
  • 节点 3 有 2 个祖先 0 和 1 。
  • 节点 4 有 2 个祖先 0 和 2 。
  • 节点 5 有 3 个祖先 0 ,1 和 3 。
  • 节点 6 有 5 个祖先 0 ,1 ,2 ,3 和 4 。
  • 节点 7 有 4 个祖先 0 ,1 ,2 和 3 。
    示例 2:

在这里插入图片描述

输入:n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
输出:[[],[0],[0,1],[0,1,2],[0,1,2,3]]
解释:
上图为输入所对应的图。

  • 节点 0 没有任何祖先。
  • 节点 1 有 1 个祖先 0 。
  • 节点 2 有 2 个祖先 0 和 1 。
  • 节点 3 有 3 个祖先 0 ,1 和 2 。
  • 节点 4 有 4 个祖先 0 ,1 ,2 和 3 。

提示:

1 <= n <= 1000
0 <= edges.length <= min(2000, n * (n - 1) / 2)
edges[i].length == 2
0 <= fromi, toi <= n - 1
fromi != toi
图中不会有重边。
图是 有向 且 无环 的。

逆向dfs(菜狗不会,抄的灵神):

class Solution {
public:vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {vector<vector<int>> g(n);for (auto& e : edges) {g[e[1]].push_back(e[0]); // 反向建图}vector<vector<int>> ans(n);vector<int> vis(n);function<void(int)> dfs = [&](int x) {vis[x] = true; // 避免重复访问for (int y : g[x]) {if (!vis[y]) {dfs(y); // 只递归没有访问过的点}}};for (int i = 0; i < n; i++) {ranges::fill(vis, false);dfs(i);         // 从 i 开始 DFSvis[i] = false; // ans[i] 不含 ifor (int j = 0; j < n; j++) {if (vis[j]) {ans[i].push_back(j);}}}return ans;}
};

题解:两种方法:逆向/正向

1026. 节点与其祖先之间的最大差值

给定二叉树的根节点 root,找出存在于 不同 节点 A 和 B 之间的最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。

(如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先)

示例 1:

在这里插入图片描述

输入:root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出:7
解释:
我们有大量的节点与其祖先的差值,其中一些如下:
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中,最大值 7 由 |8 - 1| = 7 得出。
示例 2:
在这里插入图片描述

输入:root = [1,null,2,null,0,3]
输出:3

提示:

树中的节点数在 2 到 5000 之间。
0 <= Node.val <= 1e5

DFS:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),* right(right) {}* };*/
class Solution {
public:int maxAncestorDiff(TreeNode* root) {return dfs(root, root->val, root->val);}private:int dfs(TreeNode* node, int mn, int mx) {if (!node) {return mx - mn;}mx = max(mx, node->val);mn = min(mn, node->val);return max(dfs(node->left, mn, mx), dfs(node->right, mn, mx));}
};

1483. 树节点的第 K 个祖先(Hard)

给你一棵树,树上有 n 个节点,按从 0 到 n-1 编号。树以父节点数组的形式给出,其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。

树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。

实现 TreeAncestor 类:

TreeAncestor(int n, int[] parent) 对树和父数组中的节点数初始化对象。
getKthAncestor(int node, int k) 返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点,返回 -1 。

示例 1:

在这里插入图片描述

输入:
[“TreeAncestor”,“getKthAncestor”,“getKthAncestor”,“getKthAncestor”]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

输出:
[null,1,0,-1]

解释:
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);

treeAncestor.getKthAncestor(3, 1); // 返回 1 ,它是 3 的父节点
treeAncestor.getKthAncestor(5, 2); // 返回 0 ,它是 5 的祖父节点
treeAncestor.getKthAncestor(6, 3); // 返回 -1 因为不存在满足要求的祖先节点

提示:

1 <= k <= n <= 5 * 104
parent[0] == -1 表示编号为 0 的节点是根节点。
对于所有的 0 < i < n ,0 <= parent[i] < n 总成立
0 <= node < n
至多查询 5 * 1e4 次

看题解是acm的板子题,菜鸡不会(orz)

class TreeAncestor {private:vector<vector<int>> dp;public:TreeAncestor(int n, vector<int>& parent) : dp(n) {for (int i = 0; i < n; i++)dp[i].push_back(parent[i]);for (int j = 1;; j++) {bool allneg = true;for (int i = 0; i < n; i++) {int t = dp[i][j - 1] != -1 ? dp[dp[i][j - 1]][j - 1] : -1;dp[i].push_back(t);if (t != -1)allneg = false;}if (allneg)break; // 所有的节点的 2^j 的祖先都是 -1 了,就不用再计算了}}int getKthAncestor(int node, int k) {if (k == 0 || node == -1)return node;int pos =ffs(k) -1; // C++ 语言中 ffs(k) 求解出 k 的最右侧第一个 1 的位置(1-based)return pos < dp[node].size()? getKthAncestor(dp[node][pos], k - (1 << pos)): -1;}
};

是另外的大佬的题解:

力扣在逐渐把 ACM 模板题搬上来,这个问题是 Binary Lifting

1600. 王位继承顺序

一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点,这个家庭里有人出生也有人死亡。

这个王国有一个明确规定的王位继承顺序,第一继承人总是国王自己。我们定义递归函数 Successor(x, curOrder) ,给定一个人 x 和当前的继承顺序,该函数返回 x 的下一继承人。

Successor(x, curOrder):
如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中:
如果 x 是国王,那么返回 null
否则,返回 Successor(x 的父亲, curOrder)
否则,返回 x 不在 curOrder 中最年长的孩子
比方说,假设王国由国王,他的孩子 Alice 和 Bob (Alice 比 Bob 年长)和 Alice 的孩子 Jack 组成。

一开始, curOrder 为 [“king”].
调用 Successor(king, curOrder) ,返回 Alice ,所以我们将 Alice 放入 curOrder 中,得到 [“king”, “Alice”] 。
调用 Successor(Alice, curOrder) ,返回 Jack ,所以我们将 Jack 放入 curOrder 中,得到 [“king”, “Alice”, “Jack”] 。
调用 Successor(Jack, curOrder) ,返回 Bob ,所以我们将 Bob 放入 curOrder 中,得到 [“king”, “Alice”, “Jack”, “Bob”] 。
调用 Successor(Bob, curOrder) ,返回 null 。最终得到继承顺序为 [“king”, “Alice”, “Jack”, “Bob”] 。
通过以上的函数,我们总是能得到一个唯一的继承顺序。

请你实现 ThroneInheritance 类:

ThroneInheritance(string kingName) 初始化一个 ThroneInheritance 类的对象。国王的名字作为构造函数的参数传入。
void birth(string parentName, string childName) 表示 parentName 新拥有了一个名为 childName 的孩子。
void death(string name) 表示名为 name 的人死亡。一个人的死亡不会影响 Successor 函数,也不会影响当前的继承顺序。你可以只将这个人标记为死亡状态。
string[] getInheritanceOrder() 返回 除去 死亡人员的当前继承顺序列表。

示例:

输入:
[“ThroneInheritance”, “birth”, “birth”, “birth”, “birth”, “birth”, “birth”, “getInheritanceOrder”, “death”, “getInheritanceOrder”]
[[“king”], [“king”, “andy”], [“king”, “bob”], [“king”, “catherine”], [“andy”, “matthew”], [“bob”, “alex”], [“bob”, “asha”], [null], [“bob”], [null]]
输出:
[null, null, null, null, null, null, null, [“king”, “andy”, “matthew”, “bob”, “alex”, “asha”, “catherine”], null, [“king”, “andy”, “matthew”, “alex”, “asha”, “catherine”]]

解释:
ThroneInheritance t= new ThroneInheritance(“king”); // 继承顺序:king
t.birth(“king”, “andy”); // 继承顺序:king > andy
t.birth(“king”, “bob”); // 继承顺序:king > andy > bob
t.birth(“king”, “catherine”); // 继承顺序:king > andy > bob > catherine
t.birth(“andy”, “matthew”); // 继承顺序:king > andy > matthew > bob > catherine
t.birth(“bob”, “alex”); // 继承顺序:king > andy > matthew > bob > alex > catherine
t.birth(“bob”, “asha”); // 继承顺序:king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // 返回 [“king”, “andy”, “matthew”, “bob”, “alex”, “asha”, “catherine”]
t.death(“bob”); // 继承顺序:king > andy > matthew > bob(已经去世)> alex > asha > catherine
t.getInheritanceOrder(); // 返回 [“king”, “andy”, “matthew”, “alex”, “asha”, “catherine”]

提示:

1 <= kingName.length, parentName.length, childName.length, name.length <= 15
kingName,parentName, childName 和 name 仅包含小写英文字母。
所有的参数 childName 和 kingName 互不相同。
所有 death 函数中的死亡名字 name 要么是国王,要么是已经出生了的人员名字。
每次调用 birth(parentName, childName) 时,测试用例都保证 parentName 对应的人员是活着的。
最多调用 105 次birth 和 death 。
最多调用 10 次 getInheritanceOrder 。

哈希建树,前序遍历:

class ThroneInheritance {unordered_map<string, vector<string>> edges;unordered_set<string> dead;string king;public:ThroneInheritance(string kingName) { king = kingName; }void birth(string parentName, string childName) {edges[parentName].push_back(childName);}void death(string name) { dead.insert(name); }vector<string> getInheritanceOrder() {vector<string> ans;preorder(ans, king);return ans;}void preorder(vector<string>& ans, string name) {if (!dead.count(name)) {ans.push_back(name);}for (const string& childName : edges[name]) {preorder(ans, childName);}}
};/*** Your ThroneInheritance object will be instantiated and called as such:* ThroneInheritance* obj = new ThroneInheritance(kingName);* obj->birth(parentName,childName);* obj->death(name);* vector<string> param_3 = obj->getInheritanceOrder();*/

2009. 使数组连续的最少操作数(Hard)

给你一个整数数组 nums 。每一次操作中,你可以将 nums 中 任意 一个元素替换成 任意 整数。

如果 nums 满足以下条件,那么它是 连续的 :

nums 中所有元素都是 互不相同 的。
nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。
比方说,nums = [4, 2, 5, 3] 是 连续的 ,但是 nums = [1, 2, 3, 5, 6] 不是连续的 。

请你返回使 nums 连续 的 最少 操作次数。

示例 1:

输入:nums = [4,2,5,3]
输出:0
解释:nums 已经是连续的了。
示例 2:

输入:nums = [1,2,3,5,6]
输出:1
解释:一个可能的解是将最后一个元素变为 4 。
结果数组为 [1,2,3,5,4] ,是连续数组。
示例 3:

输入:nums = [1,10,100,1000]
输出:3
解释:一个可能的解是:

  • 将第二个元素变为 2 。
  • 将第三个元素变为 3 。
  • 将第四个元素变为 4 。
    结果数组为 [1,2,3,4] ,是连续数组。

提示:

1 <= nums.length <= 1e5
1 <= nums[i] <= 1e9

滑动窗口,当时做这题没想到方法wa了好多次,思维比肌肉记忆更重要:

class Solution {
public:int minOperations(vector<int>& nums) {ranges::sort(nums);int n = nums.size();int m = unique(nums.begin(), nums.end()) - nums.begin();int ans = 0, left = 0;for (int i = 0; i < m; i++) {while (nums[left] < nums[i] - n + 1) {left++;}ans = max(ans, i - left + 1);}return n - ans;}
};

2529. 正整数和负整数的最大计数

给你一个按 非递减顺序 排列的数组 nums ,返回正整数数目和负整数数目中的最大值。

换句话讲,如果 nums 中正整数的数目是 pos ,而负整数的数目是 neg ,返回 pos 和 neg二者中的最大值。
注意:0 既不是正整数也不是负整数。

示例 1:

输入:nums = [-2,-1,-1,1,2,3]
输出:3
解释:共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。
示例 2:

输入:nums = [-3,-2,-1,0,0,1,2]
输出:3
解释:共有 2 个正整数和 3 个负整数。计数得到的最大值是 3 。
示例 3:

输入:nums = [5,20,66,1314]
输出:4
解释:共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。

提示:

1 <= nums.length <= 2000
-2000 <= nums[i] <= 2000
nums 按 非递减顺序 排列。

进阶:你可以设计并实现时间复杂度为 O(log(n)) 的算法解决此问题吗?

二分:

class Solution {
public:int maximumCount(vector<int>& nums) {int left = 0, right = nums.size();while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < 0) {left = mid + 1;} else {right = mid;}}int negCount = left;left = 0, right = nums.size();while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] <= 0) {left = mid + 1;} else {right = mid;}}int posCount = nums.size() - left;return max(negCount, posCount);}
};

但是看了灵神题解后发现他的真的很简洁:

class Solution {
public:int maximumCount(vector<int> &nums) {int neg = 0, pos = 0;for (int x : nums) {if (x < 0) {neg++;} else if (x > 0) {pos++;}}return max(neg, pos);}
};

题解:两种方法:遍历 / 二分查找(Python/Java/C++/Go/JS/Rust)

1702. 修改后的最大二进制字符串

给你一个二进制字符串 binary ,它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改:

操作 1 :如果二进制串包含子字符串 “00” ,你可以用 “10” 将其替换。
比方说, “00010” -> “10010”
操作 2 :如果二进制串包含子字符串 “10” ,你可以用 “01” 将其替换。
比方说, “00010” -> “00001”
请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字,那么我们称二进制字符串 x 大于二进制字符串 y 。

示例 1:

输入:binary = “000110”
输出:“111011”
解释:一个可行的转换为:
“000110” -> “000101”
“000101” -> “100101”
“100101” -> “110101”
“110101” -> “110011”
“110011” -> “111011”
示例 2:

输入:binary = “01”
输出:“01”
解释:“01” 没办法进行任何转换。

提示:

1 <= binary.length <= 105
binary 仅包含 ‘0’ 和 ‘1’ 。

模拟贪心:


class Solution {
public:string maximumBinaryString(string binary) {int n = binary.size();int j = 0;for (int i = 0; i < n; i++) {if (binary[i] == '0') {while (j <= i || (j < n && binary[j] == '1')) {j++;}if (j < n) {binary[j] = '1';binary[i] = '1';binary[i + 1] = '0';}}}return binary;}
};

1766. 互质树

给你一个 n 个节点的树(也就是一个无环连通无向图),节点编号从 0 到 n - 1 ,且恰好有 n - 1 条边,每个节点有一个值。树的 根节点 为 0 号点。

给你一个整数数组 nums 和一个二维数组 edges 来表示这棵树。nums[i] 表示第 i 个点的值,edges[j] = [uj, vj] 表示节点 uj 和节点 vj 在树中有一条边。

当 gcd(x, y) == 1 ,我们称两个数 x 和 y 是 互质的 ,其中 gcd(x, y) 是 x 和 y 的 最大公约数 。

从节点 i 到 根 最短路径上的点都是节点 i 的祖先节点。一个节点 不是 它自己的祖先节点。

请你返回一个大小为 n 的数组 ans ,其中 ans[i]是离节点 i 最近的祖先节点且满足 nums[i] 和 nums[ans[i]] 是 互质的 ,如果不存在这样的祖先节点,ans[i] 为 -1 。

示例 1:

在这里插入图片描述

输入:nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
输出:[-1,0,0,1]
解释:上图中,每个节点的值在括号中表示。

  • 节点 0 没有互质祖先。
  • 节点 1 只有一个祖先节点 0 。它们的值是互质的(gcd(2,3) == 1)。
  • 节点 2 有两个祖先节点,分别是节点 1 和节点 0 。节点 1 的值与它的值不是互质的(gcd(3,3) == 3)但节点 0 的值是互质的(gcd(2,3) == 1),所以节点 0 是最近的符合要求的祖先节点。
  • 节点 3 有两个祖先节点,分别是节点 1 和节点 0 。它与节点 1 互质(gcd(3,2) == 1),所以节点 1 是离它最近的符合要求的祖先节点。
    示例 2:

在这里插入图片描述

输入:nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
输出:[-1,0,-1,0,0,0,-1]

提示:

nums.length == n
1 <= nums[i] <= 50
1 <= n <= 105
edges.length == n - 1
edges[j].length == 2
0 <= uj, vj < n
uj != vj

DFS回溯,抄的灵神题解:

const int MX = 51;
vector<int> coprime[MX];auto init = [] {// 预处理:coprime[i] 保存 [1, MX) 中与 i 互质的所有元素for (int i = 1; i < MX; i++) {for (int j = 1; j < MX; j++) {if (gcd(i, j) == 1) {coprime[i].push_back(j);}}}return 0;
}();class Solution {vector<vector<int>> g;vector<int> ans;pair<int, int> val_depth_id[MX]; // 包含深度和节点编号void dfs(int x, int fa, int depth, vector<int> &nums) {int val = nums[x]; // x 的节点值// 计算与 val 互质的数中,深度最大的节点编号int max_depth = 0;for (int j : coprime[val]) {auto [depth, id] = val_depth_id[j];if (depth > max_depth) {max_depth = depth;ans[x] = id;}}auto tmp = val_depth_id[val]; // 用于恢复现场val_depth_id[val] = {depth, x}; // 保存 val 对应的节点深度和节点编号for (int y : g[x]) {if (y != fa) {dfs(y, x, depth + 1, nums);}}val_depth_id[val] = tmp; // 恢复现场}public:vector<int> getCoprimes(vector<int> &nums, vector<vector<int>> &edges) {int n = nums.size();g.resize(n);for (auto &e : edges) {int x = e[0], y = e[1];g[x].push_back(y);g[y].push_back(x);}ans.resize(n, -1);dfs(0, -1, 1, nums);return ans;}
};

DFS 中记录节点值的深度和编号,回溯写法

学到了学到了

2923. 找到冠军 I

一场比赛中共有 n 支队伍,按从 0 到 n - 1 编号。

给你一个下标从 0 开始、大小为 n * n 的二维布尔矩阵 grid 。对于满足 0 <= i, j <= n - 1 且 i != j 的所有 i, j :如果 grid[i][j] == 1,那么 i 队比 j 队 强 ;否则,j 队比 i 队 强 。

在这场比赛中,如果不存在某支强于 a 队的队伍,则认为 a 队将会是 冠军 。

返回这场比赛中将会成为冠军的队伍。

示例 1:

输入:grid = [[0,1],[0,0]]
输出:0
解释:比赛中有两支队伍。
grid[0][1] == 1 表示 0 队比 1 队强。所以 0 队是冠军。
示例 2:

输入:grid = [[0,0,1],[1,0,1],[0,0,0]]
输出:1
解释:比赛中有三支队伍。
grid[1][0] == 1 表示 1 队比 0 队强。
grid[1][2] == 1 表示 1 队比 2 队强。
所以 1 队是冠军。

提示:

n == grid.length
n == grid[i].length
2 <= n <= 100
grid[i][j] 的值为 0 或 1
对于所有 i, grid[i][i] 等于 0.
对于满足 i != j 的所有 i, j ,grid[i][j] != grid[j][i] 均成立
生成的输入满足:如果 a 队比 b 队强,b 队比 c 队强,那么 a 队比 c 队强

暴力即可:

class Solution {
public:int findChampion(vector<vector<int>>& grid) {int ans = 0;for (int i = 1; i < grid.size(); i++) {if (grid[i][ans]) {ans = i;}}return ans;}
};

2924. 找到冠军 II

一场比赛中共有 n 支队伍,按从 0 到 n - 1 编号。每支队伍也是 有向无环图(DAG) 上的一个节点。

给你一个整数 n 和一个下标从 0 开始、长度为 m 的二维整数数组 edges 表示这个有向无环图,其中 edges[i] = [ui, vi] 表示图中存在一条从 ui 队到 vi 队的有向边。

从 a 队到 b 队的有向边意味着 a 队比 b 队 强 ,也就是 b 队比 a 队 弱 。

在这场比赛中,如果不存在某支强于 a 队的队伍,则认为 a 队将会是 冠军 。

如果这场比赛存在 唯一 一个冠军,则返回将会成为冠军的队伍。否则,返回 -1 。

注意

环 是形如 a1, a2, …, an, an+1 的一个序列,且满足:节点 a1 与节点 an+1 是同一个节点;节点 a1, a2, …, an 互不相同;对于范围 [1, n] 中的每个 i ,均存在一条从节点 ai 到节点 ai+1 的有向边。
有向无环图 是不存在任何环的有向图。

示例 1:

在这里插入图片描述

输入:n = 3, edges = [[0,1],[1,2]]
输出:0
解释:1 队比 0 队弱。2 队比 1 队弱。所以冠军是 0 队。
示例 2:

在这里插入图片描述

输入:n = 4, edges = [[0,2],[1,3],[1,2]]
输出:-1
解释:2 队比 0 队和 1 队弱。3 队比 1 队弱。但是 1 队和 0 队之间不存在强弱对比。所以答案是 -1 。

提示:

1 <= n <= 100
m == edges.length
0 <= m <= n * (n - 1) / 2
edges[i].length == 2
0 <= edge[i][j] <= n - 1
edges[i][0] != edges[i][1]
生成的输入满足:如果 a 队比 b 队强,就不存在 b 队比 a 队强
生成的输入满足:如果 a 队比 b 队强,b 队比 c 队强,那么 a 队比 c 队强

直接遍历:

class Solution {
public:int findChampion(int n, vector<vector<int>>& edges) {vector<int> indegree(n, 0);for (const auto& edge : edges) {indegree[edge[1]]++;}int champion = -1;for (int i = 0; i < n; ++i) {if (indegree[i] == 0) {if (champion != -1) {return -1;}champion = i;}}return champion;}
};

705. 设计哈希集合

不使用任何内建的哈希表库设计一个哈希集合(HashSet)。

实现 MyHashSet 类:

void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。

示例:

输入:
[“MyHashSet”, “add”, “add”, “contains”, “contains”, “add”, “contains”, “remove”, “contains”]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
输出:
[null, null, null, true, false, null, true, null, false]

解释:
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ,(未找到)
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // 返回 False ,(已移除)

提示:

0 <= key <= 1e6
最多调用 1e4 次 add、remove 和 contains

HashSet基础:

class MyHashSet {
public:MyHashSet() { data = vector<bool>(1000001, false); }void add(int key) { data[key] = true; }void remove(int key) { data[key] = false; }bool contains(int key) { return data[key]; }private:vector<bool> data;
};/*** Your MyHashSet object will be instantiated and called as such:* MyHashSet* obj = new MyHashSet();* obj->add(key);* obj->remove(key);* bool param_3 = obj->contains(key);*/

706. 设计哈希映射

不使用任何内建的哈希表库设计一个哈希映射(HashMap)。

实现 MyHashMap 类:

MyHashMap() 用空映射初始化对象
void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中,则更新其对应的值 value 。
int get(int key) 返回特定的 key 所映射的 value ;如果映射中不包含 key 的映射,返回 -1 。
void remove(key) 如果映射中存在 key 的映射,则移除 key 和它所对应的 value 。

示例:

输入:
[“MyHashMap”, “put”, “put”, “get”, “get”, “put”, “get”, “remove”, “get”]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
输出:
[null, null, null, 1, -1, null, 1, null, -1]

解释:
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]]
myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(1); // 返回 1 ,myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(3); // 返回 -1(未找到),myHashMap 现在为 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]](更新已有的值)
myHashMap.get(2); // 返回 1 ,myHashMap 现在为 [[1,1], [2,1]]
myHashMap.remove(2); // 删除键为 2 的数据,myHashMap 现在为 [[1,1]]
myHashMap.get(2); // 返回 -1(未找到),myHashMap 现在为 [[1,1]]

提示:

0 <= key, value <= 1e6
最多调用 1e4 次 put、get 和 remove 方法

同样的Hashset专题,基础:


class MyHashMap {
public:MyHashMap() {data = vector<int>(1000001 , -1);}void put(int key, int value) {data[key] = value;}int get(int key) {return data[key];}void remove(int key) {data[key] = -1;}private:vector<int> data;
};/*** Your MyHashMap object will be instantiated and called as such:* MyHashMap* obj = new MyHashMap();* obj->put(key,value);* int param_2 = obj->get(key);* obj->remove(key);*/

924. 尽量减少恶意软件的传播(Hard)

给出了一个由 n 个节点组成的网络,用 n × n 个邻接矩阵图 graph 表示。在节点网络中,当 graph[i][j] = 1 时,表示节点 i 能够直接连接到另一个节点 j。

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接,且其中至少一个节点受到恶意软件的感染,那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续,直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后,整个网络中感染恶意软件的最终节点数。

如果从 initial 中移除某一节点能够最小化 M(initial), 返回该节点。如果有多个节点满足条件,就返回索引最小的节点。

请注意,如果某个节点已从受感染节点的列表 initial 中删除,它以后仍有可能因恶意软件传播而受到感染。

示例 1:

输入:graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输出:0
示例 2:

输入:graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
输出:0
示例 3:

输入:graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
输出:1

提示:

n == graph.length
n == graph[i].length
2 <= n <= 300
graph[i][j] == 0 或 1.
graph[i][j] == graph[j][i]
graph[i][i] == 1
1 <= initial.length <= n
0 <= initial[i] <= n - 1
initial 中所有整数均不重复

DFS+并查集来做,虽然知道方法还是wa了10发,受不了了还是看了灵神题解:

class Solution {
public:int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {set<int> st(initial.begin(), initial.end());vector<int> vis(graph.size());int ans = -1, max_size = 0, node_id, size;function<void(int)> dfs = [&](int x) {vis[x] = true;size++;// 按照状态机更新 node_idif (node_id != -2 && st.contains(x)) {node_id = node_id == -1 ? x : -2;}for (int y = 0; y < graph[x].size(); y++) {if (graph[x][y] && !vis[y]) {dfs(y);}}};for (int x : initial) {if (vis[x]) {continue;}node_id = -1;size = 0;dfs(x);if (node_id >= 0 &&(size > max_size || size == max_size && node_id < ans)) {ans = node_id;max_size = size;}}return ans < 0 ? ranges::min(initial) : ans;}
};

只包含一个被感染节点的最大连通块

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/312119.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【静态分析】软件分析课程实验-前置准备

课程&#xff1a;南京大学的《软件分析》课程 平台&#xff1a;Tai-e&#xff08;太阿&#xff09;实验作业平台 1. 实验概述 Tai-e 是一个分析 Java 程序的静态程序分析框架&#xff0c;相比于已有的知名静态程序分析框架&#xff08;如 Soot、Wala 等&#xff09;&#xf…

女上司问我:误删除PG百万条数据,可以闪回吗?

作者&#xff1a;IT邦德 中国DBA联盟(ACDU)成员&#xff0c;10余年DBA工作经验 擅长主流数据Oracle、MySQL、PG、openGauss运维 备份恢复&#xff0c;安装迁移&#xff0c;性能优化、故障应急处理等可提供技术业务&#xff1a; 1.DB故障处理/疑难杂症远程支援 2.Mysql/PG/Oracl…

字体反爬积累知识

目录 一、什么是字体反扒 二、Unicode编码 三、利用font包获取映射关系 一、什么是字体反扒 字体反爬是一种常见的反爬虫技术&#xff0c;它通过将网页中的文本内容转换为特殊的字体格式来防止爬虫程序直接获取和解析文本信息。字体反爬的原理是将常规的字符映射到特殊的字…

服务器数据恢复—xfs文件系统节点、目录项丢失的数据恢复案例

服务器数据恢复环境&#xff1a; EMC某型号存储&#xff0c;该存储内有一组由12块磁盘组建的raid5阵列&#xff0c;划分了两个lun。 服务器故障&#xff1a; 管理员为服务器重装操作系统后&#xff0c;发现服务器的磁盘分区发生改变&#xff0c;原来的sdc3分区丢失。由于该分区…

C++ | Leetcode C++题解之第31题下一个排列

题目&#xff1a; 题解&#xff1a; class Solution { public:void nextPermutation(vector<int>& nums) {int i nums.size() - 2;while (i > 0 && nums[i] > nums[i 1]) {i--;}if (i > 0) {int j nums.size() - 1;while (j > 0 && …

Keepalived+LVS+nginx搭建nginx高可用集群

一、简介 nginx是一款非常优秀的反向代理工具&#xff0c;支持请求分发&#xff0c;负载均衡&#xff0c;以及缓存等等非常实用的功能。在请求处理上&#xff0c;nginx采用的是epoll模型&#xff0c;这是一种基于事件监听的模型&#xff0c;因而其具备非常高效的请求处理效率…

笔试题1 -- 吃掉字符串中相邻的相同字符(点击消除_牛客网)

吃掉字符串中相邻的相同字符 文章目录 吃掉字符串中相邻的相同字符题目重现解法一&#xff1a;(基于 erase() 函数实现)解法二&#xff1a;&#xff08;利用 栈 辅助实现&#xff09;总结 题目链接&#xff1a; 点击消除_牛客网 题目重现 牛牛拿到了一个字符串。 他每次“点击…

msyql中SQL 错误 [1118] [42000]: Row size too large (> 8126)

场景&#xff1a; CREATE TABLE test-qd.eqtree (INSERT INTO test.eqtree (idocid VARCHAR(50) NULL,sfcode VARCHAR(50) NULL,sfname VARCHAR(50) NULL,sfengname VARCHAR(50) NULL,…… ) ENGINEInnoDB DEFAULT CHARSETutf8 COLLATEutf8_general_ci;或 alter table eqtre…

error: failed to push some refs to ‘https://gitee.com/zhao-zhimin12/gk.git‘

git push origin master发现以下报错: 解决办法: 一、强制推送 git push origin master -f &#xff08;加上 -f 就是强制&#xff09; 二、 先拉取最新代码&#xff0c;再推送 1.git pull origin master 2.git push origin master

两步解决 Flutter Your project requires a newer version of the Kotlin Gradle plugin

在开发Flutter项目的时候,遇到这个问题Flutter Your project requires a newer version of the Kotlin Gradle plugin 解决方案分两步: 1、在android/build.gradle里配置最新版本的kotlin 根据提示的kotlin官方网站搜到了Kotlin的最新版本是1.9.23,如下图所示: 同时在Ko…

腾讯云人脸服务开通详解:快速部署,畅享智能体验

请注意&#xff0c;在使用人脸识别服务时&#xff0c;需要确保遵守相关的法律法规和政策规定&#xff0c;保护用户的合法权益&#xff0c;并依法收集、使用、存储用户信息。此外&#xff0c;腾讯云每个月会提供一定次数的人脸识别调用机会&#xff0c;对于一般的小系统登录来说…

故障转移-redis

4.4.故障转移 集群初识状态是这样的&#xff1a; 其中7001、7002、7003都是master&#xff0c;我们计划让7002宕机。 4.4.1.自动故障转移 当集群中有一个master宕机会发生什么呢&#xff1f; 直接停止一个redis实例&#xff0c;例如7002&#xff1a; redis-cli -p 7002 sh…

pip如何查看Python某个包已发行所有版本号?

以matplotlib包为例子&#xff0c; pip install matplotlib6666 6666只是胡乱输入的一个数&#xff0c;反正输入任意一个不像版本号的数字都可以&#xff5e; matplotlib所有版本号如下&#xff0c; 0.86, 0.86.1, 0.86.2, 0.91.0, 0.91.1, 1.0.1, 1.1.0, 1.1.1, 1.2.0, 1.2.1…

盲人安全导航技巧:科技赋能让出行更自如

作为一名资深记者&#xff0c;长期关注并报道无障碍领域的发展动态。今日&#xff0c;我将聚焦盲人安全导航技巧&#xff0c;探讨这一主题下科技如何赋能视障人士实现更为安全、独立的出行。一款融合了实时避障、拍照识别物体及场景功能的盲人出行辅助应用叫做蝙蝠避障&#xf…

机器学习算法——决策树算法详细解读

决策树&#xff08;Decision Tree&#xff09;是在已知各种情况发生概率的基础上&#xff0c;通过构成决策树来求取净现值的期望值大于等于零的概率&#xff0c;评价项目风险&#xff0c;判断其可行性的决策分析方法&#xff0c;是直观运用概率分析的一种图解法。由于这种决策分…

Ansys在压力容器行业的典型应用(下)

压力容器热棘轮效应安定性分析 • 设计中的难点 ‐ 平均应力和交变载荷联合作用时&#xff0c;每次循环可能使容器产生一个不可逆的塑性应变增量&#xff0c;当塑性应变值递增至材料塑性被耗尽时&#xff0c;就会发生断裂。这种断裂与一般的疲劳破坏不同&#xff0c;一般的疲…

爱帮供应链邀您参观2024杭州快递物流供应链与技术装备展览会

2024年7月8-10日|杭州国际博览中心 同期举办&#xff1a;2024中国数字物流技术与应用展 2024国际电商物流包装产业展 2024新能源商用车、物流车展 展会介绍 本届展会致力于全面展示快递物流上下游领域的创新解决方案&#xff0c;涵盖快递物流供应链、智能装备、AGV机器人与…

实现 Table 的增加和删除,不依赖后端数据回显

需求 删除前 删除后 分析 首先写一个 Table <a-card style"width:100%"><template#extra><a-button type"text" click"addSelectItem" style"margin-right: 5px">添加</a-button><a-button type&quo…

基于JavaWeb开发的springboot网约车智能接单规划小程序[附源码]

基于JavaWeb开发的springboot网约车智能接单规划小程序[附源码] &#x1f345; 作者主页 央顺技术团队 &#x1f345; 欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; &#x1f345; 文末获取源码联系方式 &#x1f4dd; &#x1f345; 查看下方微信号获取联系方式 承接各种…

算法思想总结:链表

一、链表的常见技巧总结 二、两数相加 . - 力扣&#xff08;LeetCode&#xff09; class Solution { public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {//利用t来存进位信息int t0;ListNode*newheadnew ListNode(0);//创建一个哨兵节点&#xff0c;方便尾插List…