y*****3
发帖数: 451 | 1 别人问我的，我不会做，大家贡献点idea:
有一个二维数组String[][]，就像excel那样的表格，横行都用1,2,3...表示，纵行用A
,B,C...表示，每个格子里是一个数学表达式，比如下边这个：
A B C
1: 7-4 C3*2 4
2: 10/2 A1+C2 0
3: C3 10-7 4/2
写一个method，要求返回一个String[][]，每个格子中是相应格子里的表达式的结果。
难点在于：如果格子互相之间有循环refer，则返回空值。比如下边这个就是循环
reference:
A B C
1: 13-5 C3 B3
2: 12-7 C1 0
3: 11*24 A1+B2 42 |
y*****3
发帖数: 451 | 2 我能想到的就是类似求图中的回路的做法，但是好像不是最佳解。 |
d********e
发帖数: 239 | 3 拓扑排序？
用A
【在 y*****3 的大作中提到】
: 别人问我的，我不会做，大家贡献点idea:
: 有一个二维数组String[][]，就像excel那样的表格，横行都用1,2,3...表示，纵行用A
: ,B,C...表示，每个格子里是一个数学表达式，比如下边这个：
: A B C
: 1: 7-4 C3*2 4
: 2: 10/2 A1+C2 0
: 3: C3 10-7 4/2
: 写一个method，要求返回一个String[][]，每个格子中是相应格子里的表达式的结果。
: 难点在于：如果格子互相之间有循环refer，则返回空值。比如下边这个就是循环
: reference:
|
S********e
发帖数: 74 | 4 对每个cell感觉dfs就可以了，如果碰到死循环就把沿路都设为空值 |
x****g
发帖数: 1512 | 5 分两部分。
A:已经算好的。（开始是所有的裸表达的.)
B:有ref的。(开始是所有有ref的.)
找B里仅由A中构成的，记为C. 计算出来。
完了重复找和C相关的，仅有A+C （C并入A)构成的作为下一个C.
重复直到找不到则结束。B中剩下的全部有问题。
用A
【在 y*****3 的大作中提到】
: 别人问我的，我不会做，大家贡献点idea:
: 有一个二维数组String[][]，就像excel那样的表格，横行都用1,2,3...表示，纵行用A
: ,B,C...表示，每个格子里是一个数学表达式，比如下边这个：
: A B C
: 1: 7-4 C3*2 4
: 2: 10/2 A1+C2 0
: 3: C3 10-7 4/2
: 写一个method，要求返回一个String[][]，每个格子中是相应格子里的表达式的结果。
: 难点在于：如果格子互相之间有循环refer，则返回空值。比如下边这个就是循环
: reference:
|
y*****3
发帖数: 451 | 6 谢谢大牛！这大概是最好的解法了。我还是太笨了，想了一晚上没想出来。。
【在 x****g 的大作中提到】
: 分两部分。
: A:已经算好的。（开始是所有的裸表达的.)
: B:有ref的。(开始是所有有ref的.)
: 找B里仅由A中构成的，记为C. 计算出来。
: 完了重复找和C相关的，仅有A+C （C并入A)构成的作为下一个C.
: 重复直到找不到则结束。B中剩下的全部有问题。
:
: 用A
|
l******6
发帖数: 340 | 7 The problem can be abstract to one dimension by ignore parse issue.
it can be solved with dp :
pick each cell , do:
1. if it is previous recorded then return result(a number result
or a bad cell result)
2. else if it is marked as 'don't touch' record it as bad cell
return a bad cell result (circle detected)
3. else if it contains only number calculate it, record it and
return result
4. else mark it as 'don't touch' in the record area , then
recursive calculate related cells involved in this cell calculation. If all
returns normal result, combine them get the result. If any return a bad cell
result , it is a bad cell. Replace the 'don't touch' sign with the result
and return the result.
|
A*********c
发帖数: 430 | 8 嗯，合理。不用想得太复杂，这个算法和就是把人的做法code出来。
【在 x****g 的大作中提到】
: 分两部分。
: A:已经算好的。（开始是所有的裸表达的.)
: B:有ref的。(开始是所有有ref的.)
: 找B里仅由A中构成的，记为C. 计算出来。
: 完了重复找和C相关的，仅有A+C （C并入A)构成的作为下一个C.
: 重复直到找不到则结束。B中剩下的全部有问题。
:
: 用A
|
l******6
发帖数: 340 | 9 This would rely on the order..
e.g cell with a to z
a[b + c + ..z] , b[c + d +.. z] , c[d + .. z] , .... w[y + z] y[z] z[1]
scan left to right , each time only one cell can be solved.
【在 A*********c 的大作中提到】
: 嗯，合理。不用想得太复杂，这个算法和就是把人的做法code出来。
|
x****g
发帖数: 1512 | 10 这貌似没办法，依赖决定了。
你怎么弄也得一个个算。
难道你不算w就可以算w之前的？
唯一的影响是，你受到从前往后扫描思路的限制，
所以从前往后成了你这次扫描的死穴，呵呵。
所以你的问题已经转变成怎么表达这种依赖关系从而避免低性能扫描。
而你选择了递归。
:)
【在 l******6 的大作中提到】
: This would rely on the order..
: e.g cell with a to z
: a[b + c + ..z] , b[c + d +.. z] , c[d + .. z] , .... w[y + z] y[z] z[1]
: scan left to right , each time only one cell can be solved.
|
|
|
l******6
发帖数: 340 | 11 I choose dp...
【在 x****g 的大作中提到】
: 这貌似没办法，依赖决定了。
: 你怎么弄也得一个个算。
: 难道你不算w就可以算w之前的？
: 唯一的影响是，你受到从前往后扫描思路的限制，
: 所以从前往后成了你这次扫描的死穴，呵呵。
: 所以你的问题已经转变成怎么表达这种依赖关系从而避免低性能扫描。
: 而你选择了递归。
: :)
|
x****g
发帖数: 1512 | 12 请教一下啥是你所谓的dp? 没看懂你的dp。
指教一下也好，呵呵！
【在 l******6 的大作中提到】
: I choose dp...
|
l******6
发帖数: 340 | 13 Build the result container same shape as input.
Initialize all the result container as untouched.
Then work with recursion.
All the result computed along recursion will be recorded in result container
to avoid repeat computation.
For this problem the extra part is the 'don't touch' sign. If a cell is
involved during the recursion start from it, it is a circle. When it happens
, it is a bad cell. And any cell has relation to bad cell are bad cell.
【在 x****g 的大作中提到】
: 请教一下啥是你所谓的dp? 没看懂你的dp。
: 指教一下也好，呵呵！
|
x****g
发帖数: 1512 | 14 没错，你可以怎么做，没问题。
1：啥是dp?
2: 不这么做为什么会有repeat computation.
算了，瞎琢磨吧，呵呵。
container
happens
【在 l******6 的大作中提到】
: Build the result container same shape as input.
: Initialize all the result container as untouched.
: Then work with recursion.
: All the result computed along recursion will be recorded in result container
: to avoid repeat computation.
: For this problem the extra part is the 'don't touch' sign. If a cell is
: involved during the recursion start from it, it is a circle. When it happens
: , it is a bad cell. And any cell has relation to bad cell are bad cell.
|
l******6
发帖数: 340 | 15 dp dynamic programming
Your algorithm contains repeat:
each scan when check every cell int A whether contains element only in C.
Repeat scan also happens.
I think in one of my previous interview I proposed similar algorithm to a
different problem and interviewer asked me the complexity. When I say worst
is n^2 , I 羞涩地 know he won't let me pass.
【在 x****g 的大作中提到】
: 没错，你可以怎么做，没问题。
: 1：啥是dp?
: 2: 不这么做为什么会有repeat computation.
: 算了，瞎琢磨吧，呵呵。
:
: container
: happens
|
