今晚CVTE笔试Android岗位一道编程题

这个是旋转数组的题，写了一下代码如下 public static void rotateArray(int[] a, int k){ if(k%a.length==0){ return ; } if(k>a.length){ k = k%a.length; } reverse(a,0,a.length-1); reverse(a,0,k-1); reverse(a,k,a.length-1); } public static void reverse(int[] a, int start, int end){ while(start<end){ int tmp = a[end]; a[end] = a[start]; a[start] = tmp; start++; end--; } }

我用C++写了一个函数。 思想是从第一个数开始，找到它对应的下标，及i=(i+k)%size，size是数组个数，然后将这个数放到这个array[i]，接着从下标i开始，寻找它对应的下一个数组正确位置;相当于就是将数组所有的元素用一个环来连接，然后从第一个数开始，将元素逐个放到对应的位置。 需要注意的是： 1、k>size，需要将k=k%size； 2、当k能整除size，就需要额外的处理，否则按照上面的步骤需要进入一个“死循环”。 代码 void rotate(int []array,int size,int k) { //这里就不判断参数是否合法了，默认都是合法的参数 int count=0,temp,i,index,temp1,count1; if(k>size) k=k%size; if(size%k!=0) { index=0; temp=array[0]; while(count<size) { i=(index+k)%size;//下一个要被覆盖的 temp1=array[i];//临时保存这个值 array[i]=temp; index=i;//从当前继续往下覆盖 count++; temp=temp1; } } else { count=0; while(count<k)//将数组分为size/k块，每块k个元素 { index=count; temp=array[index]; while(count1<(size/k)) { i=(index+k)%size;//下一个要被覆盖的 temp1=array[i];//临时保存这个值 array[i]=temp; index=i;//从当前继续往下覆盖 count1++; temp=temp1; } count++; } } }

 /**     *     * 与字符串旋转类似。     * 题目中给出的是向右移动k个元素，(k有可能大于数组的长度len，)这样的话就相当于后面的k个元素要被放到最前面。     * 在这里可以首先把[0,len-1-k]的数组部分进行反转，然后把[len-k,len-1-k]的部分旋转，     * 最后在把整个数组[0,len-1]旋转。      *     */     public void rotate(int[] nums, int k) {         int len = nums.length;         k = k%len;         /*Step1:先把[0,len-1-k]的数组部分进行反转*/         reverse(nums,0,len-k-1);         /*Step2:把[len-k,len-1-k]的部分旋转*/          reverse(nums,len-k,len-1);          /*Step3:把整个数组旋转*/           reverse(nums,0,len-1);     }     /**      * 该方法的作用是把数组nums下标在[start,end]区间内的元素反转。       */     public void reverse(int[] nums,int start,int end){         int temp = 0;         int i=start;         int j=end;         for(;i<j;i++,j--){             temp = nums[i];             nums[i] = nums[j];             nums[j] = temp;         }     }

void Print_rigtmove(int *ar, int len, int k) { int i = len-k; int count = 0; for(;count<len;i++,count++) { if (i >=len) i %=len; printf("%d ",ar[i]); } }

http://www.kesarblog.cn/2016/03/05/%E9%9D%A2%E7%BB%8F-CVTE%E7%9A%84%E4%B8%A4%E9%81%93%E7%AC%94%E8%AF%95%E7%BC%96%E7%A8%8B%E9%A2%98/ 两道题解

// 取模， 从后往前读数据 int len=4;//数组长度 int goRight=3;//右移位数 // build data vector<int>array, ans(len); for (int i = 0; i < len; ++i) { array.push_back(i+1); } //右移位数//还有 右移位数为负没判断 /一下，向上+整数倍， goRight%=len; int index= 2*len-goRight-1; // caculate for (int j = len-1; j >=0 ; --j) { ans[j]=array[index%len]; --index; } // output for (int i = 0; i < len; ++i) { cout<<ans[i]<<" "; } cout<<endl;

感觉不难～

void rotate(vector<int>& nums, int k) { if(nums.size() == 0 || k == 0) return; k = k % nums.size(); reverse(nums.begin(),nums.end()); reverse(nums.begin(),nums.begin() + k); reverse(nums.begin()+k,nums.end()); }

比较偷懒的代码。。。 int[] charge(int n,int a[]){ int i = 0; int r[] = new int[a.length]; if (n>=a.length){ n%=a.length; } if (n<0){ } for (int j = a.length-n;j<a.length;j++){ r[i]=a[j]; i++; } for (int j=0;j<a.length-n;j++){ r[i]=a[j]; i++; } return r; }

我觉得是不是可以搞成环形队列，队首指针和队尾指针同时移动，然后再输出？

http://m.blog.csdn.net/article/details?id=50813083循环右移和左移k位