C******x
发帖数: 91 | 1 有3n个数围成一个环，取走其中一个的话会顺带去掉这个数相邻的两个数（这两个不计
入总和），剩下的继续围成环，问取走n个数构成总和的最大值。
DP是肯定的了 不知道怎么定义状态和转移方程 还有这个环。。。 |
j******o
发帖数: 4219 | |
s*********6
发帖数: 261 | 3 Do you mean to find max(\Sum_{1}{n}(i_n)) with some constraints?
Feel like house robber
Is it a G onsite question? |
w*****1
发帖数: 6807 | 4 House Robber I 和 House Robber II |
b*****s
发帖数: 11267 | 5 最大值啊，这是个简单的数学问题吧？
【在 C******x 的大作中提到】
: 有3n个数围成一个环，取走其中一个的话会顺带去掉这个数相邻的两个数（这两个不计
: 入总和），剩下的继续围成环，问取走n个数构成总和的最大值。
: DP是肯定的了 不知道怎么定义状态和转移方程 还有这个环。。。
|
L*******k
发帖数: 42 | 6 戳气球变种？
【在 C******x 的大作中提到】
: 有3n个数围成一个环，取走其中一个的话会顺带去掉这个数相邻的两个数（这两个不计
: 入总和），剩下的继续围成环，问取走n个数构成总和的最大值。
: DP是肯定的了 不知道怎么定义状态和转移方程 还有这个环。。。
|
L*******k
发帖数: 42 | 7 你理解错了吧
【在 b*****s 的大作中提到】
: 最大值啊，这是个简单的数学问题吧？
|
L*******k
发帖数: 42 | 8 house robber里面house的位置是固定的
这个题里面，每次取走3个数，原来中间隔了3个位置不相邻的两个数，就变成相邻了。
【在 w*****1 的大作中提到】
: House Robber I 和 House Robber II
|
L*******k
发帖数: 42 | 9 不过戳气球这种题，算是dp里面有难度的了。这个题比戳气球还更难些。关键你没做过
戳气球更难往哪个方向想。
不过按照我对g家面试的了解，这题interviewer估计自己都不一定会做dp的解，expect
你能写个工整的backtracking就给过了。当然了，也说不准是哪个练过acm的菜鸟
noogler刚开始面试拿来刷人的。
【在 L*******k 的大作中提到】
: 戳气球变种？
|
w*****1
发帖数: 6807 | 10 这也有点太难了吧
【在 L*******k 的大作中提到】
: house robber里面house的位置是固定的
: 这个题里面，每次取走3个数，原来中间隔了3个位置不相邻的两个数，就变成相邻了。
|
|
|
b*****s
发帖数: 11267 | 11 那又怎么了，注意这里是3n，不是2n啊，理论上乱序的话可以取走最大的n个值呀
如果是顺序的话，如果X_(0) 表示最大的话，就是看 sumX_(i), i=0,2,4,...,2n-2 和
sumsumX_(i), i=13,5,...,2n-1 那个最大呀
【在 L*******k 的大作中提到】
: house robber里面house的位置是固定的
: 这个题里面，每次取走3个数，原来中间隔了3个位置不相邻的两个数，就变成相邻了。
|
S********t
发帖数: 3431 | 12 3n个数，每次拿走3个，最后全部拿完。每次拿走的3个里面有2个是作废的。你题目真
的读懂了吗？
【在 b*****s 的大作中提到】
: 那又怎么了，注意这里是3n，不是2n啊，理论上乱序的话可以取走最大的n个值呀
: 如果是顺序的话，如果X_(0) 表示最大的话，就是看 sumX_(i), i=0,2,4,...,2n-2 和
: sumsumX_(i), i=13,5,...,2n-1 那个最大呀
|
b*****s
发帖数: 11267 | 13 对啊，理论最大值
当然对每一种排列需要单列，但是最大的就是我说的呀
[在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
:的读懂了吗？ |
S********t
发帖数: 3431 | 14 你想简单了。
【在 b*****s 的大作中提到】
: 对啊，理论最大值
: 当然对每一种排列需要单列，但是最大的就是我说的呀
: [在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
: :的读懂了吗？
|
b*****s
发帖数: 11267 | 15 对一个特定的排列，3n！种组合跑一遍呗，作为非coder人我准备写n遍for循环
[在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
:你想简单了。 |
S********t
发帖数: 3431 | 16 够暴力！
不过求教哪种编程语言能写n个for循环。。。n=100000的话你手会写酸吗
【在 b*****s 的大作中提到】
: 对一个特定的排列，3n！种组合跑一遍呗，作为非coder人我准备写n遍for循环
: [在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
: :你想简单了。
|
b*****s
发帖数: 11267 | 17 那就迭代
[在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
:够暴力！
:不过求教哪种编程语言能写n个for循环。。。n=100000的话你手会写酸吗 |
o******y
发帖数: 446 | 18 用链表和backtrack:
public int getMaxSum(int[] arr){
LinkedList q = new LinkedList<>();
for(int n: arr) q.add(n);
int[] res = new int[1];
res[0] = Integer.MIN_VALUE;
helper(res, q, 0);
return res[0];
}
void helper(int[] res, LinkedList q, int sum){
if(q.isEmpty()){
res[0] = Math.max(sum, res[0]);
return;
}
int size = q.size();
while(size-->0){
int v = q.removeLast();
int v1 = q.removeFirst();
int v2 = q.removeLast();
helper(res, q, sum+v);
q.addFirst(v1);
q.addFirst(v);
q.addLast(v2);
}
}
【在 C******x 的大作中提到】
: 有3n个数围成一个环，取走其中一个的话会顺带去掉这个数相邻的两个数（这两个不计
: 入总和），剩下的继续围成环，问取走n个数构成总和的最大值。
: DP是肯定的了 不知道怎么定义状态和转移方程 还有这个环。。。
|
C******x
发帖数: 91 | 19 学习了，是我想偏了。。。
【在 o******y 的大作中提到】
: 用链表和backtrack:
: public int getMaxSum(int[] arr){
: LinkedList q = new LinkedList<>();
: for(int n: arr) q.add(n);
: int[] res = new int[1];
: res[0] = Integer.MIN_VALUE;
: helper(res, q, 0);
: return res[0];
: }
: void helper(int[] res, LinkedList q, int sum){
|
S********t
发帖数: 3431 | 20 backtrack: weak hire
DP: strong hire
【在 C******x 的大作中提到】
: 学习了，是我想偏了。。。
|
|
|
g*********e
发帖数: 14401 | 21 不是吧 g家不都是要求最优解的吗？暴力做出来也能过？
expect
【在 L*******k 的大作中提到】
: 不过戳气球这种题，算是dp里面有难度的了。这个题比戳气球还更难些。关键你没做过
: 戳气球更难往哪个方向想。
: 不过按照我对g家面试的了解，这题interviewer估计自己都不一定会做dp的解，expect
: 你能写个工整的backtracking就给过了。当然了，也说不准是哪个练过acm的菜鸟
: noogler刚开始面试拿来刷人的。
|
S********t
发帖数: 3431 | 22 g家的老美 interviewer的 expectation不高的。
这题非要要求dp也就别想招人了。
比如题库里面有道翻硬币游戏的题，出题人自己都不知道Sprague Grundy theorem，只要
求暴力。
【在 g*********e 的大作中提到】
: 不是吧 g家不都是要求最优解的吗？暴力做出来也能过？
:
: expect
|
b*****s
发帖数: 11267 | 23 哼哼，不相信没有数学上的解法
只要
【在 S********t 的大作中提到】
: g家的老美 interviewer的 expectation不高的。
: 这题非要要求dp也就别想招人了。
: 比如题库里面有道翻硬币游戏的题，出题人自己都不知道Sprague Grundy theorem，只要
: 求暴力。
|
l***i
发帖数: 1309 | 24 It seems if you pick n elements that are not adjacent, then there is a way
to get them in a solution. If so, then you can build a dp because you only
need to know how many elements have been picked, their sum and whether the
last one is included or not.
It is also true that sometimes the interviewer himself/herself does not
understand the problem properly and happens to use that as an interview
problem. This is sad. |
S********t
发帖数: 3431 | 25 前面已经有人讲过了啊，这题是有dp解，就是比较难/复杂而已。
真要想做dp解，先去做下
https://leetcode.com/problems/burst-balloons/
然后你再看看能不能触类旁通。
【在 b*****s 的大作中提到】
: 哼哼，不相信没有数学上的解法
:
: 只要
|
C******x
发帖数: 91 | 26 多谢指教！
【在 l***i 的大作中提到】
: It seems if you pick n elements that are not adjacent, then there is a way
: to get them in a solution. If so, then you can build a dp because you only
: need to know how many elements have been picked, their sum and whether the
: last one is included or not.
: It is also true that sometimes the interviewer himself/herself does not
: understand the problem properly and happens to use that as an interview
: problem. This is sad.
|
g******d
发帖数: 152 | 27 写一个迭代的。改top to bottom dp很难
class Node(object):
def __init__(self, v):
self.v = v
self.n = None
def dfs(p, s):
if s == 3:
return max(p.v, p.n.v, p.n.n.v)
max_v = 0
for i in range(s):
p1, p2, p3 = p.n, p.n.n, p.n.n.n
p.n = p3.n
r = p2.v + dfs(p, s-3)
max_v = max(max_v, r)
p.n = p1
p = p.n
return max_v
a = [5, 1, 2, 6, 3, 4, 0, 0, 7]
dummy = Node(-1)
head = dummy
for num in a:
head.n = Node(num)
head = head.n
head.n = dummy.n
head = head.n
print dfs(head, len(a)) |
b*****s
发帖数: 11267 | 28 我是说数学上 O(n)的方法
[在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
:前面已经有人讲过了啊，这题是有dp解，就是比较难/复杂而已。
:真要想做dp解，先去做下
:https://leetcode.com/problems/burst-balloons/
:然后你再看看能不能触类旁通。 |
b*****s
发帖数: 11267 | 29 数学解尝试：
选一个起点，Let n_i, i=1,2,...,3n表示这些数，i表示它的位置。
分成三组， if n_i in 某个组，则n_(i-+3 mod 3n )也在这个组。
generally，某个组选一个数，则会在其它两个组分别消去一个数，另外原先相邻的数
不可以同时选中。
然后objective：max \sum n_i* status_i %status_i=1表明选中，=0表示被消除。
such that;
\sum status_i =n. % 只能选n个点
status_(i-1 mod 3n)+status_i<=1
status_i+status_(i+1 mod 3n)<=1%显然相邻的三个数永远不可能在一个组合
Status_i>=0
嗯感觉条件完备了，回头看看dual是啥样的
[在 beanies (以德唬人) 的大作中提到：]
:我是说数学上 O(n)的方法 |
