Facebook二面跪经。。。

wtcupup 发表于 2016-3-15 09:15
请问你的代码第41行，求i左边的maxWindowSum为什么不是i-1而是i-n？

因為 i 指的是 當前中間windows的最後一位，不是第一位，所以左邊的邊界是 i-n,也就是中間windows的左邊界
代碼33行有筆誤，可能會造成無解，看最下面補充

public class KWindow{

        // n is the number of consecutives, k is the number of counts
        public int getMaxValue(int[] nums, int n, int k) {
                int len = nums.length;
                for(int i = 1; i < len; i++) {
                        nums[i] += nums[i-1];
                }
                if(len <= n * k) return nums[len-1];
                // ask interviewer if the method should return 0 when len < n*k
                int[][] dp = new int[k+1][len+1];
                for(int i = 1; i <= k; i++) {
                        for(int j = 1; j <= len; j++) {
                                if(j <= n) dp[i][j] = nums[j-1];
                                else dp[i][j] = Math.max(dp[i][j-1], nums[j-1] - nums[j-n-1] + dp[i-1][j-n-1]);
                        }
                }
                return dp[k][len];
        }

        public static void main(String[] args) {
                KWindow window = new KWindow();
                int[] nums = new int[] {1,3,7,7,2,1,1,4,8,8,6,1,1,9};
                int n = 2, k = 3;
                System.out.println(window.getMaxValue(nums, n, k) == 40);
        }
}

針對自己之前的做法優化了一下。（代碼還是很複雜的，我覺得純DP做可能還短一些。就像樓上的）。 一樣還是以中間windows為準，而左中兩個windows因為是從左往右遞增的掃，可以直接維護最大值，對於右邊的window，因為range不斷的在縮短，所以我用了一個倒著掃過的DP數組維護了歷史，可以直接調用。。這個代碼本身是出於想優化之前的想法寫的、、反正我自己是覺得。。。好亂。=-=，特別是下標，下標看不懂的自己人自己帶進去一個數組就知道了，不多解釋了，會瘋的

1. import java.util.*;
   
2. public class Solution {
   
3.     public static void main(String[] args) {
   
4.         int[] nums = new int[]{1,3,7,7,2,1,1,4,8,8,6,1,1,9};
   
5.         System.out.println(maxThreeWindowSum(nums,2));
   
6.     }
   
7. 
   
8.     private static int[] maxWindowSumHistory(int[] nums, int start, int end, int n) {
   
9.         //range = [start, end]
   
10.         //dp store max window history from  end-n-1 back to start
    
11.         if (nums == null || end - start+1 < n) throw new IllegalArgumentException();
    
12.         int sum = 0;
    
13.         int max = Integer.MIN_VALUE;
    
14.         Queue<Integer> window = new LinkedList<>();
    
15.         int[] dp = new int[end -start + 1 - n + 1];
    
16.         int idx = dp.length-1;
    
17.         for (int i = end; i >end-n + 1; i--) {
    
18.             window.offer(nums[i]);
    
19.             sum+=nums[i];
    
20.         }
    
21.         for (int i = end-n+1; i >= start; i--) {
    
22.             sum+=nums[i];
    
23.             window.offer(nums[i]);
    
24.             max = Math.max(max,sum);
    
25.             dp[idx] = max;
    
26.             idx--;
    
27.             sum-=window.poll();
    
28.         }
    
29.         return dp;
    
30.     }
    
31. 
    
32.     public static int maxThreeWindowSum(int[] nums, int n) {
    
33.         //move the window in the middle and find max window at both side;
    
34.         //Time O(nums.length^2) Space O(nums.length)
    
35.         if (nums == null || nums.length < 3*n) throw new IllegalArgumentException();
    
36.         int max = Integer.MIN_VALUE;//total 3 windows max
    
37.         int left = 0;//left max sum;
    
38.         int maxLeft = Integer.MIN_VALUE;//left windows history max
    
39.         Queue<Integer> windowLeft = new LinkedList<>();
    
40.         int middle = 0;//middle max sum
    
41.         Queue<Integer> windowMid = new LinkedList<>();
    
42.         //initialize window
    
43.         for (int i = 0; i < n-1; i++) {
    
44.             windowLeft.offer(nums[i]);
    
45.             left+=nums[i];
    
46.         }
    
47.         for (int i = n; i < 2*n-1; i++) {
    
48.             windowMid.offer(nums[i]);
    
49.             middle+=nums[i];
    
50.         }
    
51.         //history of right side
    
52.         int[] dp = maxWindowSumHistory(nums, 2*n, nums.length -1, n);
    
53.         int idx = 0;
    
54.         //start sliding window
    
55.         for (int i = 2*n - 1; i < nums.length-n; i++) {
    
56.             left+=nums[i-n];
    
57.             maxLeft = Math.max(maxLeft, left);
    
58.             windowLeft.offer(nums[i-n]);
    
59.             middle+=nums[i];
    
60.             windowMid.offer(nums[i]);
    
61.             int right = dp[idx];
    
62.             idx++;
    
63.             max = Math.max(max, maxLeft + middle + right);
    
64.             left-=windowLeft.poll();
    
65.             middle-=windowMid.poll();
    
66.         }
    
67.         return max;
    
68.     }
    
69. }

