Jadual Kandungan
问题简介
说明
天真的方法
示例
时间和空间复杂度
前缀和法
结论
Rumah hujung hadapan web tutorial js Program JavaScript untuk pertanyaan jumlah julat yang memutar tatasusunan mengikut lawan jam oleh indeks K

Program JavaScript untuk pertanyaan jumlah julat yang memutar tatasusunan mengikut lawan jam oleh indeks K

Sep 01, 2023 pm 12:49 PM

用于按 K 索引逆时针旋转数组的范围求和查询的 JavaScript 程序

数组的逆时针旋转意味着将给定数组的所有元素向左侧旋转给定的索引数。在本文中,我们将实现一个 JavaScript 程序,用于按 k 个索引逆时针旋转数组的范围求和查询。

问题简介

在这个问题中,我们得到一个包含一些整数的数组和另一个包含成对形式的值的数组。每对将是当前查询所需的旋转次数,在给定的旋转次数之后,我们将得到一个范围,并且必须回答该给定范围中存在的元素的总和。例如,

示例1

Input
Given array: [1, 2, 3, 4, 5, 6] 
Query: [3, 1, 4]
Output 14
Salin selepas log masuk

说明

旋转次数为3,因此旋转3次后的数组为4 5 6 1 2 3。

1 到 4 范围内的元素为 5、6、1 和 2。因此,总和为 14。

示例2

Input
Given array: [1, 2, 3, 4, 5, 6] 
Query: [8, 0, 3]
Output 18
Salin selepas log masuk

说明

旋转次数为 8,因此 8 次旋转后的数组等于 8 %(数组长度)旋转,因为在数组旋转次数的长度之后,再次出现相同的数组意味着 8 次旋转是等效的至 2 次旋转。

因此,旋转 8 次后的数组为 3 4 5 6 1 2。

在该范围内,0 到 3 个元素分别为 3、4、5 和 6。因此,总和为 18。

天真的方法

在简单的方法中,我们将简单地执行查询数组中所述的所有步骤。就像,它被赋予旋转数组,然后我们将数组元素旋转给定的次数,然后检查范围内元素的总和。让我们看看它的代码 -

示例

// function to answer the queries 
function getSum(arr, rotations, L, R){
   var len = arr.length 
   var rot = rotations % len;
   var temp = new Array(len);
   
   // rotating the given array
   for(var i =0;  i< len - rot; i++ ){
      temp[i] = arr[i + rot];
   }
   
   // getting the last elements 
   for(var i = 0; i < rot; i++)    {
      temp[len-rot+i] = arr[i];
   }
   
   // getting the required sum
   var sum = 0;
   for(var i = L; i<=R; i++){
      sum += temp[i];
   }
   console.log("The sum of the elements in the range " + L + " to " + R + " after " + rotations + " number of rotations is " + sum);
}

// defining the array 
var arr = [ 1, 2, 3, 4, 5, 6]

// defining the queries array 
var queries = [ [ 3, 1, 4], [ 8, 0, 3]]
 
// traversing over the given array 
for(var i = 0; i<queries.length; i++){
   getSum(arr, queries[i][0], queries[i][1], queries[i][2]);
}
Salin selepas log masuk

时间和空间复杂度

上述代码的时间复杂度为 O(Q*N),其中 Q 是查询次数,N 是数组大小。

上述代码的时间复杂度为 O(N),因为我们正在创建一个大小为 N 的新数组。

前缀和法

在前缀和方法中,我们将创建一个前缀和数组,并且前缀和数组的每个索引包含截至当前索引的所有元素的总和。让我们看看它的代码 -

示例

// function to answer the queries 
function getSum(preSum, rotations, L, R){
   var len = preSum.length 
   var rot = rotations % len;
   
   // updating L and R 
   L = (L + rot) %len
   R = (R + rot) %len
   var sum = 0;
   if(L <= R) {
      if(L == 0) {
         sum = preSum[R];
      }
      else{
         sum = preSum[R]-preSum[L-1];
      }
   }
   else{
      sum += preSum[R];
      sum += preSum[len-1]-preSum[L-1];
   }
   console.log("The sum of the elements in the range " + L + " to " + R + " after " + rotations + " number of rotations is " + sum);
}

// defining the array 
var arr = [ 1, 2, 3, 4, 5, 6]
var preSum = new Array(arr.length)
preSum[0] = arr[0]
for(var i = 1; i<arr.length; i++){
   preSum[i] = preSum[i-1] + arr[i]
}

// defining the quries array 
var queries = [ [ 3, 1, 4], [ 8, 0, 3]] 

// traversing over the given array 
for(var i = 0; i<queries.length; i++){
   getSum(preSum, queries[i][0], queries[i][1], queries[i][2]);
}
Salin selepas log masuk

时间和空间复杂度

上述代码的时间复杂度为 O(Q),其中 Q 是查询数量。

上述代码的时间复杂度为 O(N),因为我们正在创建一个新数组来存储数组元素的前缀和。

结论

