C ++中数字小于Y的最小集合数

问题陈述

给定一串连续的数字和一个数字Y,任务是找到最小集合的数量,使每个集合遵循以下规则-

  • 集应包含连续数字

  • 不能多次使用任何数字。

  • 集合中的数字不得超过Y。

示例

如果str =“ 1234”且Y = 20,则答案为3,如下所示:

{12} {3}和{4}

算法

  • 将字符串转换为数字

  • 如果该数字不大于Y,则标记f = 1

  • 如果数字超过Y,则在f = 1时增加计数,并将f重新初始化为0,并将num初始化为s [i]-'0'或num初始化为0

  • 完全迭代字符串后,如果f为1,则增加计数

示例

#include <iostream>
#include <string>
using namespace std;
int getMinSets(string str, int y) {
   int cnt = 0;
   int num = 0;
   int l = str.length();
   int f = 0;
   for (int i = 0; i < l; ++i) {
      num = num * 10 + str[i] - 48;
      if (num <= y) {
         f = 1;
         continue;
      }
      if (f) {
         ++cnt;
      }
      num = str[i] - '0';
      f = 0;
      if (num <= y) {
         f = 1;
      } else {
         num = 0;
      }
   }
   if (f) {
      ++cnt;
   }
   return cnt;
}
int main() {
   string str = "1234";
   int y = 20;
   cout << "Minimum sets = " << getMinSets(str, y) << endl;
   return 0;
}

输出结果

当您编译并执行上述程序时。它产生以下输出-

Minimum sets = 3