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

输入: n = 1



• 用返回一个整数列表来代替打印
• 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;
}
};

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

输入: 2.00000, 10



输入: 2.10000, 3



输入: 2.00000, -2

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

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;
}
};

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

输入：00000000000000000000000000001011



输入：00000000000000000000000010000000



输入：11111111111111111111111111111101

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

# 剑指 Offer 14- II. 剪绳子 II

输入: 2

输入: 10

• 2 <= n <= 1000

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;
}
}
};

# 剑指 Offer 14- I. 剪绳子 LCOF

2 <= n <= 58

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;
}
}
};

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];
}
};

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

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

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

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;
}
};

# 剑指 Offer 12. 矩阵中的路径

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

1 <= board.length <= 200
1 <= board[i].length <= 200

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;
}
};

# 剑指 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;
}
};

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

0 <= n <= 100

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;
}
};

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

F(0) = 0,   F(1) = 1
F(N) = F(N – 1) + F(N – 2), 其中 N > 1.

0 <= n <= 100

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;
}
};

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;
}
};