Category Archives: 剑指offer

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

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

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

示例 1:

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

说明:

  • 用返回一个整数列表来代替打印
  • n 为正整数

简单解法如下:

class Solution {
public:
    vector<int> printNumbers(int n) {
        vector<int> ans;
        int m = pow(10, n) - 1;
        for(int i = 1; i <= m; ++i) ans.push_back(i);
        return ans;
    }
};

本代码提交AC,用时12MS。

如果只是这么解的话,就太easy了。这题是要考察大数越界的问题,这就需要用到string来表示数字了,然后使用递归的方法求解,具体可以看题解: https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/mian-shi-ti-17-da-yin-cong-1-dao-zui-da-de-n-wei-2/

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

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

实现函数double Power(double base, int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。

注意:本题与主站 50 题相同:https://leetcode-cn.com/problems/powx-n/


实现函数pow(x,n),与LeetCode Pow(x, n)相同,快速幂。完整代码如下:

class Solution {
public:
    double myPow(double x, int n) {
        
        long long m = n;
        if(m < 0) m = -m;
        
        double ans = 1.0;
        while(m != 0) {
            if(m % 2 == 1) {
                ans *= x;
            }
            x *= x;
            m >>= 1;
        }
        if(n < 0) return 1.0 / ans;
        else return ans;
    }
};

本代码提交AC,用时0MS。

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

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

请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

示例 1:

输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

示例 2:

输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

示例 3:

输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。

注意:本题与主站 191 题相同:https://leetcode-cn.com/problems/number-of-1-bits/


统计无符号int的二进制中1的个数。简单题,n&(n-1)能把最后一个1消掉,直到为0。与LeetCode Number of 1 Bits相同,完整代码如下:

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

本代码提交AC,用时4MS。

剑指 Offer 14- II. 剪绳子 II

剑指 Offer 14- II. 剪绳子 II

给你一根长度为 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。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示:

  • 2 <= n <= 1000

注意:本题与主站 343 题相同:https://leetcode-cn.com/problems/integer-break/


本题是上一题(剑指 Offer 14- I. 剪绳子 LCOF)的升级版,即n的范围变大了,导致次方超过int和long long的范围,需要在求pow的过程中取mod。使用快速幂的方法,代码如下:

typedef long long LL;

class Solution {
private:
    LL FastPow(LL x, LL y) {
        LL ans = 1;
        while(y != 0) {
            if(y % 2 == 1) {
                ans = ans * x % 1000000007;
            }
            x = x * x % 1000000007;
            y >>= 1;
        }
        return ans % 1000000007;
    }
public:
    int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int m = n / 3;
        if(n % 3 == 0) {
            return FastPow(3, m) % 1000000007;
        } else if(n % 3 == 1) {
            return (FastPow(3, m - 1) % 1000000007) * 4 % 1000000007;
        } else {
            return (FastPow(3, m) % 1000000007) * 2 % 1000000007;
        }
    }
};

本代码提交AC,用时0MS。

剑指 Offer 14- I. 剪绳子 LCOF

剑指 Offer 14- I. 剪绳子 LCOF

给你一根长度为 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。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示:

2 <= n <= 58
注意:本题与主站 343 题相同:https://leetcode-cn.com/problems/integer-break/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/jian-sheng-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


给定一根长为n的绳子,剪成m段,使得m段长度的乘积最大。问最大乘积是多少。

看题解,把长度切分为3,乘积最大。需要用到算术几何平均不等式,以及求导求极值等数学知识。

完整代码如下:

class Solution {
public:
    int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int m = n / 3;
        if(n % 3 == 0) {
            return pow(3, m);
        } else if(n % 3 == 1) {
            return pow(3, m - 1) * 4;
        } else {
            return pow(3, m) * 2;
        }
    }
};

本代码提交AC,用时0MS。

另一个通用解法是DP,假设dp[i]是长度为i,切分之后的最大乘积。则对于dp[j],可以把[1,…,j]切分为[1,…,k]和[k+1,…,j],因为切分之后两段的长度都小于j,所以之前已经求解过了,可直接得到乘积。题解如下: https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/shu-xue-zhi-shi-he-dong-tai-gui-hua-liang-chong-fa/ 。完整代码如下:

