Ամփոփ շարքեր Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են facebook Yandex
Դասավորություն

Խնդիրի հայտարարություն

Ամփոփ շարքերի խնդրում a տեսակավորված եզակի տրված է ամբողջ զանգված: Մենք պետք է պատրաստենք ամենափոքր տեսակավորված միջակայքերի ցուցակ, որոնք ընդգրկել բոլոր համարները ներսում դասավորություն ուղիղ մեկ անգամ այսինքն `զանգվածի յուրաքանչյուր տարր ծածկված է միջակայքերից հենց մեկով:

Aուցակում յուրաքանչյուր [a, b] միջակայքը պետք է թողարկվի հետևյալ կերպ.

«A-> b», եթե a! = B
«Ա», եթե a == b

Օրինակ

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

Բացատրությունը.

Միջակայքերը `
«0-> 2» -ն ընդգրկում է {0, 1, 2} թվերը
«4-> 5» -ն ընդգրկում է {4, 5} թվերը
«7» -ը ընդգրկում է {7} համարները

Այսպիսով, այն ընդգրկում է զանգվածի բոլոր թվերը ուղիղ մեկ անգամ:

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

Բացատրությունը.

Միջակայքերը `
[0,0] -> «0»
[2,4] -> «2-> 4»
[6,6] -> «6»
[8,9] -> «8-> 9»

Մոտեցում

Ինչպես նշվեց վերևում, մենք պետք է կազմենք միջակայքերի ամենափոքր ցուցակը: Հետևաբար, եթե հարակից երկու տարրեր տարբերվում են 1 տարբերությամբ, ապա դրանք պետք է պատկանեն նույն տիրույթին: Մյուս կողմից, եթե հարակից երկու տարրեր ունեն 1-ից մեծ տարբերություն, ապա դրանք չեն կարող պատկանել նույն տիրույթին:

Ամփոփ շարքեր Leetcode լուծում

Այսպիսով, այժմ ալգորիթմը պարզ է: Մենք պետք է անցնենք յուրաքանչյուր հարակից տարրերի համար: Եթե ​​երկու հարակից թվերի տարբերությունը 1-ից մեծ է, ապա երկրորդ համարի համար մենք ստիպված ենք նոր միջակայք կազմել: Հակառակ դեպքում, եթե տարբերությունը ճիշտ 1 է, ապա այդ թիվը կդնենք նույն տիրույթում:

Ալգորիթմ

  1. Ստեղծեք տողի ցուցակ ՝ արդյունքը պահելու համար:
  2. Սկսեք նետել զանգվածը i = 0 դեպի i<N, (N- ը զանգվածի չափն է) մի որոշ ժամանակաշրջանում:
    • Ընթացիկ ինդեքսում համարը նշեք որպես Սկիզբ միջակայքում:
    • Անցեք զանգվածը `սկսած ընթացիկ ինդեքսից և գտեք վերջին տարրը, որի տարբերությունը նախորդ տարրի հետ ճիշտ 1 է, այսինքն nums [i + 1] == nums [i] +1
    • Նշեք այս տարրը որպես վերջ միջակայքում:
    • Այժմ տեղադրեք այս ձևավորված շրջանակը մեջ արդյունք ցուցակ Եվ կրկնել մնացած տարրերի համար:
  3. Վերադարձեք արդյունք ցուցակը:

Իրականացման

C ++ ծրագիր ամփոփ միջակայքերի Leetcode լուծման համար

#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

Java ծրագիր ամփոփ միջակայքերի Leetcode լուծման համար

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

Բարդության վերլուծություն ամփոփ միջակայքերի համար Leetcode լուծման համար

Timeամանակի բարդություն

ՎՐԱ) : Որտեղ N- ը տրված զանգվածի չափն է: Չնայած մենք օգտագործում ենք երկու տեղադրված օղակ, բայց յուրաքանչյուր տարր այցելվում է միայն մեկ անգամ: Ուստի ժամանակի բարդությունը O է (N):

Տիեզերական բարդություն 

O (1): Մենք ոչ մի օժանդակ տարածք չենք օգտագործում, բացառությամբ լարերի ցուցակը վերադարձնելու: