劍指offer閱讀（一）

<h1>數(shù)據(jù)結構</h1>

<h2>面試題二： 數(shù)組</h2>

<blockquote>
數(shù)組是一種最簡單的數(shù)據(jù)結構，占據(jù)一塊連續(xù)的數(shù)據(jù)結構并按照順序存儲數(shù)據(jù)。創(chuàng)建數(shù)組時，我們需要首先指定數(shù)組的容量大小，然后根據(jù)大小分配內(nèi)存。
數(shù)組的空間利用效率很低，經(jīng)常會有空閑的區(qū)域沒有得到充分利用。因為數(shù)組中的內(nèi)存是連續(xù)的，因此，他的時間效率很高，可以根據(jù)這個優(yōu)點來實現(xiàn)簡單的哈希表，使用數(shù)組下標作為哈希表的key，使用下標賭贏的值作為value，這樣實現(xiàn)了鍵值和值的配對。有了這樣的哈希表，就可以在O(1)實現(xiàn)查找。
</blockquote>

為了解決數(shù)組空間效率不高的問題，人們又實現(xiàn)了多種動態(tài)數(shù)組。

例：
c++中的STL的vector，為了避免浪費，先為數(shù)組開辟較小的空間，然后往數(shù)組中添加數(shù)據(jù)，這樣，當數(shù)據(jù)的數(shù)目超過數(shù)組的容量時，我們再重新分配一塊更大的空間，然后把之前的數(shù)據(jù)復制到新的數(shù)組中，然后把之前的內(nèi)存釋放掉。

<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”

一個整數(shù)是4字節(jié)，在C／C++中，當數(shù)組作為參數(shù)被傳遞時，它就會退化成指針，所以也占4字節(jié)。

<h2>面試題三：二維數(shù)組的查找</h2>

<blockquote>
在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
</blockquote>

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

if(matrix != NULL &amp;&amp; rows &gt; 0 &amp;&amp; columns &gt;0){
    int row = 0;
    int column = columns - 1;
    while(row&lt;rows&amp;&amp;column &gt;= 0){
        if(matrix[row * columns +column]==nulber){
            found = true;
            break;
        }else if(matrix[row * columns + column] &gt; 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中對象作為參數(shù)傳遞時，是把對象在內(nèi)存中的地址拷貝了一份傳給了參數(shù)。

參數(shù)的值就是對該對象的引用，而不是對象的內(nèi)容。

<ol>
<li>先遍歷一次字符串，得出空格的個數(shù)，計算出替換后的字符串長度</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>
鏈表是一種動態(tài)的數(shù)據(jù)結構
</blockquote>

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

<pre><code class="cpp">//pHead是一個只想指針的指針，當我們往一個空鏈表中差入一個節(jié)點時，新插入的節(jié)點就是鏈表的頭指針，當我們往一個空鏈表中插入一個節(jié)點時，新插入的節(jié)點就是鏈表的頭指針。此時會改變頭指針，因此必須把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)-&gt;m_nValue==value){
    pToBeDeleted = *pHead;
    *pHead = (*pHead)-&gt;m_pNext;
}else{
    ListNode* pNode = *pHead;
    while(pNode-&gt;m_pNext !=NULL&amp;&amp;pNode-&gt;m_pNext-&gt;m_nValue!=value){
        pNode = pNode-&gt;m_pNext;
    }
    if(pNode-&gt;m_pNext != NULL &amp;&amp; pNode-&gt;m_pNext-&gt;m_nValue == value){
        pToBeDeleted = pNode-&gt;m_pNext;
        pNode -&gt; pNode-&gt;m_pNext-&gt;m_pNext;
    }
}
if(pToBeDeleted != NULL){
    delete pToBeDeleted;
    pToBeDeleted = NULL;
 }

}

</code></pre>

<blockquote>
輸入一個鏈表的頭節(jié)點，從尾到頭打印出每個節(jié)點的值
</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>前序遍歷 先訪問根節(jié)點，再訪問左子節(jié)點，最后訪問右子節(jié)點</li>
<li>中序遍歷 先訪問左子節(jié)點，再訪問根節(jié)點，最后訪問右子節(jié)點</li>
<li>后序遍歷 先訪問左子節(jié)點，再訪問右節(jié)點，最后訪問根子節(jié)點</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&lt;T&gt; leftNode, TreeNode&lt;T&gt; 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&lt;T&gt; getLeftNode() {  
        return leftNode;  
    }  

    public void setLeftNode(TreeNode&lt;T&gt; leftNode) {  
        this.leftNode = leftNode;  
    }  

    public TreeNode&lt;T&gt; getRightNode() {  
        return rightNode;  
    }  

    public void setRightNode(TreeNode&lt;T&gt; 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>

最后編輯于 ：
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容