class Solution {
public:
    int cuttingRope(int n) {
        vector<int> dp(n + 1, 0);
        dp[1] = 1;
        for(int i = 2; i <= n; ++i) {
            for(int j = 1; j < i; ++j) {
                dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]));
            }
        }
        return dp[n];
    }
};

本代码提交AC,用时4MS。

剑指 Offer 13. 机器人的运动范围

剑指 Offer 13. 机器人的运动范围

地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?

示例 1:

输入:m = 2, n = 3, k = 1
输出:3
示例 2:

输入:m = 3, n = 1, k = 0
输出:1
提示:

1 <= n,m <= 100
0 <= k <= 20

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


给定一个m*n的矩阵,要求从(0,0)开始移动,不能移动到坐标数字的位数之和超过k的位置,问最多有多少个可以走的格子。

简单的BFS的题,需要注意的是,BFS出队列的时候,检查一下这个点之前有没有被访问过。比如下图,最开始访问o点,然后会把a和b都进队列,接着a会把c进队列,但b也会把c进队列,导致c被进了两次,所以需要判断一下之前是否被访问。

oaxxx
bcxxx
xxxxx

完整代码如下:

struct Point {
    int x_, y_;
    Point(int x, int y) : x_(x), y_(y) {};
};

class Solution {
private:
    int SumDigits(int num) {
        int ans = 0;
        while(num != 0) {
            ans += (num % 10);
            num /= 10;
        }
        return ans;
    }
    bool IsValid(int x, int y, int k) {
        return SumDigits(x) + SumDigits(y) <= k;
    }
public:
    int movingCount(int m, int n, int k) {
        vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        vector<vector<int>> visited(m, vector<int>(n, 0));
        queue<Point> q;
        q.push(Point(0, 0));
        int ans = 0;
        while(!q.empty()) {
            Point cur = q.front();
            q.pop();

            if(visited[cur.x_][cur.y_] == 1) continue; // 注意!

            visited[cur.x_][cur.y_] = 1;
            ++ans;
            for(int i = 0; i < dirs.size(); ++i) {
                int u = cur.x_ + dirs[i][0], v = cur.y_ + dirs[i][1];
                if(u >= 0 && u < m && v >= 0 && v < n && visited[u][v] == 0 && IsValid(u, v, k)) {
                    q.push(Point(u, v));
                }
            }
        }
        return ans;
    }
};

本代码提交AC,用时8MS。

剑指 Offer 12. 矩阵中的路径

剑指 Offer 12. 矩阵中的路径

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。

[[“a”,”b”,”c”,”e”],
[“s”,”f”,”c”,”s”],
[“a”,”d”,”e”,”e”]]

但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。

示例 1:

输入:board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
输出:true
示例 2:

输入:board = [[“a”,”b”],[“c”,”d”]], word = “abcd”
输出:false
提示:

1 <= board.length <= 200
1 <= board[i].length <= 200
注意:本题与主站 79 题相同:https://leetcode-cn.com/problems/word-search/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


给定一个字符矩阵,问矩阵中是否能走出一条路径,这条路径上的字符串起来和target字符串相等。

典型的DFS题,首先找到第一个字符开始的位置,然后DFS,完整代码如下:

class Solution {
private:
    bool DFS(vector<vector<char>> &board, vector<vector<int>> &visited, int x, int y, const string &word, int idx) {

        if(idx == word.size() - 1) return true;

        visited[x][y] = 1;
        int m = board.size(), n = board[0].size();

        vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
        for(int i = 0; i < dirs.size(); ++i) {
            int u = x + dirs[i][0], v = y + dirs[i][1];
            if(u >= 0 && u < m && v >= 0 && v < n && visited[u][v] == 0 && board[u][v] == word[idx + 1]) {
                bool ans = DFS(board, visited, u, v, word, idx + 1);
                if(ans) return true;
            }
        }

        visited[x][y] = 0;

        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(word.size() == 0) return true;
        int m = board.size(), n = board[0].size();
        vector<vector<int>> visited(m, vector<int>(n, 0));
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(board[i][j] == word[0]) {
                    if(DFS(board, visited, i, j, word, 0)) return true;
                }
            }
        }
        return false;
    }
};

本代码提交AC,用时624MS。

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

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

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。  

示例 1:

输入:[3,4,5,1,2]
输出:1
示例 2:

