网站关键词在哪里修改,做网站开发的,做语文高考题网站,企业商标图案大全Hey编程小伙伴们#x1f44b;#xff0c;今天我要带大家一起解锁力扣上的一道有趣题目—— 美丽下标对的数目 - 力扣 (LeetCode)。这不仅是一次编程挑战#xff0c;更是一次深入理解欧几里得算法判断互质的绝佳机会#xff01;#x1f389;
问题简介
题目要求我们给定一…Hey编程小伙伴们今天我要带大家一起解锁力扣上的一道有趣题目—— 美丽下标对的数目 - 力扣 (LeetCode)。这不仅是一次编程挑战更是一次深入理解欧几里得算法判断互质的绝佳机会
问题简介
题目要求我们给定一个整数数组 nums找出所有满足特定条件的下标对。这里的特定条件是如果 nums[i] 的第一个数字和 nums[j] 的最后一个数字互质那么我们称这对下标为“美丽下标对”。
互质数学中的“独行侠”♂️
在数学的世界里如果两个数的最大公约数GCD是1我们称这两个数为互质的。换句话说它们之间没有其他公共的“朋友”来整除它们1是它们唯一的公约数。️♂️
欧几里得算法追溯GCD的足迹
欧几里得算法是一种非常高效的计算两个正整数最大公约数的方法。它的基本思想是两个正整数a和b假设ab的最大公约数与b和a%ba除以b的余数的最大公约数相同。
互质的判断逻辑
这里我们深入探讨一下为什么通过欧几里得算法可以判断两个数是否互质。互质的定义是两个数的最大公约数为1。欧几里得算法的核心在于它递归地将问题规模缩小直到无法再分。当较小的数变为1时如果此时较大的数也是1那么这两个数就是互质的。
算法步骤
开始我们有两个整数a和b其中a是较大的数。计算余数我们计算a除以b的余数记为r即 a % b。递归替换我们将b的值赋给a将r的值赋给b然后重复这个过程。结束条件当b变为0时a的值就是我们要找的最大公约数。
举个例子
假设我们要判断35和18是否互质
我们开始计算35除以18的余数得到17。然后我们用18除以17的余数得到1。最后我们用17除以1余数为0此时18原来的b是1这意味着35和18的最大公约数是1所以它们是互质的。
通过这种方式欧几里得算法不仅帮助我们找到了两个数的最大公约数也让我们能够判断这两个数是否互质。这是一种既简洁又高效的方法非常适合在编程中实现。
代码实现(scala)
object Solution {def countBeautifulPairs(nums: Array[Int]): Int {val pairs for {i - nums.indicesj - (i 1) until nums.length} yield (i, j)pairs.filter { case (i, j) val (firstDigit, secondDigit) (nums(i).toString.charAt(0).asDigit, nums(j) % 10)gcd(firstDigit, secondDigit) 1}.length}def gcd(a: Int, b: Int): Int if (b 0) a else gcd(b, a % b)}#算法 #力扣 #质数 #编程技巧
