ລາຍການແກ້ໄຂບັນຫາ Leetcode  


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe Amazon Bloomberg ເຟສບຸກ LinkedIn Microsoft Samsung
ຂັ້ນຕອນວິທີ ລະຫັດ ການສໍາພາດ ການສໍາພາດກ່ອນ LeetCode LeetCodeSolutions ບັນຊີທີ່ເຊື່ອມໂຍງ ສອງຈຸດ

ບັນຫາ Rotate List Leetcode Solution ໃຫ້ພວກເຮົາມີລາຍຊື່ທີ່ເຊື່ອມໂຍງແລະ ຈຳ ນວນເຕັມ. ພວກເຮົາຖືກບອກໃຫ້rotateຸນລາຍຊື່ທີ່ເຊື່ອມໂຍງໄປທາງຂວາໂດຍ k ສະຖານທີ່. ສະນັ້ນຖ້າພວກເຮົາrotateຸນບັນຊີລາຍຊື່ 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  

ບັນຫາ Rotate List Leetcode Solution ລະບຸວ່າເຈົ້າໄດ້ຮັບບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງກັບເລກເຕັມ ສຳ ລັບການ.ູນວຽນ. ນີ້meansາຍຄວາມວ່າພວກເຮົາຕ້ອງການtheຸນລາຍຊື່ສະຖານທີ່ k ໄປທາງຂວາ. ບັນຫາສາມາດເຂົ້າໃຈໄດ້ໂດຍການ ດຳ ເນີນການງ່າຍ simple ຂອງການເອົາອົງປະກອບອອກມາຈາກທ້າຍລາຍການແລະວາງພວກມັນໄວ້ທາງ ໜ້າ. ເນື່ອງຈາກວ່າບໍ່ມີທາງທີ່ຈະໄປ ປະສິດທິຜົນ ເອົາອົງປະກອບອອກຈາກປາຍແລະວາງມັນໄວ້ທາງ ໜ້າ. ພວກເຮົາຈໍາເປັນຕ້ອງຄິດຫາວິທີອື່ນເພື່ອປະຕິບັດການດໍາເນີນງານ. ຖ້າພວກເຮົາສັງເກດ, ພວກເຮົາສາມາດເຫັນໄດ້ວ່າຫຼັງຈາກປະຕິບັດການປະຕິບັດງານ k, ອົງປະກອບ k ຈາກຈຸດສິ້ນສຸດຈະຖືກເອົາອອກແລະວາງຢູ່ທາງ ໜ້າ. ສິ່ງ ໜຶ່ງ ທີ່ຄວນສັງເກດຢູ່ທີ່ນີ້ແມ່ນ, ຖ້າຂະ ໜາດ ຂອງ k ໃຫຍ່ກວ່າຂະ ໜາດ ຂອງ ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ. ພວກເຮົາຈະເອົາ modulo ຂອງ k ຕໍ່ກັບຄວາມຍາວຂອງ ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ.

ເບິ່ງ
ຊອກຫາຂໍ້ທີ່ມີຄ່າ ຕຳ ່ສຸດໃນ Binary Search Tree

ເມື່ອ ສຳ ເລັດແລ້ວ, ພວກເຮົາຈະຂ້າມຜ່ານໄປຈົນຮອດ ໂຫນດ kth ຈາກປາຍສຸດ. ຫຼັງຈາກນັ້ນ, ພວກເຮົາປະຕິບັດບາງສ່ວນຂອງການດໍາເນີນງານ, ພວກເຮົາກໍາຫນົດຕໍ່ໄປຂອງ node ສຸດທ້າຍກັບຫົວ. ມອບodeາຍຂໍ້ kth ຈາກຈຸດສຸດທ້າຍເປັນຫົວ ໜ້າ ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ. ແຕ່ພວກເຮົາບໍ່ຄວນລືມມອບtheາຍຂໍ້ຕໍ່ໄປຂອງ k-1 node ຈາກຈຸດສຸດທ້າຍເປັນ null. ດຽວນີ້, ຫຼັງຈາກປະຕິບັດການປະຕິບັດ 3 ຢ່າງນີ້, ພວກເຮົາໄດ້atedູນວຽນລາຍການ.

ລະຫັດ ສຳ ລັບການ ໝູນ ບັນຊີ Leetcode Solution  

ລະຫັດ 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

ການວິເຄາະຄວາມສັບສົນ  

ຄວາມສັບສົນເວລາ

ໂອ (N), ບ່ອນທີ່ N ສະແດງຂະ ໜາດ ຂອງລາຍຊື່ທີ່ເຊື່ອມໂຍງ. ເນື່ອງຈາກວ່າພວກເຮົາຕ້ອງໄດ້ຜ່ານບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ, ຄວາມສັບສົນຂອງເວລາແມ່ນເປັນເສັ້ນແລະຂື້ນກັບຂະ ໜາດ ຂອງບັນຊີ.

ເບິ່ງ
ໂຊລູຊັ່ນແກ້ໄຂບັນຫາ Leetcode

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (1), ເນື່ອງຈາກວ່າພວກເຮົາບໍ່ ຈຳ ເປັນຕ້ອງເກັບຂໍ້ມູນ ສຳ ລັບແຕ່ລະຂໍ້. ດັ່ງນັ້ນ, ຄວາມສັບສົນຂອງພື້ນທີ່ແມ່ນຄົງທີ່.