输入:[2,2,2,0,1]
输出:0
注意:本题与主站 154 题相同:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。剑指 Offer 11. 旋转数组的最小数字


LeetCode Find Minimum in Rotated Sorted Array II相同,即旋转有序数组中包含重复元素,求最小值。考虑nums[m]==nums[r]的情况,退化为线性查找,完整代码如下:

class Solution {
public:
	int minArray(vector<int>& numbers) {
		int n = numbers.size();
		int l = 0, r = n - 1;
        while(l <= r) {
            if(r - l <= 1) return min(numbers[l], numbers[r]);
            int m = l + (r - l) / 2;
            if(numbers[m] > numbers[r]) l = m;
            else if(numbers[m] == numbers[r]) --r;
            else r = m;
        }
		return 0;
	}
};

本代码提交AC,用时12MS。

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

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

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

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:2
示例 2:

输入:n = 7
输出:21
示例 3:

输入:n = 0
输出:1
提示:

0 <= n <= 100
注意:本题与主站 70 题相同:https://leetcode-cn.com/problems/climbing-stairs/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


对于跳到第n的位置,有两种来源,如果这一跳是2步,则f(n)=f(n-2),如果这一跳是1步,则f(n)=f(n-1),所以总的情况是f(n)=f(n-2)+f(n-1),也就是求斐波那契数列的第n项。

完整代码如下:

class Solution {
public:
    int numWays(int n) {
        if(n == 0) return 1;
        if(n == 1) return 1;
        if(n == 2) return 2;
        int a = 1, b = 2;
        for(int i = 3; i <= n; ++i) {
            int tmp = (a + b) % 1000000007;
            a = b;
            b = tmp;
        }
        return b;
    }
};

本代码提交AC,用时0MS。

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

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

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

F(0) = 0,   F(1) = 1
F(N) = F(N – 1) + F(N – 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:1
示例 2:

输入:n = 5
输出:5
 

提示:

0 <= n <= 100
注意:本题与主站 509 题相同:https://leetcode-cn.com/problems/fibonacci-number/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


求斐波那契数列的第n项。看之前的POJ题解: http://code.bitjoy.net/2017/05/04/poj-3070-fibonacci/

一共有三种解法。常规解法就是无脑递归调用。关键是如何分析这种解法的时空复杂度。无脑调用是F(n)=F(n-1)+F(n-2)。想象一下,递归调用二叉树( https://wmjtxt.github.io/2018/12/26/three_method_of_fibonacci/ )。每个节点都会分裂出2个孩子,然后孩子继续2倍分裂,所以总调用次数大概是$O(2^n)$,这是时间复杂度。空间复杂度就是递归调用的栈深度,就是树的高度,大概是$O(n)$。

常规解法是,DP的思路,每次保留数列前两项,然后不断更新这两个数。时间复杂度是$O(n)$,空间复杂度是O(1)。完整代码如下:

class Solution {
public:
    int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        long long a = 0, b = 1;
        for(int i = 2; i <= n; ++i) {
            long long tmp = a + b;
            tmp %= 1000000007;
            a = b;
            b = tmp;
        }
        return b;
    }
};

本代码提交AC,用时0MS。

最优的解法是矩阵快速幂的方法,求矩阵[[1,1],[1,0]]的n次幂,然后矩阵逆对角线位置的值就是F(n)的值。快速幂可以做到$O(lg(n))$的时间复杂度,完整代码如下:

typedef long long LL;

class Solution {
private:
    vector<vector<LL>> multiply(vector<vector<LL>> &m1, vector<vector<LL>> &m2) {
        int n = m1.size();
        vector<vector<LL>> ans(n, vector<LL>(n, 0));
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                for(int k = 0; k < n; ++k) {
                    ans[i][j] += m1[i][k] * m2[k][j] % 1000000007;
                }
            }
        }
        return ans;
    }
public:
    int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;

        vector<vector<LL>> matrix = {{1,1},{1,0}};

        vector<vector<LL>> ans = {{1,0},{0,1}};
        while(n != 0) {
            if(n % 2 == 1) ans = multiply(ans, matrix);
            matrix = multiply(matrix, matrix);
            n >>= 1;
        }

        return ans[0][1] % 1000000007;
    }
};

本代码提交AC,用时4MS。