Tag Archives: 找规律

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。

LeetCode Count Numbers with Unique Digits

LeetCode Count Numbers with Unique Digits
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])
Hint:

  1. A direct way is to use the backtracking approach.
  2. Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to 10n.
  3. This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.
  4. Let f(k) = count of numbers with unique digits with length equals k.
  5. f(1) = 10, ..., f(k) = 9 * 9 * 8 * ... (9 - k + 2) [The first factor is 9 because a number cannot start with 0].

给定n,问在[0,10n)内有多少个每一位都是不同数字的数。比如当n=2时,在[0,100)内,有91个这样的数,需要排除个位和十位数字相同的9个数。
其实这个题很简单,假设k表示数的位数,找一下规律:

  • k=1,一位数,可以填入0~9这10个数,结果为10
  • k=2,两位数,十位填入1~9这9个数,个位填入0~9中除了十位的那个数字,有9种情况,结果为9*9
  • k=3,三位数,百位填入1~9这9个数字,十位填入0~9中除了百位的那个数字,有9种情况,个位填入0~9中除了百位和十位的那两个数字,有8种情况,结果为9*9*8
  • ...
  • k=n,结果为9*9*8*...*(9-n+2)

所以我们可以用DP解题,f(k)=f(k-1)*(9-k+2),为了节省空间,只需保存上一次的结果f(k-1)。在DP的过程中,累加f(k)的结果。
代码如下:

class Solution {
public:
	int countNumbersWithUniqueDigits(int n) {
		if (n == 0)return 1;
		if (n == 1)return 10;
		int ans = 10, last = 9;
		for (int i = 2; i <= n; ++i) {
			last *= (9 - i + 2);
			ans += last;
		}
		return ans;
	}
};

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

LeetCode Queue Reconstruction by Height

LeetCode Queue Reconstruction by Height
Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.
Note:
The number of people is less than 1,100.
Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

本题给了一个存储pair的数组,每个pair是一个(h,k)对,表示身高为h的人,其前面有k个身高大于等于h的人。现在要对这个数组重新排序,使得所有pair都满足其自己的(h,k)约束。
网上有一种很巧妙的方法,先对数组排序,排序规则是h大的在前,如果h相等,则k小的在前。然后新建一个数组,把每个pair插入到下标k的位置。
我们来举个例子,比如样例数据,先按上述规则排序之后变成了:
[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
上述排序规则基于这样一个事实:h越小的,其前面比h大的数越多,越有可能满足其k约束;h相同时,肯定是k小的排前面,因为相同的h对k是有贡献的。
然后新建一个空的数组,不断把上述排好序的元素插入空数组中。

  1. [7,0]插入第0个位置,数组为[7,0]
  2. [7,1]插入第1个位置,数组为[7,0], [7,1]
  3. [6,1]插入第1个位置,数组为[7,0], [6,1], [7,1]
  4. [5,0]插入第0个位置,数组为[5,0], [7,0], [6,1], [7,1]
  5. [5,2]插入第2个位置,数组为[5,0], [7,0], [5,2], [6,1], [7,1]
  6. [4,4]插入第4个位置,数组为[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]

完整代码如下:

bool comp(const pair<int, int>& p1, const pair<int, int>& p2) {
	return p1.first > p2.first || (p1.first == p2.first&&p1.second < p2.second);
}
class Solution {
public:
	vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
		sort(people.begin(), people.end(), comp);
		vector<pair<int, int>> ans;
		for (int i = 0; i < people.size(); ++i) {
			ans.insert(ans.begin() + people[i].second, people[i]);
		}
		return ans;
	}
};

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

LeetCode Integer Break

LeetCode Integer Break
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).
Note: You may assume that n is not less than 2 and not larger than 58.
Hint:

  1. There is a simple O(n) solution to this problem.
  2. You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

给定一个数n,要求把其拆分成至少两个数的和,使得他们的乘积最大。
数学题,没啥思路,参考网上题解
把0~10的结果先列出来找找规律:

  • 0:0
  • 1:0
  • 2:1=1*1
  • 3:2=2*1
  • 4:4=2*2
  • 5:6=3*2
  • 6:9=3*3
  • 7:12=3*4
  • 8:18=3*3*2
  • 9:27=3*3*3
  • 10:36=3*3*4

可以发现,n从5开始,都至少分解出来一个3,可以推断的是,当n=11时,在10的基础上,把最后一个4改成5,然后5又可以分解成3*2,所以11=3+3+3+2使得乘积最大。
4只能分解出2+2,1+3的乘积是3小于2*2;5可以分解出3+2,所以也有3。也就是说,当n大于4时,不断分解出3来,直到剩余的数小于4为止。所以有如下代码:

