[Leetcode][Array--2]数组相关题目汇总/分析/

2019-06-13 本文已影响0人奔跑的程序媛A

Interval
- 56 Merge Intervals
- 57 Insert Interval
- 915 Partition Array into Disjoint Intervals
- 352 Data Stream as Disjoint Intervals
Buy and Sell
Shortest/Longest/SubSequence
Others
- 55 Jump Game
- 45 Jump Game II
- 11 Container With Most Water
- 42 Trapping Rain Water
- 134 Gas Station
- 164 Maximum Gap
- 239 Sliding Window Maximum

[Interval]

#56 Merge Intervals

Sol Sort
首先按照每个区间的起始点由小到大排序，依次遍历区间，如果此时的区间与前一个区间重叠，则更新前一个区间的end值，如果不重叠，则添加该区间到res
为了练习，自己写quick sort排序

public int[][] merge(int[][] intervals) {
        
        quick_sort(intervals, 0, intervals.length-1);
        int[][] res = new int[intervals.length][2];
        if(intervals.length == 0) return res;
        res[0] = intervals[0];
        int len = 1;
        int k = 0;
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] <= res[k][1]){
                res[k][1] = Math.max(intervals[i][1], res[k][1]);
            }else{
                len++;
                res[++k] = intervals[i];
            }
        }
        int[][] r = new int[len][2];
        int j = 0;
        for(int i = 0; i < res.length; i++){
            if(res[i][0] == 0 && res[i][1] == 0){
                // System.out.println(res[i][0] + " "+res[i][1]);
                continue;
            }else r[j++] = res[i];
        }
        return r;
        
    }
    public void quick_sort(int[][] interval, int s, int e){
        if(s < e){
            int i = s+1, j = e;
            int p = interval[s][0];
            while(i <= j ){
                while(i <= j && interval[i][0] <= p){
                    i++;
                }
                while(i <= j && interval[j][0] >= p){
                    j--;
                }
                if(i < j){
                    int[] tmp = interval[i];
                    interval[i] = interval[j];
                    interval[j] = tmp;
                }
            }
            if(s < j){
                int[] tmp = interval[s];
                interval[s] = interval[j];
                interval[j] = tmp;
                quick_sort(interval, s, j-1);
            }
            if(j < e){
                quick_sort(interval, j+1, e);
            }
        }
    }

#57 Insert Interval

Sol Sort & 遍历
插入排序，遍历合并

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] insert_interval = new int[intervals.length + 1][2];
        if(intervals.length == 0) {
            insert_interval[0] = newInterval;
            return insert_interval;
        }
        insert_sort(insert_interval, intervals, newInterval);
        // int[][] res = new int[intervals.length + 1][2];
        int len = merge(insert_interval);
        int[][] res = new int[len][2];
        int j = 0;
        for(int i = 0; i < intervals.length + 1; i++){
            if(insert_interval[i][0] == -1 && insert_interval[i][1] == -1){
                continue;
            }else res[j++] = insert_interval[i];
        }
        return res;
    }
    public void insert_sort(int[][] res, int[][] intervals, int[] newInterval){
        int j = 0;
        for(int i = 0; i < intervals.length; i++){
            if(intervals[i][0] <= newInterval[0]){
                res[j++] = intervals[i];
            }else{
                res[j++] = newInterval;
                while(j < res.length){
                    res[j++] = intervals[i++];
                }
                return;
            }
        }
        res[j] = newInterval;
    }
    public int merge(int[][] array){
        if(array.length == 0) return 0;
        int len = 1, j = 0;
        for(int i = 1; i < array.length; i++){
            if(array[i][0] <= array[j][1]){
                array[j][1] = Math.max(array[j][1], array[i][1]);
                array[i][0] = -1;
                array[i][1] = -1;
            }else{
                len++;
                j = i;
            }
        }
        return len;
        
    }
}

#915 Partition Array into Disjoint Intervals

Sol
记录以i位置区分，左边最大值和右边最小值

class Solution {
    public int partitionDisjoint(int[] A) {
        if(A.length == 0) return 0;
        int[] maxLeft = new int[A.length];
        int[] minright = new int[A.length];
        int l = A[0];
        maxLeft[0] = l;
        for(int i = 1; i < A.length; i++){
            l = Math.max(l, A[i]);
            maxLeft[i] = l;
        }
        l = A[A.length-1];
        minright[A.length-1] = Integer.MAX_VALUE;
        for(int i = A.length-2; i >= 0; i--){
            minright[i] = l;
            l = Math.min(l, A[i]);
        }
        for(int i = 0; i < A.length; i++){
            if(maxLeft[i] <= minright[i]){
                return i+1;
            }
        }
        return A.length;
    }
}

