d********n
发帖数: 9 | 1 The description of the problem is : Write a function which takes a positive
integer as a string and returns the minimum number of operations needed to
transform the number to 1. The number is up to 309 digits long, so there won
't too many character than you can express in that many digits. The
transform process is limited to three operations: 1. Add 1 2. Subtract 1 3.
Divide the number by 2 (only even number allow here)
我的想法是用dfstraverse所有可能， 用memorization来剪枝，但是最后还是超时了，
求教如何进一步优化或者一种方法处理。 因为输入时string所以处理起来很麻烦 |
c********t
发帖数: 5706 | 2 https://leetcode.com/problems/integer-replacement/
positive
won
.
【在 d********n 的大作中提到】
: The description of the problem is : Write a function which takes a positive
: integer as a string and returns the minimum number of operations needed to
: transform the number to 1. The number is up to 309 digits long, so there won
: 't too many character than you can express in that many digits. The
: transform process is limited to three operations: 1. Add 1 2. Subtract 1 3.
: Divide the number by 2 (only even number allow here)
: 我的想法是用dfstraverse所有可能， 用memorization来剪枝，但是最后还是超时了，
: 求教如何进一步优化或者一种方法处理。 因为输入时string所以处理起来很麻烦
|
m******n
发帖数: 1691 | 3 class Solution {
public:
int integerReplacement(int n) {
if (n==0 || n==1) return 0;
if (n==INT_MAX) return 32;
if ((n&1)==0) return 1+integerReplacement(n>>1); //even
else {
return 1+min(integerReplacement(n-1), integerReplacement(n+1));
}
}
};
【在 c********t 的大作中提到】
: https://leetcode.com/problems/integer-replacement/
:
: positive
: won
: .
|
s**********g
发帖数: 14942 | 4 你这个同时尝试两个possibility
可能会TLE
leetcode讨论里面给了个解法，只把n==3当做例外
但我不知道面试时候遇到怎么能短时间内观察出这个。。。
【在 m******n 的大作中提到】
: class Solution {
: public:
: int integerReplacement(int n) {
: if (n==0 || n==1) return 0;
: if (n==INT_MAX) return 32;
: if ((n&1)==0) return 1+integerReplacement(n>>1); //even
: else {
: return 1+min(integerReplacement(n-1), integerReplacement(n+1));
: }
: }
|
m******n
发帖数: 1691 | 5 already passed leetcode online tests.
【在 s**********g 的大作中提到】
: 你这个同时尝试两个possibility
: 可能会TLE
: leetcode讨论里面给了个解法，只把n==3当做例外
: 但我不知道面试时候遇到怎么能短时间内观察出这个。。。
|
