[44]神奇数-京东2018秋

1.题目描述

东东在一本古籍上看到有一种神奇数,如果能够将一个数的数字分成两组,其中一组数字的和 等于另一组数字的和,我们就将这个数称为神奇数。例如242就是一个神奇数,我们能够将这个数的数字分 成两组,分别是{2,2}以及{4},而且这两组数的和都是4.东东现在需要统计给定区间中有多少个神奇数,即 给定区间[l,r],统计这个区间中有多少个神奇数,请你来帮助他。

• 输入描述:
  输入包括一行,一行中两个整数l 和 r(1 ≤ l, r ≤ 10^9, 0 ≤ r - l ≤ 10^6),以空格分割 输出描述:
  输出一个整数,即区间内的神奇数个数
• 输入示例:

  1 50 
  

• 输出示例:

  4
  

2.题目解析

1. 要把数字按位转化成数组。
2. 每位数字累计求和
3. 数组中元素和是否能累加成半和。(01背包问题)

3.参考答案

自顶而下递归

#include <bits/stdc++.h> 
using namespace std; 
bool IsMagic(int i,int sum,int* nums){
    if(0 == sum) return true;
    if(0 > sum) return false;
    if(i < 0) return false;
    
    return IsMagic(i-1,sum-nums[i],nums)
         ||IsMagic(i-1,sum,nums);
}
bool check(int num) { 
    int nums[11]; // 把数字n按位存到s中
    int i = 0; // 下标
    int sum = 0; // 每位数字求和
    while(num > 0) { 
        nums[i] = num % 10; // 获取并保存每位数字 
        sum += nums[i++]; // 每位数字累计求和
        num /= 10; // 除去个位数字
    }
    // 每位数和是奇数，则肯定不是神奇数
    if(sum%2) return false;
    // 从每位数字中取出数字和是否为和的一半
    return IsMagic(i-1,sum/2,nums); 
} 
 
int main() { 
    int l = 0;
    int r = 0;
    scanf("%d%d",&l,&r);
    int res = 0; 
    for(int i = l; i <= r; ++i) { // 遍历[l,r]中所有数字
        if(check(i)) ++res; 
    } 
    printf("%d\n",res); 
    return 0;
}

自顶而下递归(备忘录法/记忆化搜索)

#include <bits/stdc++.h> 
using namespace std; 
bool IsMagic(int i,int sum,int* nums,vector<bool>* dp){
    if(0 == sum) return true;
    if(0 > sum) return false;
    if(i < 0) return false;
    if(false != dp[i][sum]) return dp[i][sum];
    return dp[i][sum] = IsMagic(i-1,sum-nums[i],nums,dp)
         ||IsMagic(i-1,sum,nums,dp);
}
bool check(int num) { 
    int nums[11]; // 把数字n按位存到s中
    int i = 0; // 下标
    int sum = 0; // 每位数字求和
    while(num > 0) { 
        nums[i] = num % 10; // 获取并保存每位数字 
        sum += nums[i++]; // 每位数字累计求和
        num /= 10; // 除去个位数字
    }
    // 每位数和是奇数，则肯定不是神奇数
    if(sum%2) return false;
    // 从每位数字中取出数字和是否为和的一半  
    vector<bool> dp[i];
    fill_n(dp,i,vector<bool>(sum/2+1,false));
    return IsMagic(i-1,sum/2,nums,dp); 
} 
 
int main() { 
    int l = 0;
    int r = 0;
    scanf("%d%d",&l,&r);
    int res = 0; 
    for(int i = l; i <= r; ++i) { // 遍历[l,r]中所有数字
        if(check(i)) ++res; 
    } 
    printf("%d\n",res); 
    return 0;
}

自底而上递推

#include <bits/stdc++.h> 
using namespace std; 
bool IsMagic(int i,int sum,int* nums,vector<bool>* dp){
    for(int idx=1;idx<=i;++idx){
        for(int s=0;s<=sum;++s){
           if(s-nums[idx] == 0){
               dp[idx][s] = true;
           }else if(s-nums[idx]>0){
               dp[idx][s] = dp[idx-1][s-nums[idx]]||dp[idx-1][s];    
           }else{
               dp[idx][s] = dp[idx-1][s];
           }            
        }
    }
    return dp[i][sum];
}
bool check(int num) { 
    int nums[11]; // 把数字n按位存到s中
    int i = 0; // 下标
    int sum = 0; // 每位数字求和
    while(num > 0) { 
        nums[i] = num % 10; // 获取并保存每位数字 
        sum += nums[i++]; // 每位数字累计求和
        num /= 10; // 除去个位数字
    }
    // 每位数和是奇数，则肯定不是神奇数
    if(sum%2) return false;
    // 从每位数字中取出数字和是否为和的一半  
    vector<bool> dp[i];
    fill_n(dp,i,vector<bool>(sum/2+1,false));
    return IsMagic(i-1,sum/2,nums,dp); 
} 
 
int main() { 
    int l = 0;
    int r = 0;
    scanf("%d%d",&l,&r);
    int res = 0; 
    for(int i = l; i <= r; ++i) { // 遍历[l,r]中所有数字
        if(check(i)) ++res; 
    } 
    printf("%d\n",res); 
    return 0;
}

滚动数组优化

#include <bits/stdc++.h> 
using namespace std; 
bool IsMagic(int i,int sum,int* nums,bool* dp){
    for(int idx=1;idx<=i;++idx){
        for(int s=sum;s>=nums[idx];--s){
           if(s-nums[idx] == 0){
               dp[nums[idx]] = true;
           }else{
               dp[s] = dp[s-nums[idx]]||dp[s];    
           }            
        }
    }
    return dp[sum];
}
bool check(int num) { 
    int nums[11]; // 把数字n按位存到s中
    int i = 0; // 下标
    int sum = 0; // 每位数字求和
    while(num > 0) { 
        nums[i] = num % 10; // 获取并保存每位数字 
        sum += nums[i++]; // 每位数字累计求和
        num /= 10; // 除去个位数字
    }
    // 每位数和是奇数，则肯定不是神奇数
    if(sum%2) return false;
    // 从每位数字中取出数字和是否为和的一半  
    bool dp[sum/2+1];
    fill_n(dp,sum/2+1,false);
    return IsMagic(i-1,sum/2,nums,dp); 
} 
 
int main() { 
    int l = 0;
    int r = 0;
    scanf("%d%d",&l,&r);
    int res = 0; 
    for(int i = l; i <= r; ++i) { // 遍历[l,r]中所有数字
        if(check(i)) ++res; 
    } 
    printf("%d\n",res); 
    return 0;
}

牛客题目