https://warmland.gitbooks.io/algorithm/content/interview/snapchat_-_2dju_zhen_de_combination.html
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=206115&page=2
横着或者竖着对称,没有旋转,就是生成的时候来判重
复杂度是 n^2 choose m. 楼主你是怎么处理重复的HashSet吗
给一个整数n和一个整数m,n表示正方形边长,正方形初始值全为0。 比如 n=3,代表初始是这样的正方形:
000
000
000
若m=2,代表将其中的2个元素翻转为1,打印出可能得到的所有正方形: 比如
011
000
000
或
000
110
000
。。。
我用backtracking做的,但是时间复杂度没有答好,估计是跪这里了。 follow up是 生成的正方形中, 011 000 000 和 000 000 011 这种对称的正方形视为重复的,如何对之前的结果进行去重。
其实就是一个combination
public List<List<String>> generate(int n, int m) {
List<List<String>> res = new ArrayList<>();
char[][] board = new char[n][n];
for(int i = 0; i < n; i++) {
Arrays.fill(board[i], '0');
}
helper(res, board, n, m, 0, 0);
return res;
}
private void helper(List<List<String>> res, char[][] board, int n, int m, int cnt, int index) {
if(cnt == m) {
List<String> curRes = new ArrayList<String>();
for(int i = 0; i < n; i++) {
curRes.add(new String(board[i]));
}
res.add(curRes);
return;
}
for(int i = index; i < n * n; i++) {
int row = i / n;
int col = i % n;
board[row][col] = '1';
helper(res, board, n, m, cnt + 1, i + 1);
board[row][col] = '0';
}
}
检查重复,用的是笨方法,把res设成Set。每次往set里面添加的时候翻转一下然后再添加
if(cnt == m) {
List<String> cur = Arrays.stream(board).map(String::valueOf).collect(Collectors.toList());
List<String> reverse = new LinkedList<>(cur);
Collections.reverse(reverse);
if (!res.contains(cur) && !res.contains(reverse)) {
res.add(cur);
}
return;
}
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=206115&page=2
横着或者竖着对称,没有旋转,就是生成的时候来判重
复杂度是 n^2 choose m. 楼主你是怎么处理重复的HashSet吗