D***0
发帖数: 138 | 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);
}
}
} | d******s
发帖数: 274 | | l*********8
发帖数: 4642 | 3 这不是完全树。 比如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*********8
发帖数: 4642 | 4 n个节点， 该“树”的高度是O(sqrt(n)).
你的方法的时间复杂度是 O( 2 ^ sqrt(n) )
【在 l*********8 的大作中提到】
: 这不是完全树。 比如8有两个parents: 9, 12.
: 你的程序会重复访问同一个节点。
| t**r
发帖数: 3428 | 5 make sense
【在 l*********8 的大作中提到】
: n个节点， 该“树”的高度是O(sqrt(n)).
: 你的方法的时间复杂度是 O( 2 ^ sqrt(n) )
| l*********8
发帖数: 4642 | 6 写了一个
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 的大作中提到】
: 刚刚店面的，一个老印，口音挺重的，说话好像离电话挺远的，接起电话连个自我介绍
: 都没有，上来就说来给我说说你的简历吧，我说完后他又问我现在的工作主要是干什么
: 的，解释了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}
| D***0
发帖数: 138 | 7 嗯，就是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*****a
发帖数: 14598 | 8 how do u update level?
【在 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*********8
发帖数: 4642 | 9 写错了。 Thanks for the catch!
【在 l*****a 的大作中提到】
: how do u update level?
| l*********8
发帖数: 4642 | 10 改了一下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*****a
发帖数: 14598 | 11 这个题是从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*********8
发帖数: 4642 | 12 题目里写： all positive numbers。 这样， 答案肯定是从root走到某个"leaf"的
sum
【在 l*****a 的大作中提到】
: 这个题是从root走到底，还是说中间任意一段都可以
: 有负数怎么办
| f******n
发帖数: 279 | | x******1
发帖数: 155 | 14 DP题，就是leetcode里面triangle吧，不过那个要求minimum,这个是maximum | j**********3
发帖数: 3211 | | l********y
发帖数: 1068 | 16 lz的代码逻辑和复杂度分析确实是正确的，bless.
【在 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}
|
|
