547. 省份數量
題目
有
n
個城市，其中一些彼此相連，另一些沒有相連。如果城市
a
與城市
b
直接相連，且城市
b
與城市
c
直接相連，那麼城市
a
與城市
c
間接相連。
省份 是一組直接或間接相連的城市，組内不含其他沒有相連的城市。
給你一個
n x n
的矩陣
isConnected
，其中
isConnected[i][j] = 1
表示第
i
個城市和第
j
個城市直接相連，而
isConnected[i][j] = 0
表示二者不直接相連。
傳回矩陣中 省份 的數量。
示例 1：
輸入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
輸出：2
示例 2：
輸入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
輸出：3
提示：
-
1 <= n <= 200
-
n == isConnected.length
-
n == isConnected[i].length
-
isConnected[i][j]
1
-
isConnected[i][i] == 1
-
isConnected[i][j] == isConnected[j][i]
題解
class Solution {
public:
int SearchRoot(int root, vector<int>& preArr)
{
int tmp;
int son;
son = root;
// 尋找目前位置的根節點
while (root != preArr[root]) {
root = preArr[root];
}
// 路徑壓縮
while (son != root) {
tmp = preArr[son];
preArr[son] = root;
son = tmp;
}
return root;
}
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
if (n == 0) {
return 0;
}
vector<int> preArr(n);
for (int i = 0; i < n; ++i) {
preArr[i] = i;
}
for (int i = 0; i < isConnected.size(); ++i) {
for (int j = i + 1; j < n; ++j) {
if (isConnected[i][j] == 0) {
continue;
}
int rootI = SearchRoot(i, preArr);
int rootJ = SearchRoot(j, preArr);
if (rootI == rootJ) {
continue;
}
preArr[rootJ] = rootI;
}
}
int res = 0;
for (int i = 0; i < n; ++i) {
if (preArr[i] == i) {
res++;
}
}
return res;
}
};
684. 備援連接配接
題目
樹可以看成是一個連通且 無環 的 無向 圖。
給定往一棵
n
個節點 (節點值
1～n
) 的樹中添加一條邊後的圖。添加的邊的兩個頂點包含在
1
到
n
中間，且這條附加的邊不屬于樹中已存在的邊。圖的資訊記錄于長度為
n
的二維數組
edges
，
edges[i] = [ai, bi]
表示圖中在
ai
和
bi
之間存在一條邊。
請找出一條可以删去的邊，删除後可使得剩餘部分是一個有着
n
個節點的樹。如果有多個答案，則傳回數組
edges
中最後出現的邊。
示例 1：
輸入: edges = [[1,2], [1,3], [2,3]]
輸出: [2,3]
示例 2：
輸入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
輸出: [1,4]
提示:
-
n == edges.length
-
3 <= n <= 1000
-
edges[i].length == 2
-
1 <= ai < bi <= edges.length
-
ai != bi
-
edges
- 給定的圖是連通的
解答
#include <functional>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <string>
#include <deque>
#include <set>
using namespace std;
int SearchRoot(int root, vector<int>& preArr)
{
while (root != preArr[root]) {
root = preArr[root];
}
return root;
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
vector<int> preArr(n + 1);
for (int i = 0; i <= n; ++i) {
preArr[i] = i;
}
for (auto e : edges) {
int rootA = SearchRoot(e[0], preArr);
int rootB = SearchRoot(e[1], preArr);
if (rootA == rootB) {
return e;
}
preArr[rootB] = rootA;
}
return {};
}
int main()
{
vector<vector<int>> arr = {{1,4},{3,4},{1,3},{1,2},{4,5}};
//{{1, 2}, {1, 3}, {2, 3}};{{1,2}, {2,3}, {3,4}, {1,4}, {1,5}}
vector<int> res = findRedundantConnection(arr);
for (auto i : res) {
cout << i << " ";
}
cout<<endl;
return 0;
}
200. 島嶼數量
題目
難度中等1373收藏分享切換為英文接收動态回報
給你一個由
'1'
（陸地）和
'0'
（水）組成的的二維網格，請你計算網格中島嶼的數量。
島嶼總是被水包圍，并且每座島嶼隻能由水準方向和/或豎直方向上相鄰的陸地連接配接形成。
此外，你可以假設該網格的四條邊均被水包圍。
示例 1：
輸入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
輸出：1
示例 2：
輸入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
輸出：3
提示：
-
m == grid.length
-
n == grid[i].length
-
1 <= m, n <= 300
-
grid[i][j]
'0'
'1'
解答
class Solution {
public:
int SearchRoot(int root, vector<int>& preArr)
{
while (root != preArr[root]) {
root = preArr[root];
}
return root;
}
int numIslands(vector<vector<char>>& grid)
{
int m = grid.size();
int n = grid[0].size();
int numOfSpcace = 0;
vector<int> preArr(m * n, -1);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '0') {
numOfSpcace++;
}
preArr[i * n + j] = i * n + j;
}
}
vector<vector<int>> edges;
for (int i = 0; i < m; i++) {
for (int j = 1; j < n; j++) {
if (grid[i][j] == '1' && grid[i][j - 1] == '1') {
edges.push_back({i * n + j - 1, i * n + j});
}
}
}
for (int j = 0; j < n; j++) {
for (int i = 1; i < m; ++i) {
if(grid[i][j] == '1' && grid[i - 1][j] == '1') {
edges.push_back({(i - 1) * n + j, i * n + j});
}
}
}
//sort(edges.begin(), edges.end());
for (auto e : edges) {
int rootA = SearchRoot(e[0], preArr);
int rootB = SearchRoot(e[1], preArr);
if (rootA == rootB) {
continue;
}
preArr[rootA] = rootB;
}
// int dx[2] = {0, 1};
// int dy[2] = {1, 0};
// for (int i = 0; i < m; i++) {
// for (int j = 0; j < n; j++) {
// if (grid[i][j] == '0') {
// numOfSpcace++;
// continue;
// }
// for (int k = 0; k < 2; k++) {
// int ni = i + dx[k];
// int nj = j + dy[k];
// if (ni < m && nj < n && grid[ni][nj] == '1') {
// int rootOld = SearchRoot(i * n + j, preArr);
// int rootNew = SearchRoot(ni * n + nj, preArr);
// if (rootOld == rootNew) {
// continue;
// }
// preArr[rootNew] = rootOld;
// }
// }
// }
// }
int res = 0;
for (int i = 0; i < m * n; i++) {
if (preArr[i] == i) {
res++;
}
}
return res - numOfSpcace;
}
};
737. 句子的相似性||
題目
給定兩個句子
words1
,
words2
（每個用字元串數組表示），和一個相似單詞對的清單
pairs
，判斷是否兩個句子是相似的。
例如，當相似單詞對是
pairs = [["great", "fine"], ["acting","drama"], ["skills","talent"]]
的時候，
words1 = ["great", "acting", "skills"] 和 words2 = ["fine", "drama", "talent"]
是相似的。
注意相似關系是 具有 傳遞性的。
例如，如果
“great”
和
“fine”
是相似的，
“fine”
和
“good”
是相似的，則
“great”
和
“good”
是相似的。
而且，相似關系是具有對稱性的。
例如，
“great”
和
“fine”
是相似的相當于
“fine”
和
“great”
是相似的。
并且，一個單詞總是與其自身相似。
例如，句子
words1 = [“great”]
,
words2 = [“great”]
,
pairs = []
是相似的，盡管沒有輸入特定的相似單詞對。
最後，句子隻會在具有相同單詞個數的前提下才會相似。
是以一個句子
words1 = [“great”]
永遠不可能和句子
words2 = [“doubleplus”,“good”]
相似。
注：andwords1
的長度不會超過 1000。words2
pairs
的長度不會超過 2000。
每個
pairs[i]
的長度為 2。
每個
和words[i]
的長度範圍為 [1, 20]。pairs[i][j]
解題
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
string SearchRoot(string root, unordered_map<string, string>& preArr)
{
string son = root;
while (root != preArr[root]) {
root = preArr[root];
}
while (son != root) {
string tmp = preArr[son];
preArr[son] = root;
son = tmp;
}
return root;
}
bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<vector<string>>& pairs)
{
int words1Len = words1.size();
int words2Len = words2.size();
if (words1Len != words2Len) {
return false;
}
int pairsLen = pairs.size();
unordered_map<string, string> preArr;
for (auto pair : pairs) {
preArr[pair[0]] = pair[0];
preArr[pair[1]] = pair[1];
}
for (auto pair : pairs) {
string rootA = SearchRoot(pair[0], preArr);
string rootB = SearchRoot(pair[1], preArr);
if (rootA == rootB) {
continue;
}
preArr[rootA] = rootB;
}
for (int i = 0; i < words1Len; ++i) {
if (words1[i] != words2[i]) {
if (preArr[words1[i]] != preArr[words2[i]]) {
return false;
}
}
}
return true;
}
int main()
{
vector<string> w1 = {"great", "acting", "skillss"};
vector<string> w2 = {"fine", "drama", "talent"};
vector<vector<string>> pairs = {{"great", "fine"}, {"acting", "drama"}, {"skills", "talent"}};
if(areSentencesSimilarTwo(w1, w2, pairs)) {
cout<<"1"<<endl;
} else {
cout<<"2"<<endl;
}
return 0;
}
1102. 最高得分路徑
題目
給你一個
R
行
C
列的整數矩陣
A
。矩陣上的路徑從
[0,0]
開始，在
[R-1,C-1]
結束。
路徑沿四個基本方向（上、下、左、右）展開，從一個已通路單元格移動到任一相鄰的未通路單元格。
路徑的得分是該路徑上的 最小 值。例如，路徑
8 → 4 → 5 → 9
的值為
4
。
找出所有路徑中得分 最高 的那條路徑，傳回其 得分。
示例 1：
輸入：[[5,4,5],[1,2,6],[7,4,6]]
輸出：4
解釋：
得分最高的路徑用黃色突出顯示。
示例 2：
輸入：[[2,2,1,2,2,2],[1,2,2,2,1,2]]
輸出：2
示例 3：
輸入：[[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]
輸出：3
提示：
1.
1 <= R, C <= 100
2.
0 <= A[i][j] <= 10^9
解答
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
struct Point {
int x;
int y;
int val;
Point(int mx, int my, int mVal) : x(mx), y(my), val(mVal) {}
};
struct Cmp {
bool operator()(Point& a, Point& b)
{
return a.val < b.val; // 大頂堆
}
};
// 優先隊列BFS
int MaximumMinimumPath0(vector<vector<int>>& A)
{
int rows = A.size();
int cols = A[0].size();
int i = 0;
int j = 0;
int res = min(A[0][0], A[rows - 1][cols - 1]);
priority_queue<Point, vector<Point>, Cmp> q;
q.push(Point(i, j, A[j][j]));
vector<vector<bool>> visited(rows, vector<bool>(cols, false));
visited[0][0] = true;
vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.empty()) {
res = min(res, q.top().val);
i = q.top().x;
j = q.top().y;
q.pop();
if (i == rows - 1 && j == cols - 1) {
return res;
}
for (auto d : dir) {
int ni = i + d[0];
int nj = j + d[1];
if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && !visited[ni][nj]) {
q.push(Point(ni, nj, A[ni][nj]));
visited[ni][nj] = true;
}
}
}
return res;
}
// 二分查找
bool FindPath(vector<vector<int>>& A, vector<vector<bool>> visited, int i, int j, int val)
{
vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
visited[i][j] = true;
if (i == A.size() - 1 && j == A[0].size() - 1) {
return true;
}
for (auto &d : dir) {
int x = i + d[0];
int y = j + d[1];
if (x >= 0 && x < A.size() && y >= 0 && y < A[0].size() && !visited[x][y] && A[x][y] >= val) {
if (FindPath(A, visited, x, y, val)) {
return true;
}
}
}
return false;
}
int MaximumMinimumPath1(vector<vector<int>>& A)
{
int m = A.size();
int n = A[0].size();
int l = 0;
int r = min(A[0][0], A[m - 1][n - 1]);
int res = r;
while (l <= r) {
vector<vector<bool>> visited(m, vector<bool>(n, false));
int midVal = l + (r - l) / 2;
if (FindPath(A, visited, 0, 0, midVal)) {
res = midVal;
l = midVal + 1;
} else {
r = midVal - 1;
}
}
return res;
}
// 并查集
bool Cmp(Point& a, Point& b)
{
return a.val > b.val;
}
int FindRoot(int root, vector<int>& preArr)
{
while (root != preArr[root]) {
root = preArr[root];
}
return root;
}
void UnionRoot(int x, int y, vector<int>& preArr)
{
int root1 = FindRoot(x, preArr);
int root2 = FindRoot(y, preArr);
if (root1 != root2) {
preArr[root1] = root2;
}
}
int MaximumMinimumPath(vector<vector<int>>& A)
{
int m = A.size();
int n = A[0].size();
vector<int> preArr(m * n, 0);
vector<Point> pointVec;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
preArr[i * n + j] = i * n + j;
pointVec.push_back(Point(i, j, A[i][j]));
}
}
int res = min(A[0][0], A[m - 1][n - 1]);
// 按照得分，從大到小排序，非常重要
sort(pointVec.begin(), pointVec.end(), Cmp);
vector<vector<bool>> visited(m, vector<bool>(n, false));
visited[0][0] = true;
visited[m - 1][n - 1] = true;
vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int bId = 0;
int eId = m * n - 1;
for (auto p : pointVec) {
res = min(res, p.val);
int x = p.x;
int y = p.y;
int rootIndex = x * n + y;
visited[x][y] = true;
for (auto &d : dir) {
int nx = x + d[0];
int ny = y + d[1];
// 找到大的已經通路過的
if (nx >= 0 && nx < m && ny >= 0 && ny < n && visited[nx][ny]) {
int rootNIndex = nx * n + ny;
UnionRoot(rootIndex, rootNIndex, preArr);
}
}
if (FindRoot(bId, preArr) == FindRoot(eId, preArr)) {
break;
}
}
return res;
}
int main()
{
vector<vector<int>> arr = {{5, 4, 5}, {1, 2, 6}, {7, 4, 6}};
cout<<MaximumMinimumPath(arr)<<endl;
return 0;
}
1135. 最低成本聯通所有城市
題目
想象一下你是個城市基建規劃者，地圖上有
N
座城市，它們按以
1
到
N
的次序編号。
給你一些可連接配接的選項
conections
，其中每個選項
conections[i] = [city1, city2, cost]
表示将城市
city1
和城市
city2
連接配接所要的成本。（連接配接是雙向的，也就是說城市
city1
和城市
city2
相連也同樣意味着城市
city2
和城市
city1
相連）。
傳回使得每對城市間都存在将它們連接配接在一起的連通路徑（可能長度為 1 的）最小成本。該最小成本應該是所用全部連接配接代價的綜合。如果根據已知條件無法完成該項任務，則請你傳回 -1。
示例 1：
輸入：N = 3, conections = [[1,2,5],[1,3,6],[2,3,1]]
輸出：6
解釋：
選出任意 2 條邊都可以連接配接所有城市，我們從中選取成本最小的 2 條。
示例 2：
輸入：N = 4, conections = [[1,2,3],[3,4,4]]
輸出：-1
解釋：
即使連通所有的邊，也無法連接配接所有城市。
提示：
-
1 <= N <= 10000
-
1 <= conections.length <= 10000
-
1 <= conections[i][0], conections[i][1] <= N
-
0 <= conections[i][2] <= 10^5
-
conections[i][0] != conections[i][1]
題解
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
struct Connection {
int A;
int B;
int cost;
Connection(int mA, int mB, int mC) : A(mA), B(mB), cost(mC) {}
};
bool Cmp(Connection &A, Connection &B)
{
return A.cost < B.cost;
}
int FindRoot(int root, vector<int>& preArr)
{
while (root != preArr[root]) {
root = preArr[root];
}
return root;
}
void UnionRoot(int a, int b, vector<int>& preArr)
{
int rootA = FindRoot(a, preArr);
int rootB = FindRoot(b, preArr);
if (rootA != rootB) {
preArr[rootB] = rootA;
}
}
int minimumCost(int N, vector<vector<int>>& connections) {
int n = connections.size();
if (n < N - 1) {
return -1;
}
vector<int> preArr(N + 1, 0);
for (int i = 1; i <= N; i++) {
preArr[i] = i;
}
vector<Connection> conVec;
for (auto &c : connections) {
conVec.push_back(Connection(c[0], c[1], c[2]));
}
sort(conVec.begin(), conVec.end(), Cmp);
vector<bool> visited(N + 1, false);
int res = 0;
for (auto c : conVec) {
if (visited[c.A] && visited[c.B] && FindRoot(c.A, preArr) == FindRoot(c.B, preArr)) {
continue;
}
visited[c.A] = true;
visited[c.B] = true;
res += c.cost;
UnionRoot(c.A, c.B, preArr);
}
int rootVal = FindRoot(1, preArr);
for (int i = 2; i <= N; ++i) {
if (rootVal != FindRoot(i, preArr)) {
return -1;
}
}
return res;
}
int main()
{
vector<vector<int>> arr = {{1,2,5},{1,3,6},{2,3,1}};
cout << minimumCost(3, arr) << endl;
return 0;
}
class Solution {
private:
vector<int> fatherMap;
vector<int> sizeMap;
int getFather(int a){
int fa = fatherMap[a];
if(fa != a) fa = getFather(fa);
// 把并查集變扁平
fatherMap[a] = fa;
return fa;
}
int merge(int a, int b){
// 确認兩個點為父節點，并且不相連
int fa = getFather(a), fb = getFather(b);
if(fa == fb) return sizeMap[fa];
if(sizeMap[fa] > sizeMap[fb]) {
// 當 b 所在的并查集元素較小時， 把 b 指向 a 所在的并查集
sizeMap[fa] += sizeMap[fb];
fatherMap[fb] = fa;
}
else {
sizeMap[fb] += sizeMap[fa];
fatherMap[fa] = fb;
}
return max(sizeMap[fa], sizeMap[fb]);
}
public:
int minimumCost(int N, vector<vector<int>>& conections) {
if(N == 1) return 0;
// 若城市個數大于 連接配接個數 + 1 不可能聯通
if(N > conections.size() + 1) return -1;
// 初始化并查集
fatherMap.resize(N), sizeMap.resize(N);
for(int i=0; i<N; i++) {
fatherMap[i] = i;
sizeMap[i] = 1;
}
int res = 0, total = 0;
// 按照每條連接配接的權重排序
sort(conections.begin(), conections.end(),
[](vector<int>& a, vector<int>& b){ return a[2] < b[2]; });
for(int i=0; i<conections.size(); i++){
int fa = getFather(conections[i][0]-1), fb = getFather(conections[i][1]-1);
// 已經屬于一個并查集了，不需要加入此連接配接
if(fa == fb) continue;
total = merge(fa, fb);
// 加上目前權重
res += conections[i][2];
// 通過傳回值，可以提前終止疊代過程
if(total == N) return res;
}
return -1;
}
};
261. 以圖辨樹
題目
解答
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
int FindRoot(int root, vector<int>& preArr)
{
while (root != preArr[root]) {
root = preArr[root];
}
return root;
}
void UnionRoot(int a, int b, vector<int>& preArr)
{
int rootA = FindRoot(a, preArr);
int rootB = FindRoot(b, preArr);
if (rootA != rootB) {
preArr[rootB] = rootA;
}
}
bool validTree(int n, vector<vector<int>>& edges)
{
int len = edges.size();
if (len != n - 1) {
return false;
}
if (len == 0 && n == 1) {
return true;
}
vector<int> preArr(n, 0);
for (int i = 0; i < n; i++) {
preArr[i] = i;
}
vector<bool> used(n, false);
for (auto &e : edges) {
if (used[e[0]] && used[e[1]] && preArr[e[0]] == preArr[e[1]]) {
return false;
}
used[e[0]] = true;
used[e[1]] = true;
UnionRoot(e[0], e[1], preArr);
}
int rootVal = FindRoot(0, preArr);
for (int i = 1; i < n; i++) {
if (FindRoot(i, preArr) != rootVal) {
return false;
}
}
return true;
}
int main()
{
vector<vector<int>> arr = {{0,1}, {1, 2}, {2,3},{1,3}, {1,4}};
if(validTree(5, arr)) {
cout<<"1"<<endl;
} else {
cout<<"0"<<endl;
}
return 0;
}
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
int FindRoot(int root, vector<int>& preArr)
{
while (root != preArr[root]) {
root = preArr[root];
}
return root;
}
void UnionRoot(int a, int b, vector<int>& preArr)
{
int rootA = FindRoot(a, preArr);
int rootB = FindRoot(b, preArr);
if (rootA != rootB) {
preArr[rootB] = rootA;
}
}
bool validTree0(int n, vector<vector<int>>& edges)
{
int len = edges.size();
if (len != n - 1) {
return false;
}
if (len == 0 && n == 1) {
return true;
}
vector<int> preArr(n, 0);
for (int i = 0; i < n; i++) {
preArr[i] = i;
}
vector<bool> used(n, false);
for (auto &e : edges) {
if (used[e[0]] && used[e[1]] && preArr[e[0]] == preArr[e[1]]) {
return false;
}
used[e[0]] = true;
used[e[1]] = true;
UnionRoot(e[0], e[1], preArr);
}
int rootVal = FindRoot(0, preArr);
for (int i = 1; i < n; i++) {
if (FindRoot(i, preArr) != rootVal) {
return false;
}
}
return true;
}
bool validTree(int n, vector<vector<int>>& edges)
{
int len = edges.size();
if (len != n - 1) {
return false;
}
if (len == 0 && n == 1) {
return true;
}
vector<int> preArr(n, 0);
for (int i = 0; i < n; i++) {
preArr[i] = i;
}
vector<bool> used(n, false);
for (auto &e : edges) {
int rootA = FindRoot(e[0], preArr);
int rootB = FindRoot(e[1], preArr);
if (rootA == rootB) {
return false;
}
if (e[0] < e[1]) {
preArr[e[1]] = rootA;
} else {
preArr[e[0]] = rootB;
}
}
return true;
}
int main()
{
vector<vector<int>> arr = {{0,1}, {1, 2}, {2,3},{1,3}, {1,4}};
if(validTree(5, arr)) {
cout<<"1"<<endl;
} else {
cout<<"0"<<endl;
}
return 0;
}
1061. 按字典序排列最小的等效字元串
題目
解答
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
unordered_map<char, char> mp;
char FindRoot(char ch)
{
char son = ch;
while (mp[ch] != ch) {
ch = mp[ch];
}
while (son != ch) {
char tmp = mp[son];
mp[son] = ch;
son = tmp;
}
return ch;
}
void UnionRoot(char ch1, char ch2)
{
char root1 = FindRoot(ch1);
char root2 = FindRoot(ch2);
if (root1 != root2) {
if (root1 < root2) {
mp[root2] = root1;
} else {
mp[root1] = root2;
}
}
}
string smallestEquivalentString(string A, string B, string S)
{
int sizeA = A.size();
int sizeB = B.size();
if (sizeA != sizeB) {
return "";
}
for (int i = 0; i < sizeA; ++i) {
if (A[i] > B[i]) {
mp[B[i]] = B[i];
mp[A[i]] = B[i];
} else if (A[i] < B[i]) {
mp[A[i]] = A[i];
mp[B[i]] = A[i];
} else {
mp[A[i]] = A[i];
mp[B[i]] = B[i];
}
}
for (int i = 0; i < sizeA; ++i) {
UnionRoot(A[i], B[i]);
}
for (int i = 0; i < S.size(); ++i) {
if (mp.find(S[i]) != mp.end()) {
S[i] = mp[S[i]];
}
}
return S;
}
int main()
{
string s1 = "leetcode";//"parker";//"hello";
string s2 = "programs";//"morris";//"world";
string s3 = "sourcecode";//"parser";//"hold";
cout<<smallestEquivalentString(s1, s2, s3)<<endl;
return 0;
}
323. 無向圖中連通分量的數目
題目
給定編号從 0 到 n-1 的 n 個節點和一個無向邊清單（每條邊都是一對節點），請編寫一個函數來計算無向圖中連通分量的數目。
示例 1:
輸入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]]
0 ********3
|**********|
1 — 2 ** 4
輸出: 2
示例 2:
輸入: n = 5 和 edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
0 *********4
| **********|
1 — 2 — 3
輸出: 1
-
注意:
你可以假設在 edges 中不會出現重複的邊。而且由于是以的邊都是無向邊，[0, 1] 與 [1, 0] 相同，是以它們不會同時在 edges 中出現。
解答
#include <iostream>
#include <vector>
using namespace std;
int FindRoot(int root, vector<int>& preArr)
{
int son = root;
while (root != preArr[root]) {
root = preArr[root];
}
while (son != root) {
int tmp = preArr[son];
preArr[son] = root;
son = tmp;
}
return root;
}
int countComponents(int n, vector<vector<int>>& edges)
{
vector<int> preArr(n, 0);
for (int i = 0; i < n; ++i) {
preArr[i] = i;
}
for (auto &e : edges) {
int root1 = FindRoot(e[0], preArr);
int root2 = FindRoot(e[1], preArr);
if (root1 == root2) {
continue;
}
preArr[root2] = root1;
}
int res = 0;
for (int i = 0; i < n; ++i) {
if (preArr[i] == i) {
res++;
}
}
return res;
}
int main()
{
vector<vector<int>> arr= {{0, 1}, {1, 2}, {2, 3}, {3, 4}};// {{0, 1}, {1, 2}, {3, 4}};
cout<<countComponents(5, arr)<<endl;
return 0;
}
924. 盡量減少惡意軟體的傳播
題目
難度困難63收藏分享切換為英文接收動态回報
在節點網絡中，隻有當
graph[i][j] = 1
時，每個節點
i
能夠直接連接配接到另一個節點
j
。
一些節點
initial
最初被惡意軟體感染。隻要兩個節點直接連接配接，且其中至少一個節點受到惡意軟體的感染，那麼兩個節點都将被惡意軟體感染。這種惡意軟體的傳播将繼續，直到沒有更多的節點可以被這種方式感染。
假設
M(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
提示：
-
1 < graph.length = graph[0].length <= 300
-
0 <= graph[i][j] == graph[j][i] <= 1
-
graph[i][i] == 1
-
1 <= initial.length < graph.length
-
0 <= initial[i] < graph.length
解答
/**
* 從初始清單中删除一個節點。如果移除這一節點将最小化 M(initial),則傳回該節點
* 解題思路 [閱讀了解]
* 1、了解題意：題目描述很不易了解,首先了解輸入graph、initial; 輸出 求初始清單中的一個節點,移除這一節點将最小化感染
* a. 輸入graph表示每個節點與其他節點的聯通情況,以題目中示例一舉例 graph = [[1,1,0],[1,1,0],[0,0,1]] 圖如下圖
* nodeId 0 1 2
* ————|————————————
* graph = 0 | 1, 1, 0
* 1 | 1, 1, 0
* 2 | 0, 0, 1
* 表示有三個節點,節點序号分别為 0,1,2.在節點網絡中，隻有當 graph[i][j] = 1 時，每個節點 i 能夠直接連接配接到另一個節點 j
* 比如 0号節點可以與 1、2号節點有聯通關系,那麼 0 号節點與 1 号節點聯通則可以表示為 graph[0][1] = 1;
* 0 号節點與 2 号節點不聯通則可以表示為 graph[0][2] = 0;
* 節點自身與自身是聯通的,也就是圖中 graph[0][0] == graph[1][1] == graph[2][2] == 1
* 那麼 graph 畫圖表示為下圖, 0 與 1 相連, 沒有節點與 2 相連
* 0
* /
* 1 2
* b. 輸入initial表示初始被感染的節點,以題目中示例一舉例 initial = [0,1] 表示一開始 0号節點與1号節點被感染了
* c. 輸出 求初始清單中的一個節點,移除這一節點将最小化感染,注意這裡“移除”的真正含義是,把該節點設定為未感染狀态,
* 以題目中示例一舉例,初始狀态0、1被感染,那麼我們不論移除0還是移除1,兩個節點都會被感染,因為0 和 1 是聯通的,移除一個後會被另一個重新傳染,
* 要注意題目中最後一句話,“某個節點已從受感染節點的清單 initial 中删除，它以後可能仍然因惡意軟體傳播而受到感染。”
* d. 題目中其他條件了解，“如果有多個節點滿足條件，就傳回索引最小的節點”,還是以題目中示例一舉例,我們知道從 輸入initial
* 初始狀态0、1被感染,那麼我們不論移除0還是移除1,兩個節點都會被感染
* 也就是移除 0 後感染的節點為 0(被1傳染),1
* 也就是移除 1 後感染的節點為 0,1(被0傳染)
* 這種情況下,我們直接傳回 索引最小的節點 0,注意這兒的索引隻的是節點的索引
* 上述就是對題意的了解,搞清楚題意後再去看官方解題思路便豁然開朗
*
*
* @param graph 節點網絡
* @param initial 最初被惡意軟體感染的節點
* @return 将最小化 M(initial)的節點
*/
class Solution {
public:
int FindRoot(int root, vector<int>& preArr)
{
while (root != preArr[root]) {
root = preArr[root];
}
return root;
}
void MergeRoot(int x, int y, vector<int>& preArr, vector<int>& size)
{
int rootX = FindRoot(x, preArr);
int rootY = FindRoot(y, preArr);
if (rootX == rootY) {
return;
}
if (size[rootX] < size[rootY]) {
swap(rootX, rootY);
}
preArr[rootY] = rootX;
size[rootX] += size[rootY];
}
int GetSize(int x, vector<int>& preArr, vector<int>& size)
{
return size[FindRoot(x, preArr)];
}
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int n = graph.size();
vector<int> preArr(n, 0);
vector<int> size(n, 1);
for (int i = 0; i < n; ++i) {
preArr[i] = i;
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (graph[i][j] == 1) {
MergeRoot(i, j, preArr, size);
}
}
}
vector<int> cnt(n, 0);
for (auto i : initial) {
cnt[FindRoot(i, preArr)]++;
}
// 大于1的話，删哪個都會被再次感染
int res = INT_MAX;
int resSize = -1;
for (int i : initial) {
int tmp = FindRoot(i, preArr);
if (cnt[tmp] == 1) {
int coverSize = GetSize(tmp, preArr, size);
if (coverSize > resSize || (coverSize == resSize && tmp < res)) {
resSize = coverSize;
res = i;
}
}
}
if (res == INT_MAX) {
for (auto i : initial) {
res = min(res, i);
}
}
return res;
}
};