August 2017 – Page 2

442. Find All Duplicates in an Array

Description:

https://leetcode.com/problems/find-all-duplicates-in-an-array/description/

Code:

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> result;
        for (int i = 0; i < nums.size();i++)
        {
            if (nums[i]!= i+1)
            {
                while (nums[nums[i] - 1] != nums[i])
                    swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < nums.size();i++)
        {
            if (nums[i]!= i+1)
                result.push_back(nums[i]);
        }
        return result;
    }
};

class Solution {

public:

vector<int> findDuplicates(vector<int>& nums) {

vector<int> result;

for (int i = 0; i < nums.size();i++)

{

if (nums[i]!= i+1)

{

while (nums[nums[i] - 1] != nums[i])

swap(nums[i], nums[nums[i] - 1]);

}

for (int i = 0; i < nums.size();i++)

{

if (nums[i]!= i+1)

result.push_back(nums[i]);

}

return result;

}

};

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

448. Find All Numbers Disappeared in an Array

Description:

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/description/

Code:

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> result;
        for (int i = 0; i < nums.size();i++)
        {
            if (nums[i]!= i+1)
            {
                while (nums[nums[i] - 1] != nums[i])
                    swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < nums.size();i++)
        {
            if (nums[i]!= i+1)
                result.push_back(i+1);
        }
        return result;
    }
};

class Solution {

public:

vector<int> findDisappearedNumbers(vector<int>& nums) {

vector<int> result;

for (int i = 0; i < nums.size();i++)

{

if (nums[i]!= i+1)

{

while (nums[nums[i] - 1] != nums[i])

swap(nums[i], nums[nums[i] - 1]);

}

for (int i = 0; i < nums.size();i++)

{

if (nums[i]!= i+1)

result.push_back(i+1);

}

return result;

}

};

Code for fastest algorithm:

class Solution {
public:
	vector<int> findDisappearedNumbers(vector<int>& nums) {
		vector<int>result;
		for (int i = 0; i < nums.size(); i++)
		{
			int n = abs(nums[i]) - 1;
			nums[n] = nums[n] > 0 ? -nums[n] : nums[n];
		}
		for (int i = 0; i < nums.size(); i++)
		{
			if (nums[i] > 0) result.push_back(i + 1);
		}
		return result;
	}
};

class Solution {

public:

vector<int> findDisappearedNumbers(vector<int>& nums) {

vector<int>result;

for (int i = 0; i < nums.size(); i++)

{

int n = abs(nums[i]) - 1;

nums[n] = nums[n] > 0 ? -nums[n] : nums[n];

}

for (int i = 0; i < nums.size(); i++)

{

if (nums[i] > 0) result.push_back(i + 1);

}

return result;

}

};

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

495. Teemo Attacking

Description:

https://leetcode.com/problems/teemo-attacking/description/

Code:

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        if (timeSeries.size() == 0) return 0;
        int time = duration;
        for (int i = 0; i < timeSeries.size() - 1;i++)
        {
            if (timeSeries[i+1] > timeSeries[i] + duration - 1)
                time += duration;
            else
                time += timeSeries[i+1] - timeSeries[i];
        }
        
        return time;
    }
};

class Solution {

public:

int findPoisonedDuration(vector<int>& timeSeries, int duration) {

if (timeSeries.size() == 0) return 0;

int time = duration;

for (int i = 0; i < timeSeries.size() - 1;i++)

{

if (timeSeries[i+1] > timeSeries[i] + duration - 1)

time += duration;

else

time += timeSeries[i+1] - timeSeries[i];

}

return time;

}

};

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

532. K-diff Pairs in an Array

Description:

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

