Tag Archives: 数学

LeetCode Super Pow

LeetCode Super Pow
Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.
Example1:

a = 2
b = [3]
Result: 8

Example2:

a = 2
b = [1,0]
Result: 1024

快速幂的进阶版,超级幂。要求a^B=a^{[b_0,b_1,b_2,...b_{n-1}]},其中的B用一个数组来表示,数组中的元素都是个位数,分别从高位到低位。比如第二个样例表示的是2^10
我一开始把a^B=a^{[b_0,b_1,b_2,...b_{n-1}]}展开成a^B=a^{b_0*10^{n-1}+b_1*10^{n-2}+...},对于每一项都用快速幂算出10^{n-i-1},然后用快速幂算出a^{b_i*10^{n-i-1}},最后累乘起来。但是很不幸WA或者TLE。
后来看了网上的题解,发现真是巧妙,这不就类似于多项式计算时层层嵌套的方法吗,一时想不起来那个叫什么名字了。比如我们要算a^{[b_0,b_1,b_2]},本来是a^{b_0*10^2+b_1*10+b_2}。但是我们计算是可以这样算,先算C_0=a^{b_0};递归到b_1时,在算到b_0的基础上,有C_1=(a^{b_0})^{10}*a^{b_1}=C_0^{10}*a^{b_1};递归到b_2时,有C_2=((a^{b_0})^{10}*a^{b_1})^{10}*a^{b_2}=C_1^{10}*a^{b_2}。把C_2展开其实就是a^{b_0*10^2+b_1*10+b_2}
完整代码如下:

typedef unsigned long long ull;
class Solution {
private:
	const static int MOD = 1337;
	ull fastPow(ull x, ull y) {
		ull ans = 1;
		while (y) {
			if (y & 1)ans = (ans*x) % MOD;
			y >>= 1;
			x = (x*x) % MOD;
		}
		return ans;
	}
public:
	int superPow(int a, vector<int>& b) {
		ull ans = 1;
		for (int i = 0; i < b.size(); ++i) {
			ans = fastPow(ans, 10)*fastPow(a, b[i]) % MOD;
		}
		return ans;
	}
};

本代码提交AC,用时9MS。

LeetCode Valid Square

LeetCode Valid Square
Given the coordinates of four points in 2D space, return whether the four points could construct a square.
The coordinate (x,y) of a point is represented by an integer array with two integers.
Example:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: True

Note:

  1. All the input integers are in the range [-10000, 10000].
  2. A valid square has four equal sides with positive length and four equal angles (90-degree angles).
  3. Input points have no order.

任给平面上的四个点,问这四个点能否构成正方形。
解法1,原始几何角度。
如果要构成正方形,必须满足四条边相等,且四个角是直角。因为给定的点的顺序是不固定的,假设我们固定一个点p1,求p1到其他三个点p2,p3,p4的距离的平方len2,len3,len4,则要形成正方形,这三个距离中必定有两个距离相等,且等于另一个距离的两倍。

p3------p4
|       |
|       |
p1------p2

比如假设形成上述正方形,则有2*len2==2*len3==len4。在满足这个条件的基础上,还需要满足p1p2垂直p1p3,且p4p3垂直p4p2,且p4到p2和p3的距离相等。
当然因为点的顺序不固定,所以还有可能2*len2==2*len4==len3或者2*len3==2*len4==len2。最后需要注意的是这些点中不能由任何两个点重合,所以需要判断两点之间的距离不能为0。
完整代码如下:

class Solution2 {
private:
	// 计算距离的平方
	int distSquare(const vector<int>& p1, const vector<int>& p2) {
		return (p1[0] - p2[0])*(p1[0] - p2[0]) + (p1[1] - p2[1])*(p1[1] - p2[1]);
	}
	// 判断直线(p1,p2)和直线(p3,p4)是否垂直
	bool isVertical(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
		return (p2[0] - p1[0])*(p4[0] - p3[0]) + (p2[1] - p1[1])*(p4[1] - p3[1]) == 0;
	}
	// 在2|p1p2|==2|p1p3|==|p1p4|的条件下,判断是否能形成正方形
	bool helper(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
		if (!isVertical(p1, p2, p1, p3))return false;
		if (!isVertical(p4, p3, p4, p2))return false;
		int len2 = distSquare(p4, p2), len3 = distSquare(p4, p3);
		return len2 == len3;
	}
public:
	bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
		int len2 = distSquare(p1, p2), len3 = distSquare(p1, p3), len4 = distSquare(p1, p4);
		if (len2 == 0 || len3 == 0 || len4 == 0)return false;
		if (len2 == len3 && 2 * len2 == len4) return helper(p1, p2, p3, p4);
		if (len2 == len4 && 2 * len2 == len3) return helper(p1, p2, p4, p3);
		if (len3 == len4 && 2 * len3 == len2) return helper(p1, p3, p4, p2);
		return false;
	}
};