在本教程中,我们实现了一个 JavaScript 程序,用于按 k 索引逆时针旋转数组的范围求和查询。数组逆时针旋转意味着将给定数组的所有元素向左侧旋转给定数量的索引。我们首先实现了两种方法,一种是时间复杂度为 O(Q*N) 的朴素方法,另一种是时间复杂度为 O(Q) 的前缀和方法。

Atas ialah kandungan terperinci Program JavaScript untuk pertanyaan jumlah julat yang memutar tatasusunan mengikut lawan jam oleh indeks K. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
2 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Repo: Cara menghidupkan semula rakan sepasukan
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Cara mendapatkan biji gergasi
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Ganti aksara rentetan dalam javascript Ganti aksara rentetan dalam javascript Mar 11, 2025 am 12:07 AM

Penjelasan terperinci mengenai kaedah penggantian rentetan javascript dan Soalan Lazim Artikel ini akan meneroka dua cara untuk menggantikan watak rentetan dalam JavaScript: Kod JavaScript dalaman dan HTML dalaman untuk laman web. Ganti rentetan di dalam kod JavaScript Cara yang paling langsung ialah menggunakan kaedah pengganti (): str = str.replace ("cari", "ganti"); Kaedah ini hanya menggantikan perlawanan pertama. Untuk menggantikan semua perlawanan, gunakan ungkapan biasa dan tambahkan bendera global g: str = str.replace (/fi

Tutorial Persediaan API Carian Google Custom Tutorial Persediaan API Carian Google Custom Mar 04, 2025 am 01:06 AM

Tutorial ini menunjukkan kepada anda bagaimana untuk mengintegrasikan API carian Google tersuai ke dalam blog atau laman web anda, menawarkan pengalaman carian yang lebih halus daripada fungsi carian tema WordPress standard. Ia menghairankan mudah! Anda akan dapat menyekat carian ke y

10 JQuery Syntax Highlighters 10 JQuery Syntax Highlighters Mar 02, 2025 am 12:32 AM

Tingkatkan Penyampaian Kod Anda: 10 Penyeret Sintaks untuk Pemaju Coretan kod perkongsian di laman web atau blog anda adalah amalan biasa bagi pemaju. Memilih penyapu sintaks yang betul dapat meningkatkan daya tarikan dan daya tarikan visual dengan ketara. T

Bina Aplikasi Web Ajax anda sendiri Bina Aplikasi Web Ajax anda sendiri Mar 09, 2025 am 12:11 AM

Jadi di sini anda, bersedia untuk mempelajari semua perkara ini yang dipanggil Ajax. Tetapi, apa sebenarnya? Istilah Ajax merujuk kepada kumpulan teknologi longgar yang digunakan untuk membuat kandungan web yang dinamik dan interaktif. Istilah Ajax, yang asalnya dicipta oleh Jesse J

Contoh warna json fail Contoh warna json fail Mar 03, 2025 am 12:35 AM

Siri artikel ini ditulis semula pada pertengahan 2017 dengan maklumat terkini dan contoh segar. Dalam contoh JSON ini, kita akan melihat bagaimana kita dapat menyimpan nilai mudah dalam fail menggunakan format JSON. Menggunakan notasi pasangan nilai utama, kami boleh menyimpan apa-apa jenis

8 plugin susun atur halaman jquery yang menakjubkan 8 plugin susun atur halaman jquery yang menakjubkan Mar 06, 2025 am 12:48 AM

Leverage JQuery untuk Layouts Laman Web yang mudah: 8 Plugin Essential JQuery memudahkan susun atur laman web dengan ketara. Artikel ini menyoroti lapan plugin jQuery yang kuat yang menyelaraskan proses, terutamanya berguna untuk penciptaan laman web manual

10 JavaScript & JQuery MVC Tutorial 10 JavaScript & JQuery MVC Tutorial Mar 02, 2025 am 01:16 AM

Artikel ini membentangkan pemilihan lebih daripada 10 tutorial mengenai rangka kerja javascript dan jquery model-view-controller (MVC), sesuai untuk meningkatkan kemahiran pembangunan web anda pada tahun baru. Tutorial ini merangkumi pelbagai topik, dari Foundatio

Apa itu ' ini ' Dalam JavaScript? Apa itu ' ini ' Dalam JavaScript? Mar 04, 2025 am 01:15 AM

Mata teras Ini dalam JavaScript biasanya merujuk kepada objek yang "memiliki" kaedah, tetapi ia bergantung kepada bagaimana fungsi dipanggil. Apabila tidak ada objek semasa, ini merujuk kepada objek global. Dalam penyemak imbas web, ia diwakili oleh tetingkap. Apabila memanggil fungsi, ini mengekalkan objek global; tetapi apabila memanggil pembina objek atau mana -mana kaedahnya, ini merujuk kepada contoh objek. Anda boleh mengubah konteks ini menggunakan kaedah seperti panggilan (), memohon (), dan mengikat (). Kaedah ini memanggil fungsi menggunakan nilai dan parameter yang diberikan. JavaScript adalah bahasa pengaturcaraan yang sangat baik. Beberapa tahun yang lalu, ayat ini

See all articles