剑指offer阅读（一）

<h1>数据结构</h1>

<h2>面试题二： 数组</h2>

<blockquote>
数组是一种最简单的数据结构，占据一块连续的数据结构并按照顺序存储数据。创建数组时，我们需要首先指定数组的容量大小，然后根据大小分配内存。
数组的空间利用效率很低，经常会有空闲的区域没有得到充分利用。因为数组中的内存是连续的，因此，他的时间效率很高，可以根据这个优点来实现简单的哈希表，使用数组下标作为哈希表的key，使用下标赌赢的值作为value，这样实现了键值和值的配对。有了这样的哈希表，就可以在O(1)实现查找。
</blockquote>

为了解决数组空间效率不高的问题，人们又实现了多种动态数组。

例：
c++中的STL的vector，为了避免浪费，先为数组开辟较小的空间，然后往数组中添加数据，这样，当数据的数目超过数组的容量时，我们再重新分配一块更大的空间，然后把之前的数据复制到新的数组中，然后把之前的内存释放掉。

<pre><code>int GetSize(int data[]){
return sizeof(data);
}

int _tmain(int argc,_TCHAR* argv[]){
int data1[] = {1,2,3,4,5};
int size1 = sizeof(data1);

int* data2 = data1;
int size2 = sizeof(data2);

int size3 = GETSize(data1);

printf("%d,%d,%d",size1,size2,size3);

}
</code></pre>

答案是“20，4，4”

一个整数是4字节，在C／C++中，当数组作为参数被传递时，它就会退化成指针，所以也占4字节。

<h2>面试题三：二维数组的查找</h2>

<blockquote>
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
</blockquote>

<pre><code><br />bool Find(int* matrix,int rows,int columns,int number){
bool found = false;

if(matrix != NULL && rows > 0 && columns >0){
    int row = 0;
    int column = columns - 1;
    while(row<rows&&column >= 0){
        if(matrix[row * columns +column]==nulber){
            found = true;
            break;
        }else if(matrix[row * columns + column] > number)
            --column;
        else 
            ++ row;
    }
}

}
</code></pre>

<pre><code class="Java"> private static boolean find(int[][] m, int target) {
boolean result = false;
if (m != null){
int lie = m[0].length-1;
for (int i = m[0].length-1;i > 0;i--){
if (m[0][i]<=target){
lie = i;
break;
}
}
for (int i = 0;i<m.length-1;i++){
if (m[i][lie]==target){
result = true;
}
}

    }
    return result;
}

</code></pre>

<h2>面试题四:替换空格</h2>

字符串

Java中对象作为参数传递时，是把对象在内存中的地址拷贝了一份传给了参数。

参数的值就是对该对象的引用，而不是对象的内容。

<ol>
<li>先遍历一次字符串，得出空格的个数，计算出替换后的字符串长度</li>
<li>准备两个指针P1和P2，P1指向原始字符串的末尾，P2指向替换之后的字符串的末尾</li>
<li>向前移动P1，逐个复制到P2的位置，直到遇到空格，在P2之前插入“%20”</li>
<li>直到P1和P2指向同一位置，表明所有空格都已替换完毕。</li>
<li>所有的字符都只复制1次，复杂度为O(n)</li>
</ol>

<pre><code class="java"><br />void ReplaceBlank(char string[],int length){
if(string == null||length <= 0){
return;
}
/originalLength为字符串string的实际长度/
int originalLength = 0;
int numberOfBlank = 0;
int i = 0;
while(string[i]!='\0'){
++ originalLength;
if(string[i] == ' '){
++ numberOfBlank;
}
++ i;
}
／newLength为把空格替换为'%20'的长度／
int newLength = originalLength + numberOfBlank * 2;
if(newLength > length)
return;
int indexOfOriginal = originalLength;
int indexOfNew = newLength;
while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal){
if(string[indexOfOriginal] == ' '){
string[indexOfNew --] = '0';
string[indexOfNew --] = '2';
string[indexOfNew --] = '%';
}else{
string[indexOfNew --] = string[indexOfOriginal];
}
-- indexOfOriginal;
}
}

</code></pre>

<h2>面试题五：从尾到头打印链表</h2>

<blockquote>
链表是一种动态的数据结构
</blockquote>

<pre><code class="cpp">//单向链表
struct ListNode{
int m+nvalue;
ListNode* m_pNext;
}
</code></pre>

<pre><code class="cpp">//pHead是一个只想指针的指针，当我们往一个空链表中差入一个节点时，新插入的节点就是链表的头指针，当我们往一个空链表中插入一个节点时，新插入的节点就是链表的头指针。此时会改变头指针，因此必须把pHead射程为指向指针的指针。
void addToTail(ListNode** pHead,int value){
ListNode* pNew = new ListNode();
pNew->m_nvalue = value;
pNew->m_pNext = NULL;
if(*pHead){
pHead = pNew;
}else{
ListNode pNode = *pHead;
while(pNode->m_pNext != NULL){
pNode = pNode->m_pNext;
}
pNode->m_pNext = pNew;
}
}
</code></pre>

