网站做哪些比较赚钱方法东莞百度搜索优化
LeetCode-1250. 检查「好数组」【数论，裴蜀定理】
- 题目描述：
- 解题思路一：裴蜀定理是：a*x+b*y=1。其中a,b是数组中的数，x,y是任意整数。如果a,b互质那么一定有解。问题即转换为寻找互质的数。
- 解题思路二：简化代码1
- 解题思路三：三行代码！
题目描述：
给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。
假如该和结果为 1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。
示例 1：
输入：nums = [12,5,7,23]
输出：true
解释：挑选数字 5 和 7。
53 + 7(-2) = 1
示例 2：
输入：nums = [29,6,10]
输出：true
解释：挑选数字 29, 6 和 10。
291 + 6(-3) + 10*(-1) = 1
示例 3：
输入：nums = [3,6]
输出：false
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
https://leetcode.cn/problems/check-if-it-is-a-good-array/description/
解题思路一：裴蜀定理是：ax+by=1。其中a,b是数组中的数，x,y是任意整数。如果a,b互质那么一定有解。问题即转换为寻找互质的数。
class Solution {
public:bool isGoodArray(vector<int>& nums) {int s=0;for (int x : nums) {s=gcd(x,s);if(s==1) return true;//剪枝}return s==1;}int gcd(int a, int b) {//辗转相除法if(b==0) return a;return gcd(b,a%b);}
};
时间复杂度：O(n)
空间复杂度：O(1)
解题思路二：简化代码1
class Solution {
public:bool isGoodArray(vector<int>& nums) {int s=0;for (int x : nums) {s=gcd(x,s);if(s==1) return true;//剪枝}return s==1;}
};
时间复杂度：O(n)
空间复杂度：O(1)
解题思路三：三行代码！
class Solution {
public:bool isGoodArray(vector<int>& nums) {int s=0;for (int x : nums) s=gcd(x,s);return s==1;}
};
时间复杂度：O(n)
空间复杂度：O(1)