h***t
发帖数: 43 | 1 电面，碰到传说中的“国人大哥”，上来考了rotate array (leetcode 原题)，很快搞
定。接着说要出一个2D array rotation问题，当时还庆幸又是原题（rotate image）
，大哥不错啊，知道放水。
接着听就不对劲了。不是90度旋转，而是要把每一个element都顺时针移动 k steps。
比如n = 5, k = 3,
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
变为
16 11 6 1 2
21 18 17 12 3
22 19 13 7 4
23 14 9 8 5
24 25 20 15 10
本来想这两道题一起出，我就用一下rotate array的程序吧，就是把每一个circle的
element取出来放到一个Array里，rotate完了，再放回去，但大哥说复杂度太高。再想
，，，
那就只有用rotate image的思路了，一个个挪，时间O(n*n),空间O(1)。
思路对了，接着写程序，才发现没那么简单，而且时间也快到了。
跪了。。。。
电话完了，接着写（google了，网上没查到有这个题），最后总算搞定了，才发现里面
还有90旋转，180旋转的情况，继续改。
，，，，，
完全搞完，花了我几个小时。
，，，
大哥，就那么点时间，你要我搞定这个！！！ | B*******1
发帖数: 2454 | | e*******7
发帖数: 347 | | n******n
发帖数: 12088 | 4 本质上还是一维啊，一圈一圈走。就是数组下标映射一下。怎么觉得这个比二维的简单。
刷题刷到见题就套，有点走火入魔。
【在 h***t 的大作中提到】
: 电面，碰到传说中的“国人大哥”，上来考了rotate array (leetcode 原题)，很快搞
: 定。接着说要出一个2D array rotation问题，当时还庆幸又是原题（rotate image）
: ，大哥不错啊，知道放水。
: 接着听就不对劲了。不是90度旋转，而是要把每一个element都顺时针移动 k steps。
: 比如n = 5, k = 3,
: 1 2 3 4 5
: 6 7 8 9 10
: 11 12 13 14 15
: 16 17 18 19 20
: 21 22 23 24 25
| z***m
发帖数: 1602 | | s******e
发帖数: 2181 | 6 如果要求空间最小，是只需要一个element的空间啊。
把第一个数字取出来，然后算逆时针k steps，看是谁要放到第一个空出来的位置上，
放过去后第二个位置空出来了，然后再计算逆时针k steps，把第3个数字放到第二个空
出来的位置上。。。直到全部move了一遍后，然后再同样对内圈操作。 | E*******1
发帖数: 3464 | 7 这个题b格够高的
【在 h***t 的大作中提到】
: 电面，碰到传说中的“国人大哥”，上来考了rotate array (leetcode 原题)，很快搞
: 定。接着说要出一个2D array rotation问题，当时还庆幸又是原题（rotate image）
: ，大哥不错啊，知道放水。
: 接着听就不对劲了。不是90度旋转，而是要把每一个element都顺时针移动 k steps。
: 比如n = 5, k = 3,
: 1 2 3 4 5
: 6 7 8 9 10
: 11 12 13 14 15
: 16 17 18 19 20
: 21 22 23 24 25
| s******x
发帖数: 417 | | w********n
发帖数: 4752 | | n*********u
发帖数: 1030 | 10 好像就是1D array rotate加个转圈就行了吧？转圈那个确实有点麻烦。
一共有n/2个圈要转。
试着把每个圈都铺平了，当linked list一样做rotate，也就是写个新的self.next()
function。
大概这样？
for offset in range(0, n/2):
# do while loop in python
x = offset
y = offset
while True:
# rotate x, y, by k steps
# 记不得怎么写rotate list的懒人路过
(x, y) = get_next(n, x, y, offset)
if x == y:
#回到出发点结束
break
# rotation 的 self.next() function。
# offset can be calculated with n, x, y, but it'll be available anyways.
def get_next(n, x, y, offset):
if x == n - offset :
if y == n - offset :
return x-1, y
else:
return x, y+1
elif x == offset :
if y == offset:
return x+1, y
else:
return x, y-1
else:
if y == n - offset :
return x-1, y
else: # y offset
return x+1, y
| | | p*****r
发帖数: 1883 | 11 不用这么麻烦，按照圈打印出来matrix（Spiral Matrix）那个题会吧，
这里就是把每圈的index加个K然后对于圈长取余算出来新坐标再放回去就行了
【在 n*********u 的大作中提到】
: 好像就是1D array rotate加个转圈就行了吧？转圈那个确实有点麻烦。
: 一共有n/2个圈要转。
: 试着把每个圈都铺平了，当linked list一样做rotate，也就是写个新的self.next()
: function。
: 大概这样？
: for offset in range(0, n/2):
: # do while loop in python
: x = offset
: y = offset
: while True:
| x*****0
发帖数: 452 | | Z**0
发帖数: 1119 | | b*******w
发帖数: 56 | 14 def rotate_by_k(matrix, k):
i = 0
while i < len(matrix)>>1:
# construct 1-d array
nums = []
x, y = i, i
while x < len(matrix) - i - 1:
nums.append(matrix[y][x])
x += 1
while y < len(matrix) - i - 1:
nums.append(matrix[y][x])
y += 1
while x > i:
nums.append(matrix[y][x])
x -= 1
while y > i:
nums.append(matrix[y][x])
y -= 1
k %= len(nums)
nums = nums[::-1]
nums = nums[k-1::-1] + nums[-1:k-1:-1]
x, y, s = i, i, 0
while x < len(matrix) - i - 1:
matrix[y][x] = nums[s]
x += 1
s += 1
while y < len(matrix) -i -1:
matrix[y][x] = nums[s]
y += 1
s += 1
while x > i:
matrix[y][x] = nums[s]
x -= 1
s += 1
while y > i:
matrix[y][x] = nums[s]
y -= 1
s += 1
i += 1 | b*******w
发帖数: 56 | 15 贴了个代码在楼上， 把值取出来ｒｏｔａｔｅ就可以了 | l******s
发帖数: 3045 | 16 private void rotateImage(int[,] board, int k)
{
int m = board.GetLength(0), n = board.GetLength(1);
int cycleM = m, cycleN = n;
while(cycleM > 1)
{
int oX = (m - cycleM) / 2, oY = (n - cycleN) / 2;
int[] xy = new int[2] { oX, oY };
int tmp = board[xy[0], xy[1]];
int[] nextXY = getNextXY(xy, m, n, cycleM, cycleN, k);
while(nextXY[0] != oX || nextXY[1] != oY)
{
tmp = tmp ^ board[nextXY[0], nextXY[1]] ^ (board[nextXY[0],
nextXY[1]] = tmp);
nextXY = getNextXY(nextXY, m, n, cycleM, cycleN, k);
}
board[oX, oY] = tmp;
cycleM -= 2;
cycleN -= 2;
}
}
private int[] getNextXY(int[] xy, int boardM, int boardN, int cycleM, int
cycleN, int k)
{
int minX = (boardM - cycleM) / 2, minY = (boardN - cycleN) / 2;
int maxX = minX + cycleM - 1, maxY = minY + cycleN - 1;
int[] newXY = new int[2] { xy[0], xy[1] };
k %= 2 * (cycleM + cycleN - 2); // If K is greater than 1 full cycle,
limit it in 1 cycle
if (k >= cycleM + cycleN - 2) // If K is greater than half a full
cycle, rotate half a cycle
{
newXY = new int[2] { boardM - xy[0] - 1, boardN - xy[1] - 1 };
k -= cycleM + cycleN - 2;
}
//Craw the edge step by step in half a cycle
while(k-- > 0)
if (newXY[0] == minX && newXY[1] != maxY) newXY[1]++;
else if (newXY[1] == maxY && newXY[0] != maxX) newXY[0]++;
else if (newXY[0] == maxX && newXY[1] != minY) newXY[1]--;
else if (newXY[1] == minY && newXY[0] != minX) newXY[0]--;
return newXY;
} | f**********e
发帖数: 288 | | c******g
发帖数: 238 | | a********8
发帖数: 1625 | 19 Java version:
public static void rotateMatrix(int[][] matrix,int k) {
if(matrix==null||matrix.length==0||matrix[0].length==0||matrix.
length!=matrix[0].length)
return ;
if(matrix.length==1)
return;
if(k<=0)
return;
int m = matrix.length/2;
for(int i = 0;i
helper(matrix,i,k,4*(matrix.length-2*i)-4);
}
}
private static void helper(int[][] matrix,int i,int k,int length) {
k = k%length;
if(k==0)
return;
int reach = length;
int sideLength = (length+4)/4;
for(int m=0;m
int[] temp_xy = getXY(m,i,sideLength,matrix.length);
int temp = matrix[temp_xy[0]][temp_xy[1]];
int n = m;
while((n-k+length)%length!=m) {
int key = (n-k+length)%length;
temp_xy = getXY(n,i,sideLength,matrix.length);
int[] new_xy = getXY(key,i,sideLength,matrix.length);
matrix[temp_xy[0]][temp_xy[1]] = matrix[new_xy[0]][new_xy[1]
];
n = key;
reach = Math.min(reach, n);
}
temp_xy = getXY(n,i,sideLength,matrix.length);
matrix[temp_xy[0]][temp_xy[1]] = temp;
}
}
private static int[] getXY(int m,int i,int sideLength,int lengthOfMatrix) {
int[] res = new int[2];
switch(m/(sideLength-1)) {
case 0:
res[0] = i;
res[1] = i+m%(sideLength-1);
return res;
case 1:
res[0] = i+m%(sideLength-1);
res[1] = lengthOfMatrix-1-i;
return res;
case 2:
res[0] = lengthOfMatrix-1-i;
res[1] = lengthOfMatrix-1-i-m%(sideLength-1);
return res;
case 3:
res[0] = lengthOfMatrix-1-i-m%(sideLength-1);
res[1] = i;
return res;
default:
return res;
}
} |
|
