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.

很有意思的一个题。一块长木板上，放了若干只蚂蚁，有的蚂蚁向左走，有的蚂蚁向右走。当两个蚂蚁碰头时，会各自掉头走。问所有蚂蚁走出木板的时间。

有点像智力题，分析了半天，发现挺简单的。想象一下，如果蚂蚁A向右走，蚂蚁B向左走，它们在坐标0点碰头了，则A掉头向左走，B掉头向右走。对于A和B来说，虽然它们的方向变了，但是对于整个木板来说，并没有差别，依然是有一只蚂蚁从0点向右走，有一只蚂蚁从0点向左走。相当于A和B交换了身份，各自帮对方走了剩下的流程。但是从宏观分析看，A和B不管掉不掉头，效果是一样的。

综上所述，完全不用考虑碰头掉头的问题，直接对向左走和向右走的蚂蚁单独分析。对于向左走的蚂蚁，最右边的蚂蚁要走最长的时间。对于向右走的蚂蚁，最左边的蚂蚁要走最长的时间。总时间就是这两种情况的最大值。代码如下：

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

本代码提交AC。

1390. 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

给定一个数组，问其中哪些数只有4个因子，把只有4个因子的数对应的所有因子加起来。

也是很无聊的一个题，按题意照做即可，注意求解因子的时候只需要循环到sqrt(v)即可，因为如果一个因子大于sqrt(v)的话，其对应的另一个因子肯定小于sqrt(v)，也就是之前已经遍历过了。

完整代码如下：

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

本代码提交AC，用时440MS。

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

给定一个数num，找出所有a*b等于num+1或num+2的(a,b)组合中，a和b的差最小的那个组合。

子问题就是给定一个数num，找出a*b==num的(a,b)组合中，a和b的差最小的组合。根据反证法，a和b必定有一个小于等于sqrt(num)，另一个大于等于sqrt(num)。所以我最开始的做法是，用之前快速求sqrt的方法，计算sqrt(num)，令left和right都等于sqrt(num)，然后判断left*right的积，如果大于num，则–right；否则++left。这样虽然能得到正确结果，但提交后TLE。

百思不得其解，后来看别人的解答，才理解为什么我会TLE。我的解法设置了left和right两个指针，根据乘积的大小关系，left和right都在移动，在某些情况总的移动数会很大。而正确解法是，只设置一个移动指针i，i从sqrt(num)递减，然后判断num是否能整除i，如果能整除，则肯定找到一个因式分解。这种方法相当于我的方法中只移动了left，速度快了不少。在这种解法下，用不用快速sqrt都能AC。

完整代码如下：

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