Xülasə Leetcode Həlli üçündür

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Facebook Yandex
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 29

Problem bəyanat

Xülasə Aralığında problem a unikal çeşidlənir tam sıra verilir. Etməliyik ən kiçik sıralanır aralıkların siyahısı bütün nömrələri əhatə edir array tam bir dəfə yəni massivin hər bir elementi aralıqlardan tam biri ilə əhatə olunur.

Siyahıdakı hər bir [a, b] aralığı aşağıdakı şəkildə çıxarılmalıdır:

A! = B olduqda “a-> b”
A == b olduqda “a”

misal

nums = [0,1,2,4,5,7]
["0->2","4->5","7"]

Explanation:

Aralıklar:
“0-> 2” rəqəmləri əhatə edir {0, 1, 2}
“4-> 5” rəqəmləri əhatə edir {4, 5}
"7" rəqəmləri əhatə edir {7}

Buna görə massivin bütün nömrələrini tam bir dəfə əhatə edir.

nums = [0,2,3,4,6,8,9]
["0","2->4","6","8->9"]

Explanation:

Aralıklar:
[0,0] -> “0”
[2,4] -> “2-> 4”
[6,6] -> “6”
[8,9] -> “8-> 9”

Yanaşma

Yuxarıda qeyd edildiyi kimi aralıkların ən kiçik siyahısını hazırlamalıyıq. Buna görə iki qonşu element 1 fərqlə fərqlənirsə, eyni aralığa aid olmalıdır. Digər tərəfdən iki qonşu elementin 1-dən çox fərqi varsa, eyni aralığa aid ola bilməzlər.

Xülasə Leetcode Həlli üçündürPin

Beləliklə, indi alqoritm sadədir. Hər bitişik element üçün keçməliyik. Bitişik iki ədəd arasındakı fərq 1-dən çoxdursa, ikinci rəqəm üçün yeni bir aralıq etməliyik. Əks təqdirdə, fərq tam olaraq 1 olarsa, bu rəqəmi eyni aralığa qoyacağıq.

Alqoritm

  1. Nəticəni saxlamaq üçün bir sətir siyahısı yaradın.
  2. Dizini gəzməyə başlayın i = 0 üçün i<N, (N, serialın ölçüsüdür) a döngə zamanı.
    • Sayı cari indeksdə qeyd edin Başlamaq menzilin.
    • Dizini cari indeksdən başlayaraq keçin və əvvəlki elementdən fərqi tam 1 olan son elementi tapın, yəni nums [i + 1] == nums [i] +1
    • Bu elementi olaraq qeyd edin son menzilin.
    • İndi bu əmələ gələn aralığı nəticələnəcək siyahı. Və qalan elementlər üçün təkrarlayın.
  3. Qayıt nəticələnəcək siyahı.

Həyata keçirilməsi

Xülasə Aralığı Leetcode Həlli üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;

vector<string> summaryRanges(vector<int>& nums) 
{
    vector<string> res;
    int i=0,n=nums.size();
    while(i<n)
    {
        int start,end;

        start=nums[i];            
        while(i+1<n && nums[i+1]==nums[i]+1) i++;
        end=nums[i];

        if(start==end)
            res.push_back(to_string(start));
        else
            res.push_back(to_string(start) + "->" + to_string(end));

        i++;
    }

    return res;
}

int main() 
{   
    vector<int> nums={0,1,2,4,5,7};
    vector<string> res= summaryRanges(nums);
    
    for(auto str:res) cout<< str <<endl;
    
    return 0; 
}
0->2
4->5
7

Xülasə Aralığı Leetcode Həlli üçün Java Proqramı

import java.util.*;
class Rextester{
    
    public static List<String> summaryRanges(int[] nums) 
    {      
        List<String> res= new ArrayList<String>();
        
        int i=0,n=nums.length;
        while(i<n)
        {
            int start,end;
            
            start=nums[i];            
            while(i+1<n && nums[i+1]==nums[i]+1) i++;
            end=nums[i];
            
            if(start==end)
                res.add(start + "");
            else
                res.add( start + "->" + end );
            
            i++;          
        }
        
        return res;
    }
    
  public static void main(String args[])
    {
        int[] nums={0,1,2,4,5,7};
        List<String> res= summaryRanges(nums);
        
        for(String str:res)
            System.out.println(str);
    }
}
0->2
4->5
7

Xülasə Aralığı Leetcode Həlli üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (N): Harada N, verilən massivin ölçüsüdür. İki iç içə döngə istifadə etməyimizə baxmayaraq, hər element yalnız bir dəfə ziyarət olunur. Beləliklə, zamanın mürəkkəbliyi O (N) -dir.

Kosmik Mürəkkəblik 

O (1): Simlərin siyahısını qaytarmaq xaricində heç bir köməkçi yerdən istifadə etmirik.

Şərh yaz

Translate »
1