# 算法题：对数组进行左、右循环移位查询

2021年3月23日14:23:32 发表评论 441 次浏览

• 1 x：向右循环将数组移动x次。如果数组为a [0], a [1], ...., a [n – 1], 则在右移一圈后, 该数组将变为a [n – 1], a [0], a [1] , …。, a [n – 2]。
• 2年：向左循环将数组y次。如果数组是a [0], a [1], ...., a [n – 1], 则在右移一圈后, 该数组将变为a [1], ...., a [n – 2], a [n – 1], a [0]。
• 3升打印子数组a [l…r](包括l和r)中的所有整数之和。

``````Input : n = 5, arr[] = { 1, 2, 3, 4, 5 }
query 1 = { 1, 3 }
query 2 = { 3, 0, 2 }
query 3 = { 2, 1 }
query 4 = { 3, 1, 4 }
Output : 12
11
Initial array arr[] = { 1, 2, 3, 4, 5 }
After query 1, arr[] = { 3, 4, 5, 1, 2 }.
After query 2, sum from index 0 to index
2 is 12, so output 12.
After query 3, arr[] = { 4, 5, 1, 2, 3 }.
After query 4, sum from index 1 to index
4 is 11, so output 11.``````

## 推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

。每旋转n次, 数组将返回其原始状态。

``````// CPP Program to solve queries on Left and Right
// Circular shift on array
#include <bits/stdc++.h>
using namespace std;

// Function to solve query of type 1 x.
void querytype1( int * toRotate, int times, int n)
{
// Decreasing the absolute rotation
(*toRotate) = ((*toRotate) - times) % n;
}

// Function to solve query of type 2 y.
void querytype2( int * toRotate, int times, int n)
{
// Increasing the absolute rotation.
(*toRotate) = ((*toRotate) + times) % n;
}

// Function to solve queries of type 3 l r.
void querytype3( int toRotate, int l, int r, int preSum[], int n)
{
// Finding absolute l and r.
l = (l + toRotate + n) % n;
r = (r + toRotate + n) % n;

// if l is before r.
if (l <= r)
cout << (preSum[r + 1] - preSum[l]) << endl;

// If r is before l.
else
cout << (preSum[n] + preSum[r + 1] - preSum[l])
<< endl;
}

// Wrapper Function solve all queries.
void wrapper( int a[], int n)
{
int preSum[n + 1];
preSum[0] = 0;

// Finding Prefix sum
for ( int i = 1; i <= n; i++)
preSum[i] = preSum[i - 1] + a[i - 1];

int toRotate = 0;

// Solving each query
querytype1(&toRotate, 3, n);
querytype3(toRotate, 0, 2, preSum, n);
querytype2(&toRotate, 1, n);
querytype3(toRotate, 1, 4, preSum, n);
}

// Driver Program
int main()
{
int a[] = { 1, 2, 3, 4, 5 };
int n = sizeof (a) / sizeof (a[0]);
wrapper(a, n);
return 0;
}``````

``````12
11``````