#352 Data Stream as Disjoint Intervals

Sol

class SummaryRanges {

    public List<int[]> intervals;
    /** Initialize your data structure here. */
    public SummaryRanges() {
        intervals = new ArrayList<>();
    }
    
    public void addNum(int val) {
        int[] newInterval = new int[]{val, val};
        List<int[]> res = new ArrayList<>();
        int[][] intervals_arr = getIntervals();
        boolean flag = false;
        for(int[] interval :intervals_arr){
            if(newInterval[0]-1>interval[1])
                res.add(interval);
            else if(newInterval[1]+1<interval[0]){
                if(!flag){
                    res.add(newInterval);
                    flag = true;
                }
                res.add(interval);
            }
            else{
                newInterval[0] = Math.min(newInterval[0], interval[0]);
                newInterval[1] = Math.max(newInterval[1], interval[1]);
            }
        }
        if(!flag)
            res.add(newInterval);
        intervals = res;
    }
    
    public int[][] getIntervals() {
        return intervals.toArray(new int[intervals.size()][2]);
    }
}

[Buy and Sell]

#121 Best Time to Buy and Sell Stock

买一次卖一次结束

Sol Peak Valley
遍历记录valley的值，计算max_profile

class Solution {
    public int maxProfit(int[] prices) {
        int buy = Integer.MAX_VALUE, res = 0;
        for(int i = 0; i < prices.length; i++){
            if(prices[i] < buy){
                buy = prices[i];
            }else if((prices[i] - buy) > res){
                res = prices[i] - buy;
            }
        }
        return res;
    }
}

#122 Best Time to Buy and Sell Stock II

买一次卖一次，买一次卖一次，买一次卖一次，。。。结束

Sol Peak Valley

遍历计算max_profile += peek-valley

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        for(int i = 1; i < prices.length; i++){
            if(prices[i] > prices[i-1]){
                res += prices[i] - prices[i-1];
            }
        }
        return res;
    }
}

    public int maxProfit(int[] prices) {
        int valley = prices[0];
        int peek = prices[0];
        int res = 0;
        for(int i = 1; i < prices.length;){
            while(i < prices.length && prices[i] > prices[i-1]) i++;
            valley = prices[i];
            while(i < prices.length-1 && prices[i] <= prices[i+1]) i++;
            peek = prices[i];
            res += peek - valley;
        }
        return res;
    }

    public int maxProfit(int[] prices) {
        int fund_sel = Integer.MIN_VALUE; // funding for selling
        int fund_buy = 0; // funding for buying
        
        for(int i=0; i<prices.length; i++) {
            // buy if we get more funds 
            fund_sel = Math.max(fund_sel, fund_buy - prices[i]);
            // sell if we get more funds
            fund_buy = Math.max(fund_buy, fund_sel + prices[i]);
            // also buying and selling on the same day counts
        }
        
        return fund_buy;
    }

#123 Best Time to Buy and Sell Stock III

买一次卖一次，买一次卖一次，结束

Sol One pass
所有变量均为收益值，sell加buy则减
TimeO(n)

class Solution {
    public int maxProfit(int[] prices) {
        int one_buy = Integer.MIN_VALUE;
        int one_profite = 0;
        int two_buy = Integer.MIN_VALUE;
        int two_profite = 0;
        for(int i = 0; i < prices.length ;i++){
            one_buy = Math.max(one_buy, 0-prices[i]);
            one_profite = Math.max(one_profite, one_buy + prices[i]);
            two_buy = Math.max(two_buy, one_profite-prices[i]);
            two_profite = Math.max(two_profite, two_buy + prices[i]);
        }
        return Math.max(one_profite, two_profite);
    }
}

#188 Best Time to Buy and Sell Stock IV

至多完成 k 次交易，只允许买一次卖一次，不可以买买买再卖

Sol DP
dp[i][k]表示对于prices[0...i] k次交易的最大收益
base case：dp[0][k] = 0，dp[i][0] = 0
recursive relationship：
dp[i][k] = Math.max(dp[i-1][k], Math.max(dp[i] - dp[j] + dp[j-1][k-1])for j in [0...i-1] )
改进：
local_max记录dp[j-1][k-1]- dp[j]for j from 0 to i-1.
dp[i][k] = Math.max(dp[i-1][k], dp[i] + local_max）

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if(n < 2) return 0;
        if(k >= n){
            int max_profit = 0;
            for(int i = 0; i < n-1; i++)
                max_profit += Math.max(prices[i+1] - prices[i], 0);
            return max_profit;
        }
        int[][] dp = new int[n][k+1];
        for(int i = 0; i < n; i++){
            dp[i][0] = 0;
        }
        for(int i = 0; i <= k; i++){
            dp[0][i] = 0;
        }
        for(int i = 1; i <= k; i++){
            int local_max = -prices[0];
            for(int j = 1; j < n; j++){
                dp[j][i] = Math.max(dp[j-1][i], prices[j] + local_max);
                local_max = Math.max(local_max, dp[j-1][i-1]- prices[j]);
            }
        }
        return dp[n-1][k];

    }
}

