[Leetcode] Summary Ranges 統(tǒng)計區(qū)間

Youngdze 發(fā)布于2019-08-14 12:33 / 1701人閱讀

摘要：雙層迭代法復雜度時間空間思路外層的循環(huán)控制每個的起點，內(nèi)層的循環(huán)控制之內(nèi)的遞增。每當遍歷完一個，就把它記錄到結果中，并更新下一個的起點。這里的技巧是，判斷一個數(shù)是否是在內(nèi)的，只要就行了，即值之差等于下標之差。

Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

雙層迭代法 復雜度

時間 O(N) 空間 O(N)

思路

外層的while循環(huán)控制每個range的起點，內(nèi)層的while循環(huán)控制range之內(nèi)的遞增。每當遍歷完一個range，就把它記錄到結果中，并更新下一個range的起點。這里的技巧是，判斷一個數(shù)是否是在range內(nèi)的，只要nums[start + range] - nums[start] = range就行了，即值之差等于下標之差。

代碼

public class Solution {
    public List summaryRanges(int[] nums) {
        List res = new LinkedList();
        if(nums.length == 0) return res;
        StringBuilder tmp = new StringBuilder();
        int start = 0;
        while(start < nums.length){
            int range = 1;
            // 遍歷當前range內(nèi)的所有數(shù)
            while(start + range < nums.length && (nums[start + range] - nums[start]) == range){
                range++;
            }
            // 遍歷完了當前range，將其加入結果中
            tmp.append(nums[start]);
            if(range > 1){
                tmp.append("->");
                tmp.append(nums[start+range-1]);
            }
            res.add(tmp.toString());
            tmp = new StringBuilder();
            // 更新下一個range的起點
            start = start + range;
        }
        return res;
    }
}

云服務器 GPU云服務器 Ranges summary LeetCode LeetCode_String

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/64553.html

［Leetcode刷題］Summary Ranges —— javascript

摘要：輸入一個排序好的整數(shù)數(shù)組，輸出數(shù)組中連續(xù)數(shù)字的范圍的數(shù)組這是我的解法，不知道有沒有有更好更快的實現(xiàn) Given a sorted integer array without duplicates, return the summary of its ranges. For example, given [0,1,2,4,5,7], return [0->2,4->5,7]. 輸入一個排...

Doyle 2019-08-19 18:33 評論0 收藏0
[Leetcode] Missing Ranges 缺失區(qū)間

摘要：想象一下假設數(shù)組前有一段連續(xù)的負無窮到，數(shù)組后有一段到正無窮，這樣是等價與上下界的。最后循環(huán)到停止，當下標為時，我們將當前指針指向，并判斷和數(shù)組末尾是否能構成最后一個區(qū)間。 Missing Ranges Given a sorted integer array where the range of elements are [lower, upper] inclusive, retu...

Gilbertat 2019-08-14 12:36 評論0 收藏0
Summary Ranges

Summary Ranges 題目鏈接：https://leetcode.com/problems... loop兩種寫法： public class Solution { public List summaryRanges(int[] nums) { List result = new ArrayList(); if(nums.length == 0) r...

yintaolaowanzi 2019-08-14 17:22 評論0 收藏0
leetcode327. Count of Range Sum

摘要：接著計算所有子數(shù)組中元素的和，并判斷是否位于數(shù)值區(qū)間內(nèi)。因此，在對左右子數(shù)組進行排序后，以左子數(shù)組中的每一位作為開頭，在右子數(shù)組中找到滿足和區(qū)間的第一個值，和超過區(qū)間的第一個值。則二者的差即為橫穿左右的滿足條件的子數(shù)組個數(shù)。題目要求 Given an integer array nums, return the number of range sums that lie in [lo...

miya 2019-08-16 16:47 評論0 收藏0
K Nearest Neighbor

摘要：而產(chǎn)生這種現(xiàn)象的唯一遠遠，僅僅是因為飛行?？屠锍虜?shù)遠大于其他特征值。但海倫認為這三種特征是同等重要的，因此作為三個等權重的特征之一，飛行?？屠锍虜?shù)并不應該如此嚴重的影響到計算結果。一、KNN概述簡單的說，k-近鄰算法采用測量不同特征值之間的距離方法進行分類。優(yōu)點：精度高、對異常值不敏感、無數(shù)據(jù)輸入假定缺點：計算復雜度高、空間復雜度高適用數(shù)據(jù)范圍：數(shù)值型和標稱型 1.1 工...

zzbo 2019-07-31 11:30 評論0 收藏0