谷歌onsite新题

给定一个二维数组，有不同的颜色，一个连通的区域叫做一种色块，一开始可以选择一个色块，比如说选了r，那么r会对应一个反转序列 比如说是 rgb...，可以依次翻转，每次翻转之后相邻的相同

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

都看不到了，12月还有最后一次面试，鸭梨山大，还有一些最近面的题目会陆续发出来，求各位加点大米。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这是我的暴力解法，用union find减少可能的开始点，然后每个开始点都按照序列flip一遍看需要多少翻转多少次，然后取最小值。 时间和空间复杂度都是O(n^3)，感觉不是很优，但是实在是想不出来了= =

1. public class FlipColors {
   
2.         @Test
   
3.         public void test() {
   
4.                 char[][] grid = new char[][] {
   
5.                         {'r', 'g','g'},
   
6.                         {'b', 'r', 'b'},
   
7.                         {'b', 'r', 'g'}
   
8.                 };
   
9. //                char[][] grid = new char[][] {
   
10. //                        {'r', 'g','b','g','b','g','r'}
    
11. //                };
    
12.                 /*
    
13.                  * Asumption: the fliping order is fixed:
    
14.                  * order = new char[] {'r', 'g', 'b'};
    
15.                  * we can not flip r to b directly
    
16.                  *
    
17.                  * when we choose the start point, we can't change the point and flip other cells
    
18.                  * m = rows, n = cols
    
19.                  * Time: O((mn)^3)
    
20.                  * Space: O((mn) ^ 3 )
    
21.                  * */
    
22.                 int res = findMinFlip(grid);
    
23.                 System.out.println(res);
    
24.         }
    
25.         int[][] dirs = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
26.         private char[] order = new char[] {'r', 'g', 'b'};
    
27.         /*
    
28.          * Main Procedure
    
29.          * */
    
30.         public int findMinFlip(char[][] grid) {
    
31.                 int rows = grid.length;
    
32.                 if(rows == 0) return 0;
    
33.                 int cols = grid[0].length;
    
34.                 if(cols == 0) return 0;
    
35.                 // init unions
    
36.                 Union union = new Union(rows * cols);
    
37.                 // union cells with same color, to compress the start points
    
38.                 for (int i = 0 ; i < rows ; i++) {
    
39.                         for (int j = 0 ; j < cols ; j++) {
    
40.                                 for(int k = 0 ; k < dirs.length ; k++) {
    
41.                                         int x = i + dirs[k][0];
    
42.                                         int y = j + dirs[k][1];
    
43.                                         if(isValidate(grid, x, y) && grid[i][j] == grid[x][y]) {
    
44.                                                 union.union(i * cols + j , x * cols + y);
    
45.                                         }
    
46.                                 }
    
47.                         }
    
48.                 }
    
49.                 // pick up all the potential start points
    
50.                 List<Integer> starts = new ArrayList<>();
    
51.                 for(int i = 0 ; i < union.ids.length ; i++) {
    
52.                         if(union.ids[i] == i) starts.add(i);
    
53.                 }
    
54.                 int res = Integer.MAX_VALUE;
    
55.                 for(Integer start : starts) {
    
56.                         char[][] copy = copyGraph(grid);
    
57.                         int ans = getFlipNum(copy, start / cols, start % cols);
    
58.                         if(ans < res) {
    
59.                                 res = ans;
    
60.                         }
    
61.                 }
    
62.                 return res;
    
63.         }
    
64. 
    
65.         private char[][] copyGraph (char[][] grid) {
    
66.                 char[][] copy = new char[grid.length][];
    
67.                 for(int i = 0 ; i < grid.length ; i++) {
    
68.                         copy[i] = Arrays.copyOfRange(grid[i], 0, grid[i].length);
    
69.                 }
    
70.                 return copy;
    
71.         }
    
72.         private int getFlipNum(char[][] grid, int row, int col) {
    
73.                 int counter = 0;
    
74.                 int rows = grid.length;
    
75.                 int cols = grid[0].length;
    
76.                 boolean flag = ifGetOneColor(grid);  // whether we get the grid with one color
    
77.                 while (!flag) {
    
78.                         counter++;
    
79.                         char prevColor = grid[row][col];
    
80.                         grid[row][col] = getNextCol(grid[row][col]);
    
81.                         boolean[][] visited = new boolean[rows][cols];
    
82.                         flipNeighbor(grid, row, col, prevColor, grid[row][col], visited);
    
83.                         flag = ifGetOneColor(grid);
    
84.                 }
    
85.                 return counter;
    
86.         }
    
87.         private void flipNeighbor(char[][] grid, int i, int j,
    
88.                         char prevColor, char currColor, boolean[][] visited) {
    
89.                 for(int k = 0 ; k < dirs.length ; k++) {
    
90.                         int x = i + dirs[k][0];
    
91.                         int y = j + dirs[k][1];
    
92.                         if(isValidate(grid, x, y) && !visited[x][y] &&
    
93.                                         grid[x][y] == prevColor) {
    
94.                                 visited[x][y] = true;
    
95.                                 grid[x][y] = currColor;
    
96.                                 flipNeighbor(grid, x, y, prevColor, currColor, visited);
    
97.                         }
    
98.                 }
    
99.         }
    
100.         private boolean ifGetOneColor(char[][] grid) {
     
101.                 char color = grid[0][0];
     
102.                 for(int i = 0 ; i < grid.length ; i++) {
     
103.                         for(int j = 0 ; j < grid[0].length ; j++) {
     
104.                                 if(grid[i][j] != color) {
     
105.                                         return false;
     
106.                                 }
     
107.                         }
     
108.                 }
     
109.                 return true;
     
110.         }
     
111.         private char getNextCol(char curr) {
     
112.                 int i = 0;
     
113.                 for( ; i < order.length ; i++) {
     
114.                         if(order[i] == curr) break;
     
115.                 }
     
116.                 if(i + 1 < order.length) return order[i + 1];
     
117.                 else return order[0];
     
118.         }
     
119.         private boolean isValidate(char[][] grid, int i, int j) {
     
120.                 return i < grid.length && i >= 0 && j >=0 && j < grid[0].length;
     
121.         }
     
122.         private class Union{
     
123.                 int[] ids;
     
124.                 int[] sizes;
     
125.                 public Union(int len) {
     
126.                         ids = new int[len];
     
127.                         sizes = new int[len];
     
128.                         for(int i = 0 ; i < ids.length ; i++) {
     
129.                                 ids[i] = i;
     
130.                                 sizes[i] = 1;
     
131.                         }
     
132.                 }
     
133.                 public int find(int id) {
     
134.                         if(ids[id] == id) return id;
     
135.                         else {
     
136.                                 int root = find(ids[id]);
     
137.                                 // path compress
     
138.                                 ids[id] = root;
     
139.                                 return root;
     
140.                         }
     
141.                 }
     
142.                 public void union(int id1, int id2) {
     
143.                         int r1 = find(id1);
     
144.                         int r2 = find(id2);
     
145.                         if(r1 == r2) return ;
     
146.                         else {
     
147.                                 ids[r2] = r1;
     
148.                                 sizes[r1] += sizes[r2];
     
149.                         }
     
150.                 }
     
151.         }
     
152. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

感觉是那个字符翻转的变种？

msu_HIDDEN 发表于 2018-11-23 08:00
感觉是那个字符翻转的变种？

你说的是926的话和那个解法没什么关系。

LuckySheep 发表于 2018-11-23 08:21
你说的是926的话和那个解法没什么关系。

https://www.1point3acres.com/bbs/thread-443299-1-1.html

这贴里的第一题

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这题我猜应该就是数有多少独立的岛屿数目，number of island变种

不是啊 这不就是暴力解用bfs直接traverse嘛

先用union find合并所有的色块，因为翻转色块和翻转一个格子的花费是一样的，然后统计所有unions中出现颜色最多的，把这个颜色当作最后的颜色花费一定是最小的，然后依次翻转所有union就好。我感觉思路是这样。

请问一下楼主， 翻转序列是想当前的颜色根据翻转序，转为其他颜色 是吗

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies