循环旋转codility c++解决方案

Question

我正在尝试解决这个问题in Codility...
这是代码：

 #include <iostream>    
 #include <vector>     
 #include <algorithm>
 using namespace std;

 vector<int> solution(vector<int> &A, int k);
 vector<int> A;   
 A.push_back(3);    
 A.push_back(5);   
 A.push_back(7);   
 A.push_back(9);   
 A.push_back(2);
 int k;
 rotate(A.rbegin(),A.rbegin()+k, A.rend());

虽然我的编译器编译运行没有问题，但 codility 告诉我 "error: 'A' does not name a type"。这是我的编译器用来检查它的代码：

  #include <iostream>
  #include <vector>
  #include <algorithm>
  using namespace std;

  int main()
  {
   vector<int> myVector;
   myVector.push_back(3);
   myVector.push_back(5);
   myVector.push_back(7);
   myVector.push_back(9);
   myVector.push_back(2);
   for(unsigned i=0;i<myVector.size();i++)
   {
     cout<<myVector[i]<<" ";
   }
   cout<<endl;
   int k;
   cout<<"Insert the times of right rotation:";
   cin>>k;
   rotate(myVector.rbegin(),myVector.rbegin()+k, myVector.rend());
   for(unsigned i=0;i<myVector.size();i++)
   {
     cout<<myVector[i]<<" ";
   }
  }

编译器输出：

func.cpp:9:3: error: 'A' does not name a type
   A.push_back(3);
   ^
func.cpp:10:3: error: 'A' does not name a type
   A.push_back(5);
   ^
func.cpp:11:3: error: 'A' does not name a type
   A.push_back(7);
   ^
func.cpp:12:3: error: 'A' does not name a type
   A.push_back(9);
   ^
func.cpp:13:3: error: 'A' does not name a type
   A.push_back(2);
   ^
func.cpp:16:9: error: expected constructor, destructor, or type conversion before '(' token
   rotate(A.rbegin(),A.rbegin()+k, A.rend());
         ^
func.cpp:18:1: error: expected declaration before '}' token
 }
 ^

Detected some errors.

Answer 1

您只能在函数外定义或声明符号。您的 A.push_back(3); 等不是定义或声明语句。这就是为什么您会收到有趣的错误消息：定义和声明以类型开头，并且由于行在函数之外，因此编译器希望看到类型，而 A 不是。

所以你需要一个函数，比如：

#include <iostream>    
#include <vector>     
#include <algorithm>
using namespace std;

vector<int> solution(vector<int> &A, int k)
{ //added
    //vector<int> A; // this is function argument, not local variable   
    A.push_back(3);    
    A.push_back(5);   
    A.push_back(7);   
    A.push_back(9);   
    A.push_back(2);
    //int k;  // this is function argument, not local variable
    rotate(A.rbegin(),A.rbegin()+k, A.rend());
    return A; // Added since the function needs to return a vector of int...
} //added

那应该编译并做一些事情。所以我所做的就是您可能打算做的：代码现在在 solution 函数中。

Answer 2

我认为你有很多问题并做了一些假设这是工作代码

1.You 不需要创建新向量，因为函数已经有一个引用向量 &A，所以任何更改都会直接反映到原始向量

2.value K 是已经输入到函数中的旋转点（因此不需要 cin）

现在 100% 搞定了

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<algorithm>


vector<int> solution(vector<int> &A, int K)
{
    if (A.empty() || A.size() == 1)
    {
        return A;
    }
    K = K % A.size();

    if (K == 0)
    {
        return A;
    }
    std::rotate(A.rbegin(), A.rbegin() + K, A.rend());
    return A;
}

输出

Answer 3

OBJECTIVE-C 解决方案 O(n*k) - 一种方法

Codility给出的结果

任务分数：100%
正确率：100%
性能：未评估

时间复杂度

最坏情况的时间复杂度是O(n*k)

Xcode Solution Here

