西安企业网站设计哪家专业,网页游戏排行榜开服时间,wordpress好用的文章编辑器,网站建设公司上海做网站公司旋转图像 给定一个NN的二维矩阵表示图像#xff0c;90度顺时针旋转图像。 看个例子 算法1#xff1a; 如上图所示#xff0c;设一个N阶二维矩阵#xff0c;则将矩阵从外向里可以分成N/2个圈#xff0c;例如#xff08;1 2 3 4 8 12 16 15 14 13 9 5#xff09;这是最外边… 旋转图像 给定一个N×N的二维矩阵表示图像90度顺时针旋转图像。 看个例子 算法1 如上图所示设一个N阶二维矩阵则将矩阵从外向里可以分成N/2个圈例如1 2 3 4 8 12 16 15 14 13 9 5这是最外边的圈设圈的维度是n最外圈有nN4而6 7 11 10这是里边的一个圈n2, 旋转90度之后每个数字是按照顺时针的方向移动了n-1个位置。 找到数字该去的位置 pairint, int getNextPos(int i, int j, int top, int left, int down, int right){//(top, left) (down, right)标示这个圈的范围即左上角坐标和右下角坐标int n down-top1;//得到这个圈的维度int move n-1;//转过move个位置while(move--){if(itop jleft jright)j;else if(itop idown jright)i;else if(idown jright jleft)--j;else if(idown itop jleft)--i;}return make_pair(i, j);
} 旋转过程 由上图可见1到4的位置4到16的位置16到13的位置13到1的位置结束循环。接着数字2和数字3按照同样的步骤完成了整个圈的旋转操作。 void rotate(vectorvectorint matrix) {// write your code here//方法1转圈法从外圈到里圈设圈的维度是n图像旋转90度后数字顺时针移动n-1个位置int circle matrix.size()/2;//得到圈的个数int top0, left0, downmatrix.size()-1, rightmatrix.size()-1;//最外圈的维度for(int cir0; circircle; cir){int ttop topcir;int lleft leftcir;int rright right-cir;int ddown down-cir; //ttop, lleft (ddown, rright)标示这个圈for(int jlleft; jrright; j){pairint, int org make_pair(ttop, j);//原始位置如果再次到这个位置说明交换完毕pairint, int cur org;int cur_val matrix[cur.first][cur.second];//当前数的值while(true){pairint, int _next getNextPos(cur.first, cur.second, ttop, lleft, ddown, rright);swap(matrix[_next.first][_next.second], cur_val);if(_nextorg) break;cur _next;}}}} 算法2 通过两次折叠先上下对换再根据对角线对换即可得到目标图像。 void rotate(vectorvectorint matrix) {int n matrix.size();for(int i0; in/2; i)for(int j0; jn; j)swap(matrix[i][j], matrix[n-i-1][j]);//上下对换for(int i0; in; i)for(int j0; ji; j)swap(matrix[i][j], matrix[j][i]);//主对角线两侧交换
} 题目链接 http://www.lintcode.com/zh-cn/problem/rotate-image/ 转载于:https://www.cnblogs.com/hujunzheng/p/5048300.html
