数位重排_网易笔试题

向宇回桌

C++因为有next_permutation，还是方便呀。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        string s_n = to_string(n);
        sort(s_n.begin(), s_n.end());
        bool flag = false;
        do {
            int p_num = stoi(s_n);
            if (p_num!=n && p_num%n==0) {
                flag = true;
                break;
            }
        } while (next_permutation(s_n.begin(), s_n.end()));
        cout << (flag ? "Possible" : "Impossible") << endl;
    }
    return 0;
}

发表于 2019-02-07 11:18:39 回复(0)

WAK

将n的每位存入vector并排序，将y = n*i(i=2~9)的每位另存入vector并排序，比较排序后的vector，若有相等的，则可能，若都不相等，则不可能。

   #include<iostream>  
   #include<string>  
   #include<vector>  
   #include<limits.h>  
   #include<algorithm>  
   using namespace std;  
   intmain(){  
       int n;  
       while(cin>>n){  
           for(int i = 0;i<n;i++){  
               int x;  
               cin>>x;  
               int b =x;  
               vector<int> vec1;  
               while(x>0){  
                   int temp = x%10;  
                   vec1.push_back(temp);  
                   x = x/10;  
               }  
               sort(vec1.begin(),vec1.end());  
               int *** = false;  
               for(int i = 2;i<10;i++){  
                   vector<int> vec2;  
                   int y = b*i;  
                   while(y>0){  
                       int temp = y%10;  
                       vec2.push_back(temp);  
                       y = y/10;  
                   }  
                   sort(vec2.begin(),vec2.end());  
                   if(vec1==vec2){  
                       *** = true;  
                       break;  
                   }  
               }  
               if(***)  
                   cout<<"Possible"<<endl;  
               else  
                   cout<<"Impossible"<<endl;  
           }  
       }  
       system("pause");  
       return0;  
   }  

编辑于 2018-07-23 10:35:01 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

bool isSame(int x, int y){
    vector<int> a, b;
    while(x){
        a.push_back(x%10);
        x /= 10;
    }
    while(y){
        b.push_back(y%10);
        y /= 10;
    }
    int n=a.size(), m=b.size();
    if(n!=m)
        return false;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for(int i=0;i<n;i++)
        if(a[i]!=b[i])
            return false;
    return true;
}

int main(){
    int t, x;
    scanf("%d", &t);
    while(t--){
        bool flag = false;
        scanf("%d", &x);
        for(int i=2;i<=9;i++){
            flag = isSame(x, x*i);
            if(flag)
                break;
        }
        if(flag)
            puts("Possible");
        else
            puts("Impossible");
    }
    return 0;
}

发表于 2020-09-08 11:55:15 回复(0)

黄宗文

python3

# 数位重排之后，是否是之前自己的倍数，假设是可以的，那可能是自己的多少倍呢
# 除去自身（1倍），还不可能到达10倍及以上，也就是只可能在2~9倍中选择，先计算出自身的2~9倍，看是否可以用自身数字重排获得即可
# 统一按照字典序排序，比较两个数字包含的每一位组合是否相同
def num_sort(ns):
    lns = sorted(list(ns))
    n = int(ns)
    for i in range(2, 10):
        if lns == sorted(list(str(n*i))):
            return 'Possible'
    else:
        return 'Impossible'
# 看输入输出，应该有个分离，现在这种写法，相当于输入一个就计算一个结果，但是花费的时间更少，而且能沟通过测试
for i in range(int(input())):
    print(num_sort(input()))

发表于 2019-08-15 21:36:48 回复(0)

offer菜鸟

思路：题目要求使用x的原始数字重排，即重排后的位数等于x的位数，
      即只需判断x的2到9倍中的数是否存在由x重排得到的数
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main()
{
    int t,mid,l;
    cin>>t;
    string s1,s2;
    while(t--)
    {
        cin>>mid;
        s1=to_string(mid);
        sort(s1.begin(), s1.end());
        for(int i=2;i<=10;i++)
        {
            l=i*mid;
            s2=to_string(l);
            if(s1.length()>s2.length())
            {
                cout<<"Impossible"<<endl;
                break;
            }
           
            else 
            {
                sort(s2.begin(), s2.end());
                if(s1==s2)
                {
                    cout<<"Possible"<<endl;
                    break;
                }
            }
            if(i==10)
            {
                cout<<"Impossible"<<endl;
            }
        }
    }
    return 0;
}

发表于 2019-05-27 21:38:16 回复(0)

