Siyahı Leetcode həllini döndərin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon Bloomberg Facebook LinkedIn microsoft Samsung
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions Bağlı siyahı İki işarəBaxılıb 89

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.

Leetcode Həll Siyahısını Döndürmə problemi bizə əlaqəli bir siyahı və tam ədəd təqdim edir. Bağlı siyahını k yerləri ilə sağa çevirməyimizi söyləyirlər. Beləliklə, k yerlərini sağa döndərsək, hər addımda siyahıdan sonuncu elementi götürürük. Biz təkrarlamaq bu əməliyyatların k sayını edənə qədər. Bir neçə nümunəyə nəzər salaq.

head = [1,2,3,4,5], k = 2
[4,5,1,2,3]

İzahat: Əməliyyatı 2 sadə fırlanma əməliyyatına ayıraq. Beləliklə, ilk addımda və ya hərəkətdə sadəcə elementi siyahının sonundan götürüb qabağa qoyuruq. Beləliklə, siyahı [5, 1, 2, 3, 4] olur. İndi yenə də siyahını düzəldən eyni əməliyyatı təkrarlayırıq [4, 5, 1, 2, 3]. Və buna görə cavab.

head = [0,1,2], k = 4
[2, 0, 1]

İzahat: Prosesi 4 dəfə təkrarlamaq cavab siyahısı ilə nəticələnir. Aşağıdakı şəkilə baxaraq daha yaxşı başa düşmək olar.

Siyahı Leetcode həllini döndərinPin

Siyahını Döndürmə Leetcode Həlli üçün yanaşma

Dönüştürmə siyahısı Leetcode Solution problemi, fırlanma üçün tam ədəd ilə əlaqəli bir siyahı verdiyinizi bildirir. Bu o deməkdir ki, k yerlərinin siyahısını sağa çevirməliyik. Problemi, siyahının sonundakı elementləri götürüb önə yerləşdirməklə sadə bir əməliyyatla başa düşmək olar. Çünki heç bir yolu yoxdur səmərəli bir elementi ucundan çıxarın və önünə qoyun. Əməliyyatı yerinə yetirmək üçün başqa bir yol düşünməliyik. Müşahidə etsək, görərik ki, k əməliyyatlarını yerinə yetirdikdən sonra ucdan k elementləri çıxarılır və önə qoyulur. Burada qeyd etmək lazım olan bir şey, əgər k -nin ölçüsü əlaqəli siyahı. K modulunu uzunluğundan götürəcəyik əlaqəli siyahı.

Bitirdikdən sonra, gedəcəyik kth node sondan. Sonra bəzi əməliyyatları yerinə yetiririk, sonuncu düyünün sonrakı hissəsini başa təyin edirik. Bağlı siyahının başı olaraq kth nodeunu sondan təyin edin. Ancaq k-1-ci düyünün sonrakı nodunu sondan sıfır olaraq təyin etməyi unutmamalıyıq. İndi bu 3 əməliyyatı etdikdən sonra siyahını döndərdik.

Siyahını Döndür Leetcode Həlli Kodu

C ++ kodu

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

struct ListNode{
    int data;
    ListNode* next;
};

ListNode* rotateRight(ListNode* head, int k) {
    if(head==NULL || head->next==NULL)return head;

    ListNode *tmp = head;
    int cnt = 0;
    while(tmp)tmp=tmp->next,cnt++;
    tmp=head;
    k%=cnt;
    if(k==0)return head;

    while(k--)tmp = tmp->next;
    ListNode *tmpHead = head;
    while(tmp->next!=NULL){
        tmp = tmp->next;
        head = head->next;
    }
    ListNode* newHead = head->next;
    tmp->next = tmpHead;
    head->next = NULL;
    return newHead;
}

int main(){
    ListNode *head = new ListNode();
    head->data = 0;
    head->next = new ListNode();
    head->next->data = 1;
    head->next->next = new ListNode();
    head->next->next->data = 2;

    head = rotateRight(head, 4);
    while(head != NULL){
        cout<<head->data<<" ";
        head = head->next;
    }
}
2 0 1

Java kodu

import java.util.*;
import java.lang.*;
import java.io.*;

class ListNode{
  int data;
  ListNode next;
}

class Solution {
    public static ListNode rotateRight(ListNode head, int k) {
        if(head==null || head.next==null)return head;
    
        ListNode tmp = head;
        int cnt = 0;
        while(tmp != null){
            tmp=tmp.next;
            cnt++;
        }
        tmp=head;
        k %= cnt;
        if(k==0)return head;

        while(k-- > 0)
            tmp = tmp.next;
        ListNode tmpHead = head;
        while(tmp.next != null){
            tmp = tmp.next;
            head = head.next;
        }
        ListNode newHead = head.next;
        tmp.next = tmpHead;
        head.next = null;
        return newHead;
    }
    
    public static void main(String[] args){
    	ListNode head = new ListNode();
      head.data = 0;
      head.next = new ListNode();
      head.next.data = 1;
      head.next.next = new ListNode();
      head.next.next.data = 2;
  
      head = rotateRight(head, 4);
      while(head != null){
          System.out.print(head.data + " ");
          head = head.next;
      }
    }
}
2 0 1

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), burada N əlaqəli siyahının ölçüsünü təmsil edir. Bağlı siyahıdan keçməli olduğumuz üçün zamanın mürəkkəbliyi xətti və siyahının ölçüsündən asılıdır.

Kosmik Mürəkkəblik

O (1), çünki qovşaqların hər biri üçün məlumat saxlamağımız lazım deyil. Beləliklə, kosmik Mürəkkəblik sabitdir.

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