#暑期实习剑指offer记录 c++

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

image-20230225215409756

  • 题解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
    public:
        int findRepeatNumber(vector<int>& nums) {
           int n = nums.size();
           for(int i = 0; i < n; i++){
               while(i != nums[i] && nums[nums[i]] != nums[i])
                    swap(nums[i], nums[nums[i]]);
                //一个标号一个坑，nums做自己的map数组
                if(i != nums[i] && nums[nums[i]] == nums[i]) return nums[i];
           }
           return -1;
        }
    };

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

image-20230225211938838

  • 题解1：

    image-20230226111011800 image-20230226111040716 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    //target<右上角，右上角的列都比target大;
    //target>右上角,右上角的行都比target小
    class Solution {
    public:
        bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
            if(matrix.empty() || matrix[0].empty()) return false;
            //从右上角往左下角走
            int i = 0, j = matrix[0].size() - 1; 
            while(i < matrix.size() && j >= 0){
                if(target == matrix[i][j]) return true;
                if(target < matrix[i][j]) j--; 
                else i++;
            }
            return false;
        }
    };

  • 题解2：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    //逐行进行二分查找
    class Solution {
    public:
        bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
            if(matrix.empty() || matrix[0].empty()) return false;
            for(int i = 0; i < matrix.size(); i ++){
                int l = 0, r = matrix[0].size() - 1;
                while(l <= r){
                    int mid = (l + r) / 2;
                    if(matrix[i][mid] == target) return true;
                    else if(matrix[i][mid] > target) r = mid - 1;
                    else l = mid + 1;
                }
            }
            return false;


        }
    };

剑指 Offer 05 替换空格

image-20230225213115528

  • 题解：开一个新string，从前往后遍历，遇到新空格 后面加”%20” 否则补原来正常字符串

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution {
    public:
        string replaceSpace(string s) {
            string tmp;
            for(int i = 0; i < s.size(); i ++){
                if(s[i]==' ') tmp +=  "%20";
                else tmp += s[i];
            }
             return tmp;
        }
    };

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

image-20230225213614660

  • 题解：用数组从头到尾遍历，最后反转数组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution {
    public:
        vector<int> reversePrint(ListNode* head) {
            vector<int> ans;
            while(head != NULL) ans.push_back(head -> val), head = head -> next;
            reverse(ans.begin(), ans.end());
            return ans;
        }
    };

剑指 Offer 07. 重建二叉树

