位数求和

[编程题]位数求和

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

所有的长度为n的数中，各个位上的数字之和为m的这些数的和是多少呢。给定n和m，求这些数的和。

示例1

输入

2,3

输出

说明

12 + 21 +30 = 63

备注:

算法知识视频讲解

坚持就是yes

两种方法

第一种：暴力遍历的方法，对n位的数字全部遍历一遍，找到符合要求的数字，相加求总和，在这就不介绍了

第二种：回溯法，从上面的暴力遍历可知，他对很对没有必要判断的数字进行了判断，进行了很多无用功，所以时间效率并不高。

回溯法，举个例子，当n=3，m=10的时候，第一位最小是1，第二位是0，第三位只能是9，回溯，第一位依然是1，第二位此时变成1，第三位只能是8；依次往下，第二位是3...最后再回到第一位。

public class Solution {
    /**
     * 返回这样的数之和
     * @param n int整型 数的长度
     * @param m int整型 各个为之和
     * @return long长整型
     */
    long res=0;
    public long sum (int n, int m) {
        // write code here
        slove(n,m,0,0,0);
        return res;
    }
    //index用来做下标，表示我们此时做了几次迭代了，对应了n的位数
    //v表示前index位上的和，如果是12，则v=3,
    //cur表示前index的和，如果是12，则cur就是12
    public void slove(int n,int m,int index,int v,int cur){
        //前面n-1位的大小已经超过了m的大小，使得最后一位没值可填了
        if(m-v<0){
            return;
        }
        //对最后一位进行判断
        if(index==n-1){
            if(m-v<10){
                res+=cur*10+m-v;
                return;
            }else{
                //这种情况说明前面n-1位数的和太小了，使得最后一位即使补9都不够m的值
                return;
            }
        }
        //第一位数字可填1-9
        if(index==0){
            for(int i=1;i<=9;i++){
                slove(n,m,index+1,v+i,cur*10+i);
            }
        }else{
            //第一位数字之后可填0-9
            for(int i=0;i<=9;i++){
                slove(n,m,index+1,v+i,cur*10+i);
            }
        }
    }
}

发表于 2021-07-05 17:26:02 回复(0)

嗷嗷_

import java.util.*;

public class Main {
    
    public long sum (int n, int m) {
        if (n <= 0 || m <= 0) {
            return 0;
        }
        
        int start = (int)Math.pow(10, n - 1);
        int end = (int)Math.pow(10, n) - 1;
        
        long res = 0;
        for (int i = start; i <= end; i++) {
            if (isEqualToM(i, m)) {
                res += i;
            }
        }
        
        return res;
    }
    
    private boolean isEqualToM(int num, int target) {
        int count = 0;
        
        while (num > 0) {
            count += num %10;
            num /= 10;
        }
        
        return count == target;
    }
    
    public static void main(String[] args) {
        Main m = new Main();
        
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            String temp = cin.next();
            String[] a = temp.split(",");
            System.out.println(m.sum(Integer.valueOf(a[0]), Integer.valueOf(a[1])));
        }
    }
}

这题的输入输出有点奇怪？？

发表于 2021-07-03 22:00:00 回复(0)

Java

花落梦里

public long sum (int n, int m) {
        long res=0;
        int end=pow(10,n);
        for(int i=end/10;i<end;i++){
            int x=i,sum=0;
            while(x!=0){
                sum+=x%10;
                x=x/10;
            }
            if(sum==m) res+=i;
        }
        return res;
    }
    public int pow(int x, int n){//n可能会溢出？
        int res=1;
        while(n>0){
            if(n%2==1)
                res=res*x;
            x=x*x;
            n=n/2;
        }
        return res;
    }

发表于 2021-03-31 19:19:59 回复(0)