首页 > 代码库 > Snapchat - 2D矩阵的combination

Snapchat - 2D矩阵的combination

2024-08-16 21:53:12   217人阅读

面筋贴：http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=206115&pid=2586947&page=1&extra=#pid2586947

给一个整数n和一个整数m，n表示正方形边长，正方形初始值全为0。
比如 n=3,代表初始是这样的正方形：.1point3acres缃?
000
000
000
若m=2，代表将其中的2个元素翻转为1，打印出可能得到的所有正方形：
比如
011
000
000
或
000
110
000
。。。
我用backtracking做的，但是时间复杂度没有答好，估计是跪这里了。
follow up是 生成的正方形中，
011
000
000
和. 涓€浜?-涓夊垎-鍦帮紝鐙鍙戝竷
000
000
011
这种对称的正方形视为重复的，如何对之前的结果进行去重。

 

其实就是一个combination

 1     public List<List<String>> generate(int n, int m) {
 2         List<List<String>> res = new ArrayList<>();
 3         char[][] board = new char[n][n];
 4         for(int i = 0; i < n; i++) {
 5             Arrays.fill(board[i], ‘0‘);
 6         }
 7         helper(res, board, n, m, 0, 0);
 8         return res;
 9     }
10     
11     private void helper(List<List<String>> res, char[][] board, int n, int m, int cnt, int index) {
12         if(cnt == m) {
13             List<String> curRes = new ArrayList<String>();
14             for(int i = 0; i < n; i++) {
15                 curRes.add(new String(board[i]));
16             }
17             res.add(curRes);
18             return;
19         }
20         for(int i = index; i < n * n; i++) {
21             int row = i / n;
22             int col = i % n;
23             board[row][col] = ‘1‘;
24             helper(res, board, n, m, cnt + 1, i + 1);
25             board[row][col] = ‘0‘;
26         }
27     }

 检查重复，用的是笨方法，把res设成Set。每次往set里面添加的时候翻转一下然后再添加

 

1         if(cnt == m) {
2             List<String> cur = Arrays.stream(board).map(String::valueOf).collect(Collectors.toList());
3             List<String> reverse = new LinkedList<>(cur);
4             Collections.reverse(reverse);
5             if (!res.contains(cur) && !res.contains(reverse)) {
6                 res.add(cur);
7             }
8             return;
9         }

 

Snapchat - 2D矩阵的combination


联系
我们