#309 Best Time to Buy and Sell Stock with Cooldown

买一次卖一次，卖一次休息一次

Sol 针对#122的改进

    public int maxProfit(int[] prices) {
        int fund_sel = Integer.MIN_VALUE; // funding for selling
        int fund_buy = 0; // funding for buying
        int delay = 0;
        for(int i=0; i<prices.length; i++) {
            // buy if we get more funds 
            fund_sel = Math.max(fund_sel, delay - prices[i]);
            delay = fund_buy;
            // sell if we get more funds
            fund_buy = Math.max(fund_buy, fund_sel + prices[i]);
            // also buying and selling on the same day counts
        }
        
        return fund_buy;
    }

[Shortest/Longest/SubSequence]

#334 Increasing Triplet Subsequence

Sol
记录前两个min值
TimeO(n) SpaceO(1)

    public boolean increasingTriplet(int[] nums) {
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        for(int i = 0; i < nums.length-1; i++){
            if(nums[i] > min2) return true;
            if(nums[i] < nums[i+1]){
                
                if(min2 < nums[i+1])
                    return true;

                if(nums[i] < min1){
                    min1 = nums[i]; 
                    min2 = nums[i+1]; 
                } else if(nums[i] != min1)
                    min2 = nums[i];

            }
        }
        return false;
    }

#674 Longest Continuous Increasing Subsequence

Sol Sliding Window

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums.length == 0) return 0; 
        int res = 0, tmp_res = 0;
        for(int i = 0; i < nums.length-1; i++){
            if(nums[i] < nums[i+1]){
                tmp_res++;
            }else{
                if(++tmp_res > res) res = tmp_res;
                tmp_res = 0;
            }
        }
        if(++tmp_res > res) res = tmp_res;
        return res;
    }
}

#673 Number of Longest Increasing Subsequence

Sol DP
count[i]与Length[i]分别记录nums[0...i]的最大长度的subsequence的个数与长度。
for j in (0...i)如果nums[j] < nums[i],更新Length[i] = Length[j]+1
如果此时的Length[i] 比之前的大，则count[i] =count[j]
如果此时的Length[i] 与之前的相同，则count[i] += count[j]
TimeO(n^2) SpaceO(n)

    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] length = new int[n];
        int[] count = new int[n];
        Arrays.fill(count, 1);
        int max_length = 0, res = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    if(length[j]+1 == length[i]){
                        count[i] += count[j];
                    }else if(length[j] >= length[i]){
                        length[i] = length[j]+1;
                        count[i] = count[j];
                    }
                }
            }
            max_length = Math.max(max_length, length[i]); 
        }

        for(int i = 0; i < n; i++){
            if(length[i] == max_length){
                res += count[i];
            }
        }
        return res;   
    }

#128 Longest Consecutive Sequence

Sol HashSet
TimeO(n) SpaceO(n)

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for(int n: nums){
            s.add(n);
        }
        int res = 0;
        for(int n: s){
            if(!s.contains(n-1)){
                int cur = n;
                int cur_len = 1;
                while(s.contains(n+1)){
                    n++;
                    cur_len++;
                }
                res = Math.max(res,cur_len);
            }
        }
        return res;
    }
}

[Others]

#55 Jump Game

Sol Greedy
从后向前遍历

    public boolean canJump(int[] nums) {
        int reachable = 0;
        for(int i=nums.length-2;i>=0;i--){
            if(nums[i]<=reachable)
                reachable++;
            else
                reachable = 0;
        }
        return reachable==0;
    }

#45 Jump Game II

用最少的步数

Sol DP
bottom-up

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        for(int i = 0; i < n-1; i++){
            dp[i] = Integer.MAX_VALUE;
        }
        for(int i = nums.length-2; i>= 0; i--){
            for(int j = 1; j <= nums[i]; j++){
                if(i+j < n && dp[i+j] < Integer.MAX_VALUE){
                    dp[i] = Math.min(dp[i+j]+1, dp[i]);
                }
            }
        }
        return dp[0] == Integer.MAX_VALUE ? 0 : dp[0];
    }
}

