小黄的刷题之路(十七)——码题集OJ赛-循环移位

一、题目

二、分析思路

2.1 审题理解

• 给我们一个正整数序列，如果能够通过若干次循环左移调整成一个升序序列，那就输出‘YES’，否则输出‘NO’
• 所谓循环左移就是把一个数组序列的第一个元素挪到最后面，其他往前挤。所谓升序序列就是序列按照从小到大的顺序，允许一样大

2.2 思路

思路很简单，那就挪挪看呗，总不能光靠眼睛观察吧，一旦序列很长，除非你有写轮眼不然你是很难断定的。

方法：对于一个给定的序列，循环左移若干次，直到把序列中最小的元素挪到了最前面，观察此时的序列，如果此时的序列非降，那就说明能够通过若干次循环左移调整成非降序列，输出YES，否则输出NO

但是我们可不是老实人，老实人才会老老实实把序列真的去循环左移好几次，但是你仔细想一想有必要吗，循环左移一次整个数组的元素都要移动，那不老费劲了，有没有办法不挪这个序列就实现循环左移呢，答案是肯定的。

我直接设置两个指针：一个头指针和一个尾指针，头指针指向序列的第一个元素，尾指针指向最后一个元素，一开始当然是两个指针指向数组的首尾，循环左移一次就修改一下这两个指针，指向新的头和尾，这样不用真的去移动数组，只是修改两个变量就好了，多方便。

int head=0,tail=n-1;//序列的头尾指针
while(a[head]!=min)//把最小的挪到最前面
{
    tail = head;
    head += 1;
}

三、代码实现

3.1. C++实现

#include<bits/stdc++.h> 
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    int min=10000;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]<min)min=a[i];//找出序列中最小的
    }
    bool flag=true;//默认可以调成非降序列
    int head=0,tail=n-1;//序列的头尾指针
    while(a[head]!=min)//把最小的挪到最前面
    {
        tail = head;
        head += 1;
    }
    //看看是否非降
    for(int i=head;i!=tail;i=(i+1)%n)if(a[i]>a[(i+1)%n]){flag=false;break;}
    if(flag)cout<<"YES";
    else cout<<"NO";
    return 0;
}

四、总结

• 这道题本身不难，但是有一个技巧却值得我们注意，那就是善用数组指针，尽量减少元素移动。这道题一开始可能会想真的去一次次循环左移，最后再去判断，但转念一想，循环移位不就是序列的头变成了尾，原来第二个元素变成了新的头，仅此而已，完全可以用两个指针来标识，然后观察这个序列就从head指针开始，一直读到tail指针。这样能节省很多时间

⭐感谢您能看到这里，这是对我莫大的鼓励！⭐