左云算法2

谁借莪１个温暖的怀抱￠ 2022-09-05 12:37 71阅读 0赞

# 6.并查集 #

**1. 判断两个集合是否属于同一集合  
2. 合并两个结合**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 2]

首次生成3张map 表

//包装集合
    		public HashMap<V, Node<V>> nodes;
    		//记录本集合下所有节点对应的父节点，即谁的父亲是谁
    		public HashMap<Node<V>, Node<V>> parents;
    		//记录本集合的大小，父亲节点和其下面挂了节点个数。
    		//只是父亲节点的时候才会记录到sizeMap中
    		public HashMap<Node<V>, Integer> sizeMap;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 3]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 4]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 7]

查找父亲节点

Stack<Node<V>> path = new Stack<>();
    			//自己指向自己即为代表节点
    			//找到代表节点
    			while (cur != parents.get(cur)) { 
    				path.push(cur);
    				cur = parents.get(cur);
    			}

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 8]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 9]

//合并两个集合
    		public void union(V a, V b) { 
    			Node<V> aHead = findFather(nodes.get(a));
    			Node<V> bHead = findFather(nodes.get(b));
    			if (aHead != bHead) { 
    				int aSetSize = sizeMap.get(aHead);
    				int bSetSize = sizeMap.get(bHead);
    				//大小集合重定向
    				Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
    				Node<V> small = big == aHead ? bHead : aHead;
    				//小集合的代表节点指向大集合的代表节点
    				parents.put(small, big);
    				sizeMap.put(big, aSetSize + bSetSize);
    				//删除小的节点大小
    				sizeMap.remove(small);
    			}
    		}

//大小集合重定向
    				Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
    				Node<V> small = big == aHead ? bHead : aHead;
    				//小集合的代表节点指向大集合的代表节点
    				parents.put(small, big);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 10]

package class14;
    package class14;
    
    import java.util.HashMap;
    import java.util.List;
    import java.util.Stack;
    
    public class Code05_UnionFind { 
    
    	public static class Node<V> { 
    		V value;
    
    		public Node(V v) { 
    			value = v;
    		}
    	}
    
    	public static class UnionFind<V> { 
    		//包装集合
    		public HashMap<V, Node<V>> nodes;
    		//记录本集合下所有节点对应的父节点，即谁的父亲是谁
    		public HashMap<Node<V>, Node<V>> parents;
    		//记录本集合的大小，父亲节点和其下面挂了节点个数。
    		//只是父亲节点的时候才会记录到sizeMap中
    		public HashMap<Node<V>, Integer> sizeMap;
    
    		public UnionFind(List<V> values) { 
    			nodes = new HashMap<>();
    			parents = new HashMap<>();
    			sizeMap = new HashMap<>();
    			for (V cur : values) { 
    				Node<V> node = new Node<>(cur);
    				nodes.put(cur, node);
    				//开始都是自己指向自己
    				parents.put(node, node);
    				//开始都是都是代表节点，大小为1
    				sizeMap.put(node, 1);
    			}
    		}
    
    		// 给你一个节点，请你往上到不能再往上，把代表返回
    		//找到给定节点的代表节点
    		public Node<V> findFather(Node<V> cur) { 
    			Stack<Node<V>> path = new Stack<>();
    			//自己指向自己即为代表节点
    			//找到代表节点
    			while (cur != parents.get(cur)) { 
    				path.push(cur);
    				cur = parents.get(cur);
    			}
    			//每次返回之前做一次优化，把集合中，中间小的父节点直接指向最上面大的父亲节点，方便下此快速查找
    			while (!path.isEmpty()) { 
    				parents.put(path.pop(), cur);
    			}
    			return cur;
    		}
    
    		//判断是否在一个集合
    		//核心判断两个集合代表节点是否相等，相等则是否属于同一个集合
    		public boolean isSameSet(V a, V b) { 
    			return findFather(nodes.get(a)) == findFather(nodes.get(b));
    		}
    
    		//合并两个集合
    		public void union(V a, V b) { 
    			Node<V> aHead = findFather(nodes.get(a));
    			Node<V> bHead = findFather(nodes.get(b));
    			if (aHead != bHead) { 
    				int aSetSize = sizeMap.get(aHead);
    				int bSetSize = sizeMap.get(bHead);
    				//大小集合重定向
    				Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
    				Node<V> small = big == aHead ? bHead : aHead;
    				//小集合的代表节点指向大集合的代表节点
    				parents.put(small, big);
    				sizeMap.put(big, aSetSize + bSetSize);
    				//删除小的节点大小
    				//合并small不再是父亲节点，要从sizeMap中删掉
    				sizeMap.remove(small);
    			}
    		}
    
    		public int sets() { 
    			return sizeMap.size();
    		}
    
    	}
    }

# 7.贪心算法 #

局部最优解，是否也是全局最优解  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 11]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 12]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70]: /images/20220829/d264da70cd544e10b5a589b67ac8585a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 1]: /images/20220829/bfc47071acde44538b2b6b9dbd01799e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 2]: /images/20220829/1828a23f3f6d420a97ed3c3a8977531f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 3]: /images/20220829/69398bef6c9841a28907d492f655050a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 4]: /images/20220829/8f932881f5be4844a9230595e1134be7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 5]: /images/20220829/8b72f7effc1a4fdab8f7a75a21554e18.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 6]: /images/20220829/7a993df8cede4e2ba737c91c5708e3ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 7]: /images/20220829/773fc0ba6b404f56a84acdf7fa84e8e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 8]: /images/20220829/cdbfb07ef2784a8aaa350a3c32012034.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 9]: /images/20220829/1493ef3ede1443dca02a050601824ba0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 10]: /images/20220829/d56a7bcb7c274b8998dc2bcdeb294966.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 11]: /images/20220829/605e3e8921c0448ca0c41d1c3f85ac19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmdzaGVuZ3dlaTIzMDYxMg_size_16_color_FFFFFF_t_70 12]: /images/20220829/fad79785f365400384dc515da4585444.png