បង្វិលបញ្ជី Leetcode ដំណោះស្រាយ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ទីភ្នាក់ងារ Bloomberg Facebook LinkedIn ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Samsung
បញ្ជីភ្ជាប់ ចំណុចពីរ

បញ្ហាបង្វិលបញ្ជីឡេឡេលេខកូដដំណោះស្រាយផ្តល់ឱ្យយើងនូវបញ្ជីភ្ជាប់និងលេខគត់។ យើងត្រូវបានគេប្រាប់ឱ្យបង្វិលបញ្ជីដែលបានភ្ជាប់ទៅខាងស្តាំដោយកន្លែង k ។ ដូច្នេះប្រសិនបើយើងបង្វិលបញ្ជីដែលភ្ជាប់ k ទៅខាងស្តាំក្នុងជំហាននីមួយៗយើងយកធាតុចុងក្រោយចេញពីបញ្ជីហើយដាក់វាពី។ យើងធ្វើម្តងទៀតរហូតដល់យើងបានធ្វើចំនួន k នៃប្រតិបត្តិការទាំងនេះ។ តោះមើលឧទាហរណ៍ខ្លះ។

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

ការពន្យល់ៈសូមបំបែកប្រតិបត្តិការទៅជាប្រតិបត្ដិការបង្វិលសាមញ្ញចំនួន ២ ។ ដូច្នេះនៅជំហានដំបូងឬផ្លាស់ទីយើងគ្រាន់តែយកធាតុពីចុងបញ្ជីហើយដាក់វានៅពីមុខ។ ដូច្នេះ, បញ្ជីក្លាយជា [2, 5, 1, 2, 3] ។ ឥឡូវម្តងទៀតយើងធ្វើប្រតិបត្តិការដដែលធ្វើបញ្ជីឈ្មោះ [៤, ៥, ១, ២, ៣] ។ ហេតុដូចនេះហើយចម្លើយ។

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

ការពន្យល់ៈការធ្វើម្តងទៀតនូវដំណើរការនេះចំនួន ៤ ដងនឹងមាននៅក្នុងបញ្ជីភ្ជាប់ចម្លើយ។ វាអាចត្រូវបានយល់កាន់តែច្បាស់ដោយមើលរូបភាពខាងក្រោម។

បង្វិលបញ្ជី Leetcode ដំណោះស្រាយ

វិធីសាស្រ្តសម្រាប់ដំណោះស្រាយវិលបញ្ជី Leetcode

បញ្ហាបង្វិលបញ្ជី Leetcode ដំណោះស្រាយបញ្ជាក់ថាអ្នកត្រូវបានផ្តល់ឱ្យនូវបញ្ជីភ្ជាប់ជាមួយលេខគត់សម្រាប់ការបង្វិល។ នេះមានន័យថាយើងត្រូវបង្វិលបញ្ជី k ទៅខាងស្តាំ។ បញ្ហាអាចត្រូវបានយល់ដោយប្រតិបត្តិការសាមញ្ញនៃការយកធាតុពីចុងបញ្ជីហើយដាក់វានៅខាងមុខ។ ដោយសារមិនមានវិធីដើម្បីយកធាតុចេញពីចុងហើយដាក់វានៅខាងមុខ។ យើងត្រូវគិតពីវិធីផ្សេងទៀតដើម្បីអនុវត្តប្រតិបត្តិការនេះ។ ប្រសិនបើយើងសង្កេតយើងអាចឃើញថាបន្ទាប់ពីអនុវត្តប្រតិបត្តិការ k ធាតុ k ពីចុងត្រូវបានដកចេញហើយដាក់នៅខាងមុខ។ រឿងមួយដែលត្រូវកត់សម្គាល់នៅទីនេះគឺប្រសិនបើទំហំរបស់ k ធំជាងទំហំនៃបញ្ជីភ្ជាប់។ យើងនឹងយកម៉ូឌុលនៃ k លើប្រវែងនៃបញ្ជីភ្ជាប់។

នៅពេលរួចរាល់យើងនឹងឆ្លងកាត់រហូតដល់ថ្នាំង kth ពីចុងបញ្ចប់។ បន្ទាប់មកយើងធ្វើប្រតិបត្តិការខ្លះយើងចាត់ចែងថ្នាំងចុងក្រោយទៅក្បាល។ ចាត់តាំងថ្នាំង kth ពីចុងបញ្ចប់ជាប្រធាននៃបញ្ជីដែលបានភ្ជាប់។ ប៉ុន្តែយើងមិនគួរភ្លេចដាក់ថ្នាំងបន្ទាប់នៃថ្នាំងទី ១ ពីទីបញ្ចប់ថាជាមោឃៈទេ។ ឥឡូវនេះបន្ទាប់ពីអនុវត្តប្រតិបត្តិការទាំងបីនេះយើងបានប្តូរបញ្ជីហើយ។

លេខកូដសំរាប់បង្វិលបញ្ជីឡេឡេលេខកូដ

លេខកូដ 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

ចាវ៉ាកូដ

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 តំណាងឱ្យទំហំនៃបញ្ជីភ្ជាប់។ ដោយសារយើងត្រូវឆ្លងកាត់បញ្ជីដែលបានតភ្ជាប់ភាពស្មុគស្មាញពេលវេលាគឺលីនេអ៊ែរហើយពឹងផ្អែកលើទំហំនៃបញ្ជី។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), ដោយសារយើងមិនចាំបាច់រក្សាទុកព័ត៌មានសម្រាប់ថ្នាំងនីមួយៗ។ ដូច្នេះចន្លោះស្មុគស្មាញគឺថេរ។