Program JavaScript menyemak sama ada tatasusunan boleh ditambah atau dikurangkan dengan memutarkannya

Putaran tatasusunan merujuk kepada andaian bahawa tatasusunan ialah tatasusunan bulat Setiap putaran memusingkan elemen tatasusunan ke kiri atau kanan dengan indeks elemen pada satu hujung boleh Ambil nilai dari hujung yang lain. Menambah tatasusunan bermakna setiap elemen akan lebih besar daripada atau sama dengan elemen sebelumnya, tatasusunan menurun bermakna setiap elemen akan kurang daripada atau sama dengan elemen sebelumnya.

Dalam masalah ini kita diberikan tatasusunan dan kita boleh memutar tatasusunan ke kiri atau kanan dan kita perlu mengetahui sama ada kita boleh membuat tatasusunan bertambah atau berkurang selepas putaran tertentu (mungkin sifar). p>

kaedah tidak bersalah

Dalam kaedah ini kita akan memutar tatasusunan dan untuk setiap putaran kita akan menyemak sama ada tatasusunan semasa meningkat atau menurun.

Contoh

Dalam contoh di bawah, kami menyemak sama ada tatasusunan yang diberikan boleh ditambah atau dikurangkan dengan memutarkannya. Di bawah adalah input dan output yang dijangkakan.

Input: arr = [3, 4, 5, 6, 1, 2]

Keluaran yang dijangkakan: Ya

Input: arr = [5, 1, 6, 2, 5, 3]

Dijangka keluaran: Tidak

Contoh

// function to rotate the given array
function rotate(arr){
   var l = 0;
   var r = arr.length-1;
   while(l < r){
      arr[l] += arr[r];
      arr[r] = arr[l]-arr[r];
      arr[l] = arr[l]-arr[r];
      l++;
   }
   return arr;
}

// function to check if the given array is increasing or not
function increasing(arr){

   // getting the size of array
   var len = arr.length
   
   // traversing over the array
   for(var i = 1; i < len; i++){
      if(arr[i] < arr[i-1]){
         return false;
      }
   }
   return true;
}

// function to check if the given array is decreasing or not
function decreasing(arr){

   // getting the size of array
   var len = arr.length
   
   // traversing over the array
   for(var i = 1; i < len; i++){
      if(arr[i] > arr[i-1]){
         return false;
      }
   }
   return true;
}

// function to check whether the given array can become
// increasing or decreasing after certain rotations
function check(arr){
   var k = arr.length
   while(k--){
      if(increasing(arr) || decreasing(arr)){
         return true;
      }
      arr = rotate(arr);
   }
   return false;
}

// defining the arr's
var arr1 = [3, 4, 5, 6, 1, 2]
var arr2 = [5, 1, 6, 2, 5, 3]
console.log("The given array is: ");
console.log(arr1)
if(check(arr1) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}
console.log("The given array is: ");
console.log(arr2)
if(check(arr2) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}

Output

The given array is: 
[ 3, 4, 5, 6, 1, 2 ]
Yes, after some rotations given array can be transformed into an increasing or decreasing array
The given array is: 
[ 5, 1, 6, 2, 5, 3 ]
No, after some rotations given array cannot be transformed into an increasing or decreasing array

Kerumitan masa kod di atas ialah O(N*N) dan kerumitan ruang ialah O(1).

kaedah yang cekap

Dalam tatasusunan sebelumnya, kami menyemak sama ada tatasusunan meningkat atau menurun dengan setiap putaran, dalam kaedah ini kami akan menyemak sebahagian tatasusunan meningkat atau menurun.

Contoh

// function to check if the given array is increasing or not
function increasing(arr){

   // getting the size of array
   var len = arr.length
   
   // traversing over the array
   var i = 0;
   for(var i = 1; i < len; i++){
      if(arr[i] < arr[i-1]){
         break;
      }
   }
   if(i == len) return true;
   i++;
   for(; i< len; i++){
      if(arr[i] < arr[i-1]){
         return false;
      }
   }
   return arr[len-1] <= arr[0];
}

// function to check if the given array is decreasing or not
function decreasing(arr){

   // getting the size of array
   var len = arr.length
   
   // traversing over the array
   var i = 0;
   for(var i = 1; i < len; i++){
      if(arr[i] > arr[i-1]){
         break;
      }
   }
   if(i == len) return true;
   i++;
   for(; i< len; i++){
      if(arr[i] > arr[i-1]){
         return false;
      }
   }
   return arr[len-1] >= arr[0];
}

// function to check whether the given array can become increasing or decreasing after certain rotations
function check(arr){
   if(increasing(arr) || decreasing(arr)){
      return true;
   }
   else{
      return false;
   }
}

// defining the arr's
var arr1 = [3, 4, 7, 6, 1, 2]
var arr2 = [5, 1, 6, 2, 5, 3]
console.log("The given array is: ");
console.log(arr1)
if(check(arr1) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}
console.log("The given array is: ");
console.log(arr2)
if(check(arr2) == true){
   console.log("Yes, after some rotations given array can be transformed into an increasing or decreasing array");
}
else{
   console.log("No, after some rotations given array cannot be transformed into an increasing or decreasing array");
}

Output

The given array is: 
[ 3, 4, 7, 6, 1, 2 ]
No, after some rotations given array cannot be transformed into an increasing or decreasing array
The given array is: 
[ 5, 1, 6, 2, 5, 3 ]
No, after some rotations given array cannot be transformed into an increasing or decreasing array

Kerumitan masa kod di atas ialah O(N) dan kerumitan ruang ialah O(1).

KESIMPULAN

Dalam tutorial ini, kami melaksanakan program JavaScript yang menyemak sama ada tatasusunan yang diberikan boleh ditambah atau dikurangkan dengan memutarkannya. Kami melaksanakan dua kaedah dengan kerumitan masa O(N*N) dan O(N), dan kerumitan ruang kedua-duanya O(1).

Atas ialah kandungan terperinci Program JavaScript menyemak sama ada tatasusunan boleh ditambah atau dikurangkan dengan memutarkannya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!