首页 > 试题广场 >

多多的数字组合

[编程题]多多的数字组合
  • 热度指数:7892 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
多多君最近在研究某种数字组合:
定义为:每个数字的十进制表示中(0~9),每个数位各不相同且各个数位之和等于N。
满足条件的数字可能很多,找到其中的最小值即可。
多多君还有很多研究课题,于是多多君找到了你--未来的计算机科学家寻求帮助。

数据范围:
进阶:空间复杂度 ,时间复杂度

输入描述:
共一行,一个正整数N,如题意所示,表示组合中数字不同数位之和。
(1 <= N <= 1,000)


输出描述:
共一行,一个整数,表示该组合中的最小值。
如果组合中没有任何符合条件的数字,那么输出-1即可。
示例1

输入

5

输出

5

说明

符合条件的数字有:5,14,23,32,41
其中最小值为5
示例2

输入

12

输出

39

说明


示例3

输入

50

输出

-1

说明

没有符合条件的数字 (T▽T) 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int flag=9;
    int sum=0;
    int i=0;
    while(flag>0){
        if(n <= flag) {
            sum += n*pow(10,i);
            cout << sum;
            return 0;
        }
        else if(n>flag){
            sum += flag*pow(10,i);
            n = n-flag;
            --flag;
            ++i;
        }
    }
    cout <<-1;
    return 0;
}
编辑于 2022-05-23 16:26:42 回复(1)
# include<iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    if(n>45){
        cout << -1 <<endl;
        return 0;
    }else{
        int cur = 9;
        int ans =0;
        int cnt =1;
        while(n>cur){
            ans =ans + cnt*cur;
            cnt *= 10;
            n = n-cur;
            cur--;
        }
        ans = ans+ cnt*n;
        cout << ans <<endl;
    }
}

发表于 2021-06-09 16:03:46 回复(0)
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        //每个数位各不相同且各个数位之和等于N——1+2+3+4+5+6+7+8+9 = 45,如果大于45一定会重复
        if(N > 45){
            System.out.println(-1);
            return;
        }
        //如果N<10,可以直接返回数字本身
        if(N < 10){
            System.out.println(N);
            return;
        }
        //右侧数位越大,越能保证左侧数位越小,越能保证整个数最小
        int nums = 0;
        int digit = 0;
        for(int i = 9; i>0; i--){
            if(N != 0 && i <= N){
                N -= i;
                nums += (int)Math.pow(10,digit)*i;
                digit++;
            }
        }
        System.out.println(nums);
    }
}

发表于 2021-05-21 15:35:05 回复(4)
暴力法求得前45个值,存入数组中,时间复杂度O(1)
import java.util.*;
  
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n < 10) {
            System.out.println(n);
            return;
        }
        if (n > 45) {
            System.out.println(-1);
            return;
        }
        String s = "1, 2, 3, 4, 5, 6, 7, 8, 9, 19, 29, 39, 49, 59, 69, 79, 89, 189, 289, 389, 489, 589, 689, 789, 1789, 2789, 3789, 4789, 5789, 6789, 16789, 26789, 36789, 46789, 56789, 156789, 256789, 356789, 456789, 1456789, 2456789, 3456789, 13456789, 23456789, 123456789";
        String[] strings = s.split(",\\s");
        System.out.println(strings[n - 1]);
    }
}


发表于 2021-05-26 21:44:20 回复(5)
最简洁python代码 -> 参考迭代思想:
当x小于等于当前计数值时结束递归,否制一直处于递减模式。
def compute(x, num):
    if x <=num: return x
    else: return num + 10 * compute(x - num, num-1)

if __name__ == "__main__":
    x = int(input())
    if (x > 45): print(-1)
    else: print(compute(x, 9))



编辑于 2021-07-20 11:25:53 回复(1)
import java.util.Scanner;

