Rəqəmlər üzrə ən çox K bitişik Swapdan sonra minimum mümkün tam ədəd LeetCode Həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon FlipkartBaxılıb 50

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Rəqəmlər üzrə ən çox K bitişik Swapdan sonra minimum mümkün tam ədəd LeetCode Həlli – Sizə sətir verilir num təmsil rəqəmlər çox böyük tam və tam ədəddən ibarətdir k. Tam ədədin hər hansı iki bitişik rəqəmini dəyişdirməyə icazə verilir ən çox k dəfə.

Qayıtmaq bu minimum tam ədədi sətir kimi də əldə edə bilərsiniz.

Rəqəmlər üzrə ən çox K bitişik Swapdan sonra minimum mümkün tam ədəd LeetCode Həlli

Input: num = "4321", k = 4
Output: "1342"
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.

Izahat

Gəlin müşahidələri anlayaq və sonra onları həyata keçirmək üçün məlumat strukturunu öyrənək.

Müşahidə 0: Yaxşı, biz bilirik ki, əgər ən kiçik rəqəmi sola ala bilsək, onda indiki rəqəmdən daha kiçik ədəd yarada biləcəyik. Bu mənada sıralanmış ədəd (Artan) artıq ən kiçik olacaqdır.

Beləliklə, qələm və kağız götürək və bunun üçün yarada biləcəyimiz ən kiçik ədədi tapmağa çalışaq:

"4321", k = 4

Beləliklə, 1-dən ən sol mövqeyə keçməyə çalışaq. Bundan sonra sola hərəkət etdiyimiz cari rəqəmi mən adlandıracağam d:
"4321", k = 4
"4312", k = 3
"4132", k = 2
"1432", k = 1
Hmm, aydın şəkildə müşahidə edə bilərik:

Müşahidə 1: rəqəmi sola köçürdükdə digər rəqəmlər sağa sürüşür. yəni 432 1 sağa sürüşdü.

Amma, gözləyin. Sağ tərəfdə başqa bir rəqəm olsaydı nə olardı d?

"43219", k = 4
"43129", k = 3
"41329", k = 2
"14329", k = 1

Yaxşı, 9-un yeri dəyişmədi. Buna görə də yuxarıdakı müşahidəmizə bəzi düzəlişlər edə bilərik.

Düzəliş edilmiş müşahidə 1: Yalnız solundakı rəqəmlər d mövqelərini dəyişdilər.

Yaxşı, sonra nə olacaq?

Amma nə olarsa k həqiqətən kiçik idi və biz 1-dən ən sola keçə bilmədik?
"43219", k = 2
"43129", k = 1
"41329", k = 0

Burada açıq şəkildə ən kiçik rəqəmə çatmadıq. üçün ən kiçik k=2 olacaq 24319.

Burada müşahidə edə bilərik ki, ən kiçiyini seçməliyik d ki, əlçatandır k.

Müşahidə 2: İlk ən kiçiyi seçin d ki, çatır k.

Bütün müşahidələri birləşdirsək, soldan sağa təkrarlayacağımızı və 0-dan 9-a kimi rəqəmləri yerləşdirməyə çalışacağımızı görə bilərik.

Gəlin daha böyük bir nümunə üzərində işləyək:

"9438957234785635408", k = 23

Soldan başlayacağıq. Gəlin burada 0 yerləşdirməyə çalışaq. 0 əlçatandır k0 sağa 17 sürüşmə uzaqdır. Beləliklə, əldə edəcəyik:
"0943895723478563548", k = 6

Sağdakıdan başqa bütün nömrələrin sağa sürüşdüyünə diqqət yetirin d (8, burada).

İndi isə növbəti mövqeyə keçək:
Gəlin burada yenidən 0-ı yerləşdirməyə çalışaq. Amma gözləyin, bizdə 0 qalmayıb, ona görə də 1-i sınayın, o da yoxdur. Beləliklə, cəhd edək 2, 2 bu mövqedən 8 məsafədədir. 8 > k, ona görə də biz 2-ni seçə bilmərik. Gəlin 3-ü sınayaq, 3-ü 2 məsafədədir. 2 < k, ona görə də 3-ü seçək.

