Commonly Used Variables in Falcor

08/27/2017

Permutation:

http://blog.csdn.net/hackbuteer1/article/details/6657435

Tomorrow:

CORDIC

532. K-diff Pairs in an Array

Description:

https://leetcode.com/problems/k-diff-pairs-in-an-array/description

Code:

Time & Space:
O(nlog(n)) & O(n)

217. Contains Duplicate

Description:

https://leetcode.com/problems/contains-duplicate/#/description

Algorithm:

  1. Use sort, very easy
  2. Don’t use sort, use a array to record the appearance of words. If a word appears for more than 1 times, return true.

Code1:

class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
if (nums.size() < 2) return false;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 1;i++)
{
if (nums[i] == nums[i+1])
return true;
}
return false;
}
};

Code2:

class Solution {
public:
bool containsDuplicate(vector& nums) {
int min = INT_MAX;
int max = INT_MIN;
for (int i = 0; i < nums.size(); ++i) { if (nums[i] > max) {
max = nums[i];
}

if (nums[i] < min) { min = nums[i]; } } vector exists(max - min + 1, false);
for (int i = 0; i < nums.size(); ++i) { if (exists[nums[i] - min]) { return true; } else { exists[nums[i] - min] = true; } } return false; } };

Time & Space:

Code1:

Time: O(nlogn) Space O(1)

Code2:

Time: O(n), Space O(n)

16. 3Sum Closest

 

Description:

https://leetcode.com/problems/3sum-closest/#/description

Algirithm:

One for loop and squeeze from left and right. This is similar to the solution of ThreeSum.

Code: (6ms, the fastest 🙂 )

class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
if (nums.size() == 3)
return nums[0] + nums[1] + nums[2];

sort(nums.begin(), nums.end());
int result = 10000;
int result_tmp = 10000;
for (int i = 0; i < nums.size() – 2; i++)
{
int left = i + 1;
int right = nums.size() – 1;
while (left < right)
{
int tmp = nums[i] + nums[left] + nums[right] – target;
result_tmp = (abs(result_tmp) < abs(tmp)) ? result_tmp : tmp;
if (tmp < 0)
left++;
else if (tmp > 0)
right–;
else
return target;
}
}
return result_tmp + target;
}
};