Code:

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (nums.size() == 0) return 0;
        if (k < 0) return 0;
        int result = 0;
        if (k == 0)
		{
			sort(nums.begin(), nums.end());
			int switcher = 0;
			for (int i = 0; i < nums.size() - 1; i++)
			{
				if (nums[i + 1] == nums[i])
				{
					if (switcher == 0)
					{
						result++;
						switcher = 1;
					}
				}
				else
				{
					switcher = 0;
				}
			}
		}
        else
        {
            unordered_map< int, int> mapping;
            sort(nums.begin(), nums.end());
			nums.erase(unique(nums.begin(), nums.end()), nums.end());
            
            for (int i = 0; i < nums.size(); ++i)
            {
                mapping[nums[i]] = i;
            }
            for (int i = 0; i < nums.size(); ++i)
            {
                int target = nums[i] + k;
                if (mapping.find(target) != mapping.end())
                    result++;
            }
        }
        return result;
    }
};

class Solution {

public:

int findPairs(vector<int>& nums, int k) {

if (nums.size() == 0) return 0;

if (k < 0) return 0;

int result = 0;

if (k == 0)

{

sort(nums.begin(), nums.end());

int switcher = 0;

for (int i = 0; i < nums.size() - 1; i++)

{

if (nums[i + 1] == nums[i])

{

if (switcher == 0)

{

result++;

switcher = 1;

}

else

{

switcher = 0;

}

else

{

unordered_map< int, int> mapping;

sort(nums.begin(), nums.end());

nums.erase(unique(nums.begin(), nums.end()), nums.end());

for (int i = 0; i < nums.size(); ++i)

{

mapping[nums[i]] = i;

}

for (int i = 0; i < nums.size(); ++i)

{

int target = nums[i] + k;

if (mapping.find(target) != mapping.end())

result++;

}

return result;

}

};

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

485. Max Consecutive Ones

Description:

https://leetcode.com/problems/max-consecutive-ones/description/

Code:

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int count = 0;
        int maxCount = 0;
        for (int i = 0; i < nums.size();i++)
        {
            if (nums[i] == 1)
            {
                count++;
                maxCount = count > maxCount ? count : maxCount;
            }
            else
                count = 0;
        }
        return maxCount;
    }
};

class Solution {

public:

int findMaxConsecutiveOnes(vector<int>& nums) {

int count = 0;

int maxCount = 0;

for (int i = 0; i < nums.size();i++)

{

if (nums[i] == 1)

{

count++;

maxCount = count > maxCount ? count : maxCount;

}

else

count = 0;

}

return maxCount;

}

};

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

08/11/2017

3 BUFFERS in OpenGL

color buffer (float)
depth buffer (float)
stencil buffer (8 bit bool, max 0xFF) stencil test的主要作用就是根据stencil buffer的内容，来丢弃不需要的fragments。

Do MSAA in GLFW: http://blog.csdn.net/column/details/14890.html

http://blog.csdn.net/jxw167/article/details/56014355

628. Maximum Product of Three Numbers

Description:

https://leetcode.com/problems/maximum-product-of-three-numbers/description/

Code:

class Solution { public: int maximumProduct(vector<int>& nums) { int large1 = INT_MIN, large2 = INT_MIN, large3 = INT_MIN; int small1 = INT_MAX, small2 = INT_MAX; for (int i = 0; i < nums.size(); i++) { if (nums[i] > large3) { if (nums[i] > large2) { if(nums[i] > large1) { large3 = large2; large2 = large1; large1 = nums[i]; } else { large3 = large2; large2 = nums[i]; } } else { large3 = nums[i]; } } if (nums[i] < small2) { if (nums[i] < small1) { small2 = small1; small1 = nums[i]; } else { small2 = nums[i]; } } } int largeNum1 = large3 * large2 * large1; int largeNum2 = large1 * small1 * small2; return largeNum1 > largeNum2 ? largeNum1 : largeNum2; } };

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int large1 = INT_MIN, large2 = INT_MIN, large3 = INT_MIN;
        int small1 = INT_MAX, small2 = INT_MAX;
        for (int i = 0; i < nums.size(); i++)
        {

            if (nums[i] > large3)
            {
                if (nums[i] > large2)
                {
                    if(nums[i] > large1)
                    {
                        large3 = large2;
                        large2 = large1;
                        large1 = nums[i];
                    }
                    else
                    {
                        large3 = large2;
                        large2 = nums[i];
                    }
                }
                else
                {
                    large3 = nums[i];
                }
            }
            if (nums[i] < small2)
            {
                if (nums[i] < small1)
                {
                    small2 = small1;
                    small1 = nums[i];
                }
                else
                {
                    small2 = nums[i];
                }
            }
        }
        int largeNum1 = large3 * large2 * large1;
        int largeNum2 = large1 * small1 * small2;
        return largeNum1 > largeNum2 ? largeNum1 : largeNum2;
    }
};

