Your Site Title

剑指offer

 
  • Jan 26, 2021

数据结构

数组

剑指 Offer 03. 数组中重复的数字

使用辅助空间记录对应数字是否出现

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        vector<bool> log(nums.size());
        for(int& val : nums){
            if(log[val]) return val;
            log[val] = true;
        }
        return -1;
    }
};

不使用辅助空间；二分，统计子数组中每个数字在原数组中出现的总次数，如果大于长度，说明有重复数字

剑指 Offer 04. 二维数组中的查找

如果从右上角出发，这个数是所在行最大的数，所在列最小的数，因此通过比较就能排除一行或者一列

如果从左上角出发，这个数是所在行列最小的数，因此不知道排除啥

另，右上角出发可以看出一颗二分搜索树

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

字符串

剑指 Offer 05. 替换空格

原地置换，提前计算位移量从后往前复制

class Solution {
public:
    string replaceSpace(string s) {
        int cnt=0, size = s.size();
        for(char& c : s) if(c == ' ') cnt++;
        int newsize = size + cnt*2;
        s.resize(newsize);
        int i=size-1, j=newsize-1;
        while(i != j){
            while(s[i] != ' ') s[j--]=s[i--];
            s[j--]='0'; s[j--]='2';s[j--]='%';
            i--;
        }
        return s;
    }
};

链表

剑指 Offer 06. 从尾到头打印链表

用户栈

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        stack<int> s;
        while(head){
            s.push(head->val);
            head = head->next;
        }
        vector<int> res(s.size());
        for(int i=0; i<res.size(); i++){
            res[i] = s.top(); s.pop();
        }

        return res;
    }
};

递归

class Solution {
public:
    void print(ListNode* head, vector<int>& res){
        if(!head) return;
        print(head->next, res);
        res.push_back(head->val);
    }
    vector<int> reversePrint(ListNode* head) {
        vector<int> res;
        print(head, res);
        return res;
    }
};

树

剑指 Offer 07. 重建二叉树

分别记录前序和中序子树的起始下标和长度

class Solution {
public:
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int l1, int l2, int len){
        if(len < 1) return NULL;
        int val = preorder[l1], root;
        for(int i=l2; i<l2+len; i++)
            if(inorder[i]==val) 
                root=i;
        TreeNode *cur = new TreeNode(val);
        int newLen = root-l2;
        cur->left  = build(preorder, inorder, l1+1, l2, newLen);
        cur->right = build(preorder, inorder, l1+1+newLen, root+1, l2+len-root-1);
        return cur;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder, inorder, 0, 0, preorder.size());
    }
};/* 57% **/

使用Hash减少用于搜索根节点的耗时

map<int, int> rootHash;
for(int i=0; i<inorder.size(); i++) rootHash[inorder[i]] = i;
int val = preorder[l1], root = rootHash[val];
/* 81.8% **/

栈和队列

剑指 Offer 09. 用两个栈实现队列

一个管进一个管出，出的没了就找进的要

class CQueue {
    stack<int> _in, _out;
public:
    CQueue() {}
    
    void appendTail(int value) {
        _in.push(value);
    }
    
    int deleteHead() {
        int t=-1;
        if(_out.size() > 0){
            t = _out.top(); _out.pop();
        }else if(_in.size() > 0){
            while(!_in.empty()){
                _out.push(_in.top()); _in.pop();
            }
            t = deleteHead();
        }
        return t;
    }
};

另：用两个队列模拟栈，可以计数，出栈时将n-1个元素放到另一个栈，剩下的一个就是出栈元素

算法和数据操作

递归和循环

剑指 Offer 10- I. 斐波那契数列

分类：数学

class Solution {
public:
    int fib(int n) {
        if(n < 2) return n;
        int a=0, b=1, c;
        while(n-->=2) {
            c = (a+b)%(1e9+7);
            a=b;
            b=c;
        }
        return c;
    }
};

or

int fib(int n) {
    if(n<2) return n;
    int a=0, b=1;
    for(int i=1; i<n; i++){
        b = a+b;
        a = b-a;
        b = b%1000000007;
    }
    return b;
}

另解，矩阵公式

剑指 Offer 10- II. 青蛙跳台阶问题

分类：数学

f(0)=1, f(1)=1, f(n)=f(n-1)+f(n-2);

class Solution {
public:
    int numWays(int n) {
        if(n < 2) return 1;
        int a=1, b=1, c;
        while(n-->=2){
            c = (a+b)%1000000007;
            a = b;
            b = c;
        }
        return c;
    }
};

查找和排序

剑指 Offer 11. 旋转数组的最小数字

特例：

  • 顺序数组
  • l mid r指向的数字均相等，如 10111 11101 1131
class Solution {
public:
    int findInorder(vector<int>& numbers, int l, int r){
        int p = numbers[l];
        for(int i=l+1; i<=r; i++){
            p = min(p, numbers[i]);
        }
        return p;
    }
    int minArray(vector<int>& numbers) {
        int l=0, r=numbers.size()-1, mid = 0;
        if(numbers[l] < numbers[r]) return numbers[0];
        while(l+1 < r){
            mid = (l+r) >> 1;
            if(numbers[l] == numbers[mid] && numbers[mid] == numbers[r]){ //无法确定位置
                return findInorder(numbers, l, r);
            }else if(numbers[l] <= numbers[mid]){ //说明mid在较大数组中，则较小数组在mid右边
                l = mid; //最终指向较大数组的最后一个数
            }else if(numbers[mid] <= numbers[r]){ //说明mid在较小数组中，可进一步缩小较小数组的范围
                r = mid; //最终指向较小数组的第一个数
            }
        }
        return numbers[r];
    }
};
Search