C*x
2 楼
有3n个数围成一个环，取走其中一个的话会顺带去掉这个数相邻的两个数（这两个不计
入总和），剩下的继续围成环，问取走n个数构成总和的最大值。
DP是肯定的了 不知道怎么定义状态和转移方程 还有这个环。。。
入总和），剩下的继续围成环，问取走n个数构成总和的最大值。
DP是肯定的了 不知道怎么定义状态和转移方程 还有这个环。。。
D*9
3 楼
check hosiptal
【在 t*********u 的大作中提到】
: 能卖多少
【在 t*********u 的大作中提到】
: 能卖多少
j*o
4 楼
double linked list?
s*6
5 楼
Do you mean to find max(\Sum_{1}{n}(i_n)) with some constraints?
Feel like house robber
Is it a G onsite question?
Feel like house robber
Is it a G onsite question?
w*1
6 楼
House Robber I 和 House Robber II
b*s
7 楼
最大值啊，这是个简单的数学问题吧？
【在 C******x 的大作中提到】
: 有3n个数围成一个环，取走其中一个的话会顺带去掉这个数相邻的两个数（这两个不计
: 入总和），剩下的继续围成环，问取走n个数构成总和的最大值。
: DP是肯定的了 不知道怎么定义状态和转移方程 还有这个环。。。
【在 C******x 的大作中提到】
: 有3n个数围成一个环，取走其中一个的话会顺带去掉这个数相邻的两个数（这两个不计
: 入总和），剩下的继续围成环，问取走n个数构成总和的最大值。
: DP是肯定的了 不知道怎么定义状态和转移方程 还有这个环。。。
L*k
8 楼
戳气球变种？
【在 C******x 的大作中提到】
: 有3n个数围成一个环，取走其中一个的话会顺带去掉这个数相邻的两个数（这两个不计
: 入总和），剩下的继续围成环，问取走n个数构成总和的最大值。
: DP是肯定的了 不知道怎么定义状态和转移方程 还有这个环。。。
【在 C******x 的大作中提到】
: 有3n个数围成一个环，取走其中一个的话会顺带去掉这个数相邻的两个数（这两个不计
: 入总和），剩下的继续围成环，问取走n个数构成总和的最大值。
: DP是肯定的了 不知道怎么定义状态和转移方程 还有这个环。。。
L*k
9 楼
你理解错了吧
【在 b*****s 的大作中提到】
: 最大值啊，这是个简单的数学问题吧？
【在 b*****s 的大作中提到】
: 最大值啊，这是个简单的数学问题吧？
L*k
10 楼
house robber里面house的位置是固定的
这个题里面，每次取走3个数，原来中间隔了3个位置不相邻的两个数，就变成相邻了。
【在 w*****1 的大作中提到】
: House Robber I 和 House Robber II
这个题里面，每次取走3个数，原来中间隔了3个位置不相邻的两个数，就变成相邻了。
【在 w*****1 的大作中提到】
: House Robber I 和 House Robber II
L*k
11 楼
不过戳气球这种题，算是dp里面有难度的了。这个题比戳气球还更难些。关键你没做过
戳气球更难往哪个方向想。
不过按照我对g家面试的了解，这题interviewer估计自己都不一定会做dp的解，expect
你能写个工整的backtracking就给过了。当然了，也说不准是哪个练过acm的菜鸟
noogler刚开始面试拿来刷人的。
【在 L*******k 的大作中提到】
: 戳气球变种？
戳气球更难往哪个方向想。
不过按照我对g家面试的了解，这题interviewer估计自己都不一定会做dp的解，expect
你能写个工整的backtracking就给过了。当然了，也说不准是哪个练过acm的菜鸟
noogler刚开始面试拿来刷人的。
【在 L*******k 的大作中提到】
: 戳气球变种？
w*1
12 楼
这也有点太难了吧
【在 L*******k 的大作中提到】
: house robber里面house的位置是固定的
: 这个题里面，每次取走3个数，原来中间隔了3个位置不相邻的两个数，就变成相邻了。
【在 L*******k 的大作中提到】
: house robber里面house的位置是固定的
: 这个题里面，每次取走3个数，原来中间隔了3个位置不相邻的两个数，就变成相邻了。
b*s
13 楼
那又怎么了，注意这里是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个位置不相邻的两个数，就变成相邻了。
如果是顺序的话，如果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
14 楼
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 的大作中提到】
: 那又怎么了，注意这里是3n，不是2n啊，理论上乱序的话可以取走最大的n个值呀
: 如果是顺序的话，如果X_(0) 表示最大的话，就是看 sumX_(i), i=0,2,4,...,2n-2 和
: sumsumX_(i), i=13,5,...,2n-1 那个最大呀
b*s
15 楼
对啊，理论最大值
当然对每一种排列需要单列，但是最大的就是我说的呀
[在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
:的读懂了吗？
当然对每一种排列需要单列，但是最大的就是我说的呀
[在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
:的读懂了吗？
S*t
16 楼
你想简单了。
【在 b*****s 的大作中提到】
: 对啊，理论最大值
: 当然对每一种排列需要单列，但是最大的就是我说的呀
: [在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
: :的读懂了吗？
【在 b*****s 的大作中提到】
: 对啊，理论最大值
: 当然对每一种排列需要单列，但是最大的就是我说的呀
: [在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
: :的读懂了吗？
b*s
17 楼
对一个特定的排列，3n！种组合跑一遍呗，作为非coder人我准备写n遍for循环
[在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
:你想简单了。
[在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
:你想简单了。
S*t
18 楼
够暴力！
不过求教哪种编程语言能写n个for循环。。。n=100000的话你手会写酸吗
【在 b*****s 的大作中提到】
: 对一个特定的排列，3n！种组合跑一遍呗，作为非coder人我准备写n遍for循环
: [在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
: :你想简单了。
不过求教哪种编程语言能写n个for循环。。。n=100000的话你手会写酸吗
【在 b*****s 的大作中提到】
: 对一个特定的排列，3n！种组合跑一遍呗，作为非coder人我准备写n遍for循环
: [在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
: :你想简单了。
b*s
19 楼
那就迭代
[在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
:够暴力！
:不过求教哪种编程语言能写n个for循环。。。n=100000的话你手会写酸吗
[在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
:够暴力！
:不过求教哪种编程语言能写n个for循环。。。n=100000的话你手会写酸吗
o*y
20 楼
用链表和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是肯定的了 不知道怎么定义状态和转移方程 还有这个环。。。
public int getMaxSum(int[] arr){
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
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
21 楼
学习了，是我想偏了。。。
【在 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){
【在 o******y 的大作中提到】
: 用链表和backtrack:
: public int getMaxSum(int[] arr){
: 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
S*t
22 楼
backtrack: weak hire
DP: strong hire
【在 C******x 的大作中提到】
: 学习了，是我想偏了。。。
DP: strong hire
【在 C******x 的大作中提到】
: 学习了，是我想偏了。。。
g*e
23 楼
不是吧 g家不都是要求最优解的吗？暴力做出来也能过？
expect
【在 L*******k 的大作中提到】
: 不过戳气球这种题，算是dp里面有难度的了。这个题比戳气球还更难些。关键你没做过
: 戳气球更难往哪个方向想。
: 不过按照我对g家面试的了解，这题interviewer估计自己都不一定会做dp的解，expect
: 你能写个工整的backtracking就给过了。当然了，也说不准是哪个练过acm的菜鸟
: noogler刚开始面试拿来刷人的。
expect
【在 L*******k 的大作中提到】
: 不过戳气球这种题，算是dp里面有难度的了。这个题比戳气球还更难些。关键你没做过
: 戳气球更难往哪个方向想。
: 不过按照我对g家面试的了解，这题interviewer估计自己都不一定会做dp的解，expect
: 你能写个工整的backtracking就给过了。当然了，也说不准是哪个练过acm的菜鸟
: noogler刚开始面试拿来刷人的。
S*t
24 楼
g家的老美 interviewer的 expectation不高的。
这题非要要求dp也就别想招人了。
比如题库里面有道翻硬币游戏的题，出题人自己都不知道Sprague Grundy theorem，只要
求暴力。
【在 g*********e 的大作中提到】
: 不是吧 g家不都是要求最优解的吗？暴力做出来也能过？
:
: expect
这题非要要求dp也就别想招人了。
比如题库里面有道翻硬币游戏的题，出题人自己都不知道Sprague Grundy theorem，只要
求暴力。
【在 g*********e 的大作中提到】
: 不是吧 g家不都是要求最优解的吗？暴力做出来也能过？
:
: expect
b*s
25 楼
哼哼，不相信没有数学上的解法
只要
【在 S********t 的大作中提到】
: g家的老美 interviewer的 expectation不高的。
: 这题非要要求dp也就别想招人了。
: 比如题库里面有道翻硬币游戏的题，出题人自己都不知道Sprague Grundy theorem，只要
: 求暴力。
只要
【在 S********t 的大作中提到】
: g家的老美 interviewer的 expectation不高的。
: 这题非要要求dp也就别想招人了。
: 比如题库里面有道翻硬币游戏的题，出题人自己都不知道Sprague Grundy theorem，只要
: 求暴力。
l*i
26 楼
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.
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
27 楼
前面已经有人讲过了啊，这题是有dp解，就是比较难/复杂而已。
真要想做dp解，先去做下
https://leetcode.com/problems/burst-balloons/
然后你再看看能不能触类旁通。
【在 b*****s 的大作中提到】
: 哼哼，不相信没有数学上的解法
:
: 只要
真要想做dp解，先去做下
https://leetcode.com/problems/burst-balloons/
然后你再看看能不能触类旁通。
【在 b*****s 的大作中提到】
: 哼哼，不相信没有数学上的解法
:
: 只要
C*x
28 楼
多谢指教！
【在 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.
【在 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
29 楼
写一个迭代的。改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))
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
30 楼
我是说数学上 O(n)的方法
[在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
:前面已经有人讲过了啊，这题是有dp解，就是比较难/复杂而已。
:真要想做dp解，先去做下
:https://leetcode.com/problems/burst-balloons/
:然后你再看看能不能触类旁通。
[在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到：]
:前面已经有人讲过了啊，这题是有dp解，就是比较难/复杂而已。
:真要想做dp解，先去做下
:https://leetcode.com/problems/burst-balloons/
:然后你再看看能不能触类旁通。
b*s
31 楼
数学解尝试：
选一个起点，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)的方法
选一个起点，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)的方法
相关阅读
在FANG实现年薪百万的美国梦有人上过那个Grokking***Interview系列的课程吗？华人大佬看见华人就想招是吗Seattle UI/UX postion 求推荐SAS【2019年10月11日，997个米股短期谷底高峰预测】 (转载)看美剧学英语 – The office | 办公室第一季第二集精讲解析 (下)Re: 中概股这么炒作，SEC不管吗？ (转载)【Facebook】Looking for senior engineers一线大公司有经验的也是general hire么？H1B是不是不能同时给两个雇主打工？YNXO约你学哦招募计划apple厨子公开发推支持s386 (转载)【2分钟英语】Talk turkey 到底什么意思呢？【今后逢高峰卖空米股，五年内财富暴增五倍以上】 (转载)【20年11月19日收市后对1000个米股的短期预测】 (转载)现在美境内H1换工，受川普禁令大影响么？公司们还支持么？Re: 感恩节来了，新手分享入市五个月收获和思考（无科技股） (转载)【周末马前炮。近千米股暴利预测。一切在预料中】 (转载)Re: 求仁得仁，报应来得这么快 (转载)