3.1 --- Describe how you could use a single array to implement three stacks.

Q: Describe how you could use a single array to implement three stacks. A: 1) for three stacks, top1, top2,top3, where top1= 3*i top2= 3*i+1 top3= 3*i+2 2) devide array into 3 parts, part 1: 0- array.length()/3; part 2: array.length()/3+1 - 2* array.length()/3; part 3: 2* array.length()/3+1 - array.length() 这个，要好好看看书上的， clean, maintainable 的例子。

3 --- stack and queue

自己写的，两个基本类型的，基于链表的实现。

public class Stack implements Cloneable {
 Node top; // pointing to the toppest node on a stack

 Node pop() {
  if (top != null) {
   Node item = top;
   top = top.next;
   return item;
  }
  return null;
 }

 void push(int k) {
  Node t = new Node(k);
  t.next = top;
  top = t;
 }

 Object peek() {
  return top.data;
 }

 public Stack clone() throws CloneNotSupportedException {
  return (Stack) super.clone();
 }
 
 boolean isEmpty(){
  return (this.top ==null);
 }
}

public class Queue {
 // in this implementation, tail.next is always null;, so that we can enqueue() at tail
 // thus, delete at head();
 Node head, tail;
 void enqueue(Node item){// enqueue at tail. 
  if(tail ==null){
   tail = item;
   head = item;
  }else{
   tail.next = item;
   item.next = null;
   tail = item;
  }
 }
 Object dequeue(){//  dequeue at head 
  // head point to the just added item. or the first in a single list
  if(head!=null){
   Object item = head;
   head = head.next;
   return item;
  }
  return null;
 }
}

Learned:
1: Constructor call must be the first statement in a constructor

2.7 --- check if a list is palindrome

Q:
Implement a function to check if a linked list is a palindrome.

A：
Solution #1: reverse and compare
Idea： create another list reversely , and compare two list  (注意，我们只需要对比前一半儿就行了。 也就是说，创建新的list的时候，计数得知listSize）

 private static boolean checkPalindrome(LinkList list) {
  // create another list reversely , and compare them one by one
  LinkList newList = new LinkList();
  Node runner = list.header.next;
  while (runner != null) {
   Node tmpNode = new Node(runner.data);
   newList.insertAtBeginning(tmpNode);

   runner = runner.next;
  }
  // compare the two list
  Node runner1 = list.header.next;
  Node runner2 = newList.header.next;
  while (runner1 != null && runner2 != null && runner1.data == runner2.data) {
   runner1 = runner1.next;
   runner2 = runner2.next;
  }
  if (runner1 == null && runner2 == null) { // reach the end of these two
             // list
   return true;
  } else {
   return false;
  }

 }

Solution #2: Iterative Approcach
 use a stack to store the first half part.
1) if the list size is already known, delete the size,  (be careful of when the list size is odd.
2) if the list size is unknown.  use a fast/ slow runner, when the fast reach end, slow only at middle, 

 private static boolean checkPalindrome(LinkList list) {
  // create another list reversely , and compare them one by one
  Node slowRunner = list.header;
  Node fastRunner = list.header;
  // in math, fastRunner point to the node: 2,4,6,8
  // slow point to the 1,3,5,7
  while (fastRunner != null && fastRunner.next != null) {
   fastRunner = fastRunner.next.next;
   slowRunner = slowRunner.next;

  }
  boolean isListSizeOdd = false; // default is Even number
  if (fastRunner == null) {// list length is odd number
   // Now slowRunner point to exactly the middle one
   isListSizeOdd = true;
  }

  fastRunner = list.header.next;
  // put into Stack
  Stack stack = new Stack();
  if (isListSizeOdd) {
   while (fastRunner != slowRunner) {
    stack.push(fastRunner);
    fastRunner = fastRunner.next;
   }
  } else { // list length is even number, the slowRunner point to the
   while (fastRunner != slowRunner.next) {
    stack.push(fastRunner);
    fastRunner = fastRunner.next;
   }
  }
  slowRunner = slowRunner.next; // slowRunner point to the half tail part.
  while (slowRunner != null && !stack.isEmpty()) {
   Node tmpNode = stack.pop();
   if (tmpNode.data != slowRunner.data) {
    return false;
   } else {
    slowRunner = slowRunner.next;
   }

  }
  if (slowRunner == null & stack.isEmpty()) {
   return true;
  } else {
   System.err.println("something wrong");
   System.exit(1);
   return false;
  }

 }