"0394895723478563548", k = 4

və biz belə davam edə bilərik.

1-ci müşahidə üçün növbələrin düzgün sayını hesablamaq üçün biz də əvvəl neçə elementi saxlamalıyıq d artıq dəyişib. Bunun üçün bir seqment ağacından istifadə edəcəyik.

Müşahidə 2 üçün, hər rəqəmin ən son baş verməsini seçmək üçün növbədən istifadə edəcəyik.

Kodu

Rəqəmlər üzrə ən çox K bitişik Swapdan sonra Minimum Mümkün Tam Ədər üçün Java Kodu

class Solution {
    public String minInteger(String num, int k) {
        //pqs stores the location of each digit.
        List<Queue<Integer>> pqs = new ArrayList<>();
        for (int i = 0; i <= 9; ++i) {
            pqs.add(new LinkedList<>());
        }

        for (int i = 0; i < num.length(); ++i) {
            pqs.get(num.charAt(i) - '0').add(i);
        }
        String ans = "";
        SegmentTree seg = new SegmentTree(num.length());

        for (int i = 0; i < num.length(); ++i) {
            // At each location, try to place 0....9
            for (int digit = 0; digit <= 9; ++digit) {
                // is there any occurrence of digit left?
                if (pqs.get(digit).size() != 0) {
                    // yes, there is a occurrence of digit at pos
                    Integer pos = pqs.get(digit).peek();
          // Since few numbers already shifted to left, this `pos` might be outdated.
                    // we try to find how many number already got shifted that were to the left of pos.
                    int shift = seg.getCountLessThan(pos);
                    // (pos - shift) is number of steps to make digit move from pos to i.
                    if (pos - shift <= k) {
                        k -= pos - shift;
                        seg.add(pos); // Add pos to our segment tree.
                        pqs.get(digit).remove();
                        ans += digit;
                        break;
                    }
                }
            }
        }
        return ans;
    }

    class SegmentTree {
        int[] nodes;
        int n;

        public SegmentTree(int max) {
            nodes = new int[4 * (max)];
            n = max;
        }

        public void add(int num) {
            addUtil(num, 0, n, 0);
        }

        private void addUtil(int num, int l, int r, int node) {
            if (num < l || num > r) {
                return;
            }
            if (l == r) {
                nodes[node]++;
                return;
            }
            int mid = (l + r) / 2;
            addUtil(num, l, mid, 2 * node + 1);
            addUtil(num, mid + 1, r, 2 * node + 2);
            nodes[node] = nodes[2 * node + 1] + nodes[2 * node + 2];
        }

        // Essentialy it tells count of numbers < num.
        public int getCountLessThan(int num) {
            return getUtil(0, num, 0, n, 0);
        }

        private int getUtil(int ql, int qr, int l, int r, int node) {
            if (qr < l || ql > r) return 0;
            if (ql <= l && qr >= r) {
                return nodes[node];
            }

            int mid = (l + r) / 2;
            return getUtil(ql, qr, l, mid, 2 * node + 1) + getUtil(ql, qr, mid + 1, r, 2 * node + 2);
        }
    }

}

Rəqəmlər üzrə ən çox K bitişik Swapdan sonra minimum mümkün tam ədəd üçün Python kodu

class Solution:
  def minInteger(self, num: str, k: int) -> str:
    if k <= 0: return num
    n = len(num)
    if k >= n*(n-1)//2: 
      return "".join(sorted(list(num)))

    # for each number, find the first index
    for i in range(10):
      ind = num.find(str(i))
      if 0 <= ind <= k:
        return str(num[ind]) + self.minInteger(num[0:ind] + num[ind+1:], k-ind)

Rəqəmlər üzrə ən çox K bitişik Swapdan sonra Minimum Mümkün Tam Ədər üçün Mürəkkəblik Təhlili LeetCode Həlli

Zamanın mürəkkəbliyi

O(nLogn)

Kosmik Mürəkkəblik

O (N)

Referans: https://en.wikipedia.org/wiki/Fenwick_tree

Crack Sistemi Dizayn Müsahibələri
Translate »