Leetcode – Xiaoxu Meng

Iterator of set

		std::set<int> myset;
		std::set<int>::iterator it;

		// insert some values:
		for (int i = 1; i<10; i++) myset.insert(i * 10);  // 10 20 30 40 50 60 70 80 90

		it = myset.begin(); // "it" points now to 10
		auto prev = it; //"prev" points to 10
		prev++; // "prev" points to 20
		myset.erase(it); // "it points to myset.end()"  If erase, it will point to end() no matter where it is.
		it = prev; // "it points to 20" 
		it++; // "it points to 30" 
		cout << *prev << endl; // 20
		cout << *it << endl; // 30

std::set<int> myset;

std::set<int>::iterator it;

// insert some values:

for (int i = 1; i<10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90

it = myset.begin(); // "it" points now to 10

auto prev = it; //"prev" points to 10

prev++; // "prev" points to 20

myset.erase(it); // "it points to myset.end()" If erase, it will point to end() no matter where it is.

it = prev; // "it points to 20"

it++; // "it points to 30"

cout << *prev << endl; // 20

cout << *it << endl; // 30

Commonly Used functions about string

* isalnum()

* tolower()

more: http://www.cplusplus.com/reference/cctype/

136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Solution:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int A = nums[0];
        for(int i = 1; i < nums.size();i++)
        {
            A = A ^ nums[i];
        }
        return A;
    }
};

class Solution {

public:

int singleNumber(vector<int>& nums) {

int A = nums[0];

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

{

A = A ^ nums[i];

}

return A;

}

};

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)

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)

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

Posts navigation

Page 1 Page 2 … Page 8 Next page