本代码提交AC,用时6MS。
解法2,特征法。
任何一个正方形,如果求出所有点之间的距离,则这些距离只可能有两种取值,一种是邻边全相等,另一种是对角边也相等。所以我们只需要用一个map保存不同边的长度以及出现的频率即可,如果最终只有两个映射,则是正方形,否则不是。注意当出现边长为0时,说明两点重合,不能构成正方形。
代码如下:

class Solution {
private:
	// 计算距离的平方
	int distSquare(const vector<int>& p1, const vector<int>& p2) {
		return (p1[0] - p2[0])*(p1[0] - p2[0]) + (p1[1] - p2[1])*(p1[1] - p2[1]);
	}
public:
	bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
		unordered_map<int, int> umdist;
		vector<vector<int>> points = { p1,p2,p3,p4 };
		for (int i = 0; i < 4; ++i) {
			for (int j = i + 1; j < 4; ++j) {
				int dist = distSquare(points[i], points[j]);
				if (dist == 0)return false;
				++umdist[dist];
			}
		}
		return umdist.size() == 2;
	}
};

本代码提交AC,用时9MS。
不过上述代码有局限性,如果顶点都只是整数,则没有问题,但是如果顶点可以是实数,则会有问题。比如等边三角形的三个点和三角形的中心点,这四个点两两之间只有2种不同的距离,但他们不能构成正方形。可以再加一个限制条件,即两种不同长度的边的频率一个是4,一个是2,且出现2次的边长是出现4次的边长的两倍。
讨论区见:https://discuss.leetcode.com/topic/89985/c-3-lines-unordered_set/4

LeetCode Array Nesting

LeetCode Array Nesting
A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0, N - 1].
Sets S[K] for 0 <= K < N are defined as follows:
S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }.
Sets S[K] are finite for each K and should NOT contain duplicates.
Write a function that given an array A consisting of N integers, return the size of the largest set S[K] for this array.
Example 1:

Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

Note:

  1. N is an integer within the range [1, 20,000].
  2. The elements of A are all distinct.
  3. Each element of array A is an integer within the range [0, N-1].

求嵌套集合的最大长度。首先给定原数组A,嵌套集合为S[K] = { A[K], A[A[K]], A[A[A[K]]], ... },就是不断的把值当下标递归的取值,因为数组A中的值的范围也是0~n-1的,所以下标不会超出范围。
暴力方法就是求出每一个S[K]的大小,然后求最大值。但是仔细分析一个样例就会发现,很多S[K]集合是完全一样的,比如第一个样例中,S[0]和S[2]都等于{5,6,2,0},因为他们构成了一个循环。所以我们可以创建一个visited数组,访问过就置1,只对哪些visited为0的下标开始递归。这样对于第一个样例,其实只需要3次递归就可以了,也就是下标到值的构成的图中环的个数:{5,6,2,0},{3},{1,4}。所以总的复杂度其实只有O(n)。
代码如下:

class Solution {
private:
	int nest(vector<int> &nums, vector<int> &visited, int k) {
		int ans = 0;
		while (visited[k] == 0) {
			visited[k] = 1;
			++ans;
			k = nums[k];
		}
		return ans;
	}
public:
	int arrayNesting(vector<int>& nums) {
		int n = nums.size();
		vector<int> visited(n, 0);
		int ans = 0;
		for (int i = 0; i < nums.size(); ++i) {
			if (visited[i] == 0) {
				int cur = nest(nums, visited, i);
				ans = max(ans, cur);
			}
		}
		return ans;
	}
};

本代码提交AC,用时39MS。

LeetCode Different Ways to Add Parentheses

LeetCode Different Ways to Add Parentheses
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example 1
Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]
Example 2
Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.


