数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中将数字切割成多个部分，使得最大数量的部分能被3整除
在这个问题中，我们给定一个很大的整数（最多105位）。我们的任务是打印所需的总切割次数，使得被3整除的部分最多。
让我们举个例子来理解这个问题
输入 − 9216
输出 − 3
解释 − 数字被分成 9|21|6。
为了解决这个问题，我们必须从数字的最低有效位开始，也就是数字的最后一位。在这里，我们将找到最小的能被三整除的数字。然后根据它更新计数。
示例 − 如果arr[i]构成一个能被3整除的数字，那么我们将增加计数并移动到数字的下一位。如果arr[i]不能被3整除，那么我们将它与下一位组合起来，并检查能否被3整除。
3的倍数 − 如果一个数字的各位数字之和能被三整除，则该数字能被三整除。
示例
程序演示我们解决方案的实现
#include <bits/stdc++.h>
using namespace std;
int countMaximum3DivisibleNumbers(string number){
int n = number.length();
vector<int> remIndex(3, -1);
remIndex[0] = 0;
vector<int> counter(n + 1);
int r = 0;
for (int i = 1; i <= n; i++) {
r = (r + number[i-1] - '0') % 3;
counter[i] = counter[i-1];
if (remIndex[r] != -1)
counter[i] = max(counter[i], counter[remIndex[r]] + 1);
remIndex[r] = i+1;
}
return counter[n];
}
int main() {
string number = "216873491";
cout<<"The number of 3 divisible number created by cutting "<<number<<" are : " <<countMaximum3DivisibleNumbers(number);
return 0;
}输出
The number of 3 divisible number created by cutting 216873491 are : 5
更新于: 2020年4月17日
97 次浏览
广告