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

目录

  1. Interval
  2. Buy and Sell
  3. Shortest/Longest/SubSequence
  4. Others

[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
  1. We create the deque
  2. 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.
  3. At any point, we want to remove all elements from the end which are smaller than the current element which is being inserted.
  4. We will remove elements from the start of the deque if it doesn't belong to the window.
  5. 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;
    }
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 217,734评论 6赞 505
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,931评论 3赞 394
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 164,133评论 0赞 354
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,532评论 1赞 293
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,585评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,462评论 1赞 302
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,262评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,153评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,587评论 1赞 314
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,792评论 3赞 336
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,919评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,635评论 5赞 345
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,237评论 3赞 329
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,855评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,983评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,048评论 3赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,864评论 2赞 354

推荐阅读更多精彩内容