/**
 * @author xq
 * @create 2021-05-20-15:13
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        if (N > 45){
            System.out.println(-1);
            System.exit(0);
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 9; i > 0; i--) {
            if (N>=i){
                N-=i;
                stringBuilder.insert(0,i);
            }
        }
        System.out.println(stringBuilder.toString());
    }
}

发表于 2021-06-06 21:31:24 回复(0)
小于10的数字直接返回
因为 1+2+3+4+5+6+7+8+9=45,所以大于45的数字直接返回-1
右边数越大,其结果越小,循环9到1,得到最终结果
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int getMinByN(int N) {
	if (N < 10) return N;
	if (N > 45) return -1;
	int m = N;
	vector<int> stk;
	for (int i = 9; i > 0; i--) {
		if (m != 0 && i<=m) {
			stk.push_back(i);
			m -= i;
		}
	}
	int res = 0;
	for (int i = 0; i < stk.size(); i++) {
		res += stk[i] * pow(10, i);
	}
	return res;
}

int main() {
	int N;
	cin >> N;
	int res = getMinByN(N);
	cout << res << endl;
	system("pause");
	return 0;
}


发表于 2021-05-14 11:15:50 回复(7)
这个题N能取到1000真的是唬人,要求数字的每一位都不相同,最大也就是9位数123456789,从1加到9等于45,45以上全部都输出-1,10以下全部输出N,要费点心思的只有10~45的N。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if(n < 10){
            System.out.println(n);
        }else if(n > 45){
            System.out.println(-1);
        }else{
            int num = 0;
            int index = 0;
            for(int i = 9; i > 0; i--){
                // 从9开始自减遍历,将大数放在低位来保证结果最小
                if(n > 0 && i <= n){
                    n -= i;      // i用完了就减掉
                    num += (int) Math.pow(10, index) * i;
                    index ++;
                }
            }
            System.out.println(num);
        }
    }
}
scala版
import scala.io.StdIn

object Main {
    def main(args: Array[String]): Unit = {
        var n = StdIn.readInt
        if(n < 10){
            println(n)
        }else if(n > 45){
            println(-1)
        }else{
            var num = 0
            var index = 0
            for(i <- 9 to 1 by -1){
                if(n > 0 && n >= i){
                    n -= i
                    num += (i * math.pow(10, index)).toInt
                    index += 1
                }
            }
            println(num)
        }
    }
}

发表于 2021-08-29 17:14:09 回复(1)
N=input()
N=int(N)
if N>0 and N<=17:
    m=N//9
    n=N%9
    print((n+1)*10**m-1)
elif N<=24:
    n=N-17
    print((n+1)*10**2-11)
elif N<=30:
    n=N-24
    print((n+1)*10**3-211)
elif N<=35:
    n=N-30
    print((n+1)*10**4-3211)
elif N<=39:
    n=N-35
    print((n+1)*10**5-43211)
elif N<=42:
    n=N-39
    print((n+1)*10**6-543211)
elif N<=44:
    n=N-42
    print((n+1)*10**7-6543211)
elif N==45:
    print(123456789)
else:
    print(-1)


发表于 2021-07-20 11:34:28 回复(0)
最简代码
import java.util.*; 
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        // 根据  每个数位各不相同 可得  123456789 是最小的不重复组合 相加为45 所以 1<=N<=45
        //打印值
        String dy="-1";
            if(N<=45&&N>=1){
            dy="";
            f:for(int i =9;i>=1;i--){
                //不匹配则进去下一循环
                if(i>N){continue f;}
                    N=N-i;
                    dy=i+dy;
                 //匹配成功结束循环
                    if(N==0){break f;}
                }
           }
       System.out.println(dy);
    }
}
编辑于 2021-06-28 11:43:58 回复(0)
#include <stdio.h>
int main()
{
   int x, res=0;
   scanf("%d",&x);
  res = hhh(x);
    printf("%d",res);
}
int hhh(int x){
     int  res=0,base=1;
    if(x<10) return x;
   if(x>45) {
       return -1;
   }
   for(int i = 9;i>0;i--){
       if(x){
           if((x-i)>=0){
               x=x-i;
               res = res+base*i;
               base = base*10;
           }
           else continue;
       }
       else break;
   }
   return res;
}
发表于 2021-07-16 15:42:40 回复(0)
#include<stdio.h>

c语言版本~
int main(void){
	
	int N;
	while(~scanf("%d",&N) != 0)
	if(N>45){
		printf("-1");
		return 0;
	}else{
		double s[45] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 19, 29, 39, 49, 59, 69, 79, 89, 189, 289, 389, 489, 589, 689, 789, 1789, 2789, 3789, 4789, 5789, 6789, 16789, 26789, 36789, 46789, 56789, 156789, 256789, 356789, 456789, 1456789, 2456789, 3456789, 13456789, 23456789, 123456789};	
		printf("%0.0f",s[N-1]);
		return 0;		
	}
}

发表于 2021-07-01 08:14:46 回复(0)
添加一个Python的解法,4个题只做出1个,有点丢人,整体思路和楼上老哥一样,10以下,45以上直接输出,中间的部分先给出一个几乎是递增的序列,和为N,此时这个数是满足条件的数里面最大的,然后不断地降低数字的位数,直到无法再降低为止。具体操作是从最低位开始,依次向前面的位求和,如果求和结果在1-9之间且没有出现过,则保留和,将两个加数删除,依次类推,每减少一位后注意排序即可。

N = int(input())
list = [1,2,3,4,5,6,7,8,9]
if N<10:
    print(N)
elif N>45:
    print(-1)
else:
    flag = -1
    temp = 0
    for i in list:
        temp = temp + i
        if N-temp>0 and N-temp<=9:
            flag = N-temp
            break
    templist = list[0:i]
    templist.append(flag)
    while 1:
        lastlen = len(templist)
        for j in range(len(templist)-1,0,-1):
            k = j - 1
            while templist[j] + templist[k] >= 10&nbs***bsp;templist[j] + templist[k]  in templist:
                k = k -1
                if k < 0:
                    break
            if templist[j] + templist[k] < 10 and templist[j] + templist[k] not in templist:
                templist.append(templist[j]+templist[k])
                remove1 = templist[j]
                remove2 = templist[k]
                templist.remove(remove1)
                templist.remove(remove2)
                templist.sort()
                break
        newlen = len(templist)
        if lastlen==newlen:
            break
    result = 0
    for inum in range(len(templist) - 1, -1,-1):
        result = templist[inum]*(10**(len(templist) - 1-inum)) + result
    print(result)


发表于 2021-05-10 21:54:40 回复(1)
Java解析,可知组合数最长可以有10位,例如1023456789、1203456789等等。这个最长的组合数的数位和一定为45,所以,我们只用考虑N取值在45及45以下的,以上直接返回-1。当N确定,我们想得到一个最小的组合数,那么我们希望这个数的长度越小越好,所以0直接排除,因为它不为数位做贡献且拉长数字长度。我们需要将1-9中尽可能将大的数塞进组合数中,那么思路就清晰了
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();
        sc.close();
        if (input>45){
            System.out.println(-1);
            return;
        }
        if (input<=9){
            System.out.println(input);
            return;
        }
        //  欲使得到的数最小,我们应尽量使越高的位的数字越小
        // 即最后得到的数看起来像是一个递增的数列
        // 换言之,低位的数越大越好
        // 即个位最好为9,十位最好为8(如果存在更高的位的话)
        int res = 0;//拼接结果
        int bit = 0;
        while (input>9-bit){
            res+=(9-bit)*Math.pow(10,bit);
            input-=9-bit++;
        }
        res+=input*Math.pow(10,bit);
        System.out.println(res);
    }
}


发表于 2021-05-08 22:20:46 回复(0)
n = int(input())
after_minize = n
number_mut = 9
result = 0
i = 0
if n < 10:
    print(n)
elif n > 45:
    print(-1)
else:
    while after_minize > 9:
        result = (10**i) * number_mut + result
        i = i + 1
        after_minize = after_minize - number_mut
        number_mut = number_mut - 1

    if after_minize < number_mut:
        result = result + after_minize * (10**i)
        print(result)
    else:
        a = after_minize
        while after_minize > number_mut:
            after_minize = after_minize - 1
        result = result + after_minize * (10**i)
        number_mut = number_mut - 1
        i = i + 1

        after_minize = a - after_minize
        b = after_minize
        while after_minize > number_mut:
            after_minize = after_minize - 1
        result = result + after_minize * (10**(i)) + (b-after_minize) * (10**(i+1))
        print(result)
发表于 2023-03-29 14:54:57 回复(0)
C++
#include <iostream>
using namespace std;

int main() {
    int a;
    while (cin >> a) { // 注意 while 处理多个 case
        if(a > 45) {
            cout<<-1<<endl;
            continue;
        }            
        int sum = 0;
        int d = 9;
        int e = 1;
        while(a > d) {
            a -= d;
            sum += e*d;
            d--;
            e *= 10;
        }
        sum += e*a;
        cout<<sum<<endl;
    }
}

发表于 2023-03-15 10:40:02 回复(0)
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        if (n < 10) {
            System.out.println(n);
        } else if (n <= 45) {
            int i = 9, ans = 0, temp = 1;
            while (n > i) {
                ans += i * temp;
                n -= i;
                temp *= 10;
                i--;
            }
            ans += n * temp;
            System.out.println(ans);
        } else {
            System.out.println(-1);
        }
    }
}

发表于 2023-03-12 16:08:43 回复(0)
贪心算法,大的数放低位,小的数放高位,依次放9,8,7,6,...., 直至n放完

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        if (n > 45) {
            System.out.println(-1);
            return;
        }

        int t = 1;
        int res = 0;
        int a = 9;
        while (n != 0) {
            if (n > a) {
                n -= a;

            } else {
                a = n;
                n = 0;
            }
            res += t * a;
            t *= 10;
            a--;
        }

        System.out.println(res);
    }
}


发表于 2023-03-11 21:30:41 回复(0)
var compute = function(n){
    let index = 0;//组合数的第几位,比如1234,4在index=0那个位置
    let num = 0;//返回的最小数
    for (let i = 9; i > 0; i--) {//从9开始自减遍历,将大数放在最低位来保证结果最小
        if (n > 0 && i <= n) {
            n -= i;
            num += Math.pow(10, index) * i;
            index++;
        }
    }
    return num;
}
let n = parseInt(readline());//读取输入,并将字符转换为整数
if (n < 10) print(n);
else if (n > 45) {//要求数字的每一位都不同,所以最大1+2+3+4+5+6+7+8+9=45
    print(-1);
}
else print(compute(n))

编辑于 2023-03-04 22:07:21 回复(1)
let N = +readline()
// 每个数位各不相同
if(N > 45){
    print(-1);
}else if(N<10){
    print(N);
}else{
    //组合值==N, 组合的大数放在低位
    let arr = [];
    for(let i=9;i>0;i--){
        if(N >= i){
            N -= i;
            arr.unshift(i);//先进的放在低位
        }
    }
    print(arr.join(""))
}


发表于 2022-08-29 17:23:25 回复(0)

热门推荐

通过挑战的用户