题目列表

https://www.nowcoder.com/ta/coding-interviews

JZ3 数组中重复的数字

时间空间复杂度都为\(O(n)\)，直接建一个数组a，初始化全0，出现数i就a[i]++

    int duplicate(vector<int>& numbers) {
        const int N = 10005;
        vector<int> count(N, 0);
        for(int i = 0; i < numbers.size(); i ++){
            count[numbers[i]] ++;
        }
        for(int i = 0; i < count.size(); i ++){
            if(count[i] > 1){
                return i;
            }
        }
        return -1;
    }

JZ4 二维数组中的查找

由题：二维数组从左到右从上到下递增，则a[i][j]是该元素到右下角的矩阵里最小的元素
为了控制不走回头路，从右上方或者左下方的元素开始。
从右上方开始：target < a[i][j]， target在该列左边
target > a[i][j]， target在该行下方
如果超出了矩阵范围还没找到，说明没有这个数。

    bool Find(int target, vector<vector<int> > array) {
        int row = array.size() - 1;
        int col = array[0].size() - 1;
        if(array.empty() || array[0].empty()) return false;
        int i = 0, j = col;
        while(i <= row && j >= 0){
            if(target > array[i][j])
                i ++;
            else if(target < array[i][j])
                j --;
            else{
                return true;
            }
        }
        return false;
    }

JZ5 替换空格

复习了一下string的用法
既可以用str[i]直接遍历，也可以用iterator遍历，改字符可以用string.insert
注意string.append用法

//s[i]写法
    string replaceSpace(string s) {
        // write code here
        for(int i = 0; i < s.size(); i ++){
            if(s[i] == ' '){
                s[i] = '%';
                s.insert(i + 1, "20");
            }
        }
        return s;
    }
//iterator写法
    string replaceSpace(string s) {
        // write code here
        int length = s.length();
        string ans = "";
        string::iterator iter = s.begin();
        for(; iter < s.end(); iter ++){
            if(*iter == ' ')
                ans.append("%20");
            else {
                ans.append(iter, iter + 1);
            }
        }
        return ans;
    }

JZ6 从尾到头打印链表

vector逆序写法
反向迭代器：rbegin()指向最后一个元素，rend()指向第一个元素前面的位置

    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        ListNode* l;
        l = head;
        while(l != nullptr){
            res.push_back(l -> val);
            l = l -> next;
        }
        return vector<int>(res.rbegin(), res.rend());
    }

JZ7 重建二叉树

用递归做，根据前序遍历序列的第一个数（当前根节点）把中序遍历分成左右子树，根据左右子树序列的长度，分出左右子树的前序遍历序列，对左右子树进行递归，返回值分别为当前root的left和right

    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.empty() || vin.empty()) return NULL;
        TreeNode *treenode = new TreeNode(pre[0]);
        int l = distance(vin.begin(), find(vin.begin(), vin.end(), pre[0]));
        vector<int> pre1(pre.begin() + 1, pre.begin() + l + 1);
        vector<int> pre2(pre.begin() + l + 1, pre.end());
        vector<int> vin1(vin.begin(), vin.begin() + l);
        vector<int> vin2(vin.begin() + l + 1, vin.end());
        treenode -> left = reConstructBinaryTree(pre1, vin1);
        treenode -> right = reConstructBinaryTree(pre2, vin2);

        return treenode;
    }

JZ8 二叉树的下一个结点

分类讨论：1. 没有右子树，返回寻找父节点，如果当前节点是父节点的右儿子，就继续向上寻找父节点，直到当前节点是父节点的左儿子。如果无父节点返回null
2.有右子树，找右子树中最左边的节点。
段错误一发，原因是分类讨论1时，找父节点忘记判断父节点是否存在

    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        TreeLinkNode* node;
        if(pNode == nullptr) return NULL;
        if(pNode -> right == nullptr){
            if(pNode -> next == nullptr) return NULL;
            node = pNode->next;
            while(node->right == pNode){
                pNode = node;
                if(node->next == nullptr) return NULL;
                node = node->next;
            }
            return node;
        }
        else{
            node = pNode->right;
            while(node->left != nullptr){
                node = node->left;
            }
            return node;
        }
    }