《剑指Offer》之数据结构篇

1. 长度为n数组，数字在 0～n-1 范围内，找出数组中任意一个重复的数

O(n)

bool duplicate(int numbers[], int length, int* duplication) {
    if (numbers == nullptr || length <= 0) {
        return false;
    }
    
    for (int i = 0; i < length; ++i) {
        if (numbers[i] < 0 || numbers[i] >= length) {
            return false;
        }
    }
    
    for (int i = 0; i < length; ++i) {
        while (numbers[i] != i) {
            if (numbers[i] == numbers[numbers[i]]) {
                *duplication = numbers[i];
                return true;
            }
            int tmp = numbers[i];
            numbers[i] = numbers[tmp];
            numbers[tmp] = tmp;
        }
    }
    return false;
}

2. 不修改数组找出重复数字，长度为 n+1，范围 1～n

O(nlogn)

int countRange(const int* numbers, int lenght, int left, int mid) {
    int count = 0;
    for (int i = 0; i < lenght; ++i) {
        if (numbers[i] >= left && numbers[i] <= mid) {
            ++count;
        }
    }
    return count;
}

int getDuplication(const int* numbers, int length) {
    
    if (numbers == nullptr || length <= 0) {
        return -1;
    }
    int left = 1;
    int right = length - 1;
    
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        int count = countRange(numbers, length, left, mid);
        if (left == right) {
            if (count > 1) {
                return left;
            } else {
                break;
            }
        }
        if (count > (mid - left + 1)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

3. 一个从左到右从上到下递增的二维数组，判断是否含有某整数

bool Find(int* matrix, int rows, int columns, int number) {
    if (matrix == nullptr || rows <= 0 || columns <= 0) {
        return false;
    }
    int row = 0;
    int column = columns - 1;
    while (row < rows && column >= 0) {
        if (matrix[row * columns + column] == number) {
            return true;
        } else if (matrix[row * columns + column] > number) {
            -- column;
        } else {
            ++ row;
        }
    }
    return false;
}

4. 替换字符串中的空格为“%20”，在原字符串上替换，假设原字符串后面有足够的空间

O(n)

void ReplaceBlank(char string[], int length) {
    if (string == nullptr || length <= 0) {
        return;
    }
    
    int count = 0;
    int i = 0;
    while (string[i] != '\0') {
        if (string[i] == ' ') {
            ++ count;
        }
        ++ i;
    }
    int originLength = i;
    int newLength = originLength + count * 2;
    if (newLength > length) {
        return;
    }
    int originIndex = originLength;
    int newIndex = newLength;
    while (originLength >= 0 && newIndex > originIndex) {
        if (string[originIndex] == ' ') {
            string[newIndex--] = '0';
            string[newIndex--] = '2';
            string[newIndex--] = '%';
        } else {
            string[newIndex--] = string[originIndex];
        }
        -- originIndex;
    }
}

链表末尾添加节点

struct ListNode
{
    int value;
    ListNode* next;
};

void AddToTail(ListNode** pHead, int value) {
    ListNode* pNew = new ListNode();
    pNew->value = value;
    pNew->next = nullptr;
    
    if (*pHead == nullptr) {
        *pHead = pNew;
    } else {
        ListNode* pNode = *pHead;
        while (pNode->next != nullptr) {
            pNode = pNode->next;
        }
        pNode->next = pNew;
    }
}

在链表中找到第一个含有某值的节点并删除

void RemoveNode(ListNode** pHead, int value) {
    if (*pHead == nullptr || pHead == nullptr) {
        return;
    }
    ListNode* toBeDeleted = nullptr;
    if ((*pHead)->value == value) {
        toBeDeleted = *pHead;
        *pHead = (*pHead)->next;
    } else {
        ListNode* pNode = *pHead;
        while (pNode->next != nullptr && pNode->next->value != value) {
            pNode = pNode->next;
        }
        if (pNode->next != nullptr && pNode->next->value == value) {
            toBeDeleted = pNode->next;
            pNode->next = pNode->next->next;
        }
    }
    if (toBeDeleted != nullptr) {
        delete toBeDeleted;
        toBeDeleted = nullptr;
    }
}

5. 从尾到头打印链表，不得修改链表结构

栈

void PrintListReversingly_Iteratively(ListNode* pHead) {
    stack<ListNode*> nodes;
    
    ListNode* pNode = pHead;
    while (pNode != nullptr) {
        nodes.push(pNode);
        pNode = pNode->next;
    }
    while (!nodes.empty()) {
        pNode = nodes.top();
        printf("%d\t", pNode->value);
        nodes.pop();
    }
}

递归，可能导致函数调用栈溢出

void PrintListReversingly_Recursively(ListNode* pHead) {
    if (pHead != nullptr) {
        if (pHead->next != nullptr) {
            PrintListReversingly_Recursively(pHead->next);
        }
        printf("%d\t", pHead->value);
    }
    
}

6. 根据二叉树前序遍历和中序遍历的结果，重建该二叉树，假设不含重复数字

struct BinaryTreeNode {
    int value;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
};

BinaryTreeNode* Construct(int* preorder, int* inorder, int length) {
    if (preorder == nullptr || inorder == nullptr || length <= 0) {
        return nullptr;
    }
    return ConstructCore(preorder, preorder + length - 1, inorder, inorder + length - 1);
}

BinaryTreeNode* ConstructCore (int* startPreorder, int* endPreorder, int* startIorder, int* endInorder) {
    int rootValue = startPreorder[0];
    BinaryTreeNode* root = new BinaryTreeNode();
    root->value = rootValue;
    root->left = root->right = nullptr;
    if (startPreorder == endPreorder) {
        if (startIorder == endInorder && *startPreorder == *startIorder)
            return root;
        else
            throw exception();
    }
    int* rootInorder = startIorder;
    while (rootInorder <= endInorder && *rootInorder != rootValue) {
        ++rootInorder;
    }
    if (rootInorder == endInorder && *rootInorder != rootValue) {
        throw exception();
    }
    
    int leftLendth = rootInorder - startIorder;
    int* leftPreorderEnd = startPreorder + leftLendth;
    if (leftLendth > 0) {
        root->left = ConstructCore(startPreorder + 1, leftPreorderEnd, startIorder, rootInorder - 1);
    }
    if (leftLendth < endPreorder - startIorder) {
        root->right = ConstructCore(leftPreorderEnd + 1, endPreorder, rootInorder + 1, endInorder);
    }
    return root;
}

7. 给定一颗二叉树和其中一个节点，如何找出中序遍历序列的下一个节点，树中节点除了有两个分别指向左右子节点的指针，还有一个指向父节点的指针

struct BinaryTreeNode {
    int value;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode* parent;
};

BinaryTreeNode* GetNext(BinaryTreeNode* pNode) {
    if (pNode == nullptr) {
        return nullptr;
    }
    BinaryTreeNode* pNext = nullptr;
    if (pNode->right != nullptr) {
        pNext = pNode->right;
        while (pNext->left != nullptr) {
            pNext = pNext->left;
        }
    } else if (pNext->parent != nullptr) {
        BinaryTreeNode* current = pNode;
        BinaryTreeNode* parent = pNode->parent;
        while (parent != nullptr && current == parent->right) {
            current = parent;
            parent = parent->parent;
        }
        pNext = parent;
    }
    return pNext;
}

8. 用两个栈实现队列，实现 appendTail 和 deleteHead 函数

template <typename T> class CQueue {
public:
    CQueue(void);
    ~CQueue(void);
    
    void appendTail(const T& node);
    T deleteHead();

private:
    stack<T> stack1;
    stack<T> stack2;
};

template <typename T> void CQueue<T>::appendTail(const T& element)
{
    stack1.push(element);
}

template <typename T> T CQueue<T>::deleteHead() {
    if (stack2.size() <= 0) {
        while (stack1.size()) {
            stack2.push(stack1.top());
            stack1.pop();
        }
    }
    if (stack2.size() == 0) {
        throw new exception();
    }
    
    T head = stack2.top();
    stack2.pop();
    return head;
}