C*x
2 楼
有3n个数围成一个环,取走其中一个的话会顺带去掉这个数相邻的两个数(这两个不计
入总和),剩下的继续围成环,问取走n个数构成总和的最大值。
DP是肯定的了 不知道怎么定义状态和转移方程 还有这个环。。。
入总和),剩下的继续围成环,问取走n个数构成总和的最大值。
DP是肯定的了 不知道怎么定义状态和转移方程 还有这个环。。。
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
15 楼
对啊,理论最大值
当然对每一种排列需要单列,但是最大的就是我说的呀
[在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到:]
:的读懂了吗?
当然对每一种排列需要单列,但是最大的就是我说的呀
[在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到:]
:的读懂了吗?
b*s
17 楼
对一个特定的排列,3n!种组合跑一遍呗,作为非coder人我准备写n遍for循环
[在 SecretVest (秘甲 (采蘑菇的小马甲)) 的大作中提到:]
:你想简单了。
[在 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是肯定的了 不知道怎么定义状态和转移方程 还有这个环。。。
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)的方法
相关阅读
小弟求一个微软的REFERG intern 感谢+host match求收留你们公司python 主要做什么重要活Bloomberg 最新onsite 面经 【PASS】Leetcode oj 的答案CPT 挂靠公司的问题老中不改思维方式,永远就是这样的结局,无情冷酷的现实有人了解G家这两个组吗?提供OPT挂靠面salesforce的童鞋都被要求做那个online test了吗?A家 interview event形式的几时出结果?OPT Pending期间,没有offer letter,能去加勒比海的cruise吗?Google的hiring committee是多少人?国内有什么好的单位,想回国面试去了FLG有自己的research lab吗?offer letterAppDynamics 长期 refer求问啊 怎么和HR 谈 offer啊老印最后给code照相就是挂了的意思吧?内推软件工程师C++/Java