w**s
发帖数: 5 | 1 请教一道算法题 看起来毫无头绪啊
You are given two integers L and R. Their values are initially set to L = 0
and R = 1.
You can change their values by performing the following commands:
the command 'L' changes the value of L to 2 * L - R;
the command 'R' changes the value of R to 2 * R - L.
You are given an integer N. The goal is to find the minimum number of
commands after which L = N or R = N.
For example, consider N = -11: the shortest sequence of commands required to
set either L or R to -11 is ['L', 'L', 'R', 'L']. After each command, the
values of L and R are as follows:
initial values: L = 0, R = 1;
command 'L': L = -1, R = 1;
command 'L': L = -3, R = 1;
command 'R': L = -3, R = 5;
command 'L': L = -11, R = 5.
After the fourth command we get L = N.
expected worst-case time complexity is O(log(N));
expected worst-case space complexity is O(1).
时间复杂度要求O(log(N)) 这个是在提示什么算法啊
谢谢 | I******c
发帖数: 163 | 2 想了好一阵子，开始以为是动态规划，后来发现时间复杂度不对。
观察了一下题目的例子，有以下结果：
1. 如果第一步走L，那么以后无论走L还是走R，L，R都是奇数。 如果第一步走R，以后
L，R都是偶数
2. L， R 其中是一个正数，另一个负数，而且都是各自向坐标轴的两端增长
3. 增长的幅度是 2^0,2^1,2^2,2^3...
所以，以N=-11为例，因为－11是奇数，所以第一步走L，这个时候L，R分别是－1，1.
－1和－11相差10. 10的二进制是101,也就是从－1到－11，需要的增长幅度是2和8，用
L, R表示，就是LRL,加上第一步是L,所以总的步骤就是LLRL. | w**s
发帖数: 5 | 3 请教一道算法题 看起来毫无头绪啊
You are given two integers L and R. Their values are initially set to L = 0
and R = 1.
You can change their values by performing the following commands:
the command 'L' changes the value of L to 2 * L - R;
the command 'R' changes the value of R to 2 * R - L.
You are given an integer N. The goal is to find the minimum number of
commands after which L = N or R = N.
For example, consider N = -11: the shortest sequence of commands required to
set either L or R to -11 is ['L', 'L', 'R', 'L']. After each command, the
values of L and R are as follows:
initial values: L = 0, R = 1;
command 'L': L = -1, R = 1;
command 'L': L = -3, R = 1;
command 'R': L = -3, R = 5;
command 'L': L = -11, R = 5.
After the fourth command we get L = N.
expected worst-case time complexity is O(log(N));
expected worst-case space complexity is O(1).
时间复杂度要求O(log(N)) 这个是在提示什么算法啊
谢谢 | I******c
发帖数: 163 | 4 想了好一阵子，开始以为是动态规划，后来发现时间复杂度不对。
观察了一下题目的例子，有以下结果：
1. 如果第一步走L，那么以后无论走L还是走R，L，R都是奇数。 如果第一步走R，以后
L，R都是偶数
2. L， R 其中是一个正数，另一个负数，而且都是各自向坐标轴的两端增长
3. 增长的幅度是 2^0,2^1,2^2,2^3...
所以，以N=-11为例，因为－11是奇数，所以第一步走L，这个时候L，R分别是－1，1.
－1和－11相差10. 10的二进制是101,也就是从－1到－11，需要的增长幅度是2和8，用
L, R表示，就是LRL,加上第一步是L,所以总的步骤就是LLRL. |
|