class Solution {
public:
	int integerBreak(int n) {
		if (n <= 3)return n - 1;
		int ans = 1;
		while (n > 4) {
			ans *= 3;
			n -= 3;
		}
		return ans*n;
	}
};

本代码提交AC,用时0MS。
再次观察上述规律,n=10的结果是n=7=10-3的结果乘以3;n=9的结果也是n=6=9-3的结果乘以3。可以推断,n的结果是(n-3)的结果乘以3。所以先列出前几个结果,后面的结果通过其前3的结果乘以3推导得到。代码如下:

class Solution {
public:
	int integerBreak(int n) {
		vector<int> dp = { 0,0,1,2,4,6,9 };
		for (int i = 7; i <= n; ++i)dp.push_back(dp[i - 3] * 3);
		return dp[n];
	}
};

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

LeetCode Bitwise AND of Numbers Range

LeetCode Bitwise AND of Numbers Range
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.


求把从m~n的所有整数相与的结果。
暴力方法就是从m到n遍历一遍,把所有数都相与一下。但是TLE。
这题明显是个数学题或者找规律题。网上的解法大多数是这样的,把m~n的所有数相与的结果等于m和n这两个数的二进制的最长公共前缀。比如题目中的[5,7],5和7的二进制分别为101和111,最长公共前缀就是100=4,后两位不一样也要补0。再比如[26,30],26和30的二进制分别为11010和11110,最长公共前缀为11000=24。
知道这个规律就好办了,因为m和n都是正数,不断同时把m和n往右移,直到他们相等,最后再把m往左移回去就是最终结果。代码如下:

class Solution {
public:
	int rangeBitwiseAnd(int m, int n) {
		int offset = 0;
		while (m != n) {
			m >>= 1;
			n >>= 1;
			++offset;
		}
		return m << offset;
	}
};

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

LeetCode Elimination Game

LeetCode Elimination Game
There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.
We keep repeating the steps again, alternating left to right and right to left, until a single number remains.
Find the last number that remains starting with a list of length n.
Example:

Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
Output:
6

本题介绍了一个消除游戏,就是1~n排列了n个数,先从左往右每隔一个数消除一个(包含1),然后从右往左每隔一个数消除一个(包含最后一个数),如此循环,直到只剩一个数,要求输出这个数。
我一开始以为这是个模拟题,直接用STL的双向链表list模拟了,代码如下:

class Solution {
public:
	int lastRemaining(int n) {
		list<int> l;
		for (int i = 1; i <= n; i++)l.push_back(i);
		while (l.size() != 1) {
			list<int>::iterator it = l.begin();
			while (it != l.end()) {
				it = l.erase(it);
				if (it != l.end())++it;
			}
			if (l.size() == 1)break;
			list<int>::reverse_iterator rit = l.rbegin();
			while (rit != l.rend()) {
				rit = list<int>::reverse_iterator(l.erase(--(rit.base())));
				if (rit != l.rend())++rit;
			}
			if (l.size() == 1)break;
		}
		return *l.begin();
	}
};

很不幸,本代码提交TLE,超时了。
网上查题解,这个人讲得比较清楚。一开始1,2,3,4,5,6,7,8,...,n,第一次从左往右消除之后,剩余2,4,6,8...,n,其实就相当于2*(1,2,3,4,...n/2)。但是这个时候我们要对1,2,3,4,...n/2从右往左消除了,那么从右往左和从左往右消除得到的结果有什么规律呢,他们的结果应该是呈镜像对称的,也就是说如果长度为n/2的话,如果从左往右的结果为x,那么从右往左的结果就应该是n/2+1-x;同理如果从右往左的结果是y的话,那么从左往右的结果就应该是n/2+1-y。
代码实现为:

class Solution {
public:
	int lastRemaining(int n) {
		return n == 1 ? 1 : 2 * (n / 2 + 1 - lastRemaining(n / 2));
	}
};

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

LeetCode Magical String

LeetCode Magical String
A magical string S consists of only '1' and '2' and obeys the following rules:
The string S is magical because concatenating the number of contiguous occurrences of characters '1' and '2' generates the string Sitself.
The first few elements of string S is the following: S = "1221121221221121122……"
If we group the consecutive '1's and '2's in S, it will be:
1 22 11 2 1 22 1 22 11 2 11 22 ......
and the occurrences of '1's or '2's in each group are:
1 2 2 1 1 2 1 2 2 1 2 2 ......
You can see that the occurrence sequence above is the S itself.
Given an integer N as input, return the number of '1's in the first N number in the magical string S.
Note: N will not exceed 100,000.
Example 1:

Input: 6
Output: 3
Explanation: The first 6 elements of magical string S is "12211" and it contains three 1's, so return 3.

这道题给了一个magic字符串,具体怎么magic题目说得很清楚了。这个字符串只包含字符1和2,依次计算字符串中连续的1或2出现的次数,把这些数字串起来,构成的一个新的字符串和原字符串是完全一样的!然后问字符串中前n个字符出现1的次数。
这是一个模拟题,我们根据magic的规则模拟生成这个字符串,然后统计一下前n个字符中1出现的次数。
模拟的方法就是把字符串中的数当做原字符串中1或2出现的次数,然后不断在原字符串中追加新的字符。比如开始是122:1表示1出现1次;第一个2表示出现两次,因为前面有1出现1次的约束,所以出现两次的只可能是2;第二个2也表示出现两次,因为前面已经出现了两个2了,所以这里不能再接两个2了(要不然就出现4个2了),只能表示出现了两次1,所以我们可以在原字符串中追加两个1,变为12211。如此不断的模拟下去,直到字符串长度满足要求。
完整代码如下:

class Solution {
public:
	int magicalString(int n) {
		string magic = "122";
		int pos = 2;
		while (magic.size() < n) {
			switch (magic[magic.size()-1])
			{
			case '1':
				magic += string(magic[pos] - '0', '2');
				break;
			case '2':
				magic += string(magic[pos] - '0', '1');
				break;
			}
			++pos;
		}
		int ans = 0;
		for (int i = 0; i < n; ++i) {
			ans += magic[i] == '1' ? 1 : 0;
		}
		return ans;
	}
};

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

LeetCode Single Number II

LeetCode Single Number II
Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?


数组中有出现3次的数,但是也有一个出现1次的数,现在要把这个只出现1次的数找出来。要求是线性时间复杂度和常数空间复杂度。
相比于LeetCode Single Number有难度。网上看到一个很不错的题解,分析得很详细。
初级解法是,把数组中每个数字的对应二进制位加起来,因为3个相同的数对应二进制位加起来之后模3一定等于0,比如5的二进制为101,三个101加起来就是303,每一位模3就是000。所以如果混入了一个只出现一次的数,这样取模之后,剩余位为1的就是我们要找的数的二进制形式。
这种解法需要一个32位的数组,用来统计所有数每一位出现1的次数之和,所以空间复杂度是O(32)=O(1)。时间复杂度的话,相当于O(32n)=O(n),是线性的。完整代码如下:

class Solution {
public:
	int singleNumber(vector<int>& nums) {
		int bit_len = sizeof(int) * 8;
		vector<int> bit(bit_len, 0);
		for (int i = 0; i < bit_len; ++i) {
			for (int j = 0; j < nums.size(); ++j) {
				bit[i] += (nums[j] & 1);
				nums[j] >>= 1;
			}
		}
		int ans = 0;
		for (int i = 0; i < bit_len; ++i) {
			int r = bit[i] % 3;
			ans |= (r << i);
		}
		return ans;
	}
};

本代码提交AC,用时12MS。
高级解法是,使用三个int的每一位表示所有数每一位出现1次数之和的情况,one对应位为1表示这一位出现了1次1,two对应位为1表示这一位出现了2次1,three对应位为1表示这一位出现了3次1。但是one,two,three对应位不可能都同时为1。
通过分析对应位的关系(请看原博客),发现one,two,three可以快速通过位运算计算得到。完整代码如下:

class Solution {
public:
	int singleNumber(vector<int>& nums) {
		int one = 0, two = 0, three = 0;
		for (int i = 0; i < nums.size(); ++i) {
			two |= (one&nums[i]);
			one ^= nums[i];
			three = one&two;
			one -= three;
			two -= three;
		}
		return one;
	}
};

本代码提交AC,用时15MS。
初级解法还是好理解一些,会不会是一个通用的解法呢,比如数组中出现1次和出现4次(甚至k次)的数混在一起,都可以通过模k求解呢?

LeetCode Arithmetic Slices

LeetCode Arithmetic Slices
A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

 
A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.
A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.
The function should return the number of arithmetic slices in the array A.
 
Example:

A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