啥玩意😭

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int t = input.nextInt();
        for(int j = 0;j<t;j++){
            int x = input.nextInt();
            boolean flag = true;
            for(int i =2;i<=9;i++){
                int y = x*i;
                if(Equal(x,y)){
                    System.out.println("Possible");
                    flag = false;
                    break;
                }
            }
            if(flag)
                System.out.println("Impossible");
        }
    }
    public static boolean Equal(int x,int y){
        String str = String.valueOf(x);
        String str1 = String.valueOf(y);
        if(str.length() != str1.length())
            return false;
        char[] s1 =str.toCharArray();
        
        char[] s2 =str1.toCharArray();
        Arrays.sort(s1);
        Arrays.sort(s2);
        for(int i =0;i<s1.length;i++){
            if(s1[i]!=s2[i])
                return false;
        }
        return true;
 
    }

}

发表于 2019-04-09 15:23:05 回复(0)

Python

华科平凡

python3解法

核心是找到一个数，这个数是原数的倍数，且组成数字与原来的数相同。例如1035和3105。
只需要将某个数从2乘到9，每一个结果都判断一下组成数字是否与原来相同。（乘到10位数都变了，肯定不满足条件，所以是阈值）

def judge(number):
    for i in range(2, 10):
        if sorted(str(number * i)) == sorted(str(number)):
            return True
    return False

for i in range(int(input())):
    print("Possible" if judge(int(input())) else "Impossible")

编辑于 2019-02-23 09:53:26 回复(5)

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)

C/C++

牛客549207409号

#include<iostream>
#include<string>
#include<algorithm>
int main()
{
int t;
long x;
while(std::cin>>t)
{
for(int i=0;i<t;i++)
{
std::cin>>x;
bool flag=false;
std::string s=std::to_string(x);
sort(s.begin(),s.end());
for(int j=2;j<=10;j++)
{
long a=j*x;
std::string t=std::to_string(a);
sort(t.begin(),t.end());
if(s==t)
{
std::cout<<"Possible"<<std::endl;
flag=true;
break;
}
}
if(flag==false)std::cout<<"Impossible"<<std::endl;
}

}
return 0;
}

发表于 2020-09-19 21:15:02 回复(0)

Runsen

import itertools

t = int(input())
# 题目要求使用x的原始数字重排，即重排后的位数等于x的位数，即只需判断x的2到9倍中的数是否存在由x重排得到的数
def f(s):
    x = itertools.permutations(s)
    for n in x:
        for k in range(2,10):
            a = "".join(list(n))
            if int(a) == (k*int(s)):
                return "Possible"
    return "Impossible"


i = 0
while i < t:
    s = input()
    print(f(s))
    i = i + 1

发表于 2020-09-10 21:06:45 回复(0)

223s

import java.util.*;

public class Main{


    public static void main(String[] args){

        Scanner s  = new Scanner(System.in);

        int t = s.nextInt();
        List<String> res = new ArrayList<>();
        for(int i=0;i<t;i++){
            int num = s.nextInt();
            int prud = 0;
            boolean flag = false;
            for(int j=2;j<10;j++){
                prud = num*j;
                if(equals(num,prud)){
                    flag = true;
                    break;
                }
            }
            if(flag){
                res.add("Possible");
            }else{
                res.add("Impossible");
            }
        }

        for (String re : res) {
            System.out.println(re);
        }

    }

    private static boolean equals(Integer x,Integer y){
        String a = x.toString();
        String b = y.toString();

        for(int i=0;i<a.length();i++){
            if(b.indexOf(a.charAt(i)) ==-1){
                return false;
            }
        }

        return true;
    }

}

本地测试半点问题都没有，提交上来就少输出，我傻了

发表于 2020-08-11 18:16:37 回复(0)

皮蛋秀柚秋

#include<bits/stdc++.h>
using namespace std;
int x;
int getLength(int x){
    int ans = 0;
    while(x){
        x/=10;
        ++ans;
    }
    return ans;
}
string s;
void dfs(int cur,int n,string& tmp,int& find,vector<int>& vis){
    if(cur==n){
        if(tmp!=s&&stoi(tmp)%x==0) find=1;
        return;
    }
    for(int i=0;i<n;++i){
        if(!vis[i]){
            vis[i]=1;
            tmp.push_back(s[i]);
            dfs(cur+1,n,tmp,find,vis);
            tmp.pop_back();
            vis[i]=0;
        }
    }
}
int main(){
    int t;;
    cin>>t;
    while(t--){
        cin>>x;
        int find = 0;
        int n = getLength(x);
        vector<int>vis(n,0);
        s = to_string(x);
        string tmp = "";
        dfs(0,n,tmp,find,vis);
        cout<<(find?"Possible":"Impossible")<<endl;
    }
    return 0;
}

