-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
397.py
39 lines (35 loc) · 1.19 KB
/
397.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
__________________________________________________________________________________________________
class Solution:
def make_dp(function):
dp = {}
def helper(o, n):
if n not in dp:
dp[n] = function(o, n)
return dp[n]
return helper
@make_dp
def integerReplacement(self, n: int) -> int:
result = 0
if n == 1: return result
if n % 2 == 0:
result += (1 + self.integerReplacement(n / 2))
else:
result += (1 + min(self.integerReplacement(n + 1),
self.integerReplacement(n - 1)))
return result
__________________________________________________________________________________________________
sample 32 ms submission
class Solution:
def integerReplacement(self, n: int) -> int:
ops = 0
while n > 1:
if n % 2:
if n > 4 and n % 4 == 3:
n += 1
else:
n -= 1
else:
n >>= 1
ops += 1
return ops
__________________________________________________________________________________________________