AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

LeetCode 858. Mirror Reflection    原题链接    中等

作者: 作者的头像   wzc1995 ,  2019-01-19 08:19:10 ,  所有人可见 ,  阅读 1326


1


题目描述

有一个特殊的正方形房间,每面墙上都有一面镜子。除西南角以外,每个角落都放有一个接受器,编号为 0,1,以及 2。

正方形房间的墙壁长度为 p,一束激光从西南角射出,首先会与东墙相遇,入射点到接收器 0 的距离为 q。

返回光线最先遇到的接收器的编号(保证光线最终会遇到一个接收器)。

样例

输入:p = 2, q = 1
输出:2
解释:这条光线在第一次被反射回左边的墙时就遇到了接收器 2。

注意

  • 1 <= p <= 1000
  • 0 <= q <= p

算法

(找规律) $O(\log p + \log q)$
  1. 求出 p 和 q 的最小公倍数 lcm,令 x = lcm / p, y = lcm / q。
  2. 如果 y 为奇数,则说明最终会被右墙的接收器接收,此时若 x 也为奇数,则说明是右上角,否则是右下角。
  3. 如果 y 为偶数,如果题目保证了一定能被接收,则一定是左上角的接收器。

时间复杂度

  • 算法核心在求最大公约数,时间复杂度为 $O(\log p + \log q)$。

空间复杂度

  • 由于使用了递归辗转相处,故需要额外的 $O(\log p + \log q)$ 的栈空间。

C++ 代码

class Solution {
public:
    int gcd(int x, int y) {
        return y ? gcd(y, x % y) : x;
    }

    int mirrorReflection(int p, int q) {
        int lcm = p * q / gcd(p, q);
        int x = lcm / p, y = lcm / q;
        if (y % 2 == 1) {
            if (x % 2 == 1)
                return 1;
            return 0;
        }
        return 2;
    }
};

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息