ዝርዝር አዙር የሌትኮድ መፍትሔ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን ብሉምበርግ ፌስቡክ LinkedIn የ Microsoft ሳምሰንግ
የተገናኘ-ዝርዝር ሁለት ጠቋሚዎች

ችግሩ አሽከርክር ዝርዝር Leetcode Solution የተገናኘ ዝርዝር እና ኢንቲጀር ይሰጠናል ፡፡ የተገናኘውን ዝርዝር በ 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 መፍትሄ አቀራረብ

ችግሩ አሽከርክር ዝርዝር Leetcode መፍትሔ ለማሽከርከር ከ ‹ኢንቲጀር› ጋር የተገናኘ ዝርዝር ይሰጥዎታል ፡፡ ይህ ማለት የዝርዝሩን k ቦታዎችን ወደ ቀኝ ማዞር ያስፈልገናል ማለት ነው ፡፡ ከዝርዝሩ መጨረሻ ላይ ያሉትን ንጥረ ነገሮች በመውሰድ ከፊት ለፊታቸው በማስቀመጥ በቀላል ክዋኔ ችግሩን መረዳት ይቻላል ፡፡ አንድን ንጥረ ነገር ከጫፉ ላይ በብቃት ለማስወገድ እና ከፊት ለፊቱ ለማስቀመጥ ምንም መንገድ ስለሌለ። ክዋኔውን ለማከናወን ሌላ ማንኛውንም መንገድ ማሰብ አለብን ፡፡ ካስተዋልን የ k ክዋኔዎችን ከፈፀምን በኋላ ከጫፉ ላይ ያሉት k አካላት ይወገዳሉ እና ከፊት ለፊት ይቀመጣሉ ፡፡ እዚህ ላይ ልብ ሊባል የሚገባው ነገር ቢኖር ፣ የ k መጠን ከተያያዘው ዝርዝር መጠን የበለጠ ከሆነ ነው ፡፡ ከተያያዘው ዝርዝር ርዝመት በላይ የ k ሞዱሉን እንወስዳለን ፡፡

አንዴ እንደጨረስን ፣ እስከ መጨረሻው እስከ kth መስቀለኛ ክፍል ድረስ እናልፋለን ፡፡ ከዚያ የተወሰኑትን ክዋኔዎች እናከናውናለን ፣ ቀጣዩን የመጨረሻ መስቀለኛ ክፍል ለጭንቅላቱ እንመድባለን ፡፡ የተገናኘውን ዝርዝር ራስ እንደ መጨረሻው kth node ይመድቡ። ግን የመጨረሻውን የ k-1 ኛ መስቀለኛ መስቀለኛ መንገድን ከመጨረሻው እንደ ባዶ ማድረጉን መርሳት የለብንም ፡፡ አሁን እነዚህን 3 ክዋኔዎች ከፈፀምን በኋላ ዝርዝሩን አዙረናል ፡፡

ለማሽከርከር ዝርዝር Leetcode መፍትሔ ኮድ

ሲ ++ ኮድ

#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

የጃቫ ኮድ

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ N የተገናኘውን ዝርዝር መጠን የሚወክልበት። የተገናኘውን ዝርዝር መሻገር ስላለብን ፣ የጊዜ ውስብስብነቱ ቀጥተኛ እና በዝርዝሩ መጠን ላይ የተመሠረተ ነው።

የቦታ ውስብስብነት

ኦ (1) ፣ ለእያንዳንዱ የአንጓዎች መረጃ ማከማቸት ስለማንፈልግ ፡፡ ስለሆነም የቦታ ውስብስብነት ቋሚ ነው።