算法训练2

1、请实现一个函数，把字符串中的每个空格替换成“%20”，例如，输入“we are happy”，则输出“we%20are%20happy”。

/********************** 字符串 **********************/
#include <string.h>
#include <stdlib.h>
void replaceBlank(char string[]) {
    int length = (int)strlen(string);
    int i = 0, blankNum = 0;
    while (string[i] != '\0') {
        if (string[i] == ' ') {
            blankNum ++;
        }
        i++;
    }
    int newLength = length + blankNum * 2;
    printf("%d,%d\n",blankNum,newLength);
    if (newLength > length) {
        char *newString = realloc(string, newLength);
        if (newString == NULL) {
            return;
        }else{
            string = newString;
        }
    }
    int index_new = newLength, index_old = length;
    while (index_new > index_old && index_old >= 0) {
        //从后往前走
        if (string[index_old] != ' ') {
            string[index_new--] = string[index_old];
        }else{
            string[index_new--] = '0';
            string[index_new--] = '2';
            string[index_new--] = '%';
        }
        index_old --;
    }
}
/********************** 字符串 **********************/
int main(int argc, const char * argv[]) {
    char *str = (char *)malloc(18);
    strcpy(str, "hello world happy.");
    replaceBlank(str);
    printf("str替换后的结果为：%s\n",str);
    return 0;
}

思路如下： 字符串.png

2、输入一个链表的头结点，从尾到头反过来打印出每个节点的值。

利用栈的先进后出原则，做以下操作。

/********************** 链表-栈 **********************/
struct ListNode {
    int m_nKey;
    struct ListNode *m_pNext;
};   //链表
void PrintListNode(struct ListNode *pHead) {
    std::stack<ListNode *> nodes;
    ListNode *pNode = pHead;
    while (pNode != NULL) {
        nodes.push(pNode);  //入栈操作
        pNode = pNode -> m_pNext;
    }
    while (!nodes.enpty()) {
        pNode = nodes.top();
        printf("%d\t",pNode -> m_nKey);     //打印栈顶
        nodes.pop();    //出栈操作
    }
}
/********************** 链表-栈 **********************/

因为栈的本质是递归，所以，我们也可以利用递归进行操作。

/********************** 链表-递归 **********************/
struct ListNode {
    int m_nKey;
    struct ListNode *m_pNext;
};
void PrintListNode(struct ListNode *pHead) {
    if (pHead != NULL) {
        if (pHead -> m_pNext != NULL) {
            PrintListNode(pHead -> m_pNext);
        }
        printf("%d\t",pHead -> m_nKey);
    }
}
//缺点：当链表很长的时候，调用层级太深，从而导致调用函数栈溢出。
/********************** 链表-递归 **********************/

3、给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。

思路：假设要删除I结点，找到I结点的下一个结点J，将J的内容复制给I，将I的m_pNext指向J，然后删除J。
有两个特殊情况，1、删除的I结点是链表的尾结点，需要从头到尾循环找到前结点，将前结点的m_pNext指向NULL; 2、链表只有一个结点，即I结点，删除I结点后，将链表头部结点指向NULL

/********************** 链表 **********************/
struct ListNode {
    int m_nKey;
    struct ListNode *m_pNext;
};   //链表

void deleteNode(struct ListNode **pListHead, struct ListNode *pToBeDelete) {
    if (pListHead == NULL || pToBeDelete == NULL) {
        return;
    }
    //要删除的结点在链表中间
    if (pToBeDelete -> m_pNext != NULL) {
        struct ListNode *node = pToBeDelete -> m_pNext;
        pToBeDelete -> m_nKey = node -> m_nKey;
        pToBeDelete -> m_pNext = node -> m_pNext;
        delete node;
        node = NULL;
    }
    //链表中只有一个结点的时候，删除I结点后，将链表头部结点指向NULL
    else if (*pListHead == pToBeDelete) {
        delete pToBeDelete;
        pToBeDelete = NULL;
        *pListHead = NULL;
    }
    //要删除的结点在链表尾部,需要从头到尾循环找到前结点，将前结点的m_pNext指向NULL
    else {
        struct ListNode *node = *pListHead;
        while (node -> m_pNext != pToBeDelete) {
            node = node -> m_pNext;
        }
        node -> m_pNext = NULL;
        delete pToBeDelete;
        pToBeDelete = NULL;
    }
}
/********************** 链表 **********************/