Tag Archives: 数学

LeetCode Set Mismatch

LeetCode Set Mismatch The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number. Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array. Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]

Note:

The given array size will in the range [2, 10000].
The given array’s numbers won’t have any order.

一个大小为n的数组，本来包含1~n这n个数，但是某个数x“突变”成y了，这就导致数组中丢了x，而y重复出现了两次，现在要找出丢掉的x和重复的y。简单题，首先用hash可以找到重复的y，然后根据数学关系可以找到x，本来1~n的和是S=n*(n+1)/2，设现在的和是T，则有x=y-T+S。代码如下： [cpp] class Solution { public: vector<int> findErrorNums(vector<int>& nums) { vector<int> ans(2, 0); unordered_set<int> hash; int sum = 0, n = nums.size(); for (const auto& num : nums) { if (hash.find(num) != hash.end())ans[0] = num; hash.insert(num); sum += num; } ans[1] = ans[0] – sum + n*(n + 1) / 2; return ans; } }; [/cpp] 本代码提交AC，用时59MS。还有一种空间复杂度O(1)的方法，不过需要改变原有数组。因为数组元素是1~n的，所以遍历数组，把数值-1当作下标访问数组，使该处的元素变为原来的相反数，如果遇到某个数y-1访问的那个数是负数，说明y重复了，之前有一个y把y-1处的数变成了负数。遍历完一遍之后，丢失的那个数x指向的x-1处的数应该是正数，因为x丢掉了，没有经过上面的过程，所以再遍历一遍可以找到x。整个过程不需要借助额外的空间，代码如下： [cpp] class Solution { public: vector<int> findErrorNums(vector<int>& nums) { vector<int> ans(2, 0); for (int i = 0; i < nums.size(); ++i) { int idx = nums[i] < 0 ? -nums[i] : nums[i]; if (nums[idx – 1] < 0) { ans[0] = idx; } else { nums[idx – 1] = -nums[idx – 1]; } } for (int i = 0; i < nums.size(); ++i) { if (nums[i] > 0) { ans[1] = i + 1; break; } } return ans; } }; [/cpp] 本代码提交AC，用时36MS。]]>

LeetCode Solve the Equation

Leave a reply

LeetCode Solve the Equation Solve a given equation and return the value of x in the form of string “x=#value”. The equation contains only ‘+’, ‘-‘ operation, the variable xand its coefficient. If there is no solution for the equation, return “No solution”. If there are infinite solutions for the equation, return “Infinite solutions”. If there is exactly one solution for the equation, we ensure that the value of x is an integer. Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"

Example 2:

Input: "x=x"
Output: "Infinite solutions"

Example 3:

Input: "2x=x"
Output: "x=0"

Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"

Example 5:

Input: "x=x+2"
Output: "No solution"

