Bölmə Etiketləri LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Facebook google microsoft Nutanix Kahin Über VMware YandexBaxılıb 36

Problem bəyanat

Bölmə Etiketləri LeetCode Həlli – Sizə sətir verilir s. Biz sətri mümkün qədər çox hissəyə bölmək istəyirik ki, hər hərf ən çox bir hissədə görünsün.

Qeyd edək ki, bölmə elə aparılır ki, bütün hissələri ardıcıllıqla birləşdirdikdən sonra nəticə sətir olmalıdır s.

Qayıtmaq bu hissələrin ölçüsünü ifadə edən tam ədədlərin siyahısı.

Nümunələr və izahat

Misal 1:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.

Misal 2:
Input: s = "eccbbbbdec"
Output: [10]
Explanation: 
The given string can not partitioned further as the letters will be repeated if partitioned.

Alqoritm

Nümunə 1-ə baxaq, birinciyə 'a' daxil etsək, görə bilərik arakəsmə onda biz sətirdə görünən bütün 'a'ları daxil etməliyik. Beləliklə, biz alt sətri birinci indeksdən 'a' baş vermələrinin son indeksinə qədər daxil edəcəyik. İkinci bölmədə, "defegde" , o cümlədən qeyd edirik alt sətir ilk 'd' indeksindən 'd' son indeksinə qədər kifayət etməyəcək. Bu o deməkdir ki, biz "d" hərfinin ilk və son indeksləri arasında görünən bütün hərflərin bütün son indekslərini daxil etməliyik.

Bölmə Etiketləri LeetCode HəlliPin

Kodu

Bölmə Etiketləri üçün C++ proqramı

class Solution {
public:
    vector<int> partitionLabels(string s) {
        map<char,int> index;
        for(int i=0; i<s.size(); i++) {
            index[s[i]]=i;
        }
        vector<int>res;
        int pivot=0;
        int last_index=0;
        for(int curr=0; curr<s.size(); curr++) {
            last_index = max(last_index, index[s[curr]]);
            if(curr == last_index) {
                res.push_back(last_index-pivot+1);
                pivot=curr+1;
            }
        }
        return res;
    }
};

Bölmə etiketləri üçün Java proqramı

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] index = new int[26];
        for (int i = 0; i < s.length(); ++i)
            index[s.charAt(i) - 'a'] = i;
        
        List<Integer> res= new ArrayList();
        int pivot=0;
        int last_index=0;
        for(int curr=0; curr <s.length(); curr++) {
            last_index = Math.max(last_index, index[s.charAt(curr) - 'a']);
            if(curr == last_index) {
                res.add(last_index-pivot+1);
                pivot=curr+1;
            }
        }
        return res;
    }
}

Bölmə Etiketləri üçün Mürəkkəblik Təhlili LeetCode Həlli

Translate »
1