LeetCode 365. 水壶问题

Categories:

题目描述
思路分析
1. 解法一：贝祖定理（推荐）
相似题目

题目描述

✅ 365. 水壶问题

思路分析

解法一：贝祖定理（推荐）

核心思路：

若 z 能由 x 和 y 表示，则必须满足 z <= x + y。

且 z 必须是 gcd(x, y) 的倍数。

直接计算即可判断可行性。

复杂度分析：

时间复杂度：O(log min(x, y))，计算最大公约数。

空间复杂度：O(1)。

class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        if (z == 0) {
            return true;
        }
        if (x + y < z) {
            return false;
        }
        if (x == 0 || y == 0) {
            return z == x || z == y;
        }
        return z % gcd(x, y) == 0;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}

func canMeasureWater(x int, y int, z int) bool {
	if z == 0 {
		return true
	}
	if x+y < z {
		return false
	}
	if x == 0 || y == 0 {
		return z == x || z == y
	}
	return z%gcd(x, y) == 0
}

func gcd(a int, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

相似题目

题目	难度	考察点
149. 直线上最多的点数	困难	最大公约数
365. 水壶问题	中等	数学
780. 到达终点	困难	数学
598. 范围求和 II	简单	数学
1006. 笨阶乘	中等	数学

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/96843432