Time & Space:

O(n) & O(1)

Posted on August 11, 2017Categories LeetcodeLeave a comment on 628. Maximum Product of Three Numbers

621. Task Scheduler

Description:
https://leetcode.com/problems/task-scheduler/description/

Code:

class Solution { public: int leastInterval(vector<char>& tasks, int n) { int taskNum = tasks.size(); vector<int> table = vector<int>(26, 0); for (int i = 0; i < taskNum; i++) { table[tasks[i] - 'A']++; } sort(table.begin(), table.end()); int rowNum = table[25] - 1; int idleNum = rowNum * n; for (int i = 0; i < 25; i++) { idleNum -= min(table[i], rowNum); } return idleNum < 0 ? taskNum : idleNum + taskNum; } };

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
int taskNum = tasks.size();
vector<int> table = vector<int>(26, 0);
for (int i = 0; i < taskNum; i++)
{
table[tasks[i] - 'A']++;
}
sort(table.begin(), table.end());
int rowNum = table[25] - 1;
int idleNum = rowNum * n;

for (int i = 0; i < 25; i++)
{
idleNum -= min(table[i], rowNum);
}
return idleNum < 0 ? taskNum : idleNum + taskNum;
}
};

Time & Space:
Record: O(1)
Sort: O(nlogn)
Calculate idle: O(1)

Space: O(1)

Posted on August 11, 2017August 11, 2017Categories Leetcode3 Comments on 621. Task Scheduler

611. Valid Triangle Number

Description:

https://leetcode.com/problems/valid-triangle-number/description/

Algorithm1:

Use for loop for three times.

It works but slow (beats 23.60%)

Code1:

class Solution { public: int triangleNumber(vector& nums) { if (nums.size() < 3) return 0; int result = 0; sort(nums.begin(), nums.end()); int threshold; for (int i = 0; i < nums.size() - 2; i++) { for (int j = i + 1; j < nums.size() - 1; j++) { threshold = nums[i] + nums[j]; for (int k = j + 1; k < nums.size(); k++) { if (nums[k] < threshold) result++; else break; } } } return result; } };

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int triangleNumber(vector& nums) {
        if (nums.size() < 3) return 0;
        int result = 0;
        sort(nums.begin(), nums.end());
        int threshold;
        for (int i = 0; i < nums.size() - 2; i++)
        {
            for (int j = i + 1; j < nums.size() - 1; j++)
            {
                threshold = nums[i] + nums[j];
                for (int k = j + 1; k < nums.size(); k++)
                {
                    if (nums[k] < threshold)
                        result++;
                    else
                        break;
                }
            }
        }
        return result;
    }
};

Timing & Space:

O(n^3) & O(1)

Algorithm2:

Code2:

