谷歌onsite新题

楼主给个timeliness吧。另外刷题刷了多久呢

您好！
本帖隐藏的内容需要积分高于 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. }

复制代码

似乎只能bfs（dfs当然也行 只是慢一点）　
先union一下色块  对每个色块反转一次放到queue里  然后看是否都是一个颜色了
之后重复这几部的操作...
想想就觉得麻烦

what does 依次翻转 mean?

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

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

可能会有更好的贪心解，但是我感觉直接把色块最多的点的颜色当作终止颜色可能并不一定最优，枚举一下比较保险

可以请问楼主是在哪个office面的吗。。。