今天晚上上一题# JobHunting - 待字闺中
p*2
1 楼
问题描述：假设你的起点在坐标轴0点，第一次你可以选择向左或向右移动一个位置，
第二次选择向左或向右移动两个个位置，以此类推，问至少要移动多少次可以移动到一
个指定的位置(x)。10^(-9)
第二次选择向左或向右移动两个个位置，以此类推，问至少要移动多少次可以移动到一
个指定的位置(x)。10^(-9)
H*e
2 楼
不知道这样行不行
define T[x,j] 为在位置x, 跳 j 次可能不可能 1/0
T[x,j]= T[x-j,j-1] | T[x+j,j-1]
然后填表
填表的时候从最左边列开始， 一列一列往右扫描
最后back track出路线？
j:
0 1 2 3 4 **
x:
-4
-3
-2
-1
0
1
2
3
4
最后取x对应行为1的最小j值。。
【在 p*****2 的大作中提到】
: 问题描述：假设你的起点在坐标轴0点，第一次你可以选择向左或向右移动一个位置，
: 第二次选择向左或向右移动两个个位置，以此类推，问至少要移动多少次可以移动到一
: 个指定的位置(x)。10^(-9)
define T[x,j] 为在位置x, 跳 j 次可能不可能 1/0
T[x,j]= T[x-j,j-1] | T[x+j,j-1]
然后填表
填表的时候从最左边列开始， 一列一列往右扫描
最后back track出路线？
j:
0 1 2 3 4 **
x:
-4
-3
-2
-1
0
1
2
3
4
最后取x对应行为1的最小j值。。
【在 p*****2 的大作中提到】
: 问题描述：假设你的起点在坐标轴0点，第一次你可以选择向左或向右移动一个位置，
: 第二次选择向左或向右移动两个个位置，以此类推，问至少要移动多少次可以移动到一
: 个指定的位置(x)。10^(-9)
c*g
3 楼
若是以相邻的移动为配对
先右再左 == 向左移一步
先左再右 == 向右移一步
先假设x为正 (负数的话其实答案是一样的 只是移动方向相反)
先从0开始同一方向累加至最靠近x的点z(超过x也可以, 若x正好在中间, 取小的那点为
z)
若是z=x, 那就找到
若是z>x, 那就向左移(z-x)步, 也就是要移动2(z-x)次
若是z
if(x == 0)
return 0;
int counter = 0;
int acc = 0;
float temp1 = 0; // 其实可省略
while(acc
counter++;
temp1++;
acc = acc + temp1;
}
if(acc-abs(x)
else
return counter-1+2*(abs(x)-(acc-temp1));
【在 p*****2 的大作中提到】
: 问题描述：假设你的起点在坐标轴0点，第一次你可以选择向左或向右移动一个位置，
: 第二次选择向左或向右移动两个个位置，以此类推，问至少要移动多少次可以移动到一
: 个指定的位置(x)。10^(-9)
先右再左 == 向左移一步
先左再右 == 向右移一步
先假设x为正 (负数的话其实答案是一样的 只是移动方向相反)
先从0开始同一方向累加至最靠近x的点z(超过x也可以, 若x正好在中间, 取小的那点为
z)
若是z=x, 那就找到
若是z>x, 那就向左移(z-x)步, 也就是要移动2(z-x)次
若是z
if(x == 0)
return 0;
int counter = 0;
int acc = 0;
float temp1 = 0; // 其实可省略
while(acc
counter++;
temp1++;
acc = acc + temp1;
}
if(acc-abs(x)
else
return counter-1+2*(abs(x)-(acc-temp1));
【在 p*****2 的大作中提到】
: 问题描述：假设你的起点在坐标轴0点，第一次你可以选择向左或向右移动一个位置，
: 第二次选择向左或向右移动两个个位置，以此类推，问至少要移动多少次可以移动到一
: 个指定的位置(x)。10^(-9)
g*y
4 楼
这个题还很有意思。
1.只有x是奇数才有解，因为第一步移动1，以后都是偶数，无论怎么叠加，都会是奇数
2.只要x是奇数，都有解，这个解法类似汉诺塔，可以用递归解
举例：
3 = 1+2, 5=-1+2+4, 7=1+2+4, 9=-1-2+4+8
数学上可以证明这个。
【在 p*****2 的大作中提到】
: 问题描述：假设你的起点在坐标轴0点，第一次你可以选择向左或向右移动一个位置，
: 第二次选择向左或向右移动两个个位置，以此类推，问至少要移动多少次可以移动到一
: 个指定的位置(x)。10^(-9)
1.只有x是奇数才有解，因为第一步移动1，以后都是偶数，无论怎么叠加，都会是奇数
2.只要x是奇数，都有解，这个解法类似汉诺塔，可以用递归解
举例：
3 = 1+2, 5=-1+2+4, 7=1+2+4, 9=-1-2+4+8
数学上可以证明这个。
【在 p*****2 的大作中提到】
: 问题描述：假设你的起点在坐标轴0点，第一次你可以选择向左或向右移动一个位置，
: 第二次选择向左或向右移动两个个位置，以此类推，问至少要移动多少次可以移动到一
: 个指定的位置(x)。10^(-9)
l*a
5 楼
为什么第3次不是移动3步？
【在 g**********y 的大作中提到】
: 这个题还很有意思。
: 1.只有x是奇数才有解，因为第一步移动1，以后都是偶数，无论怎么叠加，都会是奇数
: 2.只要x是奇数，都有解，这个解法类似汉诺塔，可以用递归解
: 举例：
: 3 = 1+2, 5=-1+2+4, 7=1+2+4, 9=-1-2+4+8
: 数学上可以证明这个。
【在 g**********y 的大作中提到】
: 这个题还很有意思。
: 1.只有x是奇数才有解，因为第一步移动1，以后都是偶数，无论怎么叠加，都会是奇数
: 2.只要x是奇数，都有解，这个解法类似汉诺塔，可以用递归解
: 举例：
: 3 = 1+2, 5=-1+2+4, 7=1+2+4, 9=-1-2+4+8
: 数学上可以证明这个。
g*y
6 楼
That's a good question, maybe u r right, problem is designed that way. Need
peking2's explaination.
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 l*****a 的大作中提到】
: 为什么第3次不是移动3步？
peking2's explaination.
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 l*****a 的大作中提到】
: 为什么第3次不是移动3步？
p*2
7 楼
Need
不好意思，没有说清除。每一步加1. 所以下一次是移动3.
【在 g**********y 的大作中提到】
: That's a good question, maybe u r right, problem is designed that way. Need
: peking2's explaination.
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
g*y
8 楼
If that's the case, then bfs
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 l*****a 的大作中提到】
: 为什么第3次不是移动3步？
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 l*****a 的大作中提到】
: 为什么第3次不是移动3步？
p*2
9 楼
火鸡在多想想。bfs performance恐怕会有问题。
【在 g**********y 的大作中提到】
: If that's the case, then bfs
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
l*a
10 楼
相当于一个complete binary tree
一层层的找。。。
别卖关子了，不这样怎么玩？
【在 p*****2 的大作中提到】
:
: 火鸡在多想想。bfs performance恐怕会有问题。
一层层的找。。。
别卖关子了，不这样怎么玩？
【在 p*****2 的大作中提到】
:
: 火鸡在多想想。bfs performance恐怕会有问题。
p*2
11 楼
那我上code了。
public class test
{
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
int x=Math.abs(in.nextInt());
int step=1;
int start=0;
while(start
while((start-x)%2!=0)
start+=step++;
System.out.println(step-1);
}
}
【在 l*****a 的大作中提到】
: 相当于一个complete binary tree
: 一层层的找。。。
: 别卖关子了，不这样怎么玩？
l*a
12 楼
不懂
while(start
while((start-x)%2!=0)
start+=step++;
如果第一层循环 到了某个start >x
而且(start-x)%2==0
then u will get the solution?
或者说start越来越大？越走越远？
【在 p*****2 的大作中提到】
:
: 那我上code了。
: public class test
: {
: public static void main(String[] args)
: {
: Scanner in=new Scanner(System.in);
: int x=Math.abs(in.nextInt());
: int step=1;
: int start=0;
while(start
while((start-x)%2!=0)
start+=step++;
如果第一层循环 到了某个start >x
而且(start-x)%2==0
then u will get the solution?
或者说start越来越大？越走越远？
【在 p*****2 的大作中提到】
:
: 那我上code了。
: public class test
: {
: public static void main(String[] args)
: {
: Scanner in=new Scanner(System.in);
: int x=Math.abs(in.nextInt());
: int step=1;
: int start=0;
p*2
13 楼
这题是greeddy的算法。首先你要走到x或者超过x，不然就浪费了。因为这是求最短路
径。如果刚好到达x，那一定是最优的。如果已经超过了x，只要start-x是even number
, 就意味着你在其中(start-x)/2步上往回跳。这样总的就是
start-(2*(start-x)/2)=x了。
【在 l*****a 的大作中提到】
: 不懂
: while(start
: while((start-x)%2!=0)
: start+=step++;
: 如果第一层循环 到了某个start >x
: 而且(start-x)%2==0
: then u will get the solution?
: 或者说start越来越大？越走越远？
g*y
14 楼
start-x是奇数呢？比如5
number
【在 p*****2 的大作中提到】
:
: 这题是greeddy的算法。首先你要走到x或者超过x，不然就浪费了。因为这是求最短路
: 径。如果刚好到达x，那一定是最优的。如果已经超过了x，只要start-x是even number
: , 就意味着你在其中(start-x)/2步上往回跳。这样总的就是
: start-(2*(start-x)/2)=x了。
number
【在 p*****2 的大作中提到】
:
: 这题是greeddy的算法。首先你要走到x或者超过x，不然就浪费了。因为这是求最短路
: 径。如果刚好到达x，那一定是最优的。如果已经超过了x，只要start-x是even number
: , 就意味着你在其中(start-x)/2步上往回跳。这样总的就是
: start-(2*(start-x)/2)=x了。
p*2
15 楼
那就再往下走，直到出现偶数。最多多走两步。
【在 g**********y 的大作中提到】
: start-x是奇数呢？比如5
:
: number
g*y
16 楼
我就是在这步卡住的，只想过多走一步。这是codeforce的题？还是面试题？
【在 p*****2 的大作中提到】
:
: 那就再往下走，直到出现偶数。最多多走两步。
【在 p*****2 的大作中提到】
:
: 那就再往下走，直到出现偶数。最多多走两步。
l*a
17 楼
多走两次的话。
start-x最多可能差出来最后三次的步长-1
那样你折半回退就无法一次完成了
【在 p*****2 的大作中提到】
:
: 那就再往下走，直到出现偶数。最多多走两步。
start-x最多可能差出来最后三次的步长-1
那样你折半回退就无法一次完成了
【在 p*****2 的大作中提到】
:
: 那就再往下走，直到出现偶数。最多多走两步。
j*g
18 楼
I guess it is like this! Actually, it is the same with peking2's code, and i
just try to explain it.
assume
sum(1+2+...,+ n-1) < x
sum(1+2+...,+n) > x
Construction (greedy) the moving sequence as following：
[-k1] means left movement with size k1.
1, 2, 3, 4, ..., [-k1], k1+1,...,[-k2], k2+1,..., kn-1, -[kn], km+1, ... n +
km
x = sum(1+2...+n+km) - 2(k1+k2+k3+...)
k1+k2+k3+...+km = [sum(1+2+...+n+km) - x]/2.
min m = 1 or 2, depends on the value of x.
just try to explain it.
assume
sum(1+2+...,+ n-1) < x
sum(1+2+...,+n) > x
Construction (greedy) the moving sequence as following：
[-k1] means left movement with size k1.
1, 2, 3, 4, ..., [-k1], k1+1,...,[-k2], k2+1,..., kn-1, -[kn], km+1, ... n +
km
x = sum(1+2...+n+km) - 2(k1+k2+k3+...)
k1+k2+k3+...+km = [sum(1+2+...+n+km) - x]/2.
min m = 1 or 2, depends on the value of x.
p*2
19 楼
不是这个意思。只要start-x是偶数
那么你就在(start-x)/2步的时候往后跳，这样来回就少了start-x了。
【在 l*****a 的大作中提到】
: 多走两次的话。
: start-x最多可能差出来最后三次的步长-1
: 那样你折半回退就无法一次完成了
c*p
20 楼
int step(int x)
{
int s, i = 0;
while ((s = i*(i+1)/2) < x || (s-x)%2 ){
i++;
}
return i;
}
【在 p*****2 的大作中提到】
: 问题描述：假设你的起点在坐标轴0点，第一次你可以选择向左或向右移动一个位置，
: 第二次选择向左或向右移动两个个位置，以此类推，问至少要移动多少次可以移动到一
: 个指定的位置(x)。10^(-9)
{
int s, i = 0;
while ((s = i*(i+1)/2) < x || (s-x)%2 ){
i++;
}
return i;
}
【在 p*****2 的大作中提到】
: 问题描述：假设你的起点在坐标轴0点，第一次你可以选择向左或向右移动一个位置，
: 第二次选择向左或向右移动两个个位置，以此类推，问至少要移动多少次可以移动到一
: 个指定的位置(x)。10^(-9)
D*n
21 楼
他是说多走两步的情况下，(start-x)/2的值已经大于当前的step值了,所以一步退不回去。
【在 p*****2 的大作中提到】
:
: 不是这个意思。只要start-x是偶数
: 那么你就在(start-x)/2步的时候往后跳，这样来回就少了start-x了。
【在 p*****2 的大作中提到】
:
: 不是这个意思。只要start-x是偶数
: 那么你就在(start-x)/2步的时候往后跳，这样来回就少了start-x了。
l*a
22 楼
你这个code很多情况下一步就可以返回了吧
(s-x)%2==1
【在 c***p 的大作中提到】
: int step(int x)
: {
: int s, i = 0;
: while ((s = i*(i+1)/2) < x || (s-x)%2 ){
: i++;
: }
: return i;
: }
(s-x)%2==1
【在 c***p 的大作中提到】
: int step(int x)
: {
: int s, i = 0;
: while ((s = i*(i+1)/2) < x || (s-x)%2 ){
: i++;
: }
: return i;
: }
t*7
23 楼
public static int getLeastStep(int dest, int start, int step){
if(start+step==dest || start-step==dest){
return step;
}
if(step > (10^9) || step<0){
return -1;
}
int rightStep = getLeastStep(dest, start+step, step+1);
int leftStep = getLeastStep(dest, start-step, step+1);
if(rightStep != -1 && leftStep != -1){
return Math.min(rightStep, leftStep);
}
if(rightStep != -1 || leftStep != -1){
return rightStep!=-1?rightStep:leftStep;
}
return -1;
}
if(start+step==dest || start-step==dest){
return step;
}
if(step > (10^9) || step<0){
return -1;
}
int rightStep = getLeastStep(dest, start+step, step+1);
int leftStep = getLeastStep(dest, start-step, step+1);
if(rightStep != -1 && leftStep != -1){
return Math.min(rightStep, leftStep);
}
if(rightStep != -1 || leftStep != -1){
return rightStep!=-1?rightStep:leftStep;
}
return -1;
}
c*p
24 楼
如果 (s-x)%2 ＝＝ 1，继续走， 即i++；直到超过x, 而且走过的距离s 与x 同奇偶。
【在 l*****a 的大作中提到】
: 你这个code很多情况下一步就可以返回了吧
: (s-x)%2==1
【在 l*****a 的大作中提到】
: 你这个code很多情况下一步就可以返回了吧
: (s-x)%2==1
p*2
25 楼
是的。我跟他讨论过了，要退两步。
回去。
【在 D******n 的大作中提到】
: 他是说多走两步的情况下，(start-x)/2的值已经大于当前的step值了,所以一步退不回去。
回去。
【在 D******n 的大作中提到】
: 他是说多走两步的情况下，(start-x)/2的值已经大于当前的step值了,所以一步退不回去。
w*o
26 楼
这个题我压根就没有看懂：
x怎么会是小数 10^(-9) 呀？
难道不是每次移动都是整数位置吗？
谢谢！
【在 p*****2 的大作中提到】
: 问题描述：假设你的起点在坐标轴0点，第一次你可以选择向左或向右移动一个位置，
: 第二次选择向左或向右移动两个个位置，以此类推，问至少要移动多少次可以移动到一
: 个指定的位置(x)。10^(-9)
x怎么会是小数 10^(-9) 呀？
难道不是每次移动都是整数位置吗？
谢谢！
【在 p*****2 的大作中提到】
: 问题描述：假设你的起点在坐标轴0点，第一次你可以选择向左或向右移动一个位置，
: 第二次选择向左或向右移动两个个位置，以此类推，问至少要移动多少次可以移动到一
: 个指定的位置(x)。10^(-9)
R*1
27 楼
感觉是-10^9
【在 w****o 的大作中提到】
: 这个题我压根就没有看懂：
: x怎么会是小数 10^(-9) 呀？
: 难道不是每次移动都是整数位置吗？
: 谢谢！
【在 w****o 的大作中提到】
: 这个题我压根就没有看懂：
: x怎么会是小数 10^(-9) 呀？
: 难道不是每次移动都是整数位置吗？
: 谢谢！
相关阅读
H1B批准后会有新的EAD卡吗？急问：跟hiring manager约好的电话面试如何改时间请教刷题H1b 续第二个三年最早什么时候可以开始办？弯曲的工资和北京工资换算法申请part time h1b的问题two sigma电面面经码农如何接私活 下班时间给孩子赚点奶粉钱那种再问一道，很多string和regular expression比较OPT转CPT，需要rehire，并且不能保持full-time regular要以intern身份工作?on-site前主动和对方打电话可以吗？有人了解弗吉尼亚Amazon 么？什么意思：HM说，我的情况有什么变动的话，可以告诉他苹果什么行情啊为啥大家都不待见A家？如果现在在加州该向哪个servicen center投opt申请呢? (转载)急问求助：自愿离职是不是就没有 unemployment benefit年终bonus一问提供g家full time的refer接受Offer之后，反悔，以后一定没法去这家了吗？