由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 求助一道算法题, 在限定三个operation下使一个数变成1的最小操作数
相关主题
A Google questionmake matrix all 0
问一个Facebook大数相乘的题贡献一道M的链表题
Divide Two Integers讨论一道面试题
Divide Two Integers OJ和CCP150的做法Divide Two Integers
zenefits店面 -已挂了一个面试题
Divide a number by 3 without using *, /, +, -, % operators [转载]那个phone number的group的题,大家看看我写的行不行(还有string class那个s[0]==s[1]==s[2] 不work好像)
求助:一道careercup的算法题google 面经
Subtraction for link list represented integerfast way to sove n*m or n/m using only "add" operation?
相关话题的讨论汇总
话题: number话题: return话题: int话题: transform
进入JobHunting版参与讨论
1 (共1页)
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当做例外
: 但我不知道面试时候遇到怎么能短时间内观察出这个。。。

1 (共1页)
进入JobHunting版参与讨论
相关主题
fast way to sove n*m or n/m using only "add" operation?zenefits店面 -已挂了
一道难题Divide a number by 3 without using *, /, +, -, % operators [转载]
讨论下lc最新的那道hard题吧求助:一道careercup的算法题
请教将任意递归问题转换为尾递归的方法Subtraction for link list represented integer
A Google questionmake matrix all 0
问一个Facebook大数相乘的题贡献一道M的链表题
Divide Two Integers讨论一道面试题
Divide Two Integers OJ和CCP150的做法Divide Two Integers
相关话题的讨论汇总
话题: number话题: return话题: int话题: transform