Lexi's Leetcode solutions

Posts Tagged ‘twoPointers

有点后悔,这个题当时看了就好了,T家真的就考了类似的。要是看了就不至于现场出现当天同时买卖那个bug;从后往前scan array也不会那么生疏。。G家也是,要是看了CC150那道题就不会挂在拓扑排序上。没事,记住教训就好了——题是不能越过去的,越是skip的越有考的可能。

这个题一开始是二分法做的,每次切一刀然后左边O(n)做一次右边O(n)做一次,整体是O(n^2),超时。正确方法是一维dp从左到右扫一遍,再从右到左扫一遍,然后两次加和。
两个一维数组的定义一定要搞清,onsite的时候就栽在这上面了!

  • d[i]: [0…i]这段时间的买卖一次的最大利润。所以i应该从1开始。
  • f[i]: [i…n – 1]这段时间的买卖一次的最大利润。所以i应该最大n – 2。
  • 然后就看出问题了——两个i不能同步,否则就当天买卖了。最后加和的时候要错开。
  • 因为“最多买卖两次”, 所以还要包括买卖一次的情况。用d[n-1]就是[0…n-1]可以表达这种情况。
        public int maxProfit(int[] prices) {
	    if (prices.length == 0)
	        return 0;
	    int[] d = buildMaxProfitFromStart(prices);
	    int[] f = buildMaxProfitFromEnd(prices);
	    int maxProfit = d[prices.length - 1]; 
	    for (int i = 0; i < prices.length - 1; i++) { 			
                maxProfit = Math.max(maxProfit, d[i] + f[i + 1]); 		
            } 		
            return maxProfit; 	
        } 	
        private int[] buildMaxProfitFromEnd(int[] arr) { 		
            int[] f = new int[arr.length]; 		
            f[arr.length - 1] = 0; 		
            int max = arr[arr.length - 1]; 		
            int maxProfit = 0; 		
            for (int i = arr.length - 2; i >= 0; i--) {
	        maxProfit = Math.max(maxProfit, max - arr[i]);
		max = Math.max(max, arr[i]);
		f[i] = maxProfit;
	    }
	    return f;
	}
	private int[] buildMaxProfitFromStart(int[] arr) {
	    int[] d = new int[arr.length];
	    d[0] = 0;
	    int min = arr[0];
	    int maxProfit = 0;
	    for (int i = 1; i < arr.length; i++) {
	  	maxProfit = Math.max(maxProfit, arr[i] - min);
		min = Math.min(min, arr[i]);
		d[i] = maxProfit;
	    }
	    return d;
	}
Advertisements

和3sum一样,多加一维就多n的复杂度,这个是O(n^3),没看到别人有什么好的做法。注意防止duplicate的地方都标红了,算是比较简洁的two pointers防止dup的方式,以后可以都这么些。

    public ArrayList<ArrayList> fourSum(int[] num, int target) {
    	ArrayList<ArrayList> result = new ArrayList<ArrayList>();
    	Arrays.sort(num);
    	for (int i = 0; i < num.length; i++) {     		
                if (i > 0 && num[i] == num[i - 1])
    			continue;
    		for (int j = i + 1; j < num.length; j++) {     			
                        if (j > i + 1 && num[j] == num[j - 1] ) //一开始写的j > 0,就把1111 x=4的组合给漏掉了
    				continue;
    			int p = j + 1, q = num.length - 1;
    			while (p < q) {
    				int sum = num[i] + num[j] + num[p] + num[q];
    				if (sum == target) {
    					ArrayList quad = new ArrayList();
    					quad.add(num[i]);
    					quad.add(num[j]);
    					quad.add(num[p]);
    					quad.add(num[q]);
					result.add(quad);
					do {p++;} while (p < q && num[p] == num[p - 1]);
					do {q--;} while (p < q && num[q] == num[q + 1]);
    				} else if (sum < target) {
    					p++;
    				} else {
    					q--;
    				}
    			}
    		}
    	}
    	return result;
    }