首页 > 试题广场 >

数位重排

[编程题]数位重排
  • 热度指数：85 时间限制：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
pein531头像 pein531

暴力

(1) 对原始数字num的各位进行全排列，并去除含前导零的数值形成候选集；
(2) 遍历候选集里面的数有没有num的倍数。 
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while(t-- > 0){
            String str = br.readLine();
            char[] chars = str.toCharArray();
            int num = Integer.parseInt(str);
            List<Integer> res = new ArrayList<>();
            permutation(chars, 0, res);
            boolean flag = false;
            for(int candicate: res){
                if(candicate != num && candicate % num == 0){
                    flag = true;
                    break;
                }
            }
            if(flag){
                System.out.println("Possible");
            }else{
                System.out.println("Impossible");
            }
        }
    }
    
    private static void permutation(char[] num, int index, List<Integer> res) {
        if(index == num.length){
            if(num[0] != '0'){
                res.add(Integer.parseInt(String.valueOf(num)));
            }
        }else{
            for(int i = index; i < num.length; i++){
                swap(num, index, i);
                permutation(num, index + 1, res);
                swap(num, index, i);
            }
        }
    }
    
    private static void swap(char[] chars, int i, int j) {
        if(i != j){
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
        }
    }
}

发表于 2022-03-04 22:40:37 回复(0)
SDGSlhh头像 SDGSlhh
#include <iostream>
#include<algorithm>
#include <cstring>
using namespace std;
int result;
int Integer(char s[])
{
    int n=strlen(s),flag=1,sum=0;
    for(int i=n-1;i>=0;i--)
    {
        sum+=flag*(s[i]-'0');
        flag*=10;
    }
    return sum;
}
bool is(int index,char s[],int length){
    if(index==length){
        int res=Integer(s);
        if(res%result==0&&res!=result)
           return true;
        else
            return false;
    }
    else{
        for(int i=index;i<length;i++){
            swap(s[i],s[index]);
            if(is(index+1,s,length))
                return true;
            swap(s[i],s[index]);
        }
        return false;
    }
}
int main(){
    char str[10];
    int m;
    cin>>m;
    while(m--){
        cin>>str;
        result=Integer(str);
        int length=strlen(str);
        if(is(0,str,length))
            cout<<"Possible"<<endl;
        else
            cout<<"Impossible"<<endl;
    }
}

发表于 2022-03-05 11:58:10 回复(0)
提交观点

问题信息

数组 模拟 穷举 网易 算法工程师 2018
上传者：小小
难度：
2条回答 1470浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号