发表于 2020-06-11 23:43:20 回复(0)

夏花爱秋叶

var n=parseInt(readline());
while(n>0){
    n--;
    var num=parseInt(readline());
    var old=String(num).split('').sort().join()
    // 遍历
    var flag=true;
    for(var j=2;j<10;j++){
        var sum=num*j;
        var mynew=String(sum).split('').sort().join()
        if(old==mynew){
            console.log("Possible")
            flag=false;
            break;
        }
    }
    if(flag){
        console.log("Impossible")
    }
}

发表于 2020-03-29 14:10:19 回复(0)

牛客761313044号

nn = int(input())
for i in range(nn):
n = input()
new = [str(int(n)*i) for i in range(2, 10)]
count = 0
for j in new:
if sorted(n) == sorted(j):
count += 1
if count > 0:
print('Possible')
else:
print('Impossible')

发表于 2020-03-10 05:43:33 回复(0)

渡口的小太阳

import java.util.HashMap;
import java.util.Scanner;

public clas***ain {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arrs=new int[n];

        for(int i=0;i<n;i++){
            arrs[i]=sc.nextInt();
        }
        for(int j:arrs){
            if(isPossible(j)){
                System.out.println("Possible");
            }else{
                System.out.println("Impossible");
            }
        }
    }

    private static boolean isPossible(int n){
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<10;i++){
            map.put(i,0);
        }
        int t=n;
        while(t>0){
            int val=map.get(t%10)+1;
            map.put(t%10,val);
            t/=10;
        }
        //用于恢复
        HashMap<Integer,Integer> mapTemp=new HashMap<>();
        for(int i=2;i<10;i++){
            int x=n*i;
            while(x>0){
                int val2=map.get(x%10);
                if(!mapTemp.containsKey(x%10)){
                    mapTemp.put(x%10,val2);
                }
                map.put(x%10,val2-1);
                x/=10;
            }
            for(int val:map.keySet()){
                if(map.get(val)!=0){
                    for(int j:mapTemp.keySet()){
                        map.put(j,mapTemp.get(j));
                    }
                    break;
                }
                if(val==9){
                    return true;
                }
            }
        }
        return false;
    }
}

发表于 2019-05-14 21:11:27 回复(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)

爱运动的妹妹

import sys
if __name__ == '__main__':
    n = input()
    i = 0
    while i < int(n):
        s = sys.stdin.readline().strip()
        if s == '':
            break
        if len(s) == 1:
            print('Impossible')
        else:
            j = 2
            res = str(int(s)*j)
            while len(res) <= len(s):
                j += 1
                res = str(int(s)*j)
                if set(res) == set(s)and len(res) <= len(s):
                    print('Possible')
                    break
            else:
                print('Impossible')

发表于 2019-04-15 17:02:31 回复(0)

𓆡𓆝𓆟𓆜𓆞𓆝𓆟𓆜20190403110475

//计算输入的数的2-9倍与原数据进行判断
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(reader.readLine());
        Random random = new Random();
        for (int i = 0; i < count; i++) {
            String s1 = reader.readLine();
            panduan(i, s1);
        }
    }

    public static void panduan(int i, String s1) {
        int num = Integer.parseInt(s1);
        int count=0;
        for (int j = 2; j <= 9; j++) {
            int x = num * j;
            String s2 = String.valueOf(x);
            if (s1.length() != s2.length()) {
                System.out.println("Impossible");
                break;
            } else {
                for (int k = 0; k < s1.length(); k++) {
                    if (!s1.contains(String.valueOf(s2.charAt(k)))) {
                        count++;
                        if (count == 8) {
                            System.out.println("Impossible");
                        }
                        break;
                    }
                    if (k == s1.length() - 1) {
                        System.out.println("Possible");
                        return;
                    }
                }
            }
        }
    }
}

发表于 2019-04-10 19:58:23 回复(0)

KronosChan

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        int ori=stoi(s),flag=0;
        sort(s.begin(),s.end());
        
        do{
            int num=stoi(s);
            if(num!=ori&&num%ori==0){
                flag=1;
                break;
            }
        }while(next_permutation(s.begin(),s.end()));
        if(flag)cout<<"Possible"<<endl;
        else cout<<"Impossible"<<endl;
    }
}

发表于 2019-04-03 20:20: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)

数位重排

输入描述:

输出描述:

输入

输出

python3解法

问题信息

热门推荐

通过挑战的用户

相关试题