資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學旋轉陣列中給定長度的連續子陣列最大和查詢的JavaScript程式
旋轉陣列意味著我們會得到一個數字，我們必須按照迴圈順序向右或向左移動陣列的元素。這裡沒有具體說明，因此我們將使用右旋轉作為標準，在給定次數的旋轉後，我們將返回具有最大和的子陣列。我們將在文章中看到帶有適當解釋的程式碼。
問題介紹
在這個問題中，我們得到一個包含整數的陣列和另一個包含查詢對的陣列。查詢陣列的每個索引包含兩個整數，第一個表示當前陣列旋轉的次數，第二個整數表示所需子陣列的長度。例如：
如果給定陣列為 [5, 7, 1, 4, 3, 8, 2]，查詢如下：
Queries: 3 rotations and size 3 After the three rotations, the array looks like: 3, 8, 2, 5, 7, 1, 4 From the above array, the result is 15 by subarray: 8, 2, and 5. Queries: 2 rotations and size 4 After the two rotations, the array looks like: 8, 2, 5, 7, 1, 4, 3 From the above array, the result is 22 by subarrays 8, 2, 5, and 7
讓我們轉向解決這個問題的方法。
樸素方法
樸素方法很簡單，我們將使用兩個for迴圈來實現給定的問題。首先，我們將遍歷陣列並將其順時針旋轉給定次數。然後，我們找到給定大小的子陣列以及具有最大和的子陣列。讓我們看看它的程式碼：
示例
// function to rotate the array and find the subarray sum
function subSum(arr, rotations, size){
var n = arr.length
var temp = new Array(n)
var j = 0;
for(var i = n-rotations; i<n;i++){
temp[j] = arr[i];
j++;
}
for(var i = 0; i < n-rotations; i++){
temp[j] = arr[i];
j++;
}
// getting the size of the first window of the given size
var ans = -1000000000;
for(var i = 0; i<=n-size; i++) {
var cur = 0;
for(var j = i; j < i+size; j++) {
cur += temp[j];
}
if(ans < cur) {
ans = cur;
}
}
console.log("The maximum sum or given subarray with size " + size + " after " + rotations + " number of rotations is " + ans);
}
// defining array
var arr= [5, 7, 1, 4, 3, 8, 2]
// defining quries
var queries = [[3,3], [2,4]]
// traversing over the array
for(var i =0; i<queries.length; i++){
subSum(arr, queries[i][0], queries[i][1]);
}
時間和空間複雜度
上述程式碼的時間複雜度為 O(Q*D*N)，其中 Q 是查詢數，D 是每個所需子陣列的大小，N 是陣列的長度。
上述程式碼的空間複雜度為 O(N)，因為我們使用額外的陣列來儲存旋轉後的陣列。
高效方法
這個問題可以使用滑動視窗方法以高效的方式解決。讓我們直接進入這個問題的程式碼，並透過它進行概述：
示例
// function to rotate the array and find the subarray sum
function subSum(arr, rotations, size){
var n = arr.length
var temp = new Array(n)
var j = 0;
for(var i = n-rotations; i<n;i++){
temp[j] = arr[i];
j++;
}
for(var i = 0; i < n-rotations; i++){
temp[j] = arr[i];
j++;
}
// getting the size of the first window of the given size
var ans = -1000000000
var cur = 0;
for(var i = 0;i<size;i++){
cur += temp[i];
}
ans = cur;
for(var i = size; i<n;i++){
cur -= temp[i-size];
cur += temp[i];
if(ans < cur) {
ans = cur;
}
}
console.log("The maximum sum of given subarray with size " + size + " after " + rotations + " number of rotations is " + ans);
}
// defining array
var arr= [5, 7, 1, 4, 3, 8, 2]
// defining quries
var queries = [[3,3], [2,4]]
// traversing over the array
for(var i =0; i<queries.length; i++){
subSum(arr, queries[i][0], queries[i][1]);
}
時間和空間複雜度
上述程式碼的時間複雜度為 O(Q*N)，其中 Q 是查詢數，N 是陣列的長度。
上述程式碼的空間複雜度為 O(N)，因為我們使用額外的陣列來儲存旋轉後的陣列。
結論
在本教程中，我們實現了一個 JavaScript 程式，用於查詢旋轉陣列中給定長度的連續子陣列的最大和。我們實現了一個時間複雜度為 O(N*Q*D) 的樸素方法，然後使用滑動視窗的概念將其改進為 O(N*Q) 的時間複雜度，但兩個程式碼的空間複雜度相同，均為 O(N)。
更新於：2023年4月14日
瀏覽量：124
廣告