从零开始算法之路 ---- 1042. 不邻接植花（others）

野性酷女 2024-04-17 21:48 27阅读 0赞

**前言**:小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）  
**题源:** 力扣(LeetCode）[https://leetcode-cn.com/problems/flower-planting-with-no-adjacent/][https_leetcode-cn.com_problems_flower-planting-with-no-adjacent]  
**题目描述:**  
有 N 个花园，按从 1 到 N 标记。在每个花园中，你打算种下四种花之一。

paths\[i\] = \[x, y\] 描述了花园 x 到花园 y 的双向路径。

另外，没有花园有 3 条以上的路径可以进入或者离开。

你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。

以数组形式返回选择的方案作为答案 answer，其中 answer\[i\] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1, 2, 3, 4 表示。保证存在答案。  
**思路：** 先把花园的邻接矩阵初始化，answer 即花园的种植种类数组初始化为 0，然后从第一个花园的开始，每一个花园的种类都从第一种(k=1)开始寻找,把种类去和当前花园的每一个邻接花园的种类比较，找到没有重复的种上即可。 **详情看代码**

##### C++ 版代码： #####

class Solution { 
    public:
        vector<int> gardenNoAdj(int N, vector<vector<int> >& paths) { 
            vector<int> answer(N,0);                      // 初始化选择的方案作都为 0
    		vector<vector<int> > vertexList(N);           // 定义 N 个花园的邻接矩阵 
    		for(int i = 0; i < paths.size(); i++){         // 初始化图发邻接矩阵
    		 	vertexList[paths[i][0] - 1].push_back(paths[i][1]); 
    		 	vertexList[paths[i][1] - 1].push_back(paths[i][0]);
    		} 
    		for(int i = 0; i < N; i++){                    // 从一个开始种 
    		 	for(int k = 1; k < 5; k++ ){  // 每一个花园的种类都要去所有邻接花园比较，直到找到没有相同的再种上去，即 flag = true 时 
    			    bool flag = true;                      // 定义标志位变量 
    		 		for(int j = 0; j < vertexList[i].size(); j++){ 			 	
    				 	if(answer[vertexList[i][j] - 1] == k){   // 如果当前种类已经被邻接花园种上，type + 1 
    				 	    flag = false;          // 此类花不可以种，已有邻接花园种上，break 之后寻找下一种 
    				 		break;
    					} 			 	
    			    }
    			    if(flag){       // 找到了可以种的花的种类，种植 
    			    	answer[i] = k; 	
    			    	break;
    				}
    			} 
    		} 
    		return answer;       
        }
    };

##### Java 版代码： #####

class Solution { 
        public int[] gardenNoAdj(int N, int[][] paths) { 
            int []answer = new int[N];               // 定义答案数组
            int [][]vertexList = new int[N][4];      // 定义邻接矩阵
            int index = 0;
            for(int i = 0; i < paths.length;  i++) {   // 初始化邻接矩阵
            	for(int j = 0; j < 4; j++) { 
            		if(vertexList[paths[i][0] - 1][j] == 0) { 
            			index = j;
            			break;     // 如果当前 i 花园的邻接花园个数 为 0
            		} 				
            	}
            	vertexList[paths[i][0] - 1][index] = paths[i][1];
            	for(int j = 0; j < 4; j++) { 
            		if(vertexList[paths[i][1] - 1][j] == 0) { 
            			index = j;
            			break;     // 如果当前 i 花园的邻接花园个数 为 0
            		} 				
            	}
            	vertexList[paths[i][1] - 1][index] = paths[i][0];
            }
            for(int i = 0; i < N; i++) { 
            	for(int k = 1; k < 5;k++) { 
            		boolean flag = true;              // 定义标志位
            		for(int j = 0; j < 4; j++) { 
            			if(vertexList[i][j] - 1 < 0) break;
            			if(answer[vertexList[i][j] - 1] == k) { 
            				flag = false;
            				break;
            			}
            		}
            		if(flag) { 
            			answer[i] = k;
            			break;
            		}
            	}
            }                
            return answer;
        }
    }

[https_leetcode-cn.com_problems_flower-planting-with-no-adjacent]: https://leetcode-cn.com/problems/flower-planting-with-no-adjacent//