復習一下<程序員面試攻略>,并記錄一些心得.

鏈表:
1. 找到單鏈表中倒數第m個元素
方法：使用兩個指針，這兩個指針相距m個元素，然后使得兩個指針同步前進，當后一個指針到空時，前一個指針即為倒數第m個元素
實現：
elem* FindMToLastElem(elem* head, int m)
{
    elem* current, mbehind;
    current = head;
    for(int i=0; i<m; i++)
    {
        if(current->next)
        {
            current = current->next;
        }
        else
        {
            return NULL;
        }
    }
    
    mbehind = head;
    while(current->next)
    {
        current = current->next;
        mbehind = mbehind->next;
    }

    return mbehind;
}

2. 判斷一個鏈表為循環鏈表還是非循環鏈表

方法：使用快慢指針，快指針每次走兩步，慢指針每次走一步，若快指針到達NULL，則為非循環鏈表，若快指針超過了慢指針，則為循環鏈表
實現：
int determin_termination(node* head)
{
    node* fast, slow;
    if(!head || !(head->next))
    {
        return 0;
    }
    fast = head->next->next;
    slow = head->next;
    while(1)
    {
        if(!fast || !(fast->next))
        {
            return 0;
        }
        else if(fast == slow || fast->next == slow)
        {
            return 1;
        }
        else
        {
            fast = fast->next->next;
            slow = slow->next;
        }
    }
}

樹和圖:
1. 二叉樹前序遍歷的非遞歸算法
方法：使用堆棧
實現：
void PreorderTraversal(node* head)
{
    elem* stack;
    CreateStack(&stack);
    Push(&stack, head);
    
    node* pNode;
    while(Pop(&stack, &pNode)
    {
        if(NULL != pNode)
        {
            printf("%d\n", pNode->value);
            Push(&stack, pNode->right);
            Push(&stack, pNode->left);
        }
    }
    DeleteStack(&stack);
}

數組和字符串:
1. 高效刪除特定字符
方法：每次刪除字符時不在數組中移動字符串，而是直接拷貝到之前掃描過的位置中。另外采用數組來減少字符串比較次數。
void RemoveChars(char str[], char remove[])
{
    // create an array for remove characters
    char removeArray[256];
    for(int i=0; i<256; i++)
    {
        removeArray[i] = 0;
    }
    int src = 0;
    while(remove[src])
    {
        removeArray[remove[src]] = 1;
        src++;
    }
    int dest = 0;
    src = 0;
    do
    {
        if(!removeArray[remove[src]])
        {
            str[dest++] = str[src];
        }
    }while(str[src++]);
    
}

2. 顛倒單詞出現的次序
Do or do not, there is no try. 轉換為 try. no is there not, do or Do
方法：先將整個字符串顛倒，再將新字符串中的每個單詞顛倒

3. 編寫字符串和數字相互轉換函數
int Str2Int(char* str)
{
    int num = 0, neg = 1, i = 0;
    if(str[0] == '-')
    {
        neg = -1;
        i = 1;
    }
    
    while(str[i])
    {
        num = num * 10 + str[i++] - '0';
    }
    num = num * neg;
    return num;
}

void Int2Str(int num, char str[])
{
    int neg = 1;
    if(num < 0)
    {
        num *= -1;
        neg = -1;
    }
    
    int i = 0;
    do
    {
        str[i++] = num % 10 + '0';
        num = num / 10;
    }while(num)

    if(neg == -1)
    {
        str[i++] = '-';
    }
    str[i] = 0;
    
    for(int j = 0; j < i/2; j++)
    {
        str[j] = str[i-1-j];
    }
    
}