解一个一元一次方程。简单题，首先把方程分解成等号两边两个子表达式，然后解析这两个子表达式，使成为la+lb*x=ra+rb*x，再转换为(lb-rb)x=ra-la，令lb-rb=b, ra-la=a，则最终的表达式等价于bx=a。如果b等于0，且a也等于0，则有无穷多解。如果b等于0，但a不等于0，则无解。否则x=a/b。所以问题的难点是怎样把一个表达式转换为a+bx的形式。也就是代码中的convert函数。遍历字符串，取出每个带符号的操作数，如果该操作数包含’x’，则取出系数，加到b上；否则是常数项，加到a上。有一个需要注意的点是包含’x’的操作数可能是’-x’或者’+x’，提取系数时需要特殊判断。代码如下： [cpp] class Solution { private: void convert(string& s, int& a, int& b) { int aa = 0, bb = 0; s += "+"; int start = 0, end = 0; for (end = 0; end < s.size(); ++end) { if (end != 0 && (s[end] == ‘+’ || s[end] == ‘-‘)) { // -x=-1 string tmp = s.substr(start, end – start); if (tmp.find(‘x’) != string::npos) { if (tmp == "x" || tmp == "+x")bb += 1; else if (tmp == "-x")bb -= 1; else bb += stoi(tmp.substr(0, tmp.size() – 1)); } else { aa += stoi(tmp); } start = end; } } a = aa; b = bb; } public: string solveEquation(string equation) { size_t pos = equation.find(‘=’); string left = equation.substr(0, pos), right = equation.substr(pos + 1); int la = 0, lb = 0, ra = 0, rb = 0; convert(left, la, lb); convert(right, ra, rb); int b = lb – rb, a = ra – la; if (b == 0) { if (a == 0)return "Infinite solutions"; else return "No solution"; } else { return "x=" + to_string(a / b); } } }; [/cpp] 本代码提交AC，用时3MS。]]>

LeetCode Continuous Subarray Sum

Leave a reply

LeetCode Continuous Subarray Sum Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer. Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

The length of the array won’t exceed 10,000.
You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

给定一个非负整数数组和k，问数组中是否存在长度至少为2的连续子数组，子数组的和是k的n倍，n也是一个整数。这个题之前好像在哪遇到过。遇到连续子数组的问题，首先要想到前缀和。因为这里要求和是k的n倍，有点麻烦。首先我们需要知道一个数学知识，如果到i的前缀和accusum1和到j的前缀和accusum2除以k的余数相等，那么(i,j]的连续子数组的和就是k的整数倍。比如第一个样例中，连续子数组的和以及连续子数组的和除以k的余数：

[23,25,29,35,42]
[5,1,5,5,0]

如果下标从0开始，则下标为0和2的accusum%k都等于5，说明(0,2]的连续子数组的和是k的整数倍。accusum(0,2]=2+4=6，确实是6的整数倍。这个道理其实很好理解，accusum0%k=5，到了accusum2%k还等于5，说明中间只加了整数倍的k，才导致余数没变，因为整数倍的k 模k是等于0的。知道了这个道理就好办了，我们用map保存accusum%k的值和计算到现在的accusum的下标，如果后来遇到一个accusum模k的余数在map中，说明找到了一个可能，我们再判断一下他们之间的距离是否至少为2即可。还有一个特殊的地方需要注意的是，如果k等于0，则不能取模运算。最后还要注意的一点是，第12行，把当前余数和下标插入map是在else分支的，只有当map中不存在这个余数才插入，否则不插入。比如上面的例子，我们遇到多个accusum模k的余数是5，但是我们map中保存的应该是第0个下标，后续的余数等于5的下标不能更新0这个下标，因为这样才能使得后续的余数相等的下标和map中的下标的差越大，即更好的满足距离至少为2的约束。完整代码如下： [cpp] class Solution { public: bool checkSubarraySum(vector<int>& nums, int k) { unordered_map<int, int> reminders; reminders[0] = -1; int accusum = 0; for (int i = 0; i < nums.size(); ++i) { accusum += nums[i]; if (k != 0)accusum %= k; // 注意k为0时，不能取模 if (reminders.find(accusum) != reminders.end()) { if (i – reminders[accusum] >= 2)return true; } else reminders[accusum] = i; // 注意必须是在else分支 } return false; } }; [/cpp] 本代码提交AC，用时26MS。]]>

LeetCode Sum of Square Numbers

Leave a reply

LeetCode Sum of Square Numbers Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a² + b² = c. Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3
Output: False

给定一个非负整数c，问是否存在两个整数a和b，使得a² + b² = c。简单题，首尾指针法，首尾指针分别指向[0,c]，根据a² + b² 和 c的大小，首指针++或者尾指针–。但是这样性能太差，过不了大数据，其实尾指针只需要到sqrt(c)即可，因为如果b大于sqrt(c)的话，a² + b² 肯定大于 c的。所以新的首尾指针范围就是[0,sqrt(c)]，性能大幅提升。代码如下： [cpp] class Solution { public: bool judgeSquareSum(int c) { long long i = 0, j = sqrt(c) + 1; while (i <= j) { long long cur = i*i + j*j; if (cur == c)return true; else if (cur < c)++i; else –j; } return false; } }; [/cpp] 本代码提交AC，用时3MS。]]>

LeetCode Minimum Factorization

Leave a reply

LeetCode Minimum Factorization Given a positive integer a, find the smallest positive integer b whose multiplication of each digit equals to a. If there is no answer or the answer is not fit in 32-bit signed integer, then return 0. Example 1 Input:

Output:

Example 2 Input:

Output:

给定一个数a，要求找一个最小的数b，使得b的各位数字相乘的结果等于a。很有意思的一个题，考察数学，当时没做出来，参考了这个题。首先，如果a小于10的话，那么最小的b就是a了，否则b就要变成十位数或者百位数。比如a=8，则最小的b就是8，当然b也可以是十位数比如24或者42，但是都大于个位数8自己。当a大于等于10时，我们需要找a的因子，为了是b最小，则我们希望b的位数越少越好。所以我们要找b的因子应该越大越好。所以我们从最大的因子9开始找起，从9一直找到2，把a的所有因子都找出来。比如48从大到小的因子是8和6，则最终结果就是把因子从小到大组成一个数，即68。这里有一个问题，48的因子还可以是4和2呀，为什么没有了呢。因为我们从9→2开始找因子的过程中，是用a除以因子得到的商来不断的找。上面48找到8和6的因子之后，商就等于1了，不需要再找因子了，所以结束。如果在找因子的过程中，发现商变成了一个质数，因为大于10的质数不可能被分解，所以无解，返回0。代码如下： [cpp] class Solution { public: int smallestFactorization(int a) { if (a < 10)return a; vector<int> factors; for (int i = 9; i >= 2; –i) { while (a%i == 0) { factors.push_back(i); a /= i; } } if (a != 1)return 0; // caution long long ans = 0; for (int i = factors.size() – 1; i >= 0; –i) { ans = ans * 10 + factors[i]; } return ans > INT_MAX ? 0 : ans; } }; [/cpp] 本代码提交AC，用时3MS。]]>

LeetCode Valid Triangle Number

Leave a reply

LeetCode Valid Triangle Number Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle. Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:

The length of the given array won’t exceed 1000.
The integers in the given array are in the range of [0, 1000].

给定一个数组，问从中能取出所少个三元数组，使得取出的三个数能构成一个三角形。首先明确三条线段构成三角形的条件是任意两边之和要大于第三遍。先上暴力，直接dfs枚举出所有的三元组，判断能构成三角形，则方案数加1。代码如下： [cpp] class Solution { private: void dfs(int &ans, vector<int>& nums, vector<int>& cand, int idx) { if (cand.size() == 3) { int &a = cand[0], &b = cand[1], &c = cand[2]; if (a + b > c&&a + c > b&&b + c > a) { ++ans; //cout << a << "\t" << b << "\t" << c << endl; } return; } for (int i = idx; i < nums.size(); ++i) { if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return; cand.push_back(nums[i]); dfs(ans, nums, cand, i + 1); cand.pop_back(); } } public: int triangleNumber(vector<int>& nums) { int ans = 0; vector<int> cand; sort(nums.begin(), nums.end()); dfs(ans, nums, cand, 0); return ans; } }; [/cpp] 本代码提交TLE：219 / 243。数组最大长度是1000，则所有的组合数有1000*999*998=997002000，确实有点大。。。后来我发现，报TLE的大数据，虽然有1000个数，但是有很多都是重复的，真正不同的数大概只有100个左右。所以我就想，先对数据去重，在所有互异的数中dfs。然后根据每条边重复的次数来求组合数。比如样例中，互异的数是[2,3,4]，dfs发现[2,3,4]可以构成三角形，则所有由[2,3,4]构成的三角形的个数应该是count[2]*count[3]*count[4]=2*1*1=2。所以我们先对数组做个hash，统计数值及其出现频率的关系。注意，因为边的长度最大也只为1000，所以用一个1000长的数组来hash比用map或者unordered_map占用的内存更少，否则会MLE。然后分三类情况进行计算：1. 三条边互不相同；2.有两条边的值相等；3.三条边的值都相等。其中第一种情况用常规的DFS求解。第二种和第三种情况就是简单的枚举。还需要注意一点是，边长为0的值需要过滤掉。完整代码如下： [cpp] class Solution { private: void dfs(int& ans, vector<int>& count, vector<int>& nums, vector<int>& cand, int idx) { if (cand.size() == 3) { int &a = cand[0], &b = cand[1], &c = cand[2]; if (a + b > c&&a + c > b&&b + c > a) { ans += count[a] * count[b] * count[c]; // 三边各异 //cout << a << "\t" << b << "\t" << c << endl; } return; } for (int i = idx; i < nums.size(); ++i) { if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return; cand.push_back(nums[i]); dfs(ans, count, nums, cand, i + 1); cand.pop_back(); } } public: int triangleNumber(vector<int>& nums) { vector<int> mii(1001, 0); for (const auto& i : nums)++mii[i]; // hash vector<int> distinct; for (int i = 1; i < 1001; ++i) { if (mii[i] > 0)distinct.push_back(i); } int ans = 0; vector<int> cand; dfs(ans, mii, distinct, cand, 0); // 三边互不相同 int n = distinct.size(); for (int i = 0; i < n; ++i) { if (mii[distinct[i]] >= 3) { // 三边相同 int &d = mii[distinct[i]]; ans += (d*(d – 1)*(d – 2)) / 6; } for (int j = i + 1; j < n; ++j) { if (mii[distinct[i]] >= 2) { // 两条边一样 int &a = distinct[i], &b = distinct[i], &c = distinct[j]; if (a + b > c&&a + c > b&&b + c > a) { ans += (mii[a] * (mii[a] – 1) / 2)*mii[c]; } } if (mii[distinct[j]] >= 2) { // 两条边一样 int &a = distinct[i], &b = distinct[j], &c = distinct[j]; if (a + b > c&&a + c > b&&b + c > a) { ans += (mii[b] * (mii[b] – 1) / 2)*mii[a]; } } } } return ans; } }; [/cpp] 本代码提交AC，用时1589MS。]]>

LeetCode Rotate Function

Leave a reply

LeetCode Rotate Function Given an array of integers A and let n to be its length. Assume B_k to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow: F(k) = 0 * B_k[0] + 1 * B_k[1] + ... + (n-1) * B_k[n-1]. Calculate the maximum value of F(0), F(1), ..., F(n-1). Note: n is guaranteed to be less than 10⁵. Example:

A = [4, 3, 2, 6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

给定一个数组A，和函数F(k)，其中F(k) = 0 * B_k[0] + 1 * B_k[1] + … + (n-1) * B_k[n-1]，数组B为数组A顺时针旋转k次后的新数组。要求所有F(k)的最大值。仔细观察样例，会发现$$F(k)=\sum_{i=0}^{n-1}((k+i)\%n)*a_i$$。于是可以算出所有的F(k)，然后求最大值。代码如下： [cpp] class Solution { public: int maxRotateFunction(vector<int>& A) { if (A.empty())return 0; int ans = INT_MIN, n = A.size(); for (int k = 0; k < n; ++k) { int cur = 0; for (int i = 0; i < n; ++i) { cur += ((k + i) % n)*A[i]; } ans = max(ans, cur); } return ans; } }; [/cpp] 本代码提交TLE，复杂度是O(kn)，遇到大数据时超时了。如果再仔细研究一下样例，会发现一个更优的递推公式：$$F(k)=F(k-1)+sum-n*A[n-k]$$。这样直接根据前一项F(k-1)，可以在O(1)时间算出下一项F(k)。总的时间复杂度只有O(n)。代码如下： [cpp] class Solution { public: int maxRotateFunction(vector<int>& A) { if (A.empty())return 0; int n = A.size(), sum = 0, f0 = 0; for (int i = 0; i < n; ++i) { sum += A[i]; f0 += i*A[i]; } int ans = f0, pre = f0; for (int i = 1; i < n; ++i) { int cur = pre + sum – n * A[n – i]; ans = max(ans, cur); pre = cur; } return ans; } }; [/cpp] 本代码提交AC，用时16MS。]]>

LeetCode Super Pow

Leave a reply

LeetCode Super Pow Your task is to calculate a^b 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}$$。完整代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时9MS。]]>

LeetCode Valid Square

Leave a reply

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:

All the input integers are in the range [-10000, 10000].
A valid square has four equal sides with positive length and four equal angles (90-degree angles).
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。完整代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时6MS。解法2，特征法。任何一个正方形，如果求出所有点之间的距离，则这些距离只可能有两种取值，一种是邻边全相等，另一种是对角边也相等。所以我们只需要用一个map保存不同边的长度以及出现的频率即可，如果最终只有两个映射，则是正方形，否则不是。注意当出现边长为0时，说明两点重合，不能构成正方形。代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时9MS。不过上述代码有局限性，如果顶点都只是整数，则没有问题，但是如果顶点可以是实数，则会有问题。比如等边三角形的三个点和三角形的中心点，这四个点两两之间只有2种不同的距离，但他们不能构成正方形。可以再加一个限制条件，即两种不同长度的边的频率一个是4，一个是2，且出现2次的边长是出现4次的边长的两倍。讨论区见：https://discuss.leetcode.com/topic/89985/c-3-lines-unordered_set/4]]>

LeetCode Array Nesting

Leave a reply

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:

N is an integer within the range [1, 20,000].
The elements of A are all distinct.
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)。代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时39MS。]]>

bitJoy > code

Keep calm and carry on coding

Tag Archives: 数学

LeetCode Set Mismatch

LeetCode Solve the Equation

LeetCode Continuous Subarray Sum

LeetCode Sum of Square Numbers

LeetCode Minimum Factorization

LeetCode Valid Triangle Number

LeetCode Rotate Function

LeetCode Super Pow

LeetCode Valid Square

LeetCode Array Nesting