LeetCode 每日一题 2748. 美丽下标对的数目

Hey编程小伙伴们👋，今天我要带大家一起解锁力扣上的一道有趣题目—— 美丽下标对的数目 - 力扣 (LeetCode)。这不仅是一次编程挑战，更是一次深入理解欧几里得算法判断互质的绝佳机会！🎉

问题简介

题目要求我们给定一个整数数组 nums，找出所有满足特定条件的下标对。这里的特定条件是：如果 nums[i] 的第一个数字和 nums[j] 的最后一个数字互质，那么我们称这对下标为“美丽下标对”。🌟

互质：数学中的“独行侠”🦸‍♂️

在数学的世界里，如果两个数的最大公约数（GCD）是1，我们称这两个数为互质的。换句话说，它们之间没有其他公共的“朋友”来整除它们，1是它们唯一的公约数。🕵️‍♂️

欧几里得算法：追溯GCD的足迹🔍

欧几里得算法是一种非常高效的计算两个正整数最大公约数的方法。它的基本思想是：两个正整数a和b（假设a>b）的最大公约数与b和a%b（a除以b的余数）的最大公约数相同。🔄

互质的判断逻辑🤔

这里我们深入探讨一下，为什么通过欧几里得算法可以判断两个数是否互质。互质的定义是两个数的最大公约数为1。欧几里得算法的核心在于它递归地将问题规模缩小，直到无法再分。当较小的数变为1时，如果此时较大的数也是1，那么这两个数就是互质的。🔑

算法步骤：

1. 开始：我们有两个整数a和b，其中a是较大的数。
2. 计算余数：我们计算a除以b的余数，记为r（即 a % b）。
3. 递归替换：我们将b的值赋给a，将r的值赋给b，然后重复这个过程。
4. 结束条件：当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.indices
            j <- (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)

}

#算法 #力扣 #质数 #编程技巧