#11 Container With Most Water

找出max[(j-i) * min(ai, aj)]

Sol Two Pointer
一前一后两指针，长度优先，计算tmp_res
更新较短的高，即保留更长的边（高度）

class Solution {
    public int maxArea(int[] height) {
        int a = 0, b = height.length-1, res = 0;
        while(a < b){
            int tmp = Math.min(height[a], height[b]) * (b-a);
            if(tmp > res) res = tmp;
            if(height[a] < height[b]) a++;
            else b--;
        }
        return res;
    }
}

#42 Trapping Rain Water

Sol Two Pointer
类似#11，记录左边右边最大高度

class Solution {
    public int trap(int[] height) {
        int a = 0, b = height.length-1, res = 0;
        int max_left = 0, max_right = 0;
        while(a < b){
            if(height[a] < height[b]){
                if(max_left <= height[a]){
                   max_left = height[a];
                }else{
                    res += max_left - height[a];
                }
                a++;
            }
            else{
                if(max_right <= height[b]) max_right = height[b];
                else res += max_right - height[b];
                b--;
            }
        }
        return res;
    }
}

#134 Gas Station

Sol One Pass

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int gasLeft = 0, tank = 0, start = 0;
        for(int i = 0; i < gas.length; i++){
            gasLeft += (gas[i] - cost[i]);
            tank += (gas[i] - cost[i]);
            if(tank < 0){
                tank = 0;
                start = i+1;
            }
        }
        if(gasLeft < 0)return -1;
        return start;
    }

#164 Maximum Gap

要求solve it in linear time/space.

Sol 桶排序

    public int maximumGap(int[] nums) {
        if(nums.length <= 1) return 0;
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for(int i : nums){
            min = Math.min(min, i);
            max = Math.max(max, i);
        }
        if(min == max) return 0;
        int n = nums.length;
        int b = (max - min) / n + 1;
        int[][] buckets = new int[n][];
        for(int i = 0; i < n; i++){
            int k = (nums[i] - min) / b;
            if(buckets[k] == null){
                buckets[k] = new int[]{nums[i], nums[i]};
            }else{
                buckets[k][0] = Math.min(buckets[k][0], nums[i]);
                buckets[k][1] = Math.max(buckets[k][1], nums[i]);
            }
        }
        int maxGap = Integer.MIN_VALUE;
        int previous = min;
        for(int i = 0; i < n; i++) {
            if(buckets[i] == null) continue;
            maxGap = Math.max(maxGap, Math.max(buckets[i][1] - buckets[i][0], buckets[i][0] - previous));
            previous = buckets[i][1];
        }
        return maxGap;
    }

#239 Sliding Window Maximum

要求Time O(n)

Sol Deque

We create the deque
Before inserting an element in the deque, we check if the last element in the deque is smaller than the current element or not. If it is smaller, then we remove the last element.
At any point, we want to remove all elements from the end which are smaller than the current element which is being inserted.
We will remove elements from the start of the deque if it doesn't belong to the window.
We print the maximum element from the start of the window for the current sliding window.

    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[]{};
        int[] res = new int[nums.length - k  + 1];
        Deque<Integer> q = new LinkedList<Integer>();
        for(int i = 0; i < nums.length; i++){
            while(!q.isEmpty() && q.peek() <= i - k){
                q.remove();
            }
            while(!q.isEmpty() && nums[q.peekLast()] <= nums[i]){
                q.removeLast();
            }
            q.add(i);
            if(i >= k - 1){
                res[i - k + 1] = nums[q.peek()];
            }
        }
        return res;
    }

[Leetcode][Array--2]数组相关题目汇总/分析/

目录

[Interval]

#56 Merge Intervals

#57 Insert Interval

#915 Partition Array into Disjoint Intervals

#352 Data Stream as Disjoint Intervals

[Buy and Sell]

#121 Best Time to Buy and Sell Stock

#122 Best Time to Buy and Sell Stock II

#123 Best Time to Buy and Sell Stock III

#188 Best Time to Buy and Sell Stock IV

#309 Best Time to Buy and Sell Stock with Cooldown

[Shortest/Longest/SubSequence]

#334 Increasing Triplet Subsequence

#674 Longest Continuous Increasing Subsequence

#673 Number of Longest Increasing Subsequence

#128 Longest Consecutive Sequence

[Others]

#55 Jump Game

#45 Jump Game II

#11 Container With Most Water

#42 Trapping Rain Water

#134 Gas Station

#164 Maximum Gap

#239 Sliding Window Maximum

猜你喜欢

热点阅读