image-20230225220019609

  • 题解：

    • image-20230226110735081
    • 先根据先序遍历找出根节点3，中序遍历中根节点左边数的在根的左边[9]，根节点右边数的在根的右边[15, 50, 7]；
    • 递归 左子树[9] 和 右子树[15, 50, 7]，先序遍历找根节点.. 中序遍历 根节点左和右为其左子树和右子树
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    //递归+哈希表(需要快速找出中序遍历里根节点的位置)
    /**
     * 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:
        vector<int> preorder;
        unordered_map<int, int> dic;// 标记中序遍历
        TreeNode* recur(int root, int left, int right) { 
            if(left > right) return nullptr; /// 相等的话就是自己，递归终止
            TreeNode* node = new TreeNode(preorder[root]);  //建立根节点
            //根节点在中序遍历 inorder 中的索引i, 划分根节点、左子树 右子树
            int i = dic[preorder[root]];
            node->left = recur(root + 1, left, i - 1);              // 开启左子树递归
            node->right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
            return node;                                            // 回溯返回根节点
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            this->preorder = preorder;
             //将中序遍历的值及索引放在map中，方便递归时获取左子树与右子树的数量及其根的索引
            for(int i = 0; i < inorder.size(); i++) dic[inorder[i]] = i;
            return recur(0, 0, inorder.size() - 1); 
            //当前根的的索引,递归树的左边界/数组左边界,递归树的右边界/数组右边界
        }
    };

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

image-20230226113854594

  • 题解：出队栈和入队栈，入队栈无条件入栈，出队栈如果为空则从入队栈压入元素后再删除

    0b0a3a6e3c08ca8b403ad55522a6711 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    class CQueue {
    public:
        stack<int> stack1,stack2;
        CQueue() {
        }
        //队列尾部插入整数
        void appendTail(int value) {
            stack1.push(value);
        }
        //队列头部删除整数(若队列中没有元素，deleteHead 操作返回 -1 )
        //出队操作需要优先检查出队栈是否有数据，若无，需要从入队栈倒入后再操作。
        int deleteHead() {
            if(stack2.empty()){
                //优先检查出队栈是否有数据，若无，需要从入队栈倒入后再操作
                while(!stack1.empty()){
                    stack2.push(stack1.top());
                    stack1.pop();
                }
            } 
            //把入队栈元素已压入出队栈元素中 入队栈stk1已空
            if(stack2.empty()) return -1; //两个栈均为空
            else{
                //出队栈不空，执行删除元素操作
                int tmp = stack2.top();
                stack2.pop();
                return tmp;
            }
        }
    };

    /**
     * Your CQueue object will be instantiated and called as such:
     * CQueue* obj = new CQueue();
     * obj->appendTail(value);
     * int param_2 = obj->deleteHead();
     */

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

  • 题解1：递归 超时

    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution {
    public:
        const int MOD = 1e9+7;
        int fib(int n) {
            if(n == 0) return 0;
            if(n == 1) return 1;
            return (fib(n-1) + fib(n-2)) % MOD;
        }
    };

  • 题解2：仅记录前两项的值f(n-2) f(n-1)即可

    12651b24d1ec60b0e9c6f01d41e2193 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution {
    public:
        const int MOD = 1e9 + 7;
        int fib(int n) {
            int a = 0, b = 1;
            while(n--){
                int c = (a + b) % MOD;//求下一项
                a = b % MOD, b = c % MOD; //a:f(n-2), b:f(n-1) 
            }
            return a % MOD;
        }
    };

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

image-20230226140050001

  • 题解：和斐波那契数列一样，但初始条件 改为a =1,b=1

    c3db6aeb320d2771d550d19c9887716 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution {
    public:
        const int MOD = 1e9 + 7;
        int numWays(int n) {
            int a = 1, b = 1;
            while(n--){
                int c = (a + b) % MOD;
                a = b % MOD, b = c % MOD;
            }
            return a % MOD;
        }
    };

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

image-20230226141343884

  • 题解1：for循环比较前后两个数

    697f3d5bc39372cfb69b18141a0412d 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution {
    public:
        int minArray(vector<int>& numbers) {
            for(int i = 0; i < numbers.size() - 1; i ++){
                if(numbers[i] > numbers[i + 1]) return numbers[i + 1];
            }
            return numbers[0];
        }
    };

  • 题解2：二分出来 第一个比第一个元素小的数，就是目标值 及最小值

    image-20230226142955555旋转之前 单调递增→旋转之后，部分单增 image-20230226143016020

    发现假如去除后面重复元素，则 第一个比nums[0]小的数，就是目标值 及最小值image-20230226143538138

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
        int minArray(vector<int>& numbers) {
            int n = numbers.size() - 1;
            while(n > 0 && numbers[n] == numbers[0]) n--;     //去掉后面重复元素 
            if( numbers[n] >= numbers[0] ) return numbers[0]; //只有前面单增的部分
            // 二分：第一个比第一个元素小的数，就是目标值 及最小值
            int l = 0, r = n;
            while(l < r){
                int mid = (l + r) >> 1;
                if(numbers[mid] < numbers[0] ) r = mid;       //[l,mid] [mid+1,r]
                else l = mid + 1;
            }
            return numbers[r];
        }
    };

剑指 Offer 12. 矩阵中的路径

