<h1>數(shù)據(jù)結(jié)構(gòu)</h1>
<h2>面試題二： 數(shù)組</h2>
<blockquote>
數(shù)組是一種最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，占據(jù)一塊連續(xù)的數(shù)據(jù)結(jié)構(gòu)并按照順序存儲(chǔ)數(shù)據(jù)棍掐。創(chuàng)建數(shù)組時(shí)阵赠，我們需要首先指定數(shù)組的容量大小，然后根據(jù)大小分配內(nèi)存鹤啡。
數(shù)組的空間利用效率很低惯驼，經(jīng)常會(huì)有空閑的區(qū)域沒有得到充分利用。因?yàn)閿?shù)組中的內(nèi)存是連續(xù)的递瑰，因此祟牲，他的時(shí)間效率很高，可以根據(jù)這個(gè)優(yōu)點(diǎn)來實(shí)現(xiàn)簡(jiǎn)單的哈希表抖部，使用數(shù)組下標(biāo)作為哈希表的key说贝，使用下標(biāo)賭贏的值作為value，這樣實(shí)現(xiàn)了鍵值和值的配對(duì)慎颗。有了這樣的哈希表乡恕，就可以在O(1)實(shí)現(xiàn)查找。
</blockquote>
為了解決數(shù)組空間效率不高的問題俯萎，人們又實(shí)現(xiàn)了多種動(dòng)態(tài)數(shù)組傲宜。
例：
c++中的STL的vector，為了避免浪費(fèi)夫啊，先為數(shù)組開辟較小的空間函卒，然后往數(shù)組中添加數(shù)據(jù)，這樣撇眯，當(dāng)數(shù)據(jù)的數(shù)目超過數(shù)組的容量時(shí)报嵌，我們?cè)僦匦路峙湟粔K更大的空間，然后把之前的數(shù)據(jù)復(fù)制到新的數(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”
一個(gè)整數(shù)是4字節(jié)跷叉，在C／C++中，當(dāng)數(shù)組作為參數(shù)被傳遞時(shí)，它就會(huì)退化成指針云挟，所以也占4字節(jié)梆砸。
<h2>面試題三：二維數(shù)組的查找</h2>
<blockquote>
在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序园欣，每一列都按照從上到下遞增的順序排序帖世。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)沸枯，判斷數(shù)組中是否含有該整數(shù)日矫。
</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中對(duì)象作為參數(shù)傳遞時(shí)，是把對(duì)象在內(nèi)存中的地址拷貝了一份傳給了參數(shù)绑榴。
參數(shù)的值就是對(duì)該對(duì)象的引用哪轿，而不是對(duì)象的內(nèi)容。
<ol>
<li>先遍歷一次字符串翔怎，得出空格的個(gè)數(shù)窃诉，計(jì)算出替換后的字符串長(zhǎng)度</li>
<li>準(zhǔn)備兩個(gè)指針P1和P2，P1指向原始字符串的末尾赤套，P2指向替換之后的字符串的末尾</li>
<li>向前移動(dòng)P1飘痛，逐個(gè)復(fù)制到P2的位置，直到遇到空格容握，在P2之前插入“%20”</li>
<li>直到P1和P2指向同一位置宣脉，表明所有空格都已替換完畢。</li>
<li>所有的字符都只復(fù)制1次剔氏，復(fù)雜度為O(n)</li>
</ol>
<pre><code class="java"><br />void ReplaceBlank(char string[],int length){
if(string == null||length <= 0){
return;
}
/originalLength為字符串string的實(shí)際長(zhǎng)度/
int originalLength = 0;
int numberOfBlank = 0;
int i = 0;
while(string[i]!='\0'){
++ originalLength;
if(string[i] == ' '){
++ numberOfBlank;
}
++ i;
}
／newLength為把空格替換為'%20'的長(zhǎng)度／
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>
鏈表是一種動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)
</blockquote>
<pre><code class="cpp">//單向鏈表
struct ListNode{
int m+nvalue;
ListNode* m_pNext;
}
</code></pre>
<pre><code class="cpp">//pHead是一個(gè)只想指針的指針塑猖，當(dāng)我們往一個(gè)空鏈表中差入一個(gè)節(jié)點(diǎn)時(shí)，新插入的節(jié)點(diǎn)就是鏈表的頭指針谈跛，當(dāng)我們往一個(gè)空鏈表中插入一個(gè)節(jié)點(diǎn)時(shí)萌庆，新插入的節(jié)點(diǎn)就是鏈表的頭指針。此時(shí)會(huì)改變頭指針币旧，因此必須把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>
輸入一個(gè)鏈表的頭節(jié)點(diǎn)猿妈，從尾到頭打印出每個(gè)節(jié)點(diǎn)的值
</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é)點(diǎn)吹菱，再訪問左子節(jié)點(diǎn)，最后訪問右子節(jié)點(diǎn)</li>
<li>中序遍歷 先訪問左子節(jié)點(diǎn)彭则，再訪問根節(jié)點(diǎn)鳍刷，最后訪問右子節(jié)點(diǎn)</li>
<li>后序遍歷 先訪問左子節(jié)點(diǎn)，再訪問右節(jié)點(diǎn)俯抖，最后訪問根子節(jié)點(diǎn)</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>
