Leetcode题解 剑指 Offer 29. 顺时针打印矩阵
PROBLEM剑指 Offer 29. 顺时针打印矩阵
MY ANSWER仅使用圈数作为边界条件没写出来。
BETTER SOLUTION设置上下左右四条边界，边界相遇时说明打印完毕，从而避免漏打或者多打。时间复杂度O(NM)，空间复杂度O(1)。
class Solution {public: vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int> res; if(!matrix.size()) { return res; } int m = matrix.size() - 1; int n = matrix[0].size() - 1; int l = 0, r = n, t = 0, b = m; while(true) { for(int i = l; ...
Leetcode题解 剑指 Offer 20. 表示数值的字符串
PROBLEM剑指 Offer 20. 表示数值的字符串
难度 中等
MY ANSWER多次提交拼凑出来的答案。
class Solution {public: bool isNumber(string s) { int l = s.find_first_not_of(" "); if(l == string::npos) { return false; } s.erase(0, l); int r = s.find_last_not_of(" "); if(r != string::npos) { s.erase(r + 1); } int point = 0; int e = 0; int sign = 0; int num_ = 0; int _num = 0; ...
Leetcode题解 剑指 Offer 19. 正则表达式匹配
PROBLEM剑指 Offer 19. 正则表达式匹配
难度 困难
MY ANSWER写一晚上没写出来。
BETTER SOLUTION动态规划用dp[i][j]表示s的前i个字符和p的前j个字符是否能匹配，由于 dp[0][0] 代表的是空字符的状态， 因此 dp[i][j] 对应的添加字符是 s[i - 1] 和 p[j - 1]。时间复杂度O(mn)，空间复杂度O(mn)。
当 p[j - 1] = '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true ：
dp[i][j - 2]： 即将字符组合 p[j - 2] * 看作出现 0 次时，能否匹配；
dp[i - 1][j] 且 s[i - 1] = p[j - 2]: 即让字符 p[j - 2] 多出现 1 次时，能否匹配；
dp[i - 1][j] 且 p[j - 2] = '.': 即让字符 '.' 多出现 1 次时，能否匹配；
当 p[j - 1] != '*' 时， dp[i][j] 在当以下任一情况为 true时等于 tr ...
Leetcode题解 剑指 Offer 17. 打印从1到最大的n位数
PROBLEM剑指 Offer 17. 打印从1到最大的n位数
难度 简单
MY ANSWER题目设置有问题，所以没考虑大数，时间复杂度O(10^n)，空间复杂度O(10^n)。
class Solution {public: vector<int> printNumbers(int n) { vector<int> res; int x = 1; x = pow(10, n); for(int i = 1; i < x; i++) { res.push_back(i); } return res; }};
BETTER SOLUTION考虑大数，使用string储存大数，使用递归生成数的字符串，去除前导0后加入string向量中。
#include <iostream>#include <string>#include <vector>usi ...
Leetcode题解 剑指 Offer 15. 二进制中1的个数
PROBLEM剑指 Offer 15. 二进制中1的个数
难度 简单
MY ANSWER逐位判断，时间复杂度O(log n)，空间复杂度O(1)。
class Solution {public: int hammingWeight(uint32_t n) { int res = 0; while(n) { if(n & 1) { res++; } n >>= 1; } return res; }};
BETTER SOLUTION使用n&(n - 1)循环消去最右边的1。
class Solution {public: int hammingWeight(uint32_t n) { int ret = 0; while (n) { ...
Leetcode题解 剑指 Offer 14- II. 剪绳子 II
PROBLEM剑指 Offer 14- II. 剪绳子 II
难度 中等
MY ANSWER使用快速幂求余，使用long long防止溢出。尽量将绳子切成以3为单位，若余1则将一段变4，若余2则乘上2这段。数学原理可看这篇题解，主要使用均值不等式、导数来证明。时间复杂度O(1)，空间复杂度O(1)。
class Solution {public: long long fpow(long long x, long long y) { long long res = x; long long ans = 1; while(y) { if(y & 1) { ans = ans * res % 1000000007; } res = res * res % 1000000007; y = y>>1; } return a ...
Leetcode题解 剑指 Offer 13. 机器人的运动范围
PROBLEM剑指 Offer 13. 机器人的运动范围
难度 中等
MY ANSWER使用DFS解决，矩阵visit表示移动中是否走过该格子。DFS完成后，遍历visit得出到达的格子数。时间复杂度O(mn)，空间复杂度O(mn)。
class Solution {public: int k, r, c; vector<vector<int>> visit; int sum(int m, int n) { int s = 0; while(m) { s += m % 10; m /= 10; } while(n) { s += n % 10; n /= 10; } return s; } void dfs(int m, int n) { if(sum(m, n) > ...
Leetcode题解 剑指 Offer 12. 矩阵中的路径
PROBLEM剑指 Offer 12. 矩阵中的路径
难度 中等
MY ANSWER使用DFS与回溯解决，矩阵visit表示搜索中是否走过该格子，index代表当前需要匹配的字符串的字符。dfs(int i, int j, int index)表示从matrix(i, j)出发能否搜索到从索引k开始的word(k, -1)。执行时：
当前字符不匹配，直接返回false；
当前字符匹配且已经是末尾，直接返回true；
当前字符匹配但不是末尾，将当前格子设置为访问过。递归遍历未访问过的相邻格子，若相邻格子中的dfs有返回true，则返回true，否则返回false。这一步返回前要将当前格子设置为未访问，进行回溯。
时间复杂度O(MN3^K)，K为字符串长度，但由于剪枝，时间复杂度并不会这么大。空间复杂度O(MN)，开销用于visit矩阵。
class Solution {public: vector<vector<char>> matrix; vector<vector<int>> visit; string ...
Leetcode题解 剑指 Offer 11. 旋转数组的最小数字
PROBLEM剑指 Offer 11. 旋转数组的最小数字
难度 简单
MY ANSWER二分法，交了好几次改的代码很乱。时间复杂度O(log n)，空间复杂度O(1)。
class Solution {public: int minArray(vector<int>& numbers) { int min = 0; int x = numbers.size(); int l = 0, r = numbers.size() - 1; if(x == 1) { return numbers[0]; } while(x) { int mid = (l + r) / 2; if(mid == l) { break; } if(numbers[l] == numbers[mid ...
Leetcode题解 剑指 Offer 10- II. 青蛙跳台阶问题
PROBLEM剑指 Offer 10- II. 青蛙跳台阶问题
难度 简单
MY ANSWER与求斐波那契数相同，f(n) = f(n - 1) + f(n - 2)，只不过f(0) = 1, f(1) = 1。时间复杂度O(n)，空间复杂度O(1)。
class Solution {public: int numWays(int n) { int a = 1, b = 1, c = 0; for(int i = 0; i < n; i++) { c = (a + b) % 1000000007; a = b; b = c; } return a; }};
BETTER SOLUTION矩阵快速幂同样适用于求斐波那契数。时间复杂度O(logn)，O(1)。
使用快速幂计算M的n次幂就可以得到结果。
class Solution {public: vector<ve ...