2022-10-28

字数统计: 3.7k字 | 阅读时长: 17分

剑指offer

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int,int> mp;
        for(int i=0; i<nums.size(); i++){
            if(mp.find(nums[i]) != mp.end()) return nums[i];
            else mp[nums[i]] ++;
        }
        return -1;
    }
};

剑指 Offer 04. 二维数组中的查找 - 力扣（LeetCode）

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

和之前的leetcode hot100题一样，从右向左，从上向下遍历

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

剑指 Offer 05. 替换空格 - 力扣（LeetCode）

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

class Solution {
public:
    string replaceSpace(string s) {
        int oldsize = s.size();
        int space = 0;
        for(int i = 0; i < oldsize; i++) {
            if(s[i] == ' ') {
                space++;
            }
        }
        int newsize = oldsize + 2 * space;
        s.resize(newsize);
        //双指针
        for(int i = oldsize - 1, j = newsize - 1; i <= j, i >=0, j >= 0; i--, j--) {
            if(s[i] != ' ') {
                s[j] = s[i];
            }
            else {
                s[j - 2] = '%';
                s[j - 1] = '2';
                s[j] = '0';
                j = j - 2;
            }
        }
        return s;
    }
};

剑指 Offer 06. 从尾到头打印链表 - 力扣（LeetCode）

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

由于栈有先进后出的特性，考虑用栈实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        //借用一个栈实现
        stack <int> st;
        ListNode* temp = head;
        while(temp != NULL) {
            st.push(temp->val);
            temp = temp->next;
        }
        vector <int> result;
        while(!st.empty()) {
            result.push_back(st.top());
            st.pop();
        }
        return result;
    }
};

剑指 Offer 09. 用两个栈实现队列 - 力扣（LeetCode）

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

class CQueue {
private:
    stack <int> st1;
    stack <int> st2;
public:
    CQueue() {
    }
    
    void appendTail(int value) {
        st1.push(value);
    }
    
    int deleteHead() {
        if(!st2.empty())     //注意如果s2非空先拿s2里的，
        {
            int a=st2.top();
            st2.pop();
            return a;
        }
        if(st1.empty())  return -1;
        while(!st1.empty())
          {
                st2.push(st1.top());
                st1.pop();
                
          }
          int b = st2.top();
          st2.pop();
          return b;
    }
};