image-20230226161208584

  • 题解：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    //经典搜索问题：枚举所有可能的路径，如果存在字符串返回true 不存在返回False
    //如何枚举所有路径？ 枚举起点 再枚举方向至无路可走
    class Solution {
    public:
        bool exist(vector<vector<char>>& board, string word) {
            rows = board.size();
            cols = board[0].size();
            for(int i = 0; i < rows; i ++) {
                for(int j = 0; j < cols; j ++) {
                    //第0个字符串开始枚举 起点坐标是所有(i,j)
                    if(dfs(board, word, i, j, 0)) return true;
                }
            }
            return false;
        }
    private:
        int rows, cols;
        bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {
            if(i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false; //超边界
            if(k == word.size() - 1) return true;
            board[i][j] = '\0';
            bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1); //四个方向
            board[i][j] = word[k];
            return res;
        }
    };

剑指 Offer 14- I. 剪绳子

image-20230226174450194

  • 题解：分成尽可能多的3，剩下的数分成2

    image-20230226173856445

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // 一个整数划分为若干个正整数的和，使切出来的若干个正整数的乘积最大 
    // N%3==0 拆成多个3; N%3==1 拆成2个2和多个3; N%3==2 1个2和多个3
    class Solution {
    public:
        int cuttingRope(int n) {
            if( n <= 3) return 1 * (n - 1); //特判 边界
            int res = 0, count3 = n / 3;
            if(n % 3 == 0) return pow(3, count3);
            else if( n % 3 == 1) return pow(3, --count3) * 4;
            else return pow(3, count3) * 2;
        }
    };

剑指 Offer 14- II. 剪绳子 II

image-20230226180806392

  • 题解：分成尽可能多的3，剩下的数分成2

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution {
        public:
        const int N = 1e9+7;
        int cuttingRope(int n) {
            if( n <= 3) return 1 * (n - 1);
            else if(n == 4) return n;
            long res = 1;
            while(n > 4){
                res *= 3;
                res %= N;
                n -= 3;
            }
            return (int) (res * n % N);
        }
    };

剑指 Offer 15. 二进制中1的个数

image-20230226201121172

  • 题解：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //正数的补码和原码相同，负数的补码为反码+1
    class Solution {
    public:
        int hammingWeight(uint32_t n) {
            int s = 0;
            while(n) s += n & 1, n = n >> 1;
            //每次比较个位 如果是1 s++,如果不是i不加；取完之后右移一位 把个位删掉
            return s;
        }
    };

剑指 Offer 16. 数值的整数次方

image-20230226204704647

  • 题解：n是偶数 res=res*x*x，是奇数： res=res*x 。假如n是负数 结果为其倒数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        double myPow(double x, int n) {
            long long m = n; //n = -2^31，没法用abs取绝对值 用一个longlong类型变量接收n，再取abs
            m = abs(m);
            if(x == 1) return x;
            double res = 1.0;
            while (m){ 
                ///该数二进制的最后一位是0的话那么就为偶数。是1的话就为奇数
                if (m & 1) res = res * x;  
                x = x * x;
                m = m >> 1;
            }
            if (n < 0) res = 1 / res;
            return res;
        }
    };

剑指 Offer 17. 打印从1到最大的n位数

image-20230226205716377

  • 题解1：for循环打印输出

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution {
    public:
        vector<int> printNumbers(int n) {
            int max = pow(10, n) - 1;
            vector<int> ans;
            for(int i = 0; i < max; i ++){
                ans.push_back(i + 1);
            }
            return ans;
        }
    };

  • 题解2：用STL库函数解决。 定义在 numeric 头文件中的 iota() 函数模板会用连续的 T 类型值填充序列。前两个参数是定义序列的正向迭代器，第三个参数是初始的 T 值。第三个指定的值会被保存到序列的第一个元素中。保存在第一个元素后的值是通过对前面的值运用自增运算符得到的。

    1
    2
    3
    4
    5
    6
    7
    8
    class Solution {
    public:
        vector<int> printNumbers(int n) {
            vector<int> ans(pow(10, n) - 1, 0); //初始化具有10^n-1个0的vector
            iota(ans.begin(), ans.end(), 1); //iota() 是用来批量递增赋值vector的元素
            return ans;
        }
    };

剑指 Offer 18. 删除链表的节点

image-20230226210715384

  • 题解：

    1