数位重排

[编程题]数位重排

热度指数：2742 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

牛牛有一个正整数x,牛牛需要把数字x中的数位进行重排得到一个新数(不同于x的数),牛牛想知道这个新数是否可能是原x的倍数。请你来帮他解决这个问题。

输入描述:

输入包括t+1行,第一行包括一个整数t(1 ≤ t ≤ 10),
接下来t行,每行一个整数x(1 ≤ x ≤ 10^6)

输出描述:

对于每个x,如果可能重排之后变为自己的倍数输出"Possible", 否则输出"Impossible".

示例1

输入

2
14
1035

输出

Impossible
Possible

算法知识视频讲解

Java

飞天憨猪

笨办法：dfs遍历各种可能的组合，然后检查是否能整除原来的那个数。没有第一时间想到巧妙的方法时，可以用这种万能解法。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for(int i=0; i<n; i++) {
            int org = in.nextInt();
            int o = org;
            ArrayList<Integer> tmpl = new ArrayList<>();
            while(o != 0) {
                int t = o%10;
                tmpl.add(t);
                o = o/10;
            }
            int[] tmp = new int[tmpl.size()];
            for(int j=tmpl.size()-1; j>=0; j--) {
                tmp[tmpl.size()-1-j] = tmpl.get(j);
            }
            ArrayList<Integer> rec = new ArrayList<>();
            int[] flag = new int[1];
            dfs(tmp, rec, flag, org);
            if(flag[0] == 0) {
                System.out.println("Impossible");
            } else {
                System.out.println("Possible");
            }
        }
    }
    
    public static void dfs(int[] tmp, ArrayList<Integer> rec, int[] flag, int org) {
        if(flag[0] == 1) return;
        if(rec.size() == tmp.length) {
            int t = 0;
            for(int i=0; i<rec.size(); i++) {
                t = t*10 + rec.get(i);
            }
            if (t!=org && t%org == 0) 
                flag[0] = 1;
            return;
        } else {
            for(int i=0; i<tmp.length; i++) {
                if(tmp[i]>=0) {
                    int t = tmp[i];
                    tmp[i] = -1;
                    rec.add(t);
                    dfs(tmp, rec, flag, org);
                    rec.remove(rec.size()-1);
                    tmp[i] = t;
                }
            }
        }
    }
    
}

发表于 2022-02-03 17:02:23 回复(0)

Java

Leven11


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Digitalrearrangement {     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         int n = scanner.nextInt();         int num[] = new int[n];         ArrayList<String> arrayList = new ArrayList<String>();         for (int i = 0; i < n; i++) {             num[i] = scanner.nextInt();             if (canrearrange(num[i]) == true) {                 arrayList.add("Possible");             } else {                 arrayList.add("Impossible");             }         }         for (int i = 0; i < arrayList.size(); i++) {             System.out.println(arrayList.get(i));         }     }     public static boolean canrearrange(int num) {         int n = String.valueOf(num).length();         int[] letter = new int[n];         int temp = num;         for (int i = 0; i < n; i++) {             letter[i] = temp % 10;             temp /= 10;         }         int[] letter_tmp = new int[n];         for (int i = 2; String.valueOf(num * i).length() == n; i++) {             int tmp = num * i;             for (int j = 0; j < n; j++) {                 letter_tmp[j] = tmp % 10;                 tmp /= 10;             }             int[] tmp_letter = new int[n];             tmp_letter = letter;             Arrays.sort(tmp_letter);             Arrays.sort(letter_tmp);             if (Arrays.equals(tmp_letter, letter_tmp)) {                 return true;             }         }         return false;     }
}

	

}
}

直接按照数字读入

将数字依次乘上1,2,3……，判定条件是位数相同，最后判断一下是否包含原输入数字各个位数上的数。即可

编辑于 2019-04-19 16:52:04 回复(0)

Java

Karl_hl

import java.util.*;

public class demo4 {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int[] arr = new int[n];         for (int i = 0; i < n; i++) {             arr[i] = sc.nextInt();         }         for (int i = 0; i < n; i++) {             System.out.println(solve(arr[i]));         }              }     private static String solve(int n) {         int[] arr1 = toArr(n);         Arrays.sort(arr1);         for (int i = 2; i <= 9; i++) {             int s = n * i;             int[] arr2 = toArr(s);             Arrays.sort(arr2);             if (Arrays.equals(arr1,arr2)) {                 return "Possible";             }         }         return "Impossible";     }     private static int[] toArr(int n) {         int a = String.valueOf(n).length();// n的长度         int[] arr2 = new int[a];         String str = String.valueOf(n);         for (int i = 0; i < a; i++) {             arr2[i] = str.charAt(i);         }         return arr2;     }
}

写的比较差，，，见笑了

发表于 2019-04-02 09:44:30 回复(0)

Java

满脑子程序

import java.util.*;  /**  * @author 王志昊  * @date 2018.8.10  */ public class Main30 { static char[] chars;  static Integer input;  static Set<Integer> set;   public static void main(String[] args) {
        Scanner in =new Scanner(System.in);  int t =in.nextInt();  String str = in.nextLine();;  for (int k = 0; k < t; k++) {
            str = in.nextLine();  chars = str.toCharArray();  input = Integer.valueOf(str);  set =new HashSet<>();  Arrays.sort(chars);  set.add(Integer.valueOf(String.valueOf(chars)));  boolean stop = false;  int i,j;int n = chars.length;  while (!stop){
                stop = true;  i = n-2;  j = n-1;  while (i >= 0 && chars[i] >= chars[i+1]){
                    i--;  } if (i<0) break;  while (chars[j] <= chars[i]){
                    j--;  } if (j > i) { swap(i,j);  reverse(i+1, n-1);  stop =false;  set.add(Integer.valueOf(String.valueOf(chars)));  }
            } set.remove(input);  Iterator<Integer> iterator= set.iterator();  boolean flag = false;  while (iterator.hasNext()){ if (iterator.next()%input == 0){
                    flag =true;  System.out.println("Possible");  break;  }
            } if (!flag) System.out.println("Impossible");  }
    } private static void reverse(int i, int j) { while(i<j){ char temp = chars[i];  chars[i++] = chars[j];  chars[j--] = temp;  }
    } private static void swap(int i, int j) { char temp = chars[i];  chars[i] = chars[j];  chars[j] = temp;  }
}