挑战程序竞赛系列（6）：2.1穷尽搜索
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434757
2.1穷尽搜索
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
POJ 2718: Smallest Difference
一个数切一刀拆成两个数，两个数每一位数字的顺序都可改变，但是不能有前导0。求这两个数之差的最小值。
思路：
尽量拆分成长度相等的两个数，最小值一定存在这种情况下，得到两个数之后，在原来的数上求出所有可能的顺序，用到的知识点为nextPermutation().有了所有的顺序，我们穷尽所有顺序求得答案即可，代码如下：
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = Integer.parseInt(in.nextLine());
while(N-- != 0){
String[] nums = in.nextLine().trim().split(" ");
int[] digits = new int[nums.length];
for(int i = 0; i <nums.length; i++){
digits[i] = nums[i].charAt(0)-'0';
}
System.out.println(solve(digits));
}
in.close();
}
private static int solve(int[] digits){
int n = digits.length;
int size1 = n / 2;
int size2 = size1;
if (n % 2 != 0){
size2 ++;
}
int min = Integer.MAX_VALUE;
do{
int k = 0;
String a1 = "";
for (int i = 0; i < size1; i++){
a1 += digits[k++];
}
String a2 = "";
for (int i = 0; i < size2; i++){
a2 += digits[k++];
}
int ans = Math.abs(Integer.parseInt(a1)-Integer.parseInt(a2));
min = Math.min(min, ans);
}while(nextPermutation(digits) != null);
return min;
}
public static int[] nextPermutation(int[] nums){
int n = nums.length;
int pos = n - 2;
while (pos >= 0 && nums[pos] - nums[pos+1] >= 0){
pos --;
}
if (pos == -1) return null;
int j = n - 1;
while (j > pos && nums[j] <= nums[pos]){
j --;
}
swap(nums, pos, j);
reverse(nums, pos+1, n-1);
return nums;
}
private static void swap(int[] nums, int x, int y){
int tmp = nums[x];
nums[x] = nums[y];
nums[y] = tmp;
}
private static void reverse(int[] nums, int s, int e){
while (s < e){
swap(nums, s, e);
s++;
e--;
}
}为了得到所有的顺序，我们必须得遍历所有可能的顺序，而这种情况会有O(n!)O(n!)种情况，这复杂度实在太高了，果断TLE。
优化思路：
它其实是一道排列组合题，我不知道网上说的贪心是什么解法，暂且没有想明白贪心的做法。在上述思路中，我们知道，如果n为偶数，那就意味着，把数放在box1和box2中的任何一个是顺序无关的。所以在暴力nextPermutation时，我们可以分成n/2的两个list，分别进行nextPermutation，现在要做的无非就是从n个数中选择n/2个数装进box1，剩余的数装进box2。
在JAVA中，我能想到的随机选择n/2个数的方法是遍历2n2^n次，如：
n = 4
初始化：
1 << 4; 16
二进制表示：
10000
遍历：while (16-- != 0)
1111
1110
.
.
.
0010
0001
0000
0和1个数相等的位筛选出来，就是从n个数中随机选择n/2个数的所有情况。详细代码如下：
private static int solve(int[] digits){
int n = digits.length;
int permutate = 1 << n;
int cut = n / 2;
int min = Integer.MAX_VALUE;
while (permutate-- != 0){
String bitSet = Integer.toBinaryString(permutate);
int[] list1 = new int[cut];
int[] list2 = new int[n-cut];
char[] bits = bitSet.toCharArray();
String a1 = "";
String a2 = "";
int k = 0;
for (int i = bits.length-1; i >= 0; i--){
if (bits[i] == '1'){
a1 += digits[k++];
}else{
a2 += digits[k++];
}
}
while (k < n){
a2 += digits[k++];
}
if (a1.length() != cut){
continue;
}
if (a1.charAt(0) == '0' && a1.length() > 1){
continue;
}
for (int i = 0; i < list1.length; i++){
list1[i] = a1.charAt(i)-'0';
}
for (int i = 0; i < list2.length; i++){
list2[i] = a2.charAt(i)-'0';
}
int[] c1 = clone(list1);
int[] c2 = clone(list2);
do{
String x1 = "";
for (int i = 0; i < list1.length; i++){
x1 += c1[i];
}
c2 = clone(list2);
do{
String x2 = "";
for (int i = 0; i < list2.length; i++){
x2 += c2[i];
}
if (x2.charAt(0) == '0' && x2.length() > 1) continue;
int diff = Math.abs(Integer.parseInt(x1)-Integer.parseInt(x2));
min = Math.min(min, diff);
}while(nextPermutation(c2) != null);
}while (nextPermutation(c1) != null);
}
return min;
}POJ 3187: Backward Digits Sums
思路：
非常简单，遍历所有可能的顺序，依次求出sum即可，符合就返回结果。sum的求解使用了递归，每次递归，样本减一，所以时间复杂度为O(n)O(n)。代码如下：
public class SolutionDay19_P3187 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int S = in.nextInt();
solve(N, S);
in.close();
}
private static void solve(int N, int S){
int[] nums = new int[N];
for (int i = 0; i < N; i++){
nums[i] = i + 1;
}
do{
if (S == sum(nums)) break;
}while(nextPermutation(nums) != null);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < nums.length; i++) {
sb.append(nums[i] + " ");
}
System.out.println(sb.toString().substring(0,sb.length()-1));
}
private static int sum(int[] nums){
if (nums.length == 1) return nums[0];
int[] sum = new int[nums.length-1];
for (int i = 0; i < sum.length; i++){
sum[i] = nums[i] + nums[i+1];
}
return sum(sum);
}
public static int[] nextPermutation(int[] nums){
int n = nums.length;
int pos = n - 2;
while (pos >= 0 && nums[pos] - nums[pos+1] >= 0){
pos --;
}
if (pos == -1) return null;
int j = n - 1;
while (j > pos && nums[j] <= nums[pos]){
j --;
}
swap(nums, pos, j);
reverse(nums, pos+1, n-1);
return nums;
}
private static void swap(int[] nums, int x, int y){
int tmp = nums[x];
nums[x] = nums[y];
nums[y] = tmp;
}
private static void reverse(int[] nums, int s, int e){
while (s < e){
swap(nums, s, e);
s++;
e--;
}
}
}POJ 3050: Hopscotch
思路：
依旧是遍历，用Set记录非重复的元素，采用DFS+回溯，其他的没什么。代码如下：
public class SolutionDay19_P3050 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[][] grid = new int[5][5];
for (int i = 0; i < 5; i++){
for (int j = 0; j < 5; j++){
grid[i][j] = in.nextInt();
}
}
System.out.println(solve(grid));
in.close();
}
private static int solve(int[][] grid){
ans = new HashSet<>();
for (int i = 0; i < 5; i++){
for (int j = 0; j < 5; j++){
dfs(grid,i, j, 5, "");
}
}
return ans.size();
}
static Set<String> ans = new HashSet<>();
static int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
private static void dfs(int[][] grid,int i, int j, int hop,String path){
path += grid[i][j];
if (hop == 0){
ans.add(path);
}else{
for (int[] d : dir){
int nx = i + d[0];
int ny = j + d[1];
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5){
dfs(grid, nx, ny, hop-1, path);
}
}
}
path.substring(0,path.length()-1);
}
}AOJ 0525: Osenbei
翻译参考博文【AOJ 0525 Osenbei《挑战程序设计竞赛(第2版)》练习题答案】
题意：药药!切克闹! 煎饼果子来一套!有一个烤饼器可以烤r行c列的煎饼，煎饼可以正面朝上（用1表示）也可以背面朝上（用0表示）。一次可将同一行或同一列的煎饼全部翻转。现在需要把尽可能多的煎饼翻成正面朝上，问最多能使多少煎饼正面朝上？undefined 输入：多组输入，每组第一行为二整数r, c (1 ≤ r ≤ 10, 1 ≤ c ≤ 10 000)，剩下r行c列表示煎饼初始状态。r=c=0表示输入结束。undefined 输出：对于每组输入，输出最多能使多少煎饼正面朝上。
这道题很有意思，乍一看，它的选择千变万化，不知道如何下手，实则不然。
思路：
关于翻转有一个特性：翻转两次就能覆盖所有结果，翻转第三次时与第一次的结果相同，翻转第四次与第二次的结果相同。所以这道题，每行选择翻或者不翻，总共就有O(2row)O(2^{row})种情况，而一旦每一行确定后，关于每一列，只需要选择{0,1}中个数较多的那个数进行累加即可。
代码如下：
public class SolutionDay19_A0525 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (true) {
int row = in.nextInt();
int col = in.nextInt();
if (row == 0 && col == 0)
break;
int[][] grid = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
grid[i][j] = in.nextInt();
}
}
System.out.println(solve(grid));
}
in.close();
}
private static void flip(int[][] grid, int row){
for (int i = 0; i < grid[0].length; i++){
grid[row][i] = grid[row][i] == 1 ? 0 : 1;
}
}
private static int total(int[][] grid, int col){
int n = grid.length;
int count = 0;
for (int i = 0; i < n; i++){
if (grid[i][col] == 1) count ++;
}
return Math.max(count, n - count);
}
private static int solve(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int nn = 1 << n;
int max = Integer.MIN_VALUE;
while (nn-- != 0) {
String nns = Integer.toBinaryString(nn);
char[] nnc = nns.toCharArray();
for (int i = 0; i < nnc.length; i++){
if (nnc[i] == '1'){
flip(grid, i);
}
}
int count = 0;
for (int j = 0; j < m; j++){
count += total(grid, j);
}
max = Math.max(max, count);
//复原
for (int i = 0; i < nnc.length; i++){
if (nnc[i] == '1'){
flip(grid, i);
}
}
}
return max;
}
}关于位置的随机选取，不一定要使用String的方法，而是直接使用位操作，代码如下：
private static int solve(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int nn = 1 << n;
int max = Integer.MIN_VALUE;
for (int i = 0; i < nn; i++){
for (int j = 0; j < n; j++){
if ((i & (1 << j)) != 0) {
flip(grid, j);
}
}
int count = 0;
for (int j = 0; j < m; j++) {
count += total(grid, j);
}
max = Math.max(max, count);
for (int j = 0; j < n; j++){
if ((i & (1 << j)) != 0) {
flip(grid, j);
}
}
}
return max;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年05月19日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录