Snap 面经题目:Put 1s in All 0’s Square

0002505492

题目:
给一个整数n和一个整数m,n表示正方形边长,正方形初始值全为0。
比如 n=3,代表初始是这样的正方形:
000
000
000
若m=2,代表将其中的2个元素翻转为1,打印出可能得到的所有正方形:
比如
011
000
000

000
110
000
生成的正方形中,
011
000
000

000
000
011
这种对称的正方形视为重复的,如何对之前的结果进行去重。
思路:backtrace + set
代码:

import java.util.*;
public class Solution {
	static int t = 0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		set(3,2);
	}

	private static void set(int m, int n) {
		// TODO Auto-generated method stub
		Set set = new HashSet<>();
		int[][] board = new int[m][m];
		backtrace(board, 0, 0, m, n, set);
	}

	private static void backtrace(int[][] board, int index, int count, int m, int n, Set set) {
		// TODO Auto-generated method stub
		count++;
		for(int i = index; i < m * m - n + count; i++)
		{
			int j = i / m;
			int k = i % m;
			board[j][k] = 1;
			if(count == n) print(board, set);
			else backtrace(board, i + 1, count, m, n, set);
			board[j][k] = 0;
		}
	}

	private static void print(int[][] board, Set set) {
		// TODO Auto-generated method stub
		StringBuilder s1 = new StringBuilder();
		int m = board.length;
		for(int i = 0; i < m; i++)
		{
			for(int j = 0; j < m; j++)
			{
				s1.append(board[i][j]);
			}
		}
		if(set.contains(s1.toString())) return;
		StringBuilder s2 = new StringBuilder();
		StringBuilder s3 = new StringBuilder();
		for(int i = m - 1; i >= 0; i--)
		{
			for(int j = 0; j < m; j++)
			{
				s2.append(board[i][j]);
			}
		}
		for(int i = 0; i < m; i++)
		{
			for(int j = m - 1; j >= 0; j--)
			{
				s3.append(board[i][j]);
			}
		}
		set.add(s1.toString());
		set.add(s2.toString());
		set.add(s3.toString());
		t++;
		System.out.println("**************");
		System.out.println("t = " + t);
		for(int i = 0; i < m; i++)
		{
			for(int j = 0; j < m; j++)
			{
				System.out.print(board[i][j]);
			}
			System.out.println("");
		}
	}

}

输出:

**************
t = 1
110
000
000
**************
t = 2
101
000
000
**************
t = 3
100
100
000
**************
t = 4
100
010
000
**************
t = 5
100
001
000
**************
t = 6
100
000
100
**************
t = 7
100
000
010
**************
t = 8
100
000
001
**************
t = 9
010
100
000
**************
t = 10
010
010
000
**************
t = 11
010
000
010
**************
t = 12
010
000
001
**************
t = 13
000
110
000
**************
t = 14
000
101
000
**************
t = 15
000
100
001
**************
t = 16
000
010
001
**************
t = 17
000
001
010
**************
t = 18
000
001
001
**************
t = 19
000
000
011

568total visits,1visits today