美团笔试第四道,能否帮忙看看哪里有问题
用的DFS,但是只能过60%
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int num = in.nextInt(); int[] nums = new int[num]; String in_ = in.next(); char[] c = in_.toCharArray(); for (int i=0;i<num;i++) { nums[i] = c[i]-96; } List<Integer> x_list = new ArrayList<>(); for (int i=1;i<=num;i++) { if (num%i==0) { x_list.add(i); } } int _max = Integer.MAX_VALUE; for (int x: x_list) { int y = num/x; int res = f(x, y, nums); _max = Math.min(_max, res); } System.out.println(_max); } public static int f(int x, int y, int[] nums) { int[][] s = new int[x][y]; int n = 0; for (int i=0;i<x;i++) { for (int j=0;j<y;j++) { s[i][j] = nums[n]; n++; } } int res = 0; boolean[][] used = new boolean[x][y]; int col = s.length; int line = s[0].length; for (int i=0;i<col;i++) { for (int j = 0; j < line; j++) { if (!used[i][j]) { dfs(s, used, i, j); res++; } } } return res; } public static void dfs(int[][] nums, boolean[][] used, int i, int j) { if (used[i][j]) return; int col = nums.length; int row = nums[0].length; used[i][j] = true; if (i + 1 < col && !used[i + 1][j] && nums[i][j] == nums[i + 1][j]) { dfs(nums, used, i+1, j); } if (i - 1 >= 0 && !used[i - 1][j] && nums[i][j] == nums[i - 1][j]) { dfs(nums, used, i-1, j); } if (j + 1 < row && !used[i][j+1] && nums[i][j] == nums[i][j+1]) { dfs(nums, used, i, j+1); } if (j - 1 >= 0 && !used[i][j-1] && nums[i][j] == nums[i][j-1]) { dfs(nums, used, i, j=1); } } }#美团##美团笔试#