给定一个包含+-*的运算字符串,求所有加括号的方案计算到的值。
采用分治法的思路,尝试在每个操作符分成两个部分,这就相当于分别把操作符左右两边括起来单独计算。然后left和right分开进行递归,最后merge。递归的终止条件是当字符串中不包含操作符时,直接返回这个字符串对应的数值。
分治法很经典的例子。
代码如下:

class Solution {
private:
	int operate(int a, int b, char c) {
		switch (c) {
			case '+':return a + b;
			case '-':return a - b;
			case '*':return a*b;
		}
	}
public:
	vector<int> diffWaysToCompute(string input) {
		int n = input.size();
		vector<int> ans;
		bool found = false;
		for (int i = 0; i < n; ++i) {
			if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
				found = true;
				vector<int> lefts = diffWaysToCompute(input.substr(0, i));
				vector<int> rights = diffWaysToCompute(input.substr(i + 1));
				for (int j = 0; j < lefts.size(); ++j) {
					for (int k = 0; k < rights.size(); ++k) {
						ans.push_back(operate(lefts[j], rights[k], input[i]));
					}
				}
			}
		}
		if (!found)return{ atoi(input.c_str()) };
		return ans;
	}
};

本代码提交AC,用时3MS。

LeetCode Fraction Addition and Subtraction

LeetCode Fraction Addition and Subtraction
Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should be irreducible fraction. If your final result is an integer, say 2, you need to change it to the format of fraction that has denominator 1. So in this case, 2 should be converted to 2/1.
Example 1:

Input:"-1/2+1/2"
Output: "0/1"

Example 2:

Input:"-1/2+1/2+1/3"
Output: "1/3"

Example 3:

Input:"1/3-1/2"
Output: "-1/6"

Example 4:

Input:"5/3+1/3"
Output: "2/1"

Note:

  1. The input string only contains '0' to '9', '/', '+' and '-'. So does the output.
  2. Each fraction (input and output) has format ±numerator/denominator. If the first input fraction or the output is positive, then '+' will be omitted.
  3. The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1,10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.
  4. The number of given fractions will be in the range [1,10].
  5. The numerator and denominator of the final result are guaranteed to be valid and in the range of 32-bit int.

给定一个只包含+-/的运算字符串,要求求出这个字符串的值,并且用最简分数的形式表示。
参考这篇博客,没什么技巧,就是用代码模拟手算的过程。首先求出所有分母的最小公倍数,然后通分,使得所有数的分母都相同,最后把所有通分过的分子加起来,得到结果。最最后一步就是把分子和分母约分。
这些步骤中涉及到求最小公倍数和最大公约数。最大公约数的求法gcd是必须掌握的,另外再根据gcd(x,y)*lcm(x,y)=x*y的性质,可以求到最小公倍数lcm(x,y)
代码如下:

class Solution {
private:
	int gcd(int x, int y) {
		while (y) {
			int tmp = x % y;
			x = y;
			y = tmp;
		}
		return x;
	}
	int lcm(int x, int y) {
		return x * y / gcd(x, y);
	}
public:
	string fractionAddition(string expression) {
		vector<int> num, denom; // 分子,分母
		expression += "+"; // 哨兵
		int i = 0, j = 0;
		bool isnum = true;
		for (j = 0; j < expression.size(); ++j) {
			if (j != 0 && (expression[j] == '/' || expression[j] == '-' || expression[j] == '+')) {
				int one = atoi(expression.substr(i, j - i).c_str());
				if (isnum)num.push_back(one);
				else denom.push_back(one);
				isnum = !isnum;
				if (expression[j] == '/') i = j + 1;
				else i = j;
			}
		}
		int fm = 1;
		for (int i = 0; i < denom.size(); ++i)fm = lcm(fm, denom[i]);
		int fz = 0;
		for (int i = 0; i < num.size(); ++i)fz += num[i] * (fm / denom[i]);
		int g = 0;
		if (fz < 0)
			g = gcd(-fz, fm);
		else
			g = gcd(fz, fm);
		return to_string(fz / g) + "/" + to_string(fm / g);
	}
};

本代码提交AC,用时3MS。

LeetCode Optimal Division

LeetCode Optimal Division
Given a list of positive integers, the adjacent integers will perform the float division. For example, [2,3,4] -> 2 / 3 / 4.
However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the maximum result, and return the corresponding expression in string format. Your expression should NOT contain redundant parenthesis.
Example:

