6466. 美丽下标对的数目

题目描述

描述：给你一个下标从 0 开始的整数数组 nums 。如果下标对 i、j 满足 0 ≤ i < j < nums.length ，如果 nums[i] 的 第一个数字 和 nums[j] 的 最后一个数字 互质 ，则认为 nums[i] 和 nums[j] 是一组 美丽下标对 。

返回 nums 中 美丽下标对 的总数目。

对于两个整数 x 和 y ，如果不存在大于 1 的整数可以整除它们，则认为 x 和 y 互质 。换而言之，如果 gcd(x, y) == 1 ，则认为 x 和 y 互质，其中 gcd(x, y) 是 x 和 k 最大公因数 。

示例 1：

输入：nums = [2,5,1,4]
输出：5
解释：nums 中共有 5 组美丽下标对：
i = 0 和 j = 1 ：nums[0] 的第一个数字是 2 ，nums[1] 的最后一个数字是 5 。2 和 5 互质，因此 gcd(2,5) == 1 。
i = 0 和 j = 2 ：nums[0] 的第一个数字是 2 ，nums[1] 的最后一个数字是 1 。2 和 5 互质，因此 gcd(2,1) == 1 。
i = 1 和 j = 2 ：nums[0] 的第一个数字是 5 ，nums[1] 的最后一个数字是 1 。2 和 5 互质，因此 gcd(5,1) == 1 。
i = 1 和 j = 3 ：nums[0] 的第一个数字是 5 ，nums[1] 的最后一个数字是 4 。2 和 5 互质，因此 gcd(5,4) == 1 。
i = 2 和 j = 3 ：nums[0] 的第一个数字是 1 ，nums[1] 的最后一个数字是 4 。2 和 5 互质，因此 gcd(1,4) == 1 。
因此，返回 5 。

示例 2：

输入：nums = [11,21,12]
输出：2
解释：共有 2 组美丽下标对：
i = 0 和 j = 1 ：nums[0] 的第一个数字是 1 ，nums[1] 的最后一个数字是 1 。gcd(1,1) == 1 。
i = 0 和 j = 2 ：nums[0] 的第一个数字是 1 ，nums[1] 的最后一个数字是 2 。gcd(1,2) == 1 。
因此，返回 2 。

提示：

2 <= nums.length <= 100
1 <= nums[i] <= 9999
nums[i] % 10 != 0

解题思路

思路：最直观的想法是，使用first记录每个数字的第一位，使用last记录每个数字的最后一位，然后两层循环，判断gcd(first[i],last[j])是否等于1。

class Solution {
public:int countBeautifulPairs(vector<int>& nums) {int n=nums.size();//存储数字第一位vector<int> first(n);//存储数字最后一位vector<int> last(n);for(int i=0;i<n;i++){first[i]=to_string(nums[i])[0]-'0';last[i]=nums[i]%10;}int res=0;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(gcd(first[i],last[j])==1)res++;}}return res;}
};

总结：获取数字的第一位可以先将数字转换为字符串再取第一位，即to_string(nums[i])[0]-‘0’；获取数字的最后一位可以直接nums[i]%10；判断数字x和y是否互质可以使用gcd(x,y)来判断，如果等于1则是互质，反之不是。

6910. 将数组划分成若干好子数组的方式

题目描述

描述：给你一个二元数组 nums 。

如果数组中的某个子数组 恰好 只存在 一 个值为 1 的元素，则认为该子数组是一个 好子数组 。

请你统计将数组 nums 划分成若干 好子数组 的方法数，并以整数形式返回。由于数字可能很大，返回其对 109 + 7 取余 之后的结果。

子数组是数组中的一个连续 非空 元素序列。

示例 1：

输入：nums = [0,1,0,0,1]
输出：3
解释：存在 3 种可以将 nums 划分成若干好子数组的方式：
- [0,1] [0,0,1]
- [0,1,0] [0,1]
- [0,1,0,0] [1]

示例 2：

输入：nums = [0,1,0]
输出：1
解释：存在 1 种可以将 nums 划分成若干好子数组的方式：
- [0,1,0]

提示：

1 <= nums.length <= 105
0 <= nums[i] <= 1

解题思路

思路：最直观的想法是，乘法原理。其需要在每两个1之间画一个分割线，如果两个1之间有x个0则可以画x+1个分割线，最后的结果即为这多个x+1的乘积。使用一个变量prev表示上一个数字1的位置，初始为-1；使用一个变量cnt表示当前数字1的数量，初始为0；使用一个变量res表示分割方案数，初始为1。遍历数字数组，如果当前数字为1，则将cnt加一，如果cnt大于1则需要计算两个1之间的分割线数，其可以使用(i-prev)实现，然后乘以res，再更新上一个数字1的位置为当前数字1的位置，最后如果数字1的数量小于1则需要将res设置为0，比如数字数组[0,0]。

class Solution {
public:const int mod=1e9+7;int numberOfGoodSubarraySplits(vector<int>& nums) {//表示当前数字1的数量int cnt=0;//表示上一个数字1的位置int prev=-1;//表示分割方案数int res=1;int n=nums.size();for(int i=0;i<n;i++){if(nums[i]==1){cnt++;if(cnt>1)res=(long long)(res)*(i-prev)%mod;prev=i;}}if(cnt<1)res=0;return res;}
};

总结：乘法原理。