class Solution { public: int triangleNumber(vector& nums) { long n = nums.size(); int i, j, k; int total, a, b, c; if (n < 3) return 0; vector ct(1001, 0), sum(2001, 0); vector<pair<long, long>> p; for (i = 0; i < n; i++) ct[nums[i]]++; sum[0] = 0; // 0 cannot form triangle for (i = 1; i <= 1000; i++) sum[i] = sum[i - 1] + ct[i]; p.clear(); for (i = 1; i <= 1000; i++) if (ct[i] > 0) p.push_back(make_pair(i, ct[i])); for (i = 1001; i <= 2000; i++) sum[i] = sum[1000]; c = p.size(); total = 0; for (a = 0; a < c; a++) { if (p[a].second >= 2) { // a = b < c; total += (sum[p[a].first * 2 - 1] - sum[p[a].first]) * (p[a].second * (p[a].second - 1) / 2); // a = b = c if (p[a].second > 2) total += (p[a].second * (p[a].second - 1) / 2 * (p[a].second - 2) / 3); } for (b = a + 1; b < c; b++) { // a < b < c total += (sum[p[a].first + p[b].first - 1] - sum[p[b].first]) * p[a].second * p[b].second; // a < b = c if (p[b].second > 1) total += p[a].second * (p[b].second * (p[b].second - 1) / 2); } } return total; } };

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
public:
int triangleNumber(vector& nums) {
long n = nums.size();
int i, j, k;
int total, a, b, c;
if (n < 3) return 0;
vector ct(1001, 0), sum(2001, 0);
vector<pair<long, long>> p;
for (i = 0; i < n; i++)
ct[nums[i]]++;

sum[0] = 0; // 0 cannot form triangle
for (i = 1; i <= 1000; i++)
sum[i] = sum[i - 1] + ct[i];

p.clear();
for (i = 1; i <= 1000; i++) if (ct[i] > 0)
p.push_back(make_pair(i, ct[i]));

for (i = 1001; i <= 2000; i++) sum[i] = sum[1000];
c = p.size();

total = 0;
for (a = 0; a < c; a++) { if (p[a].second >= 2) {
// a = b < c; total += (sum[p[a].first * 2 - 1] - sum[p[a].first]) * (p[a].second * (p[a].second - 1) / 2); // a = b = c if (p[a].second > 2)
total += (p[a].second * (p[a].second - 1) / 2 * (p[a].second - 2) / 3);
}
for (b = a + 1; b < c; b++) {
// a < b < c
total += (sum[p[a].first + p[b].first - 1] - sum[p[b].first]) * p[a].second * p[b].second;
// a < b = c if (p[b].second > 1)
total += p[a].second * (p[b].second * (p[b].second - 1) / 2);
}
}
return total;
}
};

Timing & Space:

Time:

Worst: O(n^2)

Best: O(1)

Space: O(1)

Posted on August 9, 2017August 9, 2017Categories LeetcodeLeave a comment on 611. Valid Triangle Number

565. Array Nesting

Description:

https://leetcode.com/problems/array-nesting/description/

Algorithm:

Actually we are separating the array into several groups by determining S[k]. The numbers inside of S[k] will form a cycle.

For example:

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}

S[5] = {A[5], A[6], A[2], A[0]} = {6, 2, 0, 5}

S[6] = {A[6], A[2], A[0], A[5]} = {2, 0, 5, 6}

S[2] = {A[2], A[0], A[5], A[6]} = {0, 5, 6, 2}

S[1] = {A[1], A[4]} = {4,1}

S[4] = {A[4], A[1]} = {1,4}

S[3] = {A[3]} = {3}

So just mark the used number in the finding process. If meets used number -> stop.

Code:

class Solution { public: int arrayNesting(vector<int>& nums) { int n = nums.size(); int currentIdx = 0; int maxLength = 0; int currentLength = 0; int IdxTemp = 0; for (int i = 0; i < n; i++) { currentIdx = i; currentLength = 0; while(nums[currentIdx] != -1) { IdxTemp = currentIdx; currentIdx = nums[IdxTemp]; nums[IdxTemp] = -1; currentLength++; } maxLength = currentLength > maxLength? currentLength : maxLength; } return maxLength; } };

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
int arrayNesting(vector<int>& nums) {
int n = nums.size();

int currentIdx = 0;
int maxLength = 0;
int currentLength = 0;
int IdxTemp = 0;
for (int i = 0; i < n; i++)
{
currentIdx = i;
currentLength = 0;
while(nums[currentIdx] != -1)
{
IdxTemp = currentIdx;
currentIdx = nums[IdxTemp];
nums[IdxTemp] = -1;
currentLength++;
}
maxLength = currentLength > maxLength? currentLength : maxLength;
}
return maxLength;
}
};

Timing & Space:

fastest

O(n) & O(1)

Posted on August 9, 2017August 9, 2017Categories LeetcodeLeave a comment on 565. Array Nesting

Posts navigation

Previous page Page 1 Page 2 Page 3 Next page