526互联

【Leetcode刷题记录】1、统计参与通信的服务器；2、统计二叉树中好节点的数目；3、从两个数字数组里生成最小数字

发布时间 2023-09-06 17:20:32作者: Archigenius

1、统计参与通信的服务器

题目：这里有一幅服务器分布图，服务器的位置标识在 m * n 的整数矩阵网格 grid 中，1 表示单元格上有服务器，0 表示没有。

如果两台服务器位于同一行或者同一列，我们就认为它们之间可以进行通信。

请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。

思路：二次遍历！第一次遍历统计服务器数量，同时新建两个数组，对每个位置的服务器，将该服务器对应的行和列数组 + 1 操作。第二次遍历遇到服务器，判断该服务器所在的行和列是不是仅有一个服务器，如果是，则结果 - 1。

代码：C++

 1 class Solution {
 2 public:
 3     int countServers(vector<vector<int>>& grid) {
 4         int m = grid.size();
 5         int n = grid[0].size();
 6         vector<int> row(m,0);
 7         vector<int> col(n,0);
 8         int cnt = 0;
 9         for(int i = 0; i < m; ++i){
10             for(int j = 0; j < n; ++j){
11                 if(grid[i][j] == 1){
12                     cnt++;
13                     row[i]++;
14                     col[j]++;
15                 }
16             }
17         }
18         for(int i = 0; i < m; ++i){
19             for(int j = 0; j < n; ++j){
20                 if(grid[i][j] == 1 && row[i] == 1 && col[j] == 1){
21                     cnt--;
22                 }
23             }
24         }
25         return cnt;
26     }
27 };

2、统计二叉树中好节点的数目

题目：给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。

「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。

思路：广度优先遍历！

代码：C++

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10  * };
11  */
12 class Solution {
13 public:
14     int goodNodes(TreeNode* root) {
15         int res = 1;
16         queue<TreeNode*> que;
17         que.push(root);
18         while(!que.empty()){
19             TreeNode* node = que.front();
20             que.pop();
21             if(node->left){
22                 if(node->left->val >= node->val){
23                     res++;
24                 }
25                 node->left->val = max(node->val,node->left->val);
26                 que.push(node->left);
27             }
28             if(node->right){
29                 if(node->right->val >= node->val){
30                     res++;
31                 }
32                 node->right->val = max(node->val,node->right->val);
33                 que.push(node->right);
34             }
35         }
36         return res;
37     }
38 };

3、从两个数字数组里生成最小数字

题目：给你两个只包含 1 到 9 之间数字的数组 nums1 和 nums2 ，每个数组中的元素 互不相同 ，请你返回 最小 的数字，两个数组都 至少 包含这个数字的某个数位。

思路：模拟！

代码：C++

 1 class Solution {
 2 public:
 3     int minNumber(vector<int>& nums1, vector<int>& nums2) {
 4         int x = findmin(nums1);
 5         int y = findmin(nums2);
 6         int res = min(x * 10 + y, y * 10 + x);
 7         set<int> st;
 8         for(auto const& num : nums1){
 9             st.insert(num);
10         }
11         for(auto const& num : nums2){
12             if(st.find(num) != st.end()){
13                 res = min(res,num);
14             }
15         }
16         return res;
17     }   
18 private:
19     int findmin(vector<int>& nums){
20         int res = nums[0];
21         for(auto num : nums){
22             res = min(res,num);
23         }
24         return res;
25     }
26 };