/**
 * 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. 斐波那契数列 - 力扣（LeetCode）

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

使用动态规划的思想，比递归效率更高，不需要重复计算。

class Solution {
public:
    int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        int dp[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            dp[i] = dp[i] % 1000000007;
        }
        return dp[n];
    }
};

剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣（LeetCode）

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

实际上与前面的斐波那契数列一样

//dp数组表示登上第i个台阶有多少种走法
class Solution {
public:
    int numWays(int n) {
        if(n == 0) return 1;
        if(n == 1) return 1;
        if(n == 2) return 2;
        int dp[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            dp[i] = dp[i] % 1000000007;
        }
        return dp[n];
    }
};

剑指 Offer 11. 旋转数组的最小数字 - 力扣（LeetCode）

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在重复元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

考虑[1, 3, 3, 3, 3, 4, 5]的情况，变形后变成[3, 3, 3, 3, 4, 5, 1]或者[4, 5, 1, 3, 3, 3, 3]

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int i = 0;
        int j = numbers.size() - 1;
        while(i < j) {
            int mid = (i + j) / 2;
            if(numbers[mid] > numbers[j]) {
                i = mid + 1;
            }
            else if(numbers[mid] < numbers[j]) {
                j = mid;
            }
            else j--;
        }
        return numbers[i];      //最后返回numbers[i]和numbers[j]都可以，都是相等的
    }
};

剑指 Offer 12. 矩阵中的路径 - 力扣（LeetCode）

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

深度优先的思想

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++) {
                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';        //标注一下，说明本轮循环board[i][j]已经访问过
        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];      //一次循环完成，需要将 board[i][j]恢复
        return res;
    }
};

剑指 Offer 14- I. 剪绳子 - 力扣（LeetCode）

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

动态规划的思想：dp[i]表示长度为i的绳子的最大乘积

//dp[i]表示长度为i的绳子的最大乘积
class Solution {
public:
    int cuttingRope(int n) {
        vector <int> dp(n + 1);
        for(int i = 2; i <= n; i++) {
            for(int j = 1; j <= i - 1; j++) {
                dp[i] = max(dp[i] , max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
};

剑指 Offer 14- II. 剪绳子 II - 力扣（LeetCode）

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

dp方法不行了，只能用数值解法，实际上将所有的数都尽可能拆成3乘积最大。

//dp[i]表示长度为i的绳子的最大乘积
class Solution {
public:
int cuttingRope(int n) {
    if(n<2) return 0;
    if(n<4) return n-1;
    long maxNum=1,mod = 1000000007;
    while(n>4){
        maxNum*=3;
        maxNum %=mod;
        n-=3;
    }
    maxNum*=n;
    maxNum %=mod;
    return maxNum;
    }
};

剑指 Offer 15. 二进制中1的个数 - 力扣（LeetCode）

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量).）。

n & 1 == 1即n最右边一位为1.

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while(n != 0) {
            if(n & 1 == 1) res++;
            n = n >> 1;
        }
        return res;
    }
};

剑指 Offer 16. 数值的整数次方 - 力扣（LeetCode）

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

class Solution {
public:
    double myPow(double x, long n) {
        double res = 1;
        if(n < 0) {
            x = 1 / x;
            n = n * -1;
        }
        if(n == 0) {
            return 1;
        }
        
        if(x == 1) {
            return 1;
        }
        
        while(n != 0) {
                if(n & 1 == 1) {		//如果是奇数，就单独乘一个x
                    res = res * x;
                }
                x = x * x;
                n = n >> 1;
            }
        return res;
    }
};

剑指 Offer 17. 打印从1到最大的n位数 - 力扣（LeetCode）

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

class Solution {
public:
    vector<int> printNumbers(int n) {
        long long num = pow(10, n) - 1;
        vector <int> result;
        for(int i = 1, j = 0; i <= num; i++, j++) {
            result.push_back(i);
        }
        return result;
    }
};

另一种方法：回溯

class Solution {
public:
    vector<int> res;
    void backTrack(const int &digits, int numIndex, string &num) {
        if (numIndex == digits) {
            res.push_back(stoi(num));
            return;
        }

        for (int i = 0; i <= 9; ++i) {
            num.push_back(i + '0');
            backTrack(digits, numIndex + 1, num);
            num.pop_back();
        }
    }
public:
    vector<int> printNumbers(int n) {
        // 考虑大数的全排列 回溯生成
        res.clear();
        for (int i = 1; i <= n; ++i) {  // 数据位数遍历
            for (int j = 1; j <= 9; ++j) {  // 首位选择 1-9
                string number(1, j + '0');	//代表number是1个j字符
                backTrack(i, 1, number);
            }
        }
        return res;
    }
};

剑指 Offer 18. 删除链表的节点 - 力扣（LeetCode）

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode* dummynode = new ListNode(0);
        dummynode->next = head;
        ListNode* cur = head;
        ListNode* pre = dummynode;
        while(cur != NULL) {
            if(cur->val == val) {
                pre->next = cur->next;
            }
            pre = pre->next;
            cur = cur->next;
        }
        return dummynode->next;
    }
};

剑指 Offer 19. 正则表达式匹配 - 力扣（LeetCode）

请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。

class Solution {
public:
    bool isMatch(string s, string p) {
        s=" "+s;//防止该案例：""\n"c*"
        p=" "+p;
        int m=s.size(),n=p.size();
        bool dp[m+1][n+1];
        memset(dp,false,(m+1)*(n+1));
        dp[0][0]=true;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s[i-1]==p[j-1] || p[j-1]=='.'){
                    dp[i][j]=dp[i-1][j-1];
                }
                else if(p[j-1]=='*'){
                    if(s[i-1]!=p[j-2] && p[j-2]!='.')   //直接去除*
                        dp[i][j]=dp[i][j-2];
                    else{
                        dp[i][j]=dp[i][j-1] || dp[i][j-2] || dp[i-1][j];    //dp[i][j-1]对应*匹配一次，dp[i-1][j]对应*匹配多次，dp[i][j-2]对应*不匹配

                    }
                }
            }
        }
        return dp[m][n];
    }
};

剑指 Offer 20. 表示数值的字符串 - 力扣（LeetCode）

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：

有限状态机的思想，小数点前后有没有数字都行，e前后必须有数字。

class Solution {
private:
    // 整数的格式可以用[+|-]B表示, 其中B为无符号整数
    bool scanInteger(const string s, int& index){

        if(s[index] == '+' || s[index] == '-')
            ++index;

        return scanUnsignedInteger(s, index);
    }
    
    bool scanUnsignedInteger(const string s, int& index){

        int befor = index;
        while(index != s.size() && s[index] >= '0' && s[index] <= '9')
            index ++;

        return index > befor;
    }
public:
    // 数字的格式可以用A[.[B]][e|EC]或者.B[e|EC]表示，
    // 其中A和C都是整数（可以有正负号，也可以没有），而B是一个无符号整数
    bool isNumber(string s) {

        if(s.size() == 0)
            return false;
        int index = 0;

        //字符串开始有空格，可以返回true
        while(s[index] == ' ')  //书中代码没有该项测试
            ++index;

        bool numeric = scanInteger(s, index);

        // 如果出现'.'，接下来是数字的小数部分
        if(s[index] == '.'){

            ++index;

            // 下面一行代码用||的原因：
            // 1. 小数可以没有整数部分，例如.123等于0.123；
            // 2. 小数点后面可以没有数字，例如233.等于233.0；
            // 3. 当然小数点前面和后面可以有数字，例如233.666
            numeric = scanUnsignedInteger(s, index) || numeric; //scanUnsignedInteger(s, index)代表小数点后面是整数，numeric代表小数点前面是整数
        }

        // 如果出现'e'或者'E'，接下来跟着的是数字的指数部分
        if(s[index] == 'e' || s[index] == 'E'){

            ++index;

            // 下面一行代码用&&的原因：
            // 1. 当e或E前面没有数字时，整个字符串不能表示数字，例如.e1、e1；
            // 2. 当e或E后面没有整数时，整个字符串不能表示数字，例如12e、12e+5.4
            numeric = numeric && scanInteger(s ,index);     //e的前面和后面都要有整数
        }

        //字符串结尾有空格，可以返回true
        while(s[index] == ' ')
            ++index;
        cout << s.size() << " " << index;   //调试用

        return numeric && index == s.size();
    }
};

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode）

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

双指针的思想，从前向后遍历偶数和从后向前遍历的奇数互换。

//双指针
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int i = 0, j = nums.size() - 1;
        while(i < j) {
            while(i < j && (nums[i] & 1) == 1) i++;
            while(i < j && (nums[j] & 1) == 0) j--;
            swap(nums[i], nums[j]);
        }
        return nums;
    }
};