复制代码

补充内容 (2016-3-15 09:58):
忘了，時間應該是2n了，left和middle window掃一次，right掃一次

nuanuan1208 发表于 2016-3-15 09:27
public class KWindow{

        // n is the number of consecutives, k is the number of counts

大神能解释下这个推导公式么。

nuanuan1208 发表于 2016-3-15 09:27
public class KWindow{

        // n is the number of consecutives, k is the number of counts

看懂了，大神太厉害了。五体投地。这dp掌握的真心扎实。

primbo 发表于 2016-3-15 10:57
看懂了，大神太厉害了。五体投地。这dp掌握的真心扎实。

不是大神@@主要是现在比较放松，要是在面试的紧张状态下也不一定能写出来@@

bless lz拿offer哈~！

nuanuan1208 发表于 2016-3-15 11:05
不是大神@@主要是现在比较放松，要是在面试的紧张状态下也不一定能写出来@@

bless lz拿offer哈~！

真的膜拜。。我想了半天也就想了掃一次的DP，另外兩個直接實時算，雖然複雜度也是O(N)，不過代碼很難看，外加不能擴展到k>3的情況

nuanuan1208 发表于 2016-3-15 11:05
不是大神@@主要是现在比较放松，要是在面试的紧张状态下也不一定能写出来@@

bless lz拿offer哈~！

又测试了一下好像有点儿问题哈，k等于4的时候最大的应该是 50哈。你试试？

primbo 发表于 2016-3-15 11:16
又测试了一下好像有点儿问题哈，k等于4的时候最大的应该是 50哈。你试试？

是的呢@@这个
nums[j-1] - nums[j-n-1] + dp[i-1][j-n-1]);
应该是 dp[i-1][j-n]

        public int getMaxValue(int[] nums, int n, int k) {
                int len = nums.length;
        int[] sum = new int[len];
                for(int i = 0; i < len; i++) {
            sum[i] = (i == 0 ? 0 : sum[i-1]) + nums[i];
                }
                if(len <= n * k) return sum[len-1];
                // ask interviewer if the method should return 0 when len < n*k
        int[] prev = new int[len+1];
                for(int i = 1; i <= k; i++) {
            int[] dp = new int[len+1];
                        for(int j = i * n; j <= len; j++) {
                                if(j == i * n) dp[j] = sum[j-1];
                                else dp[j] = Math.max(dp[j-1], sum[j-1] - sum[j-n-1] + prev[j-n]);
                        }
            prev = dp;
                }
                return prev[len];
        }
优化了一下，希望不要再有bug了