特别想讲一个政治高手的故事 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Parenting - 为人父母

特别想讲一个政治高手的故事

特别想讲一个政治高手的故事# Parenting - 为人父母

D*02016-03-05 08:03

1 楼

刚刚店面的，一个老印，口音挺重的，说话好像离电话挺远的，接起电话连个自我介绍
都没有，上来就说来给我说说你的简历吧，我说完后他又问我现在的工作主要是干什么
的，解释了3遍这哥们才算明白，难道就这么浪费我宝贵的45分钟？接下来问如何给一
个网站比如尼玛推特设计一个log系统，如果用户打开尼玛推特什么也没有怎么根据你
的log系统查（心中草泥马奔腾啊），说了一堆后，这厮说ok，快到点了，做道题吧，
11
9 12
4 8 6
2 7 3 1
int[] nums = {11, 9, 12, 4, 8, 6, 2, 7, 3, 1}
valid move: 9 - 4 or 8
invalid : 9 - 11 or 12 or 6
all positive numbers
find max sum in any number of possible moves
38 (11 + 12 + 8 + 7)
就是把树装数组里了，他说你可以是认为是完全三角形。好吧，我就开始说我的思路，
刚写
了如何找到左右子的公式，这厮就迫不及待的打断，说你不用解释，快写吧，我操，我
刚要说我的思路。好吧写了个递归，前序的。然后问了复杂度，一开始我说遍历每个点
，那就是O(n),他说不对，难道是O(nlogn)
看来这是要挂人的节奏啊，尼玛不想要何苦呢。
long findMax(int[] nums) {
if(nums == null || nums.length == 0) return 0;
HashMap map = new HashMap();
map.put("max", 0);
findMax(nums, 0, 0, 1, map);
return map.get("max");
}
void findMax(int[] nums, int root, long sum, int level, HashMap> map)
{
if(root < nums.length)
{
findMax(nums, root+level, sum + nums[root], level+1, map);
findMax(nums, root+level+1, sum + nums[root], level+1, map);
}
else
{
long max = map.get("max");
if(sum > max)
{
map.put("max", sum);
}
}
}

r*02016-03-05 08:03

2 楼

在闹市区开了两年连着的杂货店，一个店主是男的，一个店主是女的，两家水火不容。
常常为争客户大骂出口是小事，那些低价甩卖，赔本也要搞死对方的各种销售策略在
一家店刚结束，另一家又起。他们两家的不共戴天之仇也是渐渐声明远播，居民为看
热闹也有好奇之人常常跑去，也无意中买了不少东西。更有离骚之人故意在两家询价
后，告诉买家说隔壁的如何，挑拨俩家。两店家常常上当，为此也是每日必斗。连一
个小偷都忍不住跑去光顾，当然他是晚间商店打样之后。进去发现两店面通为一共同卧
室厨房，两店家正在床上用每日骂街之词互相调戏对方。

d*s2016-03-05 08:03

3 楼

lg(n)吧完全树等于高度

l*82016-03-05 08:03

4 楼

这不是完全树。比如8有两个parents: 9, 12.
你的程序会重复访问同一个节点。

【在 D***0 的大作中提到】

: 刚刚店面的，一个老印，口音挺重的，说话好像离电话挺远的，接起电话连个自我介绍
: 都没有，上来就说来给我说说你的简历吧，我说完后他又问我现在的工作主要是干什么
: 的，解释了3遍这哥们才算明白，难道就这么浪费我宝贵的45分钟？接下来问如何给一
: 个网站比如尼玛推特设计一个log系统，如果用户打开尼玛推特什么也没有怎么根据你
: 的log系统查（心中草泥马奔腾啊），说了一堆后，这厮说ok，快到点了，做道题吧，
: 11
: 9 12
: 4 8 6
: 2 7 3 1
: int[] nums = {11, 9, 12, 4, 8, 6, 2, 7, 3, 1}

l*82016-03-05 08:03

5 楼

n个节点，该“树”的高度是O(sqrt(n)).
你的方法的时间复杂度是 O( 2 ^ sqrt(n) )

【在 l*********8 的大作中提到】

: 这不是完全树。比如8有两个parents: 9, 12.
: 你的程序会重复访问同一个节点。

t*r2016-03-05 08:03

6 楼

make sense

【在 l*********8 的大作中提到】

: n个节点，该“树”的高度是O(sqrt(n)).
: 你的方法的时间复杂度是 O( 2 ^ sqrt(n) )

l*82016-03-05 08:03

7 楼

写了一个
int maxSum(int A[], int n) {
if (n < 1) return 0;
vector dp(n, 0);
dp[0] = A[0];

int level = 1;
for (int i = 0; i + level < n; i++) {
int child = i+level;
dp[child] = max(dp[child], A[child] + dp[i]);
if (++child < n)
dp[child] = max(dp[child], A[child] + dp[i]);
}

return *max_element(dp.begin(), dp.end());
}

【在 D***0 的大作中提到】

D*02016-03-05 08:03

8 楼

嗯，就是lc三角型往下走，这会是求最大值，复杂度是你说的。
反正是跪了。

【在 l*********8 的大作中提到】

: 写了一个
: int maxSum(int A[], int n) {
: if (n < 1) return 0;
: vector dp(n, 0);
: dp[0] = A[0];
:
: int level = 1;
: for (int i = 0; i + level < n; i++) {
: int child = i+level;
: dp[child] = max(dp[child], A[child] + dp[i]);

l*a2016-03-05 08:03

9 楼

how do u update level?

【在 l*********8 的大作中提到】

l*82016-03-05 08:03

10 楼

写错了。 Thanks for the catch!

【在 l*****a 的大作中提到】

: how do u update level?

l*82016-03-05 08:03

11 楼

改了一下lolhaha指出的错误。也许还有其他错。。。
int maxSum(int A[], int n) {
if (n < 1) return 0;
vector dp(n, 0);
dp[0] = A[0];

int firstInLevel = 0;
int level = 1;
for (int i = 0; i + level < n; i++) {
if (i - firstInLevel == level) {
++level;
firstInLevel = i;
}
int child = i+level;
dp[child] = max(dp[child], A[child] + dp[i]);
if (++child < n)
dp[child] = max(dp[child], A[child] + dp[i]);
}

return *max_element(dp.begin(), dp.end());
}

l*a2016-03-05 08:03

12 楼

这个题是从root走到底，还是说中间任意一段都可以
有负数怎么办

【在 l*********8 的大作中提到】

: 改了一下lolhaha指出的错误。也许还有其他错。。。
: int maxSum(int A[], int n) {
: if (n < 1) return 0;
: vector dp(n, 0);
: dp[0] = A[0];
:
: int firstInLevel = 0;
: int level = 1;
: for (int i = 0; i + level < n; i++) {
: if (i - firstInLevel == level) {

l*82016-03-05 08:03

13 楼

题目里写： all positive numbers。这样，答案肯定是从root走到某个"leaf"的
sum

【在 l*****a 的大作中提到】

: 这个题是从root走到底，还是说中间任意一段都可以
: 有负数怎么办