7/27 布鲁伯格 电面跪筋

xihaokai1 发表于 2016-7-31 22:41
第一题应该是O(n)就能做。 大致意思是这样：从第一个1（head）开始往后面延伸，碰到0就翻直到用完k次（记录 ...

8个应该只是个例子吧，是吗？

hnyjy 发表于 2016-7-31 22:54
8个应该只是个例子吧，是吗？

嗯，8个, n个，道理时一样的嘛

xihaokai1 发表于 2016-7-31 22:56
嗯，8个, n个，道理时一样的嘛

嘻嘻，我的意思是dp要记录的是股票的数量，而不是数组的size哦，对吧~

感谢楼主分享 不过感觉被黑了 希望碰见国人亲大哥啊

哪位同学能详细说下dp的解法啊。谢谢了

jy_121 发表于 2016-8-1 01:52
哪位同学能详细说下dp的解法啊。谢谢了

写了一个 感觉像背包问题~

1. class Solution {
   
2.         public int getMaxProfit(int[] arr){
   
3.                 if(arr == null || arr.length == 0) return 0;
   
4.                 int[] dp = new int[arr.length + 1];
   
5.                
   
6.                
   
7.                 for(int i = 1; i <= arr.length; i++){
   
8.                         dp[i] = arr[i - 1];
   
9.                         for(int j = 0; j <= i; j++){
   
10.                                 dp[i] = Math.max(dp[i], dp[i - j] + dp[j]);
    
11.                         }
    
12.                 }
    
13.                 return dp[arr.length];
    
14.         }
    
15.        
    
16.         public static void main(String[] args) {
    
17.                 Solution r = new Solution();
    
18.                 int[] arr = {1, 4, 7, 9,12, 3,15,20};
    
19.                 int max = r.getMaxProfit(arr);
    
20.                 System.out.println(max);
    
21.         }
    
22. }

复制代码

http://www.geeksforgeeks.org/find-index-0-replaced-1-get-longest-continuous-sequence-1s-binary-array/
http://www.geeksforgeeks.org/find-zeroes-to-be-flipped-so-that-number-of-consecutive-1s-is-maximized/

感觉可以参考下这个 东西

感觉第二题有点像combination sum的变体...

Fustang 发表于 2016-7-29 04:48
第二题类似knapsack？

LZ别哭，继续加油噜

有轮电面？。。所以你有几轮电面呀

第一题可以这样写？

public int kBinary(int[] arr, int k) {

        int maxLen = 0;
        Queue<Integer> zeroes = new LinkedList<Integer>();
        int left = -1, right = 0;

        while (right < arr.length) {

                if (arr[right] == 0) {

                        if (zeroes.size() == k) {
                                left = zeroes.poll();
                        }

                        zeroes.offer(right);
                        maxLen = Math.max(maxLen, right - left);

                }

                right++;
        }

        maxLen = Math.max(maxLen, arr.length - 1 - left);
        return maxLen;
}