这里犯了一个错误，就是由于 边想边写，头脑不够清晰。 导致判断的时候，有混淆。
以后写这种代码的时候，要先想清楚了，在纸上写好了，再誊到eclipse上

Solution #3: Recursive Approcach

要recursively 建立一个前后匹配的对儿。然后，逐层缩简。









Mistakes: 
1: 两个runner， 刚开始用了runner1.equals(runner2). 但是，其实二者是不同的list里的对象。 不能这样搞的。

2.6 -- find the first node of a circular linked list

Q：
Given a circular linked list, implement an algorithm which returns the node at
the beginning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node's next pointer points
to an earlier node, so as to make a loop in the linked list.
EXAMPLE
Input: A - > B - > C - > D - > E - > C [the same C as earlier]
Output: C

首先，我们先make circular.(for simplicity，没有边界检查什么的)

 public static void makecircular(LinkList list1, int ithPosition) {
  // making the list1 as circular , by putting the last one's next to the i_th postion
  Node ithNode = null;
  Node runner = list1.header;
  int cound = 0;
  while(runner.next!=null){
   cound++;
   if(cound == ithPosition){
    ithNode = runner;
   }
   runner = runner.next;
  }
  runner.next = ithNode;
 }

A：
 最SB 的方法，就是将map every object into a hash table, and if exist, check whether they are exactly the same. ------但如何保证对象的hash也没有重复呢？？？

用两个指针， 或者说，是两个runner，一快一慢，走阿走，直到快的，追上慢的。（可是这样只能说明有loop. ---- 慢的一次走一步，快的一次走2步)
再一个SB的算法，就是 从头儿一个个得删除节点，然后，看是否还有回路。
呵呵，先用SB的算法做吧。

自己写的算法，比较SB， 而且，结果也不全对，还是不写在这儿了。肏，浪费了好几个小时。



第二种方法，就是书上的解释。
fast runner一次跑2个节点。
slow runner一次跑1个节点。
第一次相遇后，fast runner的速度降为1，并回到header所指向的起始位置。，slow runner继续跑。直到再次相遇的时候，就为第一个节点。
自己的证明如下。

代码如下：

	private static Node findFirstOfLoop(LinkList list) {
		Node slowRunner = list.header.next;
		Node fastRunner = null;
		if (slowRunner != null) {
			fastRunner = slowRunner.next;
		}
		// find the first meet, record its position
		while (slowRunner != fastRunner) {
			if (fastRunner == null || fastRunner.next == null) {
				// we find that the list do not contains loop
				return null;
			}
			slowRunner = slowRunner.next;
			fastRunner = fastRunner.next.next;
		}
		// Now they are the same, we reset the fastRunner at the beginning, and
		// run again
		fastRunner = list.header.next;
		slowRunner = slowRunner.next;
		while (slowRunner != fastRunner) {
			slowRunner = slowRunner.next;
			fastRunner = fastRunner.next;
		}
		return slowRunner;

	}

Mistakes：
1： 在方法中， i 应该每次增加的，可是为什么没有增加呢？
     static void printList(LinkList list, int maxNumElements) {
      
        Node node = list.header.next;
        int i =0;
        while (node != null && i<maxNumElements) {
            System.out.print(node.data + "\t");
            node = node.next;
            i=i+1;
        }
        System.out.println();
    }

运行时，i的值，一直是0. 而如果变成i = i+1 就可以了。为什么呢？ Learned: 1: java中， constructor call constructor

class AA { 
    private String a;
    private String b;
 
    public AA(String a){ 
        this.a = a;
    } 
   
    public AA(String a, String b){ 
        this(a);
        this.b = b;
    } 
}

2:在 circular list中， 仅仅delete 指向的一个节点，是并不能真正删除的， 要考虑是否因为是circluar的，所以，被略过的object，依然还存在。