Input: [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation:
1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant,
since they don't influence the operation priority. So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

Note:

  1. The length of the input array is [1, 10].
  2. Elements in the given array will be in range [2, 1000].
  3. There is only one optimal division for each test case.

给定一个正整数数组,数据范围是[2,1000],初始每个数依次除以后一个数,现在要给数组加上括号,使得整个数组相除的结果最大。
首先来个暴力方法,对区间[start, end],枚举每一个分割位置i,也就是[start, i]算除法,[i+1, end]也算除法,然后把前者的结果除以后者。结果的最大值为前者的最大值除以后者的最小值,结果的最小值为前者的最小值除以后者的最大值。一直递归下去,最后就能得到整个区间[0,n-1]的最大值了。
代码如下:

struct T {
	double lfMax, lfMin;
	string strMax, strMin;
};
class Solution {
private:
	T optimal(vector<int>& nums, int start, int end){
		T t;
		if(start == end){
			t.lfMax = t.lfMin = nums[start];
			t.strMax = t.strMin = to_string(nums[start]);
			return t;
		}
		t.lfMax = std::numeric_limits<double>::min();
		t.lfMin = std::numeric_limits<double>::max();
		for(int i = start; i < end; ++i){
			T tl = optimal(nums, start, i);
			T tr = optimal(nums, i + 1, end);
			if(tl.lfMax / tr.lfMin > t.lfMax){
				t.lfMax = tl.lfMax / tr.lfMin;
				t.strMax = tl.strMax + "/" + (i + 1 != end ? "(" : "") + tr.strMin + (i + 1 != end ? ")" : "");
			}
			if(tl.lfMin / tr.lfMax < t.lfMin){
				t.lfMin = tl.lfMin / tr.lfMax;
				t.strMin = tl.strMin + "/" + (i + 1 != end ? "(" : "") + tr.strMax + (i + 1 != end ? ")" : "");
			}
		}
		return t;
	}
public:
    string optimalDivision(vector<int>& nums) {
    	T t = optimal(nums, 0, nums.size() - 1);
    	return t.strMax;
    }
};

本代码提交AC,用时86MS。暴力方法相当于枚举数组的所有排列情况,时间复杂度为O(n!)。
上述方法对某一小段区间会有很多重复计算,我们可以用数组把结果存起来达到加速的目的。使用数组memo[i][j]存储[i,j]的最大值最小值结果,递归的时候如果发现memo[start][end]已经有结果了,则直接返回。代码如下:

struct T {
	double lfMax, lfMin;
	string strMax, strMin;
};
class Solution {
private:
	T optimal(vector<int>& nums, int start, int end, vector<vector<T>>& memo){
		if(memo[start][end].strMax != "" || memo[start][end].strMin != "") return memo[start][end];
		T t;
		if(start == end){
			t.lfMax = t.lfMin = nums[start];
			t.strMax = t.strMin = to_string(nums[start]);
			memo[start][end] = t;
			return t;
		}
		t.lfMax = std::numeric_limits<double>::min();
		t.lfMin = std::numeric_limits<double>::max();
		for(int i = start; i < end; ++i){
			T tl = optimal(nums, start, i, memo);
			T tr = optimal(nums, i + 1, end, memo);
			if(tl.lfMax / tr.lfMin > t.lfMax){
				t.lfMax = tl.lfMax / tr.lfMin;
				t.strMax = tl.strMax + "/" + (i + 1 != end ? "(" : "") + tr.strMin + (i + 1 != end ? ")" : "");
			}
			if(tl.lfMin / tr.lfMax < t.lfMin){
				t.lfMin = tl.lfMin / tr.lfMax;
				t.strMin = tl.strMin + "/" + (i + 1 != end ? "(" : "") + tr.strMax + (i + 1 != end ? ")" : "");
			}
		}
		memo[start][end] = t;
		return t;
	}
public:
    string optimalDivision(vector<int>& nums) {
    	vector<vector<T>> memo(nums.size(), vector<T>(nums.size()));
    	T t = optimal(nums, 0, nums.size() - 1, memo);
    	return t.strMax;
    }
};

本代码提交AC,用时6MS。一下快了不少。
还有一种纯数学的方法。假设我们要对a/b/c/d加括号使得结果最大,则a肯定是分子不能动了,那么就相当于最小化b/c/d。b/c/d有两种加括号的方案:b/(c/d)和(b/c)/d。如果令b/(c/d)>b/c/d,因为b,c,d都是正数,推出d>1。又题目中的数据范围是[2,1000],所以b/(c/d)>b/c/d显然成立。也就是b/c/d这种方案是最小的,使得a/(b/c/d)结果最大。所以只需要把a后面的数加一个括号整体括起来就好了。
代码如下:

class Solution {
public:
    string optimalDivision(vector<int>& nums) {
    	int n = nums.size();
    	if(n == 1) return to_string(nums[0]);
    	else if(n == 2) return to_string(nums[0]) + "/" + to_string(nums[1]);
    	string ans = to_string(nums[0]) + "/(";
    	for(int i = 1; i < n - 1; ++i){
    		ans += to_string(nums[i]) + "/";
    	}
    	return ans + to_string(nums[n-1]) + ")";
    }
};

本代码提交AC,用时3MS。
参考:https://leetcode.com/articles/optimal-division/

LeetCode Complex Number Multiplication

LeetCode Complex Number Multiplication
Given two strings representing two complex numbers.
You need to return a string representing their multiplication. Note i2 = -1 according to the definition.
Example 1:

Input: "1+1i", "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

Example 2:

Input: "1+-1i", "1+-1i"
Output: "0+-2i"
Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.

Note:

  1. The input strings will not have extra blank.
  2. The input strings will be given in the form of a+bi, where the integer a and b will both belong to the range of [-100, 100]. And the output should be also in this form.

给定两个复数字符串,要求计算它们的乘积。
简单题,展开之后是:(a1+a2i)(b1+b2i)=(a1*b1-a2*b2)+(a1*b2+a2*b1)i。所以只需要提取出a1,a2,b1,b2,然后代入公式计算到c1和c2,最后用to_string转换为字符串即可。
代码如下:

class Solution {
	void str2cpx(const string& s, int& c1, int&c2) {
		int i = 0, j = 0;
		while (s[j] != '+')++j;
		c1 = atoi(s.substr(i, j - i).c_str());
		i = ++j;
		while (s[j] != 'i')++j;
		c2 = atoi(s.substr(i, j - i).c_str());
	}
public:
	string complexNumberMultiply(string a, string b) {
		int a1 = 0, a2 = 0, b1 = 0, b2 = 0, c1 = 0, c2 = 0;
		str2cpx(a, a1, a2);
		str2cpx(b, b1, b2);
		c1 = a1*b1 - a2*b2;
		c2 = a1*b2 + a2*b1;
		return to_string(c1) + "+" + to_string(c2) + "i";
	}
};

本代码提交AC,用时3MS。

LeetCode Water and Jug Problem

LeetCode Water and Jug Problem
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.
If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.
Operations allowed:

  • Fill any of the jugs completely with water.
  • Empty any of the jugs.
  • Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

很有意思的水罐问题。给定一个3L的水罐和一个5L的水罐和无限的水,问怎样才能得到4L的水。
这个例子很常见了,可以这样做:

  1. 盛满5L水罐;
  2. 将5L水罐中的水导入3L水罐,此时5L水罐中还剩2L水;
  3. 将3L水罐中的水清空;
  4. 将5L水罐中的2L水倒入3L水罐中;
  5. 盛满5L水罐;
  6. 将5L水罐中的水倒入3L水罐中,此时5L水罐中剩余4L水,3L水罐中是满的;
  7. 将3L水罐中的水清空,此时只剩5L水罐中的4L水。

但是遇到一般的x、y、z时,怎样解呢,这里面肯定暗含某种数学规律,看了题解才恍然大悟
将问题转换为这样一个问题:给定xL和yL水罐和无限的水,以及一起无穷大的水罐,怎样利用x和y才能在无穷大的水罐中盛满zL的水。假设我们要往无穷大的水罐中倒m次xL的水和n次yL的水,则有mx+ny=z,如果m为正,则是倒入,为负则是舀出。比如x=3, y=5, z=4时,有(-2)*3+2*5=4,表示往无穷大的水罐中倒入2次5L的水,并且舀出2次3L的水,剩余正好4L。而上面的7步正好也包含2次盛满5L水,2次清空3L水。
所以问题就转换为方程mx+ny=z对于m,n是否有整数解。这需要用到裴蜀定理,又是头一回听说。
假设x和y的最大公约数是d=gcd(x,y),如果z是d的整数倍,则上式有整数解。所以问题就好办了,求一下x,y的最大公约数,然后判断z是否是最大公约数的整数倍就好了。
另外要保证x+y>=z,因为如果x和y加起来的容量都没有z大,怎么可能使得两个罐中水量之和正好等于z呢。
代码如下:

class Solution {
private:
	int gcd(int x, int y) {
		return y == 0 ? x : gcd(y, x%y);
	}
public:
	bool canMeasureWater(int x, int y, int z) {
		return z == 0 || (x + y >= z&&z%gcd(x, y) == 0);
	}
};

本代码提交AC,用时0MS。

LeetCode Lexicographical Numbers

LeetCode Lexicographical Numbers
Given an integer n, return 1 - n in lexicographical order.
For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.


要求把1~n的n个数以字典序的方式输出。
明显不能先把int转换为string然后sort,这样肯定会超时。讨论区有一个大神的解法很厉害,学习一下,他通过枚举的方法一次性把1~n的字典序数组生成了。
假设我们枚举到当前数是cur,则下一个字典序的数是哪个呢。首先,下一个最小字典序的数肯定是末尾加0的,即cur*10。如果cur*10超过范围,则下一个最小字典序的数肯定是个数为加1,即cur+1。如果cur+1也超过范围了,则下一个最小字典序的数应该是十位数加1,个位数变为0,并且把个位删掉,即cur=cur/10+1。
代码如下:

class Solution {
public:
	vector<int> lexicalOrder(int n) {
		vector<int> ans;
		int cur = 1;
		for (int i = 1; i <= n; ++i) {
			ans.push_back(cur);
			if (cur * 10 <= n)cur *= 10;
			else if (cur % 10 != 9 && cur + 1 <= n)++cur;
			else {
				while ((cur / 10) % 10 == 9)cur /= 10;
				cur = cur / 10 + 1;
			}
		}
		return ans;
	}
};

本代码提交AC,用时168MS。
举个例子,假设cur=45,则下一个数首先是450;如果450超过n,则下一个数应该是46;如果46也超过范围,则下一个数应该是5。如果遇到cur=499,且跳到了第2个if,++cur==500,但是明显下一个数应该是5,所以不能进入第2个if,进入到第3个if,不断把末尾的9去掉,然后高位加1变为5。

LeetCode Bulb Switcher

LeetCode Bulb Switcher
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
Example:

Given n = 3.
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].
So you should return 1, because there is only one bulb is on.

