Tag Archives: 找规律

LeetCode Arithmetic Slices

Leave a reply

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个小的等差数列。 于是问题就转换为找出数组中所有最长连续等差数列，然后代入上述公式计算。 完整代码如下： [cpp] 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); } }; [/cpp] 本代码提交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不贡献小等差数列。 这种解法的代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时3MS。 DP一般都可以优化空间，上面的解法也可以不用一个dp数组，而只用一个变量。如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时也是3MS。]]>

LeetCode Nim Game

Leave a reply

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

Example:

Input: 4 Output: false  Explanation: 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. 292. Nim Game

博弈论的题。两个人轮流拿石头，一次可以拿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。
类似博弈论的题，一定要在纸上写几个例子出来，然后仔细找规律。

LeetCode Counting Bits

Leave a reply

LeetCode Counting Bits Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array. Example: For num = 5 you should return [0,1,1,2,1,2]. Follow up:

  • It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
  • Space complexity should be O(n).
  • Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
Hint:
  1. You should make use of what you have produced already.
  2. Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
  3. Or does the odd/even status of the number help you in calculating the number of 1s?
这一题很有意思，给定数字num，要把0~num之间每个数的二进制中1的个数列出来，比如num=5时，需要计算0,1,2,3,4,5这6个数字每个数字的二进制中，1的个数，分别是0,1,1,2,1,2。 这样就不能用LeetCode Number of 1 Bits的方法对每个数都求一遍了，复杂度肯定太高了。这题一看就知道是找规律的题，所以我们先把前几个数的二进制1的个数列出来看看。   观察的时候需要分组观察，比如[0,1]的结果为0,1，[2,3]的结果为1,2，也就是在[0,1]的结果上加了1；[4,7]的结果为1,2,2,3，也就是在[0,3]的结果上加了1；[8,15]的结果为1,2,2,3,2,3,3,4，也就是在[0,7]的结果上加了1。 所以重复的周期是以2的幂递增的，初始的时候，我们可以在ans数组中只存[0,1]的结果，然后每次添加2的幂个结果进ans，直到ans的大小大于num为止。 完整代码如下： [cpp] class Solution { public: vector<int> countBits(int num) { vector<int> ans = { 0,1 }; while (ans.size() <= num) { int old_size = ans.size(); for (int i = 0; i < old_size; ++i) { ans.push_back(ans[i] + 1); } } return vector<int>(ans.begin(), ans.begin() + num + 1); } }; [/cpp] 本代码提交AC，用时73MS。 ]]>