不邻接植花

1042. 不邻接植花

有 n 个花园，按从 1 到 n 标记。另有数组 paths ，其中 paths[i] = [x_i, y_i] 描述了花园 x_i 到花园 y_i 的双向路径。在每个花园中，你打算种下四种花之一。

另外，所有花园最多有 3 条路径可以进入或离开.

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

以数组形式返回任一可行的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1、2、3、4 表示。保证存在答案。

示例 1：

输入：n = 3, paths = [[1,2],[2,3],[3,1]]
输出：[1,2,3]
解释：
花园 1 和 2 花的种类不同。
花园 2 和 3 花的种类不同。
花园 3 和 1 花的种类不同。
因此，[1,2,3] 是一个满足题意的答案。其他满足题意的答案有 [1,2,4]、[1,4,2] 和 [3,2,1]

示例 2：

输入：n = 4, paths = [[1,2],[3,4]]
输出：[1,2,1,2]

示例 3：

输入：n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
输出：[1,2,3,4]

提示：

1 <= n <= 10⁴
0 <= paths.length <= 2 * 10⁴
paths[i].length == 2
1 <= x_i, y_i <= n
x_i != y_i
每个花园最多有 3 条路径可以进入或离开

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) { } };

python3 解法, 执行用时: 108 ms, 内存消耗: 19.6 MB, 提交时间: 2022-12-10 22:52:44

class Solution:
    def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
        
        result = [0 for x in range(N+1)]
        path_map = [[] for x in range(N+1)]
        
        #构建地图
        for num in paths:
            path_map[num[0]].append(num[1])
            path_map[num[1]].append(num[0])
        s = set() #存储该花园相邻的花园种植的花
        for i in range(1,N+1):
            s.clear()
            for j in path_map[i]:
                if( j < i):
                    s.add(result[j])
            for j in range(1,5):
                if(j not in s):
                    count = j
                    break
            result[i] = count

        return result[1:]

python3 解法, 执行用时: 148 ms, 内存消耗: 19.9 MB, 提交时间: 2022-12-10 22:51:58

'''
1、将所有的path转换为dict，key为'1'-'N'，value为'1'-'N'对应的路径；
2、将1的颜色置为1，从2开始遍历dict；
3、每一次遍历，新建一个颜色集合（[1,2,3,4]），取出key对应的花园代号，遍历代号。
如果该代号花园已经有颜色了，取出其颜色，从颜色集合中去掉；如果该花园没有颜色，跳过；
全部代号遍历结束后，取颜色集合第一个颜色作为当前key 的颜色，存入结果中；
4、反复计算更新结果，最后输出结果；
'''
class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        recorder = {}
        for i in range(1, n+1, 1):
            recorder[str(i)] = []

        for path in paths:
            recorder[str(path[0])].append(path[1])
            recorder[str(path[1])].append(path[0])

        result = [1]
        for i in range(2, n+1, 1):
            colors = [1, 2, 3, 4]
            sub_nodes = recorder[str(i)]
            for sub_node in sub_nodes:
                if sub_node > len(result):
                    continue
                else:
                    if result[sub_node-1] in colors:
                        colors.remove(result[sub_node-1])
            result.append(colors[0])
        return result

python3 解法, 执行用时: 144 ms, 内存消耗: 19.9 MB, 提交时间: 2022-12-10 22:50:31

class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        G = defaultdict(list)
        for u, v in paths:
            G[u].append(v)
            G[v].append(u)
        ans = [0] * n
        for u in range(1, n + 1):
            colors = set(range(1, 5)) - set(ans[v - 1] for v in G[u])
            ans[u - 1] = colors.pop()
        return ans

java 解法, 执行用时: 6 ms, 内存消耗: 49.9 MB, 提交时间: 2022-12-10 22:49:52

class Solution {
    public int[] gardenNoAdj(int N, int[][] paths) {
        int[][] topo = new int[N+1][3] ;
        for( int[] cur : paths ){
            int temp = 0 ;
            while( topo[cur[0]][temp] != 0 ) temp++ ;
            topo[cur[0]][temp] = cur[1] ;
            temp = 0 ;
            while( topo[cur[1]][temp] != 0 ) temp++ ;
            topo[cur[1]][temp] = cur[0] ;
        }
        int[] res1 = new int[N+1] ;
        int[] res = new int[N] ;
        for( int i = 1 ; i <= N ; i++ ){
            int temp = 1 ;
            while( res1[topo[i][0]] == temp || res1[topo[i][1]] == temp || res1[topo[i][2]] == temp ) temp++ ;
            res1[i] = temp ;
        }
        for( int i = 0 ; i < N ; i++ ) res[i] = res1[i+1] ;
        return res ;
    }
}

java 解法, 执行用时: 24 ms, 内存消耗: 50.4 MB, 提交时间: 2022-12-10 22:49:38

class Solution {
    public int[] gardenNoAdj(int N, int[][] paths) {
        /* 这是一道简单题，限制每个节点的度为3，同时提供四种颜色，因此不需要回溯 */
        /* 初始化节点，使用map保存节点与其临界点的关系 */
        /* 第一版本采用了内部类构建，参考评论区的HashMap更简洁 */
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (int i = 0; i < N; i++) {
            graph.put(i, new HashSet<>());
        }
        /* 初始化路径信息 */
        for (int[] path: paths) {
            int a = path[0] - 1;
            int b = path[1] - 1;
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            boolean[] used = new boolean[5];
            /* 查看当前节点的所有邻接点的色彩 */
            for (int adj: graph.get(i)) {
                used[res[adj]] = true;
            }
            /* 为当前节点染色 */
            for (int j = 1; j <= 4; j++) {
                if (!used[j]) {
                    res[i] = j;
                }
            }
        }
        return res;
    }
}

cpp 解法, 执行用时: 188 ms, 内存消耗: 62.8 MB, 提交时间: 2022-12-10 22:48:28

/**
 * 1、根据paths建立邻接表；
 * 2、默认所有的花园先不染色，即染0；
 * 3、从第一个花园开始走，把与它邻接的花园的颜色从color{1,2,3,4}这个颜色集中删除；
 * 4、删完了所有与它相邻的颜色，就可以把集合中剩下的颜色随机选一个给它了，为了简单，将集合中的第一个颜色赋给当前花园；
 * 5、循环3和4到最后一个花园。
 **/
class Solution {
public:
    //static const int MAXV=10000;
    //int G[MAXV][MAXV]={0};
    vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
        vector<int> G[N];
        for (int i=0; i<paths.size(); i++){//建立邻接表
            G[paths[i][0]-1].push_back(paths[i][1]-1);
            G[paths[i][1]-1].push_back(paths[i][0]-1);
        }
        vector<int> answer(N,0);//初始化全部未染色
        for(int i=0; i<N; i++){
            set<int> color{1,2,3,4};
            for (int j=0; j<G[i].size(); j++){
                color.erase(answer[G[i][j]]);//把已染过色的去除
            }
            answer[i]=*(color.begin());//染色
        }
        return answer;
    }
};

上一题

下一题

详情