Leetcode шийдлийн жагсаалтыг эргүүлэх  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe Амазоны Bloomberg Facebook-ийн LinkedIn Microsoft- Samsung
алгоритмууд кодлох ярилцлага ярилцлагын бэлтгэл LeetCode LeetCodeSolutions Холбогдсон жагсаалт Хоёр заагч

Leetcode Rotate List -ийн асуудал нь бидэнд холбосон жагсаалт болон бүхэл тоог өгдөг. Холбогдсон жагсаалтыг баруун тийш k газраар эргүүлэхийг бидэнд хэлэв. Тиймээс, хэрэв бид холбосон k жагсаалтыг баруун тийш эргүүлэх юм бол алхам тутамд жагсаалтаас хамгийн сүүлийн элементийг авч, дотроос нь байрлуулна. Бид давтан Бид эдгээр үйлдлүүдийн k тоог хийж дуустал. Хэд хэдэн жишээг авч үзье.

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

Тайлбар: Үйлдлийг 2 энгийн эргэлтийн үйлдэл болгон хуваацгаая. Тиймээс эхний алхам эсвэл шилжихдээ бид жагсаалтын төгсгөлөөс элементийг аваад урд нь байрлуулна. Тиймээс жагсаалт нь [5, 1, 2, 3, 4] болно. Одоо дахин жагсаалтыг гаргах ижил үйлдлийг давтан хийв [4, 5, 1, 2, 3]. Тиймээс хариулт.

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

Тайлбар: Процессыг 4 удаа давтан хийснээр хариултын жагсаалтыг гаргана. Доорх зургийг харвал илүү сайн ойлгогдож болно.

Leetcode шийдлийн жагсаалтыг эргүүлэхPin

Жагсаалтыг эргүүлэх Leetcode шийдлийн арга  

Асуудал Rotate List Leetcode Solution танд эргүүлэхийн тулд бүхэл тоотой холбосон жагсаалт өгсөн болно. Энэ нь бид k газруудын жагсаалтыг баруун тийш эргүүлэх хэрэгтэй гэсэн үг юм. Жагсаалтын төгсгөлд байгаа элементүүдийг аваад урд талд нь байрлуулах энгийн үйлдлээр асуудлыг ойлгож болно. Нэгэнт арга байхгүй үр ашигтай элементийг төгсгөлөөс нь аваад урд талд нь байрлуулна. Үйлдлийг гүйцэтгэх өөр арга замыг бодох хэрэгтэй. Хэрэв бид ажиглавал k үйлдлийг хийсний дараа төгсгөлөөс k элементүүдийг хасаад урд талд нь байрлуулсныг харж болно. Энд анхаарах нэг зүйл бол хэрэв k -ийн хэмжээ нь холбоотой жагсаалт. Бид k -ийн модулийг уртын дагуу авна холбоотой жагсаалт.

мөн үзнэ үү
Хоёртын хайлтын модноос хамгийн бага утга бүхий зангилааг олоорой

Үүнийг хийсний дараа бид хүрэх хүртэл явах болно kth зангилаа. Дараа нь бид зарим үйлдлүүдийг хийж, сүүлчийн зангилааны дараагийн хэсгийг толгой дээр нь өгдөг. Kth зангилааг төгсгөлөөс нь холбосон жагсаалтын толгой болгон томилно уу. Гэхдээ k-1-р зангилааны дараагийн зангилааг эцэсээс эхлэн хоосон болгохыг мартаж болохгүй. Одоо эдгээр 3 үйлдлийг хийсний дараа бид жагсаалтыг эргүүлэв.

Эргэх жагсаалтын Leetcode шийдлийн код  

C ++ код

#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 код

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

Нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (N), энд N нь холбосон жагсаалтын хэмжээг илэрхийлнэ. Бид холбогдсон жагсаалтыг тойрон гарах ёстой тул цаг хугацааны нарийн төвөгтэй байдал нь жагсаалтын хэмжээнээс хамаарна.

мөн үзнэ үү
Изоморфын мөрүүд Leetcode шийдэл

Сансрын нарийн төвөгтэй байдал

O (1), Учир нь зангилаа тус бүрт мэдээллийг хадгалах шаардлагагүй болно. Тиймээс сансрын нарийн төвөгтэй байдал нь тогтмол байдаг.

1