<pre><code>//在链表中找到某值并删除
void RemoveNode(ListNode** pHead,int value){
if(pHead == NULL||*pHead == NULL)
return;

ListNode* pToBeDeleted = NULL;
if((*pHead)->m_nValue==value){
    pToBeDeleted = *pHead;
    *pHead = (*pHead)->m_pNext;
}else{
    ListNode* pNode = *pHead;
    while(pNode->m_pNext !=NULL&&pNode->m_pNext->m_nValue!=value){
        pNode = pNode->m_pNext;
    }
    if(pNode->m_pNext != NULL && pNode->m_pNext->m_nValue == value){
        pToBeDeleted = pNode->m_pNext;
        pNode -> pNode->m_pNext->m_pNext;
    }
}
if(pToBeDeleted != NULL){
    delete pToBeDeleted;
    pToBeDeleted = NULL;
 }

}

</code></pre>

<blockquote>
输入一个链表的头节点，从尾到头打印出每个节点的值
</blockquote>

<pre><code><br />struct ListNode{
int m_nKey;
ListNode* m_pNext;
}
</code></pre>

<pre><code><br />public static void getList(LinkedList<Integer> list) {
if (list == null)
return;
Stack<Integer> stack = new Stack<>();
while (!list.isEmpty()) {
Integer i = list.getFirst();
stack.push(i);
list.removeFirst();
}
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
</code></pre>

<h2>面试题六：重建二叉树</h2>

遍历：

<ul>
<li>前序遍历 先访问根节点，再访问左子节点，最后访问右子节点</li>
<li>中序遍历 先访问左子节点，再访问根节点，最后访问右子节点</li>
<li>后序遍历 先访问左子节点，再访问右节点，最后访问根子节点</li>
</ul>

<pre><code class="java"><br />class TreeNode<T> {
private T data;
private TreeNode<T> leftNode;
private TreeNode<T> rightNode;

    public TreeNode(T data, TreeNode<T> leftNode, TreeNode<T> rightNode) {  
        this.data = data;  
        this.leftNode = leftNode;  
        this.rightNode = rightNode;  
    }  


    public T getData() {  
        return data;  
    }  

    public void setData(T data) {  
        this.data = data;  
    }  

    public TreeNode<T> getLeftNode() {  
        return leftNode;  
    }  

    public void setLeftNode(TreeNode<T> leftNode) {  
        this.leftNode = leftNode;  
    }  

    public TreeNode<T> getRightNode() {  
        return rightNode;  
    }  

    public void setRightNode(TreeNode<T> rightNode) {  
        this.rightNode = rightNode;  
    }  

}  

</code></pre>

前序遍历

<h4>递归</h4>

<pre><code class="java">public void preIterator(TreeNode<String> node){
this.printNode(node);
if(node.getLeftNode()!=null){
this.preIterator(node.getLeftNode());
}
if(node.getRightNode()!=null){
this.preIterator(node.getRightNode());
}
}
</code></pre>

<h4>非递归</h4>

<pre><code class="java">public void preIterator2（TreeNode<String> node）{
Stack<TreeNode<String>> stack = new Stack();
if(node!=null){
stack.push(node);
while(!stack.isEmpty()){
node = stack.pop();
this.printNode(node);
if(node.getRight()!=null)
stack.push(p.getRight());
if(node.getLeft()!=null)
stack.push(p.getLeft());
}
}
}
</code></pre>

<h3>中序遍历</h3>

<h4>递归</h4>

<pre><code class="java">public void midleIterator(TreeNode<String> node){
if(node.getLeftNode!=null){
this.midleIterator(node.getLeftNode);
}
this.printNode(node);
if(node.getRightNode!=null){
this.midleIterator(node.getRightNode);
}
}
</code></pre>

<h4>非递归</h4>

<pre><code class="java">protected static void midleIterator(TreeNode node){
Stack<TreeNode> stack = new Stack();
while(node!=null||stack.size()>0){
while(node!=null){
stack.push(node);
node = node.getLeft();
}
if(stack.size()>0){
node = stack.pop();
this.printNode(node);
node = node.getRight();
}
}
}

</code></pre>

<h3>后序遍历</h3>

<h4>递归</h4>

<pre><code class="java">public void lastIterator(TreeNode<String> node){
if(node.getLeftNode()!=null){
this.printNode(node.getLeftNode());
}
if(node.getRightNode()!=null){
this.printNode(node.getRightNode());
}
this.printNode(node);
}
</code></pre>

<h4>非递归</h4>

<pre><code class="java">public static void lastIterator(TreeNode node){
Stack<TreeNode> stack = new Stack();
while(node!=null||!stack.isEmpty()){
while(node!=null){
stack.push(node);
node = stack.pop();
}
if(!stack.isEmpty()){
Node temp = stack.peek().getRight();
if(temp == null || temp == prev){
node = stack.pop();
this.printNode(node);
prev = node;
node = null;
}else{
node = temp;
}
}
}
}

</code></pre>