Leetcode【858、1006】

作者: 牛奶芝麻 | 来源:发表于2019-07-17 23:56 被阅读0次

Leetcode【858、1006】
Leetcode 笨阶乘
LeetCode #1006 Clumsy Factorial
LeetCode 858. Mirror Reflection
感恩金钱涌入我的生活22
190304 用GEOquery从GEO数据库下载数据
858
858
④-858
858

问题描述：【Math】858. Mirror Reflection

解题思路：

镜面反射。给一个四面都是镜子的正方形房间，除西南角外每个角落都放有一个接受器。墙壁长度为 p，一束激光从西南角射出与东墙相遇，入射点到右下角距离为 q 。返回光线最先遇到接收器编号（保证光线最终会遇到一个接收器）。

这道题刚开始画了一些图，也观察到一些规律，但没有总结好。参考一个大牛的思路：

把这个射线无限延长，肯定会到达某个方块的右上角（方块你在草稿纸上补齐）。这样，水平方向假设 x 个方块，垂直方向假设 y 个方块，y / x = q / p。它给的数据 p 和 q 都是整数，实际水平扩展到 p 个方块，垂直扩展到 q 个方块就满足了。自己看一下规律：x 是奇数，y 是奇数时，右上角是 1；x 是奇数，y 是偶数时，右上角是 0；x 是偶数，y 是奇数时，右上角是 2；x 是偶数，y 是偶数，右上角是发射点。最后一种情况把 x，y 同时除以 2 直到某一方不是偶数就行了。

为什么上述的思想是可行的呢？假设没有镜子，我们观察以下几种情况：

对于 p/q = 3 时，激光会到达右上角，由于第二个房间和原始房间是镜面对称的，而第三个房间和第二个房间也是镜面对称的，则第三个房间和原始房间就是一样的了，那么就可以假设一下，奇数房间和原始房间的布局相同，则是接收器 1。
对于 p/q = 4 时，激光到达了右上角，而偶数房间的布局是跟原始房间呈镜面反射的，则就是接受器 2 了。
对于 p/q = 3/2 时，我们需要复制出一个 2x3 大小的矩阵出来，在水平方向共有三个房间，水平方向有奇数个房间，和原始房间布局一致；竖直方向有偶数个房间，和原始房间呈镜面反射，则最右上角为接收器 0。

因此可以得出规律：

p 为奇数，q 为奇数时，到达接收器 1。
p 为偶数，q 为奇数时，到达接收器 2。
p 为奇数，q 为偶数时，到达接收器 0。

为什么没有 p 和 q 均为偶数的情况呢？比如 p = 4, q = 2，其实只要我们画个图就知道，这个跟 p = 2, q = 1 的情况是一模一样的，若 p 和 q 均为偶数，那么那么一定可以同时除以 2。我们可以先对 p 和 q 进行判断，若二者同为偶数，则同时除以 2，直到不同时为偶数时，然后再带入上面归纳的三种情况求解即可。

Python3 实现：

class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        while p % 2 == 0 and q % 2 == 0:  # p和q同时为偶数，先进行同时除以2操作
            p //= 2
            q //= 2
        if p % 2 == 0 and q % 2 == 1:  #三种归纳情况的返回值
            return 2
        elif p % 2 == 1 and q % 2 == 1:
            return 1
        elif p % 2 == 1 and q % 2 == 0:
            return 0

问题描述：【Math】1006. Clumsy Factorial

解题思路：

笨阶乘。给一个正整数 N，按照 *、/、+、- 顺序计算阶乘。

方法1（常规方法）：

常规方法就是找规律，比如 N = 19，结果为： 19 * 18 / 17 + 16 - 15 * 14 / 13 + 12 - 11 * 10 / 9 + 8 - ...， 因为先计算乘除法，所以以每 4 项为一个整体，计算结果累加到总结果上，然后将 N 减 4 继续计算，直到 N < 4 停止。最后，对于 N < 4 单独处理，累加到结果上即可。

Python3 实现：

class Solution:
    def clumsy(self, N: int) -> int:
        if N == 1: return 1
        elif N == 2: return 2
        elif N == 3: return 6
        ans = N * (N-1) // (N-2) + (N-3)  # 前四项为正数
        N -= 4
        while N >= 4:
            tmp = N * (N-1) // (N-2)  # -30//4=-8而不是-7
            ans += -tmp + (N-3)  # tmp前面为负号
            N -= 4
        if N == 1: ans -= 1
        elif N == 2: ans -= 2
        elif N == 3: ans -= 6
        return ans

上面是迭代方法，还可以递归计算，思路相同，即 f(19) = 19 * 18 / 17 + 16 - f(15)，略。

方法2（数学证明）：

这道题还可以采取精妙的数学证明的方法求解。可以证明这样的一个式子：

i ∗ (i−1) / (i−2) = i ∗ (1 + 1 / (i−2)) = i + i / (i-2) = (i+1) + 2 / (i - 2)

因为我们要保留整数，所以我们希望：

2 / (i−2) < 1，即 i > 4

此时，我们知道 i ∗ (i−1) / (i−2) = i+1，当 i > 4 时。

所以我们的问题就变成了：

i ∗ (i−1) / (i−2) + (i−3) − (i−4) ∗ (i−5) / (i−6) + rest = (i+1) + (i−3) − (i−3) + rest = (i+1) + rest
其中至少保证 (i - 4) > 4，即 i > 8
rest 只有四种可能的情况，即 (+ 2 - 1)、(+ 3 - 2 * 1)、(+ 4 - 3 * 2 / 1)、(+ 5 - 4 * 3 / 2 + 1)，分别对应 N % 4 == 1、N % 4 == 2、N % 4 == 3 以及 N % 4 == 0 四种情况，其中 N > 8。

因此，对于 N <= 8，我们可以直接计算出结果；对于 N > 8，我们将 N 模 4 取余，判断属于上述哪种情况，然后得到最后的结果。

Python3 实现：

class Solution:
    def clumsy(self, N: int) -> int:
        ansTo8 = [0, 1, 2, 6, 7, 7, 8, 6, 9]  # N<=8的结果单独计算
        if N <= 8:
            return ansTo8[N]
        if N % 4 == 0:  # N>8的数字%4判断结果
            return N + 1
        elif N % 4 == 1:
            return N + 2
        elif N % 4 == 2:
            return N + 2
        elif N % 4 == 3:
            return N - 1