leetcode 7.13-7.19

2020-07-19

1492 n的第k个因子
397 整数替换

1492. n的第k个因子

给你两个正整数 n 和 k 。

如果正整数 i 满足 n % i == 0 ，那么我们就说正整数 i 是整数 n 的因子。

考虑整数 n 的所有因子，将它们升序排列。请你返回第 k 个因子。如果 n 的因子数少于 k ，请你返回 -1 。

示例 1：

输入：n = 12, k = 3
输出：3
解释：因子列表包括 [1, 2, 3, 4, 6, 12]，第 3 个因子是 3 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/the-kth-factor-of-n
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：暴力枚举，即AC代码，从1枚举到n

方法二：有技巧的枚举，枚举1到$\lfloor{\sqrt{n}}\rfloor$的因子，大于$\lfloor{\sqrt{n}}\rfloor$的一定是已经枚举过的因子除n的值，可以通过—i来累加count值。需要注意的特殊情况是当n为完全平方数的时候，有一个因子会被计算两次，需要减掉一次。

AC代码：

class Solution(object):
    def kthFactor(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        count = 0
        for i in range(1, n+1):
            if n % i == 0:
                count += 1
                if count == k:
                    return i
        
        return -1

397. 整数替换

给定一个正整数 n，你可以做如下操作：

如果 n 是偶数，则用 n / 2替换 n。
如果 n 是奇数，则可以用 n + 1或n - 1替换 n。
n 变为 1 所需的最小替换次数是多少？

示例 1:

输入:
8

输出:
3

解释:
8 -> 4 -> 2 -> 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-replacement
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

动态规划，dp[i] 表示 i 变为1所需的最小替换次数。公式如下，其中奇数情况可以进一步转化成偶数情况，代码实现如下。

$dp[i] = \left\{ \begin{aligned} dp[i/2] + 1, 　& x\%2 = 0, \\ min(dp[i-1], dp[i+1]) + 1, 　& x\%2 \neq 0, \end{aligned} \right.$

代码：

class Solution(object):
    def integerReplacement(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0, 0]
        for i in range(2, n+1):
            if i % 2 == 0:
                dp.append(dp[i/2] + 1)
            else:
                dp.append(min(dp[(i+1)/2], dp[(i-1)/2])+2)
        return dp[-1]

上述方法超时、超内存。仔细思考下，中间计算了很多最终结果并不需要的状态，造成浪费。

思考一下，可以用递归，偶数情况比较好计算，不要用递归添加栈的深度

AC代码：

class Solution(object):
    def integerReplacement(self, n):
        """
        :type n: int
        :rtype: int
        """
        ret = 0
        while n & 1 == 0:
            ret += 1
            n = n >> 1
        if n == 1:
            return ret
        else:
            ret += min(self.integerReplacement((n+1)/2), self.integerReplacement((n-1)/2)) + 2
            return ret

递归代码运行时间一般，参考题解，思考数学特性。我们希望奇数能尽可能向4靠齐，这样可以保证连续两次的除2操作，所以$n=4k+1$时用$n-1$替换，$n=4k+3$时用$n+1$替换。特殊情况是$n=3$，要用$n-1$替换，保证更快到达2.

AC代码：

class Solution(object):
    def integerReplacement(self, n):
        """
        :type n: int
        :rtype: int
        """
        ret = 0
        while n > 1:
            if n & 1 == 0:
                n = n >> 1
            elif n % 4 == 1 or n == 3:
                n -= 1
            else:
                n += 1
            ret += 1

        return ret