f********c
发帖数: 147 | 1 在网上查面经看到的，好像在板上看到过，不过找不到了...题目如下（直接copy）：
“
给一个list, list中有两个数. 过程中可以一直往list中加数进去(append在最后), 但
必须一直遵守三个条件:
1. list中所有数均需大于0
2. list中所有数都必须为unique
3. 新加入的数必须为已存在list中的某两数的差
要做的事情是把所有可能的过程(一直加到没办法加入新的数字为止)都给打印或是回传
ex. [30, 5], 则最新加入的数只能为25, list变为[30, 5, 25]
继续, 只能再加入20, list成为[30, 5, 25, 20], 接着就有两种选择, 可以加10(30-
20) 或是15(20-5).
于是会分出两个branch
[30, 5, 25, 20, 10] 跟[30, 5, 25, 20, 15], 然后再把最后一个可能补上之后变成
[30, 5, 25, 20, 10, 15]跟[30, 5, 25, 20, 15, 10], 所以就回传这两个list.
”
请大牛给了思路，多谢！ | b**********5
发帖数: 7881 | 2 一个difference array
一个result array
每次更新 every element in the result array时， 更新corresponding difference
array
就是不知道你这个result， 是不是要保持order。 不包吃， 就hashmap， 保持， 也
可以用linkedhashmap
【在 f********c 的大作中提到】
: 在网上查面经看到的，好像在板上看到过，不过找不到了...题目如下（直接copy）：
: “
: 给一个list, list中有两个数. 过程中可以一直往list中加数进去(append在最后), 但
: 必须一直遵守三个条件:
: 1. list中所有数均需大于0
: 2. list中所有数都必须为unique
: 3. 新加入的数必须为已存在list中的某两数的差
: 要做的事情是把所有可能的过程(一直加到没办法加入新的数字为止)都给打印或是回传
: ex. [30, 5], 则最新加入的数只能为25, list变为[30, 5, 25]
: 继续, 只能再加入20, list成为[30, 5, 25, 20], 接着就有两种选择, 可以加10(30-
| f********c
发帖数: 147 | 3 如果加入一个新element到result array，如何可以高效的update difference array啊
？可以和之前的element一个个对比，但是感觉会很慢啊。最后result array的order要
保持的。
difference
【在 b**********5 的大作中提到】
: 一个difference array
: 一个result array
: 每次更新 every element in the result array时， 更新corresponding difference
: array
: 就是不知道你这个result， 是不是要保持order。 不包吃， 就hashmap， 保持， 也
: 可以用linkedhashmap
| b**********5
发帖数: 7881 | 4 搞错了， 就一个difference array 就可以了。 然后我没觉得没有什么order啊。
我只能想到和之前的一个个对比， 我想不出更快的
【在 f********c 的大作中提到】
: 如果加入一个新element到result array，如何可以高效的update difference array啊
: ？可以和之前的element一个个对比，但是感觉会很慢啊。最后result array的order要
: 保持的。
:
: difference
| f********c
发帖数: 147 | 5 好的，多谢了！
【在 b**********5 的大作中提到】
: 搞错了， 就一个difference array 就可以了。 然后我没觉得没有什么order啊。
: 我只能想到和之前的一个个对比， 我想不出更快的
| C****t
发帖数: 53 | 6 We can order a = [5,30] first. The new added element will compare with a[0]
only, and be compared
with a[1:]. |
|
