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

# LeetCode Last Moment Before All Ants Fall Out of a Plank

5453. Last Moment Before All Ants Fall Out of a Plank

We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with speed 1 unit per second. Some of the ants move to the left, the other move to the right.

When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions doesn’t take any additional time.

When an ant reaches one end of the plank at a time t, it falls out of the plank imediately.

Given an integer n and two integer arrays left and right, the positions of the ants moving to the left and the right. Return the moment when the last ant(s) fall out of the plank.

Example 1:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
Note that the last moment when an ant was on the plank is t = 4 second, after that it falls imediately out of the plank. (i.e. We can say that at t = 4.0000000001, there is no ants on the plank).


Example 2:

Input: n = 7, left = [], right = [0,1,2,3,4,5,6,7]
Output: 7
Explanation: All ants are going to the right, the ant at index 0 needs 7 seconds to fall.


Example 3:

Input: n = 7, left = [0,1,2,3,4,5,6,7], right = []
Output: 7
Explanation: All ants are going to the left, the ant at index 7 needs 7 seconds to fall.


Example 4:

Input: n = 9, left = [5], right = [4]
Output: 5
Explanation: At t = 1 second, both ants will be at the same intial position but with different direction.


Example 5:

Input: n = 6, left = [6], right = [0]
Output: 6


Constraints:

• 1 <= n <= 10^4
• 0 <= left.length <= n + 1
• 0 <= left[i] <= n
• 0 <= right.length <= n + 1
• 0 <= right[i] <= n
• 1 <= left.length + right.length <= n + 1
• All values of left and right are unique, and each value can appear only in one of the two arrays.

class Solution {
public:
int getLastMoment(int n, vector<int>& left, vector<int>& right) {
sort(left.begin(), left.end());
sort(right.begin(), right.end());
int ans = 0;
if (!left.empty())ans = max(ans, left.back());
if (!right.empty())ans = max(ans, n - right.front());
return ans;
}
};


# LeetCode Number of Ways to Paint N × 3 Grid

You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colours: RedYellow or Green while making sure that no two adjacent cells have the same colour (i.e no two cells that share vertical or horizontal sides have the same colour).

You are given n the number of rows of the grid.

Return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 12
Explanation: There are 12 possible way to paint the grid as shown:



Example 2:

Input: n = 2
Output: 54


Example 3:

Input: n = 3
Output: 246


Example 4:

Input: n = 7
Output: 106494


Example 5:

Input: n = 5000
Output: 30228214


Constraints:

• n == grid.length
• grid[i].length == 3
• 1 <= n <= 5000

class Solution {
public:

int numOfWays(int n) {
if (n == 1)return 12;
long long pre_two_colors = 6, pre_three_colors = 6;
long long mod = 1e9 + 7;
for (int i = 2; i <= n; ++i) {
long long next_two_colors = 3 * pre_two_colors + 2 * pre_three_colors;
long long next_three_colors = 2 * pre_two_colors + 2 * pre_three_colors;
pre_two_colors = next_two_colors % mod;
pre_three_colors = next_three_colors % mod;
}
return (pre_two_colors + pre_three_colors) % mod;
}
};

# LeetCode Four Divisors

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors.

If there is no such integer in the array, return 0.

Example 1:

Input: nums = [21,4,7]
Output: 32
Explanation:
21 has 4 divisors: 1, 3, 7, 21
4 has 3 divisors: 1, 2, 4
7 has 2 divisors: 1, 7
The answer is the sum of divisors of 21 only.


Constraints:

• 1 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^5

class Solution {
public:
void FindDivisors(int v, vector<int>& ans) {
int mid = sqrt(v);
for (int i = 1; i <= mid; ++i) {
if (v%i == 0) {
ans.push_back(i);
if (v / i != i)ans.push_back(v / i);
}
}
}
int sumFourDivisors(vector<int>& nums) {
int ans = 0;
for (int i = 0; i < nums.size(); ++i) {
vector<int> divs;
FindDivisors(nums[i], divs);
if (divs.size() == 4) {
for (int j = 0; j < divs.size(); ++j)ans += divs[j];
}
}
return ans;
}
};

# LeetCode Closest Divisors

1362. Closest Divisors

Given an integer num, find the closest two integers in absolute difference whose product equals num + 1 or num + 2.

Return the two integers in any order.

Example 1:

Input: num = 8
Output: [3,3]
Explanation: For num + 1 = 9, the closest divisors are 3 & 3, for num + 2 = 10, the closest divisors are 2 & 5, hence 3 & 3 is chosen.


Example 2:

Input: num = 123
Output: [5,25]


Example 3:

Input: num = 999
Output: [40,25]


Constraints:

• 1 <= num <= 10^9

class Solution {
public:
int mySqrt(int x)
{
long long y = x;
while (y*y > x)
{
y = (y + x / y) / 2;
}
return y;
}

vector<int> work(int num) {
for (int i = mySqrt(num) + 1; i >= 1; --i) {
if (num%i == 0) {
return { i,num / i };
}
}
return { 1,num };
}
vector<int> closestDivisors(int num) {
vector<int> plus1 = work(num + 1);
vector<int> plus2 = work(num + 2);
if (abs(plus1[1] - plus1[0]) < abs(plus2[1] - plus2[0]))return plus1;
else return plus2;
}
};


# hihoCoder 1552-缺失的拼图

hihoCoder 1552-缺失的拼图

### 输出

5
0 0 4 5
0 0 3 1
0 1 2 5
3 0 4 5
2 2 3 5

2 1 3 2

# hihoCoder 1543-SCI表示法

hihoCoder 1543-SCI表示法

### 输出

2
15
8

5
1

# LeetCode 4 Keys Keyboard

LeetCode 4 Keys Keyboard Imagine you have a special keyboard with the following keys: Key 1: (A): Prints one ‘A’ on screen. Key 2: (Ctrl-A): Select the whole screen. Key 3: (Ctrl-C): Copy selection to buffer. Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed. Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of ‘A’ you can print on screen. Example 1:

Input: N = 3
Output: 3
Explanation:
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A

Example 2:
Input: N = 7
Output: 9
Explanation:
We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

Note:
1. 1 <= N <= 50
2. Answers will be in the range of 32-bit signed integer.

• A: 打印一个字符A
• Ctrl-A: 全选
• Ctrl-C: 复制
• Ctrl-V: 粘贴