剑指offer笔记

た入场券 2023-07-13 03:46 15阅读 0赞

### 面试题3 数组中的查找 ###

对于这道题来说，书上的和LeetCode上的是不一样的。

在LeetCode上，是一位数组中判断是否有重复数字，有的话任意返回一个就行。这个思路也有两个：

1.先用一个排序如快排O(nlogn)，然后就判断相邻元素是否相等，若相等直接返回即可。

2.用一个集合set，遍历数组放进去，因为集合有唯一性，若哪个在添加的时候，添加失败，说明这个已经在集合中了，就意味着重复。需要注意的是set没有push\_back。

class Solution {
    public:
        int findRepeatNumber(vector<int>& nums) {
            unordered_set<int> hset ;
            for(int num: nums) {
                if(hset.find(num) != hset.end()) {
                    return num;
                }
                else{
                    hset.insert(num);
                }
            }
            return 0;
        }
    };

3.因为数组里的数字都在0 - n-1之间，令每个数字对应到下标，最后如果得到nums\[i\] == nums\[nums\[i\]\]即出现重复值。

class Solution {
    public:
        int findRepeatNumber(vector<int>& nums) {
            for(int i = 0; i < nums.size(); ++i) {
                while(i != nums[i]) {
                    if(nums[i] == nums[nums[i]])
                        return nums[i];
                    swap(nums[i], nums[nums[i]]);
                }
            }
            return 0;
        }
    };

在书上是在二维数组中查找，对应LeetCode上的面试题4，且数组是满足从左到右，从上到下递增的，然后给定一个数，判断这个数是否在数组中。这个的解法不好想到，首先从右上角的数字开始，将其与给定的数比较，若大于给定数，说明这一列的数都大于，删除这一列即可；小于则删除这一行，以此类推即可。C++代码如下：

class Solution {
    public:
        bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
            if (matrix.size() == 0){
                return false;
            }
            int m = matrix.size();
            int n = matrix[0].size();
            int row = m - 1;
            int col = 0;
            while (row >=0 && col < n){
                if(matrix[row][col] < target){
                    col += 1;
                }
                else if(matrix[row][col] > target){
                    row -= 1;
                }
                else{
                    return true;
                }
            }
            return false;
        }
    };

注意是size()，还有m和n的表示方法，还有matrix\[row\]\[col\]这个表示方法。

### 面试题4 替换空格（LeetCode的面试题5） ###

此题是让把字符串中的所有空格替换成"%20"。遇到此题，首先考虑的是：

1.  字符串变长了，原来的内存是否能放下？假设能放下，内存足够。

思路一是从前到后遍历替换，遇到空格就换。但后果是后面的字符每次都要移动，O(n^2)。

思路二是从后向前遍历替换，O（n），先遍历一遍，得知有多少个空格，则新字符串就为源字符串数加上2倍的空格数，书上代码：

class Solution {
    public:
        string replaceSpace(string s,int length) {
            if (s.size() == nullptr && length <= 0) return; //这一行有问题，不知道怎么改
            int originalLength = 0;
            int numberOfBlank = 0;
            int i = 0;
            while(s[i] = '\0'){
                ++ originalLength;
                if(s[i] == ' ')
                    ++ numberOfBlank;
                ++i;
            }
            int newLength = originalLength + numberOfBlank;
            if (newLength > length) return ;
            int indexOfOriginal = originalLength;
            int indexOfNew = newLength;
            while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal){
                if(s[indexOfOriginal]== ' '){
                    s[indexOfNew --] = '0';
                    s[indexOfNew --] = '2';
                    s[indexOfNew --] = '%';
                }
                else
                    s[indexOfNew --] = s[indexOfOriginal];
                -- indexOfOriginal;
            }
        }
    };

其实还有更简单的代码（清清楚楚）：

class Solution {
    public:
        string replaceSpace(string s) {
            string res;
            for(auto c : s){
                if(c == ' ')
                    res += "%20";
                else
                    res += c;
            }
            return res;
        }
    };

### 面试题五 从尾到头打印链表 ###

题目描述很直接，没什么需要注意的。

方法一 ：使用栈，因为栈有现进后出的性质，先将元素压入栈中，再弹出，就实现了反转。时间和空间都是O(N)。

class Solution {
    public:
        vector<int> res;
        vector<int> reversePrint(ListNode* head) {
            stack<int> st;
            while(head){// push
                st.push(head->val);
                head = head->next;
            }
            while(!st.empty()){ // pop
                res.push_back(st.top());
                st.pop();
            }
            return res;
        }
    };

方法二：使用递归，时间和空间都是O(n)。

class Solution {
    public:
        vector<int> res;
        vector<int> reversePrint(ListNode* head) {
            if (!head) return res;        //递归终止条件
            reversePrint(head->next);
            res.push_back(head->val);
            return res;
        }
    };

方法三：从头到尾打印链表到数组中，返回反转后的结果即可。时间和空间都是O(N)。

class Solution {
    public:
        vector<int> reversePrint(ListNode* head) {
            vector<int> res;
            while (head){
                res.push_back(head->val);
                head = head->next;
            }
            reverse(res.begin(), res.end());
            return res;
        }
    };

### 面试题6 重建二叉树 ###

这道题是给出前序遍历和中序遍历的结果，要求重建出二叉树。首先，前序是（根左右），中序是（左右根）。

先找到preorder中的起始元素作为根节点，在inorder中找到根节点的索引mid；那么，前序中第一个是根节点，preorder\[1:mid + 1\]为左子树，preorder\[mid + 1:\]为右子树；中序中，inorder\[0:mid\]为左子树，mid为根节点，inorder\[mid + 1:\]为右子树。递归建立二叉树。

下面这个做法真巧妙。

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            if(preorder.size() == 0 || inorder.size() == 0) return NULL;
            TreeNode* treeNode = new TreeNode(preorder[0]); //根节点？
            int mid = distance(begin(inorder),find(inorder.begin(),inorder.end(),preorder[0]));//这个怎么用？
            //distance() 函数用于计算两个迭代器表示的范围内包含元素的个数
            //find(起始位置，终止位置，要查的值)
            vector<int> left_pre(preorder.begin() + 1,preorder.begin() + mid + 1);//前序的左子树
            vector<int> right_pre(preorder.begin() + mid + 1,preorder.end());//前序的右子树
            vector<int> left_in(inorder.begin(),inorder.begin() + mid);//中序的左子树
            vector<int> right_in(inorder.begin() + mid + 1,inorder.end());//中序的右子树
    
            treeNode -> left = buildTree(left_pre,left_in);
            treeNode -> right = buildTree(right_pre,right_in);
            return treeNode;
    
        }
    };

用中序和后序重建二叉树：程序会溢出

class Solution {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            if(inorder.size() == 0 || postorder.size() == 0) return NULL;
            TreeNode* treeNode = new TreeNode(postorder[-1]); //根节点？
            int mid = distance(begin(inorder),find(inorder.begin(),inorder.end(),postorder[-1]));
            
            vector<int> left_in(inorder.begin(),inorder.begin() + mid);
            vector<int> right_in(inorder.begin() + mid + 1,inorder.end());
            vector<int> left_post(postorder.begin(),postorder.begin() + mid);
            vector<int> right_post(postorder.begin() + mid,postorder.end() -1);
    
            treeNode -> left = buildTree(left_in,left_post);
            treeNode -> right = buildTree(right_in,right_post);
            return treeNode;
    
        }
    };