【第三轮】6.16-6.22 CareerCup 1.6

【解题思路】
   顺时针转，逆时针转，写了两个方法。
【时间复杂度】o(n^2)
【空间复杂度】o(1)
【gist link】
https://gist.github.com/jaly50/5ac7c2008e133dd765ca
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

The original image is:
  1  2  3  4
  5  6  7  8
  9 10 11 12
13 14 15 16

Clockwise:
13  9  5  1
14 10  6  2
15 11  7  3
16 12  8  4

CounterClockwise:
  1  2  3  4
  5  6  7  8
  9 10 11 12
13 14 15 16

【解题思路】
  Approach 1: layered rotate (top-right-bottom-left), the subscripts of matrix are easy to be wrong
  Approach 2: transpose + flip according to vertical middle line
【时间复杂度】
  O(N^2)
【空间复杂度】
  O(1)
【gist link】
https://gist.github.com/xun-gong/78ced3e7837e5162bcde

【解题思路】
1. 4 pixel in a group, N^2/4 times of replacement (layer by layer)i = 0 -> N/2, j = i -> N-i-1 {
temp = a[j];
a[j] = a[N-j-1];
a[N-j-1] = a[N-i-1][N-j-1];
a[N-i-1][N-j-1] = a[j][N-i-1];
a[j][N-i-1] = temp;
}
2. transpose + flip
【时间复杂度】
O(N^2) to access each element in the matrix
【空间复杂度】
O(1)
【gist link】
先占坑……
【test case】
integer matrix N = 0 - 5

难点：multidimensional array/vector



补充内容 (2014-6-24 14:01):
不能编辑了…gist link在这里
https://gist.github.com/27e9ada3a324c3adad4f

【解题思路】
1.transpose
2.switch columns

【时间复杂度】
O(N^2)

【空间复杂度】
O(1)
【gist link】
https://github.com/FinalF/Carrer ... matrixRotation.java

asdw3276 发表于 2014-6-19 01:57
【解题思路】 leetcode原题，通过观察我们可以发现旋转是4个一组进行旋转，所以只需要循环1/4个矩阵就可以 ...

the algorithm is wrong

because if it's a 4*4 matrix

in you solution, i<n/2 and j<=n/2
which means, the matrix[0][2] will be calculate twice.

solution 1
Idea: same to the one on the book: We perform such a swap on each layer, starting from the outermost layer and working our way inwards
Time Complexity: O(n^2)
Space Complexity: O(1)

solution 2
Idea: Each rotate, we need to rotate four items in the matrix. So we just need to traverse from int[0][0] to int[n/2][n/2], Remember if num is even, avoid to rotate twice!
Time Complexity: O(n^2)
Space Complexity: O(1)

Code Link is here: http://www.jyuan92.com/post-319

【解题思路】
说白了就是把第i行换成第i列，把第j列换成第j行
所以原来的矩阵输出方式：
for(int i = 0; i<n;i++)
    for(int j = 0; j<n;j++)
        System.out.print(a[j])
换成
for(int i = 0; i<n;i++)
    for(int j = n-1; j>=0;j--)
        System.out.print(a[j])
【时间复杂度】
O(N^2)

【空间复杂度】
O(1)
【gist link】
无gist……贴代码吧
import java.util.*;
public class matrix{

public static void Rotation(int[][] d){
  int k = d.length;
  for(int a = 0; a<k; a++){
   for(int b = k-1; b>=0;b--){
    System.out.print(d[b][a]+" ");
   }
   System.out.println();
  }
}
public static void main(String[] args){
  Scanner sc = new Scanner(System.in);
  System.out.print("请输入矩阵大小（0~9）");
  int n = sc.nextInt();
  int[][] m = new int[n][n];
  for(int i = 0; i<n; i++){
   for(int j = 0; j<n; j++){
    m[i][j] = i;
    System.out.print(m[i][j]+" ");
   }
   System.out.println();
  }
  System.out.println();
  Rotation(m);  
}
}

【解题思路】
说白了就是把第i行换成第i列，把第j列换成第j行
所以原来的矩阵输出方式：
for(int i = 0; i<n;i++)
     for(int j = 0; j<n;j++)
         System.out.print(a[j])
换成
for(int i = 0; i<n;i++)
     for(int j = n-1; j>=0;j--)
         System.out.print(a[j])
【时间复杂度】
O(N^2)

【空间复杂度】
O(1)
【gist link】
无gist link，贴代码在此
import java.util.*;

public class matrix{
       
        public static void Rotation(int[][] d){
                int k = d.length;
                for(int a = 0; a<k; a++){
                        for(int b = k-1; b>=0;b--){
                                System.out.print(d[b][a]+" ");
                        }
                        System.out.println();
                }
        }

        public static void main(String[] args){
                Scanner sc = new Scanner(System.in);
                System.out.print("请输入矩阵大小（0~9）");
                int n = sc.nextInt();
                int[][] m = new int[n][n];
                for(int i = 0; i<n; i++){
                        for(int j = 0; j<n; j++){
                                m[i][j] = i;
                                System.out.print(m[i][j]+" ");
                        }
                        System.out.println();
                }
                System.out.println();
                Rotation(m);               
        }
}

donnice 发表于 2014-6-27 04:46
【解题思路】
说白了就是把第i行换成第i列，把第j列换成第j行
所以原来的矩阵输出方式：

本楼和37楼请都删掉，谢谢

sanguine 发表于 2014-6-26 18:11
the algorithm is wrong

because if it's a 4*4 matrix

thank you! you are right and i have updated my solution~