2019-10-18 Daily Report —— Leetcode 991 Broken Calculator

概览

知音如不赏,归卧故山秋。

时间:Friday, October 18, 2019 09:30 AM

作者:Syncher Pylon


  • 学习算法
  • 学习英语

算法学习笔记

Leetcode 991 Broken Calculator

测试用例

给定 X 和 Y 的范围是 [1, 10^9],因此 X,Y 使用 int_32 够用,考虑如下测试用例:

1
2
3
4
5
// Case 1: X == Y

// Case 2: X > Y

// Case 3: X < Y

分析

  1. x > y,则 x –> y 只能通过减法操作,因此直接返回 x - y

  2. x == y,无需做任何变化,直接返回 0

  3. x < y
    3.1 如果 y 是奇数: f(y) = f(y+1) + 1

    3.2 如果 y 是偶数: f(y) = f(y/2) + 1

因此使用递归可以解决该问题。

Coding

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def brokenCalc(self, x: int, y: int) -> int:
def calc(y):
if x >= y:
return x - y

if y % 2 == 1:
return calc(y + 1) + 1
else:
return calc(y // 2) + 1

return calc(y)

思考:如上代码是否有交集,是否需要缓存?

英语学习笔记

  • perform: carry out, or fulfill an action, task, or function.

本文标题:2019-10-18 Daily Report —— Leetcode 991 Broken Calculator

文章作者:Syncher

发布时间:2019年10月18日 - 09:10

最后更新:2019年10月18日 - 18:10

原始链接:https://0x400.com/2019-10-18-diary-2019-10-18.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。