+(NSMutableArray*)byByOneSolution:(NSMutableArray*)array rotations:(int)k {
    // Checking for edge cases in wich the array doesn't change.
    if (k == 0 || array.count <= 1) {
        return array;
    }

    // Calculate the effective number of rotations
    // -> "k % length" removes the abs(k) > n edge case
    // -> "(length + k % length)" deals with the k < 0 edge case
    // -> if k > 0 the final "% length" removes the k > n edge case
    NSInteger n = array.count;
    NSInteger rotations = (n  + k % n ) % n;


    /******** Algorithm Explanation: Naive Method ********/
    // Rotate one by one based on the efective rotations
    for (int i = 0; i < rotations; i++) {
        id last = array[n-1];
        [array removeLastObject];
        [array insertObject:last atIndex:0];
    }
    return array;
}

Answer 4

OBJECTIVE-C 解决方案 O(n) - 基于反向的解决方案

Codility给出的结果

任务分数：100%
正确率：100%
性能：未评估

时间复杂度

最坏情况的时间复杂度是 O(3n) => O(n)

Xcode Solution Here

+(NSMutableArray*)reverseBasedsolution:(NSMutableArray*)array rotations:(int)k {

    // Checking for edge cases in wich the array doesn't change.
    if (k == 0 || array.count <= 1) {
        return array;
    }

    // Calculate the effective number of rotations
    // -> "k % length" removes the abs(k) > n edge case
    // -> "(length + k % length)" deals with the k < 0 edge case
    // -> if k > 0 the final "% length" removes the k > n edge case
    NSInteger n = array.count;
    NSInteger rotations = (n  + k % n ) % n;

    /******** Algorithm Explanation: Reverse Based ********/
    // 1.- Reverse the whole array
    // 2.- Reverse first k numbers
    // 3.- Reverse last n-k numbers

    // 1. Reverse the whole array
    NSArray* reversed = [[array reverseObjectEnumerator] allObjects];

    // 2. Reverse first k numbers
    NSRange leftRange = NSMakeRange(0, rotations);
    NSArray* leftPart = [[[reversed objectsAtIndexes:[NSIndexSet indexSetWithIndexesInRange:leftRange]] reverseObjectEnumerator] allObjects];

    // 3. Reverse last n-k numbers
    NSRange rightRange = NSMakeRange(rotations, n - rotations);
    NSArray* rightPart = [[[reversed objectsAtIndexes:[NSIndexSet indexSetWithIndexesInRange:rightRange]] reverseObjectEnumerator] allObjects];

    // Replace objects in the original array
    [array replaceObjectsInRange:leftRange withObjectsFromArray:leftPart];
    [array replaceObjectsInRange:rightRange withObjectsFromArray:rightPart];

    return  array;
}

Answer 5

如果您不想使用 <algorithm> 的旋转功能。

Codility给出的结果：

Programming : C++
Task Score: 100%
Correctness: 100%
Performance: Not assesed

解决方法：

vector<int> solution(vector<int> &A, int K)
{
    vector <int> shift;
    if (A.empty()) // check for empty array
        return {};
    if (K > A.size()) //if K bigger then size of array 
        K = K%A.size();
    if (K<A.size())
        K=A.size()-K; //normalize K to the position to start the shifted array
    if (K == A.size()) //if K= size of array, avoid any computation.
        return A;
    for (unsigned int i=K; i<A.size(); i++)
    {
        shift.push_back(A[i]);
    }
    for (unsigned int i=0; i<K; i++)
    {
        shift.push_back(A[i]);
    }
    return shift;
}

Answer 6

总分 100% 的一种可能的 C++ 实现：

#include <algorithm>
#include <iterator>

vector<int> solution(vector<int> &A, int K) {
    vector<int> ret;
    
    if (!A.empty()) {
        int kReal = K % A.size();
        std::copy(A.begin()+A.size()-kReal, A.end(), std::back_inserter(ret));
        std::copy(A.begin(), A.begin()+A.size()-kReal, std::back_inserter(ret));
    }
    return ret;
}

循环旋转codility c++解决方案

cyclic rotation codility c++ solution

c++

vector

solution