数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会科学
时装
法律在 C++ 中检查它是否为一个好的数组
假设我们有一个名为 nums 的正整数数组。我们必须选择 nums 的某个子集，然后将每个元素乘以一个整数并添加所有这些数字。如果通过任何可能的子集和乘数我们可以从数组中得到 1 的和，那么该数组将是一个好数组。
我们必须检查该数组是否好。
因此，如果输入类似于 [12,23,7,5]，则输出将为 True，这是因为如果我们取数字 5 和 7，则 5*3 + 7*(-2) = 1
为了解决这个问题，我们将遵循以下步骤 −
g := nums[0]
对于初始化 i := 1，当 i < nums 的大小，更新（将 i 增加 1），则 −
g := g 和 nums[i] 的的最大公约数
当 g 为 1 时，返回 true
让我们看看以下实现来更好地理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int gcd(int a, int b){
return !b ? a : gcd(b, a % b);
}
bool isGoodArray(vector<int>& nums){
int g = nums[0];
for (int i = 1; i < nums.size(); i++)
g = gcd(g, nums[i]);
return g == 1;
}
};
main(){
Solution ob;
vector<int> v = {12,23,7,5};
cout << (ob.isGoodArray(v));
}输入
{12,23,7,5}输出
1
更新于： 04-Jun-2020
2K+ 浏览量
广告