给定n盏灯,第一轮是所有灯都是亮的;第二轮每两盏灯触发(亮变灭或灭变亮)一盏灯;第三轮每三盏灯触发一盏灯;如此循环直到第n轮只触发最后一盏灯。问最后有多少盏灯是亮着的。
首先模拟一把:

class Solution {
public:
	int bulbSwitch(int n) {
		if (n == 0)return 0;
		vector<int> bulbs(n + 1, 1);
		for (int i = 2; i <= n; ++i) {
			for (int j = 1; j*i <= n; ++j)bulbs[j*i] = !bulbs[j*i];
		}
		int ans = 0;
		for (int i = 1; i <= n; ++i)if (bulbs[i])++ans;
		return ans;
	}
};

本代码提交TLE,过不了大数据集。
然后就把前10的结果列出来了,在OEIS中找到了序列对应的公式:a(n) = floor(sqrt(n))。后来看了网上的题解,得到了这个通项公式的解释:
如果第i盏灯的i的因子有奇数个,则这盏灯最终是亮的,比如9有1,3,9这3个因子,则第9盏灯会分别在第1、3、9轮被触发,由于第1轮是变亮,经过奇数轮之后还是亮的。如果i的因子有偶数个,则类似的分析可知这盏灯最终是灭的。
那么哪些数的因子个数是奇数呢,只有完全平方数的因子个数是奇数,因为非完全平方数的因子都是成对出现的,比如8=1*8=2*4=4*2,而完全平方数有两个因子是重复的9=1*9=3*3,3相当于1个因子。
1~n有floor(sqrt(n))个完全平方数,所以结果就是floor(sqrt(n))。
代码如下:

class Solution {
public:
	int bulbSwitch(int n) {
		return floor(sqrt(n));
	}
};

本代码提交AC,用时3MS。