当前位置:网站首页>May brush question 26 - concurrent search
May brush question 26 - concurrent search
2022-07-06 09:38:00 【A Guang chasing dreams】
May brush questions 26—— Union checking set
Today's brush topic content : Union checking set
Preface
- An algorithm opens the way to brush the questions of waste materials , Update the problem solution content of the problem brush every day
- Focus on personal understanding , Look at the difficulty and update the number of questions
- The title comes from Li Kou
- New column , Try to work out at least one question every day =v=
- Language java、python、c\c++
One 、 Today's topic
I only finished one question today , There's not much time left , Make up the rest another day
- 990. The satisfiability of equation
- 1319. The number of connected network operations
- 886. Possible dichotomy
Two 、 Their thinking
1. 990. The satisfiability of equation
- Use and search set to put all
==
The characters of fall into one category- lookup
!=
Whether the characters of belong to the same class- If existence belongs to a class , It shows that these two characters already belong to the equation , return
false
, Otherwisetrue
class Solution {
int N = 256;
int[] fset;
// Initialize and query set , Use characters to store
public void init(){
fset = new int[N];
for(int i=0; i < N; i++){
fset[i] = i;
}
}
// Find which set it belongs to
public int find(int x){
if (x == fset[x]){
return x;
}else{
// Set the parent node of the nodes along the way as the root node
fset[x] = find(fset[x]);
return fset[x];
}
}
// Merge sets
public boolean merge(int x, int y){
int rx = find(x);
int ry = find(y);
if (rx != ry){
fset[rx] = ry;
return false;
}
return true;
}
public boolean equationsPossible(String[] equations) {
int n = equations.length;
init();
// Merge two characters equally into a set
for (String e: equations){
if (e.charAt(1) == '='){
merge(e.charAt(0), e.charAt(3));
}
}
// If these two characters are already in the same set , It also appears in the equation !, The explanation must be false
for(String e: equations){
if (e.charAt(1) == '!'){
if ( find(e.charAt(0)) == find(e.charAt(3)) ){
return false;
}
}
}
return true;
}
}
/* * Use and look up sets , Only when all equations belong to a set can the problem condition be satisfied */
2. 1319. The number of connected network operations
Adopt simple method and path compression to solve the problem
Path compression and search set related view this article Union checking set
- This question , Using the simple method of searching sets
- Combine all connected computers
- Counting the number of all sets , Count all sets -1 That's the answer.
The simple code is as follows :
class Solution {
int[] fset;
int N;
/* * Initialize and query set */
public void init(int n){
fset = new int[n];
int i;
for(i = 0; i < n; i++){
fset[i] = i;
}
}
/* * lookup x Which set does it belong to */
public int find(int x){
return fset[x];
}
/* * Merge two sets */
public void merge(int x, int y){
int rx = find(x);
int ry = find(y);
// Find the set to which they belong , If different sets , Then merge the two
if (rx != ry){
for (int i = 0; i < N; i++){
if (fset[i] == ry){
fset[i] = rx;
}
}
}
}
public int makeConnected(int n, int[][] connections) {
int m = connections.length;
int i;
N = n;
if(m < n - 1){
return - 1; // n Computers , Need at least n-1 Cables
}
init(n); // initialization
int count = 0;
int[] hash = new int[n];
for(int[] nums: connections){
merge(nums[0], nums[1]); // Merge two connected computers
}
for(i = 0 ; i < n; i++){
int setId = find(i);
if (hash[setId] == 0){
hash[setId]++;
count++;
}
}
return count - 1;
// System.out.println(fset[3]);
}
}
/* n Computers , Need at least n-1 Table cable Calculate the number of computers belonging to the same set Finding out the number of independent computers that do not belong to a set is the answer */
The path compression code is as follows :
class Solution {
int[] fset;
int N;
/* * Initialize and query set */
public void init(int n){
fset = new int[n];
int i;
for(i = 0; i < n; i++){
fset[i] = i;
}
}
/* * lookup x Which set does it belong to , And set the parent nodes of the points on the path to rx */
public int find(int x){
if (x == fset[x]){
return x;
}else{
fset[x] = find(fset[x]);
return fset[x];
}
}
/* * Merge two sets ??? */
public boolean merge(int x, int y){
int rx = find(x);
int ry = find(y);
// Find the set to which they belong , If different sets , Then merge the two
if (rx != ry){
fset[rx] = ry;
return true;
}
return false;
}
public int makeConnected(int n, int[][] connections) {
int m = connections.length;
int i;
N = n;
if(m < n - 1){
return - 1; // n Computers , Need at least n-1 Cables
}
init(n); // initialization
int count = 0;
int[] hash = new int[n];
for(int[] nums: connections){
merge(nums[0], nums[1]); // Merge two connected computers
}
for(i = 0 ; i < n; i++){
int setId = find(i);
if (hash[setId] == 0){
hash[setId]++;
count++;
}
}
return count - 1;
// System.out.println(fset[3]);
}
}
/* n Computers , Need at least n-1 Table cable Calculate the number of computers belonging to the same set Finding out the number of independent computers that do not belong to a set is the answer */
3. 886. Possible dichotomy
边栏推荐
- 068.查找插入位置--二分查找
- [shell script] - archive file script
- QML control type: Popup
- Global and Chinese market of appointment reminder software 2022-2028: Research Report on technology, participants, trends, market size and share
- Scoped in webrtc_ refptr
- [Chongqing Guangdong education] reference materials for nine lectures on the essence of Marxist Philosophy in Wuhan University
- Master slave replication of redis
- QML control type: menu
- 【深度學習】語義分割-源代碼匯總
- Kratos ares microservice framework (I)
猜你喜欢
Workflow - activiti7 environment setup
Mapreduce实例(九):Reduce端join
Mapreduce实例(八):Map端join
Mapreduce实例(十):ChainMapReduce
【深度学习】语义分割-源代码汇总
小白带你重游Spark生态圈!
Redis geospatial
Redis之连接redis服务命令
Sqlmap installation tutorial and problem explanation under Windows Environment -- "sqlmap installation | CSDN creation punch in"
Mapreduce实例(七):单表join
随机推荐
Redis之五大基础数据结构深入、应用场景
Global and Chinese market of bank smart cards 2022-2028: Research Report on technology, participants, trends, market size and share
MapReduce instance (VII): single table join
Redis之Bitmap
Blue Bridge Cup_ Single chip microcomputer_ Measure the frequency of 555
Why data Tiering
CSP student queue
面渣逆袭:Redis连环五十二问,图文详解,这下面试稳了
解决小文件处过多
The five basic data structures of redis are in-depth and application scenarios
Parameterization of postman
Mapreduce实例(九):Reduce端join
MapReduce instance (VI): inverted index
Design and implementation of online snack sales system based on b/s (attached: source code paper SQL file)
YARN组织架构
Meituan Er Mian: why does redis have sentinels?
Full stack development of quartz distributed timed task scheduling cluster
Global and Chinese market of linear regulators 2022-2028: Research Report on technology, participants, trends, market size and share
Le modèle sentinelle de redis
Kratos ares microservice framework (I)