本题要求一个数组中等差数列的个数,并不要求是最长的等差数列。比如给的例子中数组A=[1,2,3,4],可以抽出3个等差数列,分别是[1,2,3]、[2,3,4]、[1,2,3,4]。
首先还是找特征,我们可以在数组中先找出最长的等差数列,然后在等差数列的基础上抽取(Slice)出比较小的等差数列,所以先研究一下长度为n的等差数列可以抽出多少个小的等差数列。

  • n=3,抽出1个
  • n=4,抽出3=1+2个,即1个长度为4的和2个长度为3的
  • n=5,抽出6=1+2+3个,即1个长度为5的、2个长度为4的和3个长度为3的
  • n=6,抽出10=1+2+3+4个,即...
  • ...

由此可以得出规律,长度为n的等差数列,可以抽出1+2+...+(n-2)=(n-1)(n-2)/2个小的等差数列。
于是问题就转换为找出数组中所有最长连续等差数列,然后代入上述公式计算。
完整代码如下:

class Solution {
public:
	inline int slice(int cnt) {
		if (cnt < 3)return 0;
		if (cnt == 3)return 1;
		return (cnt - 1)*(cnt - 2) / 2; // 1+2+...+(cnt-2)
	}
	int numberOfArithmeticSlices(vector<int>& A) {
		if (A.size() < 3)return 0;
		int ans = 0, cnt = 2, diff = A[1] - A[0];
		for (int i = 2; i < A.size(); ++i) {
			if (A[i] - A[i - 1] == diff) {
				++cnt;
			}
			else {
				ans += slice(cnt);
				cnt = 2;
				diff = A[i] - A[i - 1];
			}
		}
		return ans + slice(cnt);
	}
};

本代码提交AC,用时3MS。
网上还有一种DP解法,我们看看上面的规律,当n从4增加到5时,抽取出来的小等差数列增加了3个,是在n=4时,最后+2的基础上+1=3;当n从5增加到6时,抽取出来的小等差数列增加了4个,是在n=5时,最后+3的基础上+1=4。
所以我们设置一个dp数组,dp[i]表示:如果第i个元素和前面构成等差数列了,则能贡献多少个小等差数列,根据前面的分析,dp[i]=dp[i-1]+1,这里的dp相当于比如n=6时的10=1+2+3+4(等号右边的数组);如果第i个元素不和前面构成等差数列,则dp[i]=0不贡献小等差数列。
这种解法的代码如下:

class Solution {
public:
	int numberOfArithmeticSlices(vector<int>& A) {
		if (A.size() < 3)return 0;
		int ans = 0;
		vector<int> dp(A.size(), 0);
		for (int i = 2; i < A.size(); ++i) {
			if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
				dp[i] = dp[i - 1] + 1;
			}
			ans += dp[i];
		}
		return ans;
	}
};

本代码提交AC,用时3MS。
DP一般都可以优化空间,上面的解法也可以不用一个dp数组,而只用一个变量。如下:

class Solution {
public:
	int numberOfArithmeticSlices(vector<int>& A) {
		if (A.size() < 3)return 0;
		int ans = 0, cur = 0;
		for (int i = 2; i < A.size(); ++i) {
			if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
				++cur;
			}
			else {
				cur = 0;
			}
			ans += cur;
		}
		return ans;
	}
};

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

LeetCode Nim Game

LeetCode Nim Game
You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
Hint:

  1. If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?

博弈论的题。两个人轮流拿石头,一次可以拿1~3个,拿掉最后一个石头的人获胜。规定我先拿,问如果石头数为n时,我是否可以取胜。
看Hint,找规律。

  • 如果n∈[1,3],则我第一次拿就可以把所有石头拿走,所以我肯定可以获胜。
  • 如果n=4,则无论我第一次拿多少个,因为我最多可以拿3个,所以剩下的石头数转换为了n∈[1,3]的情况,也就是变成了对手肯定能获胜的情况。
  • 如果n∈[5,7],则我为了获胜,可以想方设法让我第一次拿了之后,剩余4个石头,这样相当于对手遇到n=4的情况,于是转换为我可以获胜的情况。
  • 如果n=8,则无论第一次拿多少个,剩余的石头个数都转换为了n∈[5,7]的情况,也就变成了对手必胜的情况。
  • ...

观察以上的分析,发现当n是4的倍数时,我必输;否则我必胜。代码就很好写了:

class Solution {
public:
	bool canWinNim(int n) {
		return n % 4 != 0;
	}
};

本代码提交AC,用时0MS。
类似博弈论的题,一定要在纸上写几个例子出来,然后仔细找规律。