661. Image Smoother

Given a 2D integer matrix M representing the gray scale of an image, you need to design a smoother to make the gray scale of each cell becomes the average gray scale (rounding down) of all the 8 surrounding cells and itself. If a cell has less than 8 surrounding cells, then use as many as you can.

Example 1:

Input:
[[1,1,1],
 [1,0,1],
 [1,1,1]]
Output:
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
Explanation:
For the point (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the point (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

Note:

1. The value in the given matrix is in the range of [0, 255].
2. The length and width of the given matrix are in the range of [1, 150].

简单题，直接根据题意做就行。

class Solution {
public:
	vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
		int x = M.size(), y = M[0].size();
		vector<vector<int>> A(x, vector<int>(y, 0));
		for (int i = 0; i < x; ++i) {
			for (int j = 0; j < y; ++j) {
				int s = 0, n = 0;
				for (int u = i - 1 >= 0 ? i - 1 : 0; u < x && u <= i + 1; ++u) {
					for (int v = j - 1 >= 0 ? j - 1 : 0; v < y && v <= j + 1; ++v) {
						s += M[u][v];
						++n;
					}
				}
				A[i][j] = s / n;
			}
		}
		return A;
	}
};

本代码提交AC，用时148MS。其实还可以保存之前算过的结果，给后面的计算节省时间，但是我估计也节省不了多少，因为对每个位置，穷举也就做9次加法，节省也快不了多少。

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

1360. Number of Days Between Two Dates

Write a program to count the number of days between two dates.

The two dates are given as strings, their format is YYYY-MM-DD as shown in the examples.

Example 1:

Input: date1 = "2019-06-29", date2 = "2019-06-30"
Output: 1

Example 2:

Input: date1 = "2020-01-15", date2 = "2019-12-31"
Output: 15

Constraints:

• The given dates are valid dates between the years 1971 and 2100.

给定两个日期，计算这两个日期之间相隔的天数。

比较简单。如果年份和月份相同，直接天数作差。如果年份相同月份不同，则先把相隔的完整月份的天数算出来，存到part2；对于较早的日期，算出这个月还剩的天数part1；对于较晚的日期，算出这个月走过的天数part3；三者加起来。如果年份也不同，和上一种情况类似，先把间隔的完整年的天数算出来，寸到part2；对于较早的日期，算出这一年还剩的天数part2；对于较晚的日期，算出这一年走过的天数part3；三者加起来。

判断闰年的标准：是400的倍数；或者是4的倍数但不是100的倍数。

完整代码如下：

struct Date {
	int year;
	int month;
	int day;
	Date() {
		year = month = day = 0;
	}
	void parse(string date) {
		year = stoi(date.substr(0, 4));
		month = stoi(date.substr(5, 2));
		day = stoi(date.substr(8, 2));
	}
};
class Solution {
public:
	bool isRunYear(int year) {
		return year % 400 == 0 || (year % 4 == 0 && year % 100 != 0);
	}
	int DaysInMonth(int m, int y) {
		switch (m) {
		case 1:
		case 3:
		case 5:
		case 7:
		case 8:
		case 10:
		case 12:
			return 31;
		case 2:
			if (isRunYear(y))return 29;
			else return 28;
		default:
			return 30;
		}
	}

	int DaysInYear(int year) {
		if (isRunYear(year))return 366;
		else return 365;
	}

	int daysBetweenDates(string date1, string date2) {
		Date d1, d2;
		if (date1 < date2) {
			d1.parse(date1);
			d2.parse(date2);
		}
		else {
			d1.parse(date2);
			d2.parse(date1);
		}

		if (d1.year == d2.year && d1.month==d2.month) {
			return d2.day - d1.day;
		}
		else if (d1.year == d2.year) {
			int part1 = DaysInMonth(d1.month, d1.year) - d1.day;
			int part3 = d2.day;
			int part2 = 0;
			for (int m = d1.month + 1; m < d2.month; ++m) {
				part2 += DaysInMonth(m, d1.year);
			}
			return part1 + part2 + part3;
		}
		else {
			int part1 = DaysInMonth(d1.month, d1.year) - d1.day;
			for (int m = d1.month + 1; m <= 12; ++m) {
				part1 += DaysInMonth(m, d1.year);
			}
			int part2 = 0;
			for (int y = d1.year + 1; y < d2.year; ++y) {
				part2 += DaysInYear(y);
			}
			int part3 = d2.day;
			for (int m = 1; m < d2.month; ++m) {
				part3 += DaysInMonth(m, d2.year);
			}
			return part1 + part2 + part3;
		}
	}
};

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

LeetCode Find K Closest Elements Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred. Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]

1. The value k is positive and will always be smaller than the length of the sorted array.
2. Length of the given array is positive and will not exceed 10⁴
3. Absolute value of elements in the array and x will not exceed 10⁴

LeetCode Judge Route Circle Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place. The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle. Example 1:

Input: "UD"
Output: true

Input: "LL"
Output: false