3：  看下面的一段代码，

		// Now they are the same, we reset the fastRunner at the beginning, and
		// run again
		fastRunner = list.header.next;
		while (slowRunner != fastRunner) {
			slowRunner = slowRunner.next;
			fastRunner = fastRunner.next;
		}

仅仅这样的话，slowRunner 和fastRunner会相差一个的距离。-------->而再上图的证明中，第一次相遇后，fastRunner要回到队列的首位置，   而  slowRunner是要走到下一个的。

2.5 ---- sum at two list (reverse and forward order)

Q:  (书上的forward 的解法，明显更繁琐些）

You have two numbers represented by a linked list, where each node contains a
single digit. The digits are stored in reverse order, such that the Ts digit is at the
head of the list. Write a function that adds the two numbers and returns the sum
as a linked list.
EXAMPLE
Input: (7-> 1 -> 6) + (5 -> 9 -> 2).That is, 617 + 295.
Output: 2 -> 1 -> 9.That is, 912.
FOLLOW UP
Suppose the digits are stored in forward order. Repeat the above problem.
EXAMPLE
Input: (6 -> 1 -> 7) + (2 -> 9 -> 5).That is, 617 + 295.
Output: 9 -> 1 -> 2.That is, 912

A:
Reverse case:

simply extract the data into an inter, and add them ,then transform them back to the list form. ( in CtCi, they add on the list, directly. which make us to manipulate the math and (进位)

 
public static LinkList reverseOrderSum(LinkList list1, LinkList list2) {
  LinkList newList = new LinkList();
  int sum1 = 0;
  int sum2 = 0;
  Node runner = null;
  int numDigits = 0;
  // calculate sum of list1,
  runner = list1.header.next;
  while (runner != null) {
   sum1 += runner.data * (Math.pow(10, numDigits));
   runner = runner.next;
   numDigits++;
  }
  // calculate sum of list2,
  runner = list2.header.next;
  numDigits = 0;
  while (runner != null) {
   sum1 += runner.data * (Math.pow(10, numDigits));
   runner = runner.next;
   numDigits++;
  }
  int total = sum1 + sum2;
  Integer totalInt = new Integer(total);
  String strSum = totalInt.toString();
  System.out.println(strSum);
  for (int i = strSum.length() - 1; i >= 0; i--) {
   String subChar = strSum.substring(i, i + 1);
   int nodeData = Integer.valueOf(subChar);
   newList.append(new Node(nodeData));
  }

  return newList;

 }

Forward case:

 public static LinkList forwardOrderSum(LinkList list1, LinkList list2) {
  LinkList newList = new LinkList();
  int sum1 = 0;
  int sum2 = 0;
  Node runner = null;
  // calculate sum of list1,
  runner = list1.header.next;
  while (runner != null) {
   sum1 = sum1 * 10 + runner.data;
   runner = runner.next;
  }
  // calculate sum of list2,
  runner = list2.header.next;
  while (runner != null) {
   sum2 = sum2 * 10 + runner.data;
   runner = runner.next;
  }

  int total = sum1 + sum2;
  Integer totalInt = new Integer(total);
  String strSum = totalInt.toString();
  System.out.println(strSum);

  for (int i = 0; i < strSum.length(); i++) {
   String subChar = strSum.substring(i, i + 1);
   int nodeData = Integer.valueOf(subChar);
   newList.append(new Node(nodeData));
  }
  return newList;

 }

Mistakes:
1:   因此， 不能简单得用 10^2 来期待得到100， 而应该用Math.pow(10,2)
^ is the bitwise exclusive OR (XOR) operator in Java (and many other languages). It is not used for exponentiation. For that, you must use Math.pow.

2.4 -- partion a linked list around a value x

Q:
Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

A:
find a pivot point,   (e.g. the first one)   and all the rest of node, whose value less than pivotValue x,  insert at head.

 private static void partitionOnPivot(LinkList list, int pivotValue) {
  // use the first node as the pivot, if the following less then
  // pivotValue, insert before, otherwise, insert after
  Node runner = null;
  Node preRunner = null;;
  if (list.head != null) {   
   preRunner = list.head;
   runner=preRunner.next;
  }
  while (runner != null) {
   if (runner.data < pivotValue) {// insert before pivotNode
    preRunner.next=runner.next; //delete runner off the list
    //insert runner at the beginning of the list
    runner.next = list.head;
    list.head = runner;
    
    //position runner 
    runner = preRunner.next;
   }else{
    preRunner = runner;
    runner = runner.next;
   }
   
  }

 }

Mistakes:
1:
对于一个LinkList类，定义为：

public class LinkList {
 Node head;
}    

  Node runner = null;
  Node preRunner = list.head;
  if (list.head != null) {   
   runner = list.head;   
  }

那么，对于一个列表为：
8 40 41 的list，
runner.data的值为什么呢？？？ -------------------          未定义（或者说，没有）
preRunner.data的值为什么呢？？？？？------------------ 8

update ： 上面这个问题，会造成混乱。 原因就在于，我们定义LinkList中的head时， 是把它作为一个单独的object，or a pointer pointing to the first element of the list.

以后的程序中，暂定是前者。（否则，就应该叫 firstNode)

2.3 --- given only the middle node, delete it from the list

Q: 2.3 
Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
EXAMPLE
Input: the node c from the linked list a - > b - > c - > d - > e
Result: nothing is returned, but the new linked list looks like a- >b- >d->e

A:
就是，从后向前，一个个地copy，似乎没有别的办法了。

 
public static Node getMiddle(LinkList list, int listSize){
  Node tmp = list.head;
  for(int i = 0 ;i<(int)(listSize/2); i++){
   tmp = tmp.next;
  }
  return tmp;
 }
 public static void deleteMiddleNode(Node node){
  Node nextNode = node.next;
  while(nextNode.next != null){
   node.data = nextNode.data;
   
   node = nextNode;
   nextNode = nextNode.next;
  }
  node.data= nextNode.data;
  node.next=null;
 }

记得，检查边界值。 

2.2 --- find the kth to the last element of a singlely linked list

Q:
Implement an algorithm to find the kth to last element of a singly linked list.

A:

假设只需要得到答案从前数是第几个，（ 可以），利用一个变量来记下，递归的次数，nthToLast(curNode.next, k)  ，以此来返回从正向数，应该输出的index数。（不能得到data）。

Method 1: use two iterations, first to calculate the size of list.
               Then run through size - k  of the elements.

Method 2:  use two pointers, with their distance as k.

 public static Node twoRunKthtoLast(LinkList list, int k) {
  int listSize = 0;
  Node pointer = list.head;
  while (pointer != null) {
   listSize++;
   pointer = pointer.next;
  }
  if (k > listSize) {
   System.err.println("no enough node in list");
   return null;
  } else {
   int frontIndex = listSize - k;
   pointer = list.head;
   for (int i = 0; i < frontIndex; i++) {
    pointer = pointer.next;
   }
   return pointer;
  }
 }

 public static Node twoPointerKthtoLast(LinkList list, int k) {
  Node preRunner, behindRunner;
  preRunner = list.head;
  for (int i = 0; i < k; i++) {
   if (preRunner == null) {
    System.err.println("no enough node in list");
    return null;
   } else {
    preRunner = preRunner.next;
   }
  }
  // Now all preRunner point to the k+1 th element,
  behindRunner = list.head;
  while (preRunner != null) {
   preRunner = preRunner.next;
   behindRunner = behindRunner.next;
  }

  return behindRunner;
 }

Mistakes：
1：LinkList.head 所指向的，是一个node， 因此不能计数
2:  永远记住， 返回的对象，可能是null的。 不能随便用它来干活儿。  LOL

2.1 --- remove duplicates from unsorted linked List

Q:
2.1
Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?

A:
Using hash table
（没想到，或者想到了，但是以前没有做过，故而不知道去搞）

 public static void deleteDuplicates(LinkList list){
  Hashtable table  = new Hashtable();
  Node pointer = list.head;
  Node prePointer = null;
  while(pointer != null){
   if(table.containsKey(pointer.data))
    prePointer.next = pointer.next;
   else{
    table.put(pointer.data, true);
   }
   prePointer = pointer;
   pointer = pointer.getNext();
  }
 }
 public static void deleteDuplicatesNoBuffer(LinkList list){
  // use two pointers to delete duplicates
  Node curPointer = list.head;
  Node runner = null;
  Node preRunner = null;
  while(curPointer != null){
   preRunner = curPointer;
   runner = curPointer.next;
   // check if all has the same value
   while(runner!= null){
    if(runner.data == curPointer.data){
     // delete the at position runner. 
     preRunner.next = runner.next;
    }else{
     preRunner = runner;     
    }
    runner = runner.next;
   }   
   curPointer = curPointer.next;
  }
  
 } 

Mistakes:

1: 在list iterate的时候， 经常忘记，update指针，使之指向下一个位置。

2 Linked Lists ---------- LinkList, 和 Node class 及一些常用基本操作

 例如: LinkList 类

public class LinkList {
 Node head;

 public LinkList() {
  head = null;
 }

 void append(int d) {
  Node end = new Node(d);
  Node n = this.head;
  while (n.next != null) {
   n = n.next;
  }
  n.next = end;
 }

 void append(Node newNode) {
  // make sure newNode.next point to null
  newNode.next = null;
  Node n = this.head;
  if (n == null) {
   this.head = newNode;

  } else {
   while (n.next != null) {
    n = n.next;
   }
   n.next = newNode;
  }
 }
}

class Node {
 Node next;;
 int data;

 public Node(int d) {
  data = d;
  next=null;
 }
}

Mistakes:
1: 创建类的constructor时，不能有void 等返回关键字。。
另外，一个java源文件，只能有一个public的类。
2: 在创建Node类时，要注意在constructor里，声明next=null；否则，就不知道跑哪儿去了。

Learned:
1：注意： “runner” technique

和 “ Recursive Problems.

1.8 ---- check string rotation, using one call of subString();

Q:
Assume you have a method isSubstring which checks if one word is a
substring of another. Given two strings, si and s2, write code to check if s2 is
a rotation of si using only one call to isSubstring (e.g.,"waterbottle"is a rota-tion of "erbottlewat").

A:
idea:
s1 = xy
s2 = yx

那既然，单独的，这样，无法直接得到。
我们就想办法，给他们增大（增长）    。
例如：
s2 = yz
s1" = s1+s1 = xyxy

然后，就可以用：isSubstring()了。
当然，还是要check the string length.



Mistake:
刚开始，又是没有看明白题目。  难怪，感觉太简单了呢。
并不是全部的, s1.length的rotation，可能仅仅是rotatte了一部分。

哎， 看不明白题目，害死人啊~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
以后面试的时候，一定要多问一下面试官，确认自己搞明白了题目。


Learned：
这个，因为刚开始看错了题目。
看了一眼答案。  （只看了s1=xy）给了提示。
哎，还是自己不够聪明阿

1.6 ---- rotate the matrix

Q:
 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

A:

 
public class Main {

 public static void main(String[] args) {

  int imSize = 6;

  int[][] image = new int[imSize][imSize];
  // Initialize image
  Tool.randomInitializeArray(image);
  Tool.printArray(image);

  rotateImage90(image);

  Tool.printArray(image);
 }

 public static void rotateImage90(int[][] im) {

  // rotate the matrix in place, clock wise direction of 90 degree
  int numRow = im.length;
  int numCol = im[1].length;

  // check they are square matrix
  if (numRow != numCol) {
   System.out.println("not square matrix");
  }
  if (numRow == 0) { // actually, this could be ignored.
   System.out.println("no elements");
  }
  int imSize = numRow;
  if (imSize % 2 == 1) {
   // if imSize is odd number, rotate from the most inner circle ( of
   // size 1*1)
   int centerIndex = (int) (numRow / 2) + 1; // in math, this is the
              // center point.
   centerIndex = centerIndex - 1; // because java starts array index
           // from zero, we need minus 1
   int radius = (int) (numRow / 2);
   for (int d = 1; d <= radius; d++) {
    // there are four lines per circle. we rotate them
    // one-by-one
    int lineLength = 2 * d;
    int[] tmpLine = new int[lineLength];
    // save the line above to tempArray
    for (int i = -d + 1; i <= d; i++)
     // ignore the left most vertex
     tmpLine[i - (-d + 1)] = im[centerIndex - d][centerIndex + i];

    // copy left to above
    for (int i = -d + 1; i <= d; i++)
     im[centerIndex - d][centerIndex + i] = im[centerIndex - i][centerIndex
       - d];

    // copy below to left
    for (int i = -d + 1; i <= d; i++)
     im[centerIndex - i][centerIndex - d] = im[centerIndex + d][centerIndex
       - i];

    // copy right to below
    for (int i = -d + 1; i <= d; i++)
     im[centerIndex + d][centerIndex - i] = im[centerIndex + i][centerIndex
       + d];

    // copy original above(now in tmpLine) to right
    for (int i = -d + 1; i <= d; i++)
     im[centerIndex + i][centerIndex + d] = tmpLine[i - (-d + 1)];
   }
  } else { // imSize is even number, i.e. , imSize == 2, 4 , 6, 8....
   int indexLeftTop = (int) (imSize / 2) - 1;
   int indexRightBottom = (int) (imSize / 2);
   int radius = (int) (imSize / 2);
   // because by considering
   System.out.println("we are working on the array, sized == "
     + imSize);
   for (int d = 1; d <= radius; d++) { // for each layer,with distance
            // to center is d
    int lineLength = indexRightBottom - indexLeftTop;
    int tmpLine[] = new int[lineLength];
    // save the above circle into the tmpLine ( do not include the
    // topLeft corner
    for (int i = 1; i <= lineLength; i++) {
     tmpLine[i - 1] = im[indexLeftTop][indexLeftTop + i];
    }
    // transfer the left into above
    for (int i = 1; i <= lineLength; i++) {
     im[indexLeftTop][indexLeftTop + i] = im[indexRightBottom
       - i][indexLeftTop];
    }
    // transfer the bottom into left
    for (int i = 1; i <= lineLength; i++) {
     im[indexRightBottom - i][indexLeftTop] = im[indexRightBottom][indexRightBottom
       - i];
    }

    // transfer the right into the bottom
    for (int i = 1; i <= lineLength; i++) {
     im[indexRightBottom][indexRightBottom - i] = im[indexLeftTop
       + i][indexRightBottom];
    }

    // transfer the saved,original above line into the right
    for (int i = 1; i <= lineLength; i++) {
     im[indexLeftTop + i][indexRightBottom] = tmpLine[i - 1];
    }
    indexLeftTop--;
    indexRightBottom++;
   }// end of the for, for each layer, from inner most to the outer
    // most

  } // end of else, for the case that the length is even number
 } // end of function rotateImage90
}

Mistakes:
0：  FUCK！！！！！！！！！！！
因为在rotate完毕，要打印数组的时候，是直接从上面copy的两个for loop，其中，就包含了一行 image[i][j] 的初始化代码。。我日阿
        以后再copy代码的时候，一定要注意，先看看代码里都是什么。(即使是自己写 的）
 
1: 遇到数组溢出。 问题出在
int centerIndex = (int)(numRow/2) + 1;
        int radius =  (int)(numRow/2)+1;  //这里，的radius是从上面一行copy下来的。
而应该自己写， 就不会加上这个 1 了。----------哎，人生阿

2： 遇到数组问题，  毛病出在。

  自己作运算的时候， 都是按照数学里的start from 1, 来计算，安排的。
可是，java中是start from 0.   ------------>  刚开始的时候，还记得，但是，直接写index的时候，就忘了。

3：for odd number, for each line, to copy and rotate into another line, 应该记住，一条边，随说是包括两边顶点。 但rotate的时候，只需要一个顶点就够了

            for(int i = -d; i<=d;i++) ------------------------这是错误的
            for(int i = -d; i<d;i++) ------------------------这是正确的。

 4：对于数组
a b c
d e f
g h i

如果按照上面的rotate算法，[a; d] 应该是 取代[ b c ] 的位置。
而不是，[ d ; g] 取代 [a b]的位置。
因此：我的初始代码中

  int imSize  = numRow;
  // if imSize is odd number,  rotate from the most inner circle ( of size 1*1)
  int centerIndex = (int)(numRow/2) + 1;  // mathetically, this is the center point. 
  centerIndex = centerIndex -1;       // because java starts array index from zero, we need minus 1
  int radius =  (int)(numRow/2);
  for (int d = 1; d <= radius; d++){
   // there are four lines for each circle.  we just rotate them one-by-one
   int lineLength = 1+2*d;
   int[] tmpLine = new int[lineLength];
   // save the line above to tempArray
   for(int i = -d; i

是错误的， 是假设了[ d ; g] 取代 [a b]的位置。 5: 对于，矩形边是偶数的时候 ， 在rotate完了每一圈之后，  忘了update indexLeftTop 和indexRightBottom的值了。

1. Strings and Array ------ 一些简单的，常用的操作，放在一个Tool类里。

思想就是： 对于，例如， 实例化一个数组， 和打印出一个数组， 自己声明了一个常用的类。

public class Tool {

  static void printArray(int[][] arr){

  System.out.println();
  int row = arr.length;
  int col = arr[0].length;
  for (int i = 0; i < row; i++) {
   for (int j = 0; j < col; j++) {
    System.out.print(arr[i][j] + "\t");
   }
   System.out.println();
  }
 }

  static void randomInitializeArray(int[][] arr) {
  // TODO Auto-generated method stub
  int row = arr.length;
  int col = arr[0].length;
  for (int i = 0; i < row; i++) {
   for (int j = 0; j < col; j++) {
    arr[i][j] = (int) (Math.random() * 50);
   }
  }
 }
 
}

1.7----- set entire row and column as zeros if element is 0

Q:

Write an algorithm such that if an element in an MxN matrix is 0, its entire row
and column are set to 0

A：
using two index array to remember which row(column ) would be set to zeros.

public class code1_1 {
public class code1_1 {

 public static void main(String[] args) {

  // String str = " 234o;908aslfjz";
  int M = 8;
  int N = 7;
  int[][] arr = new int[M][N];
  initializeArray(arr);
  // print out the array.
  for (int i = 0; i < M; i++) {
   for (int j = 0; j < N; j++) {
    System.out.print(arr[i][j] + "\t");
   }
   System.out.println();
  }

  checkAndSetZero(arr);
  System.out.println();
  System.out.println();
  // print out the array.
  for (int i = 0; i < M; i++) {
   for (int j = 0; j < N; j++) {
    System.out.print(arr[i][j] + "\t");
   }
   System.out.println();
  }
 }

 private static void checkAndSetZero(int[][] array) {
  int row = array.length;
  int col = array[0].length;
  int[] rowIndex = new int[row];
  int[] colIndex = new int[col];
  // check zero, and set indexes
  for (int i = 0; i < row; i++) {
   for (int j = 0; j < col; j++) {
    if (array[i][j] == 0) {
     rowIndex[i] = 1;
     colIndex[j] = 1;
    }
   }
  }
  // set the rows into 0s, if rowIndex is zeros
  for (int i = 0; i < row; i++) {
   if (rowIndex[i] != 0) {
    // change the whole row as zero
    for (int j = 0; j < col; j++) {
     array[i][j] = 0;
    }
   }
  }
  // set the col into 0s, if colIndex is zeros
  for (int j = 0; j < col; j++) {
   if (colIndex[j] != 0) {
    // change the whole row as zero
    for (int i = 0; i < row; i++) {
     array[i][j] = 0;
    }
   }
  }
 }

 private static void initializeArray(int[][] arr) {
  // TODO Auto-generated method stub
  int row = arr.length;
  int col = arr[0].length;
  for (int i = 0; i < row; i++) {
   for (int j = 0; j < col; j++) {
    arr[i][j] = (int) (Math.random() * 50);
   }
  }
 }

}

Mistakes:

 Learned:
Use two index array