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

更新于： 2019年11月22日

428 次查看

开启您的 职业生涯

完成课程获得认证

开始学习
广告