Xiaoxu Meng – Page 8 – Welcome to blog of Xiaoxu Meng :) Please visit http://www.mengxiaoxu.com for more information. Thanks!

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

08/08/2017

Research:

Read the three papers and decide whether they are related to FR (Not directly, but there are many techniques which could be used to accelarate rendering)

[He, Extending, 2014]: The idea is totally the same with that of coarse pixel shading. But this is an approach for forward shading.

[Yee, Spatiotemporal, 2001]: Accelerate global illumination computation for dynamic environments. Use human visual system property.

[Liktor, Decoupled Deferred, 2012]:

compact geometry buffer: stores shading samples independently from the visibility

[ClarBerg, AMFS, 2014]: powerful hardware architecture for pixel shading, which enables flexible control of shading rates and automatic shading reuse between triangles in tessellated primitives.

[Foveated Real-Time Ray Tracing for Virtual Reality Headset]

foveated sampling

[Combining Eye Tracking with Optimizations for Lens Astigmatism in modern wide-angle HMDs]

Foveated sampling: taking the minimum values of two sampling maps (lens astigmatism & current eye gaze) in the foveated region.

[Perception-driven Accelerated Rendering, 2016]

survey

[A Retina-Based Perceptually Lossless Limit and a Gaussian Foveation Scheme With Loss Control, 2014]:

not related to foveated rendering

[User, Metric, and Computational Evaluation of Foveated Rendering Methods]

[H. Tong and R. Fisher. Progress Report on an Eye-Slaved Area-of Interest Visual Display. Defense Technical Information Center, 1984.]

[Proceedings of the 1990 Symposium on Interactive 3D Graphics]

Mutlisampling & Supersampling

Multisampling: only apply super samples at the edge of primitives

Supersampling: sample for the whole frame and amplify the whole frame

Forward rendering & deferred rendering

https://gamedevelopment.tutsplus.com/articles/forward-rendering-vs-deferred-rendering–gamedev-12342

Deferred shading seems good, why not giving up forward shading?

User, Metric, and Computational Evaluation of Foveated Rendering Methods

Compare 4 foveated rendering methods

Lower resolution for foveated view

Screen-Space Ambient Occlusion instead of global ambient occlusion

Terrain Tessellation

Foveated Real-time Ray-Casting

Provide foveated image metric

HDR-VDP: compare two images and get visibility and quality

Only spacial artifacts are considered! Temporal is not considered!

Find a saliency map during free viewing.

Posted on August 8, 2017August 13, 2017Categories DiaryLeave a comment on 08/08/2017

Report 08/07/2017

As we discussed last week, to make our paper better, we should:

Make our algorithm better than others.

Do user study.

Compare with work of others.

To make our algorithm better than others, what I did last week is:

Do interpolation for the rendered scene so there is no feeling of large pixels.

Although interpolated, there are still jaggies in the frame. To reduce jaggies:

I built a contrast map and did contrast-related blur. Jaggies exist at the position where contrast is large.

I did bilateral filtering. The jaggies is not reduced, but it has very good effect of smoothing.

To compare with work of others, I need to redo the work of others.

I have already implemented the work of Microsoft without blur.

Built a summary for the

Next week:

Implement code of nvidia paper.

A similar apporach: https://github.com/GameTechDev/DeferredCoarsePixelShading

Microsoft code:

https://www.microsoft.com/en-us/download/details.aspx?id=52390

Write the summary paper.

Today:

Deferred shading is a screen-space shading technique. It is called deferred because no shading is actually performed in the first pass of the vertex and pixel shaders: instead shading is “deferred” until a second pass.

Decoupled shading: shades fragments rather than micropolygons vertices. Only shades fragments after precise computation of visibility.

Visibility: how much we read from the primitives

Shading rate: how much we render.

Posted on August 7, 2017August 7, 2017Categories DiaryLeave a comment on Report 08/07/2017

bu ai gan huo

🙁

Posted on August 6, 2017August 6, 2017Categories DiaryLeave a comment on bu ai gan huo

Posts navigation

Previous page Page 1 … Page 7 Page 8 Page 9 … Page 18 Next page