leetcode 316 - Remove Duplicate Letters

https://leetcode.com/problems/remove-duplicate-letters/

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

Example 1:

Input: s = “bcabc”
Output: “abc”
Example 2:

Input: s = “cbacdcbc”
Output: “acdb”

Constraints:

1 <= s.length <= 104
s consists of lowercase English letters.

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
class Solution {
public:
string removeDuplicateLetters(string s) {
vector<int> count(256, 0);
vector<bool> used(256, false);

for (int c : s)
count[c]++;

stack<char> stk;

for (char c : s) {
if (used[c]) {
count[c]--;
continue;
}

while (!stk.empty()) {
char tmp = stk.top();
if (tmp > c && count[tmp] > 0) {
stk.pop();
used[tmp] = false;
} else {
break;
}
}

stk.push(c);
count[c]--;
used[c] = true;
}

string result;
while (!stk.empty()) {
result.push_back(stk.top());
stk.pop();
}

reverse(result.begin(), result.end());

return result;
}
};

leetcode 1578 - Minimum Deletion Cost to Avoid Repeating Letters

https://leetcode.com/problems/minimum-deletion-cost-to-avoid-repeating-letters/

Given a string s and an array of integers cost where cost[i] is the cost of deleting the ith character in s.

Return the minimum cost of deletions such that there are no two identical letters next to each other.

Notice that you will delete the chosen characters at the same time, in other words, after deleting a character, the costs of deleting other characters will not change.

Example 1:

Input: s = “abaac”, cost = [1,2,3,4,5]
Output: 3
Explanation: Delete the letter “a” with cost 3 to get “abac” (String without two identical letters next to each other).
Example 2:

Input: s = “abc”, cost = [1,2,3]
Output: 0
Explanation: You don’t need to delete any character because there are no identical letters next to each other.
Example 3:

Input: s = “aabaa”, cost = [1,2,3,4,1]
Output: 2
Explanation: Delete the first and the last character, getting the string (“aba”).

Constraints:

s.length == cost.length
1 <= s.length, cost.length <= 10^5
1 <= cost[i] <= 10^4
s contains only lowercase English letters.

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
class Solution {
public:
int minCost(string s, vector<int>& cost) {
stack<int> stk;

int total = 0;

for (int i = 0; i < s.size(); i++) {
if (stk.empty())
stk.push(i);
else {
int k = stk.top();
if (s[k] != s[i])
stk.push(i);
else {
if (cost[k] > cost[i])
total += cost[i];
else {
total += cost[k];
stk.pop();
stk.push(i);
}
}
}
}

return total;
}
};

leetcode 1171 - Remove Zero Sum Consecutive Nodes from Linked List

https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.
Example 2:

Input: head = [1,2,3,-3,4]
Output: [1,2,4]
Example 3:

Input: head = [1,2,3,-3,-2]
Output: [1]

Constraints:

The given linked list will contain between 1 and 1000 nodes.
Each node in the linked list has -1000 <= node.val <= 1000.

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
48
49
50
51
52
53
54
55
56
57
58
59
/**
*
Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
stack<ListNode *> stk;
unordered_map<int, ListNode *> maps;

ListNode *new_head = NULL;
ListNode *node = head;
int total = 0;

maps[0] = (ListNode *)-1; //special node

while (node) {
ListNode *next = node->next;

int tmp = total + node->val;
if (ListNode *n = maps[tmp]) {
while (!stk.empty()) {
ListNode *top_node = stk.top();
if (top_node == n) {
break;
}
stk.pop();
maps.erase(total);
total -= top_node->val;
}
} else {
if (!stk.empty())
stk.top()->next = node;
else
new_head = node;
stk.push(node);

total += node->val;
maps[total] = node;
}

node = next;
}

if (!stk.empty())
stk.top()->next = NULL;
else
new_head = NULL;

return new_head;
}
};

leetcode 767 - Reorganize String

https://leetcode.com/problems/reorganize-string/

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Example 1:

Input: S = “aab”
Output: “aba”
Example 2:

Input: S = “aaab”
Output: “”
Note:

S will consist of lowercase letters and have length in range [1, 500].

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
48
49
50
51
class Solution {
public:
struct Entry {
char c;
int total;

Entry(char _c, int _total) {
c = _c;
total = _total;
}
};

string reorganizeString(string S) {
unordered_map<char, int> maps;

for (char c : S) {
maps[c]++;
}

auto mycomp = [](const Entry &e1, const Entry &e2) {
return e1.total < e2.total;
};
typedef priority_queue<Entry, vector<Entry>, decltype(mycomp)> pq_t;
pq_t pq(mycomp);

for (auto m : maps) {
pq.push(Entry(m.first, m.second));
}

string result;

while (!pq.empty()) {
Entry e = pq.top(); pq.pop();
if (result.empty() || result.back() != e.c) {
result.push_back(e.c);
if (--e.total)
pq.push(e);
} else {
if (pq.empty())
return "";
Entry e2 = pq.top(); pq.pop();
result.push_back(e2.c);
if (--e2.total)
pq.push(e2);
pq.push(e);
}
}

return result;
}
};

leetcode 1052 - Grumpy Bookstore Owner

https://leetcode.com/problems/grumpy-bookstore-owner/

Today, the bookstore owner has a store open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

Example 1:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes.
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

Note:

1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[i] <= 1

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
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
int size = customers.size();

vector<int> satisfied(size+1);
vector<int> satisfied_not_grumpy(size+1);

satisfied[0] = satisfied_not_grumpy[0] = 0;

for (int len = 1; len <= size; len++) {
int s = 0;
if (grumpy[len-1] == 0)
s = customers[len-1];

satisfied[len] = satisfied[len-1] + s;
satisfied_not_grumpy[len] = satisfied_not_grumpy[len-1] + customers[len-1];
}

int max_satisfied = 0;

for (int i = 0; i <= size - X; i++) {
int part0 = satisfied[i];
int part1 = satisfied_not_grumpy[i+X] - satisfied_not_grumpy[i];
int part2 = satisfied[size] - satisfied[i+X];

max_satisfied = max(max_satisfied, part0 + part1 + part2);
}

return max_satisfied;
}
};

leetcode 827 - Making A Large Island

In a 2D grid of 0s and 1s, we change at most one 0 to a 1.

After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).

Example 1:

Input: [[1, 0], [0, 1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
Example 2:

Input: [[1, 1], [1, 0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
Example 3:

Input: [[1, 1], [1, 1]]
Output: 4
Explanation: Can’t change any 0 to 1, only one island with area = 4.

Notes:

1 <= grid.length = grid[0].length <= 50.
0 <= grid[i][j] <= 1.

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution {
public:
vector<int> leader;
vector<int> total;

int largestIsland(vector<vector<int>>& grid) {
int row = grid.size(), col = grid[0].size();
int size = row * col;

leader.resize(size);
total.resize(size, 1);

for (int i = 0; i < size; i++) {
leader[i] = i;
}

vector<vector<int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
if (grid[r][c] == 1) {
for (auto d : dirs) {
int rr = r + d[0];
int cc = c + d[1];

if (rr < 0 || rr >= row || cc < 0 || cc >= col || grid[rr][cc] == 0)
continue;

Union(find(r*row + c), find(rr*row + cc));
}
}
}
}

int max_island = 0;
for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
if (grid[r][c] == 0) {
unordered_set<int> set;

for (auto d : dirs) {
int rr = r + d[0];
int cc = c + d[1];

if (rr < 0 || rr >= row || cc < 0 || cc >= col || grid[rr][cc] == 0)
continue;

set.insert(find(rr * row + cc));
}

int cnt = 1;
for (auto i : set)
cnt += total[i];

max_island = max(max_island, cnt);
}
}
}

return max_island == 0 ? size : max_island;
}

int find(int i) {
if (leader[i] != i)
leader[i] = find(leader[i]);

return leader[i];
}

void Union(int i, int j) {
int x = leader[i];
int y = leader[j];

if (x == y) return;

leader[x] = y;
total[y] += total[x];
}
};

leetcode 1376 - Time Needed to Inform All Employees

https://leetcode.com/problems/time-needed-to-inform-all-employees/

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company has is the one with headID.

Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Also it’s guaranteed that the subordination relationships have a tree structure.

The head of the company wants to inform all the employees of the company of an urgent piece of news. He will inform his direct subordinates and they will inform their subordinates and so on until all employees know about the urgent news.

The i-th employee needs informTime[i] minutes to inform all of his direct subordinates (i.e After informTime[i] minutes, all his direct subordinates can start spreading the news).

Return the number of minutes needed to inform all the employees about the urgent news.

Example 1:

Input: n = 1, headID = 0, manager = [-1], informTime = [0]
Output: 0
Explanation: The head of the company is the only employee in the company.
Example 2:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.
Example 3:

Input: n = 7, headID = 6, manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1]
Output: 21
Explanation: The head has id = 6. He will inform employee with id = 5 in 1 minute.
The employee with id = 5 will inform the employee with id = 4 in 2 minutes.
The employee with id = 4 will inform the employee with id = 3 in 3 minutes.
The employee with id = 3 will inform the employee with id = 2 in 4 minutes.
The employee with id = 2 will inform the employee with id = 1 in 5 minutes.
The employee with id = 1 will inform the employee with id = 0 in 6 minutes.
Needed time = 1 + 2 + 3 + 4 + 5 + 6 = 21.
Example 4:

Input: n = 15, headID = 0, manager = [-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6], informTime = [1,1,1,1,1,1,1,0,0,0,0,0,0,0,0]
Output: 3
Explanation: The first minute the head will inform employees 1 and 2.
The second minute they will inform employees 3, 4, 5 and 6.
The third minute they will inform the rest of employees.
Example 5:

Input: n = 4, headID = 2, manager = [3,3,-1,2], informTime = [0,0,162,914]
Output: 1076

Constraints:

1 <= n <= 10^5
0 <= headID < n
manager.length == n
0 <= manager[i] < n
manager[headID] == -1
informTime.length == n
0 <= informTime[i] <= 1000
informTime[i] == 0 if employee i has no subordinates.
It is guaranteed that all the employees can be informed.

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 numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
vector<vector<int>> tree(n);

int size = manager.size();
for (int i = 0; i < size; i++) {
if (manager[i] == -1) continue;

tree[manager[i]].push_back(i);
}

return recursive(tree, headID, informTime);
}

int recursive(vector<vector<int>> &tree, int i, vector<int>& informTime) {
int time = 0;

for (int k : tree[i]) {
time = max(time, recursive(tree, k, informTime));
}

return time + informTime[i];
}
};

leetcode 1582 - Special Positions in a Binary Matrix

https://leetcode.com/problems/special-positions-in-a-binary-matrix/

Given a rows x cols matrix mat, where mat[i][j] is either 0 or 1, return the number of special positions in mat.

A position (i,j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

Example 1:

Input: mat = [[1,0,0],
[0,0,1],
[1,0,0]]
Output: 1
Explanation: (1,2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.
Example 2:

Input: mat = [[1,0,0],
[0,1,0],
[0,0,1]]
Output: 3
Explanation: (0,0), (1,1) and (2,2) are special positions.
Example 3:

Input: mat = [[0,0,0,1],
[1,0,0,0],
[0,1,1,0],
[0,0,0,0]]
Output: 2
Example 4:

Input: mat = [[0,0,0,0,0],
[1,0,0,0,0],
[0,1,0,0,0],
[0,0,1,0,0],
[0,0,0,1,1]]
Output: 3

Constraints:

rows == mat.length
cols == mat[i].length
1 <= rows, cols <= 100
mat[i][j] is 0 or 1.

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
class Solution {
public:
int numSpecial(vector<vector<int>>& mat) {
int r = mat.size();
int c = mat[0].size();

vector<int> rows(r, 0), cols(c, 0);

for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (mat[i][j] == 1) {
rows[i]++;
cols[j]++;
}
}
}

int total = 0;

for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1)
total++;
}
}

return total;
}
};

leetcode 1544 - Make The String Great

https://leetcode.com/problems/make-the-string-great/

Given a string s of lower and upper case English letters.

A good string is a string which doesn’t have two adjacent characters s[i] and s[i + 1] where:

0 <= i <= s.length - 2
s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.
To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.

Return the string after making it good. The answer is guaranteed to be unique under the given constraints.

Notice that an empty string is also good.

Example 1:

Input: s = “leEeetcode”
Output: “leetcode”
Explanation: In the first step, either you choose i = 1 or i = 2, both will result “leEeetcode” to be reduced to “leetcode”.
Example 2:

Input: s = “abBAcC”
Output: “”
Explanation: We have many possible scenarios, and all lead to the same answer. For example:
“abBAcC” –> “aAcC” –> “cC” –> “”
“abBAcC” –> “abBA” –> “aA” –> “”
Example 3:

Input: s = “s”
Output: “s”

Constraints:

1 <= s.length <= 100
s contains only lower and upper case English letters.

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
class Solution {
public:
string makeGood(string s) {
if (s.empty()) return "";

stack<char> stk;

for (char c : s) {
if (!stk.empty() && abs(c - stk.top()) == 32) {
stk.pop();
} else {
stk.push(c);
}
}

if (stk.empty()) return "";

string result;
while (!stk.empty()) {
result.push_back(stk.top());
stk.pop();
}

reverse(result.begin(), result.end());

return result;
}
};

leetcode 1137 - N-th Tribonacci Number

https://leetcode.com/problems/n-th-tribonacci-number/

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

Example 1:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
Example 2:

Input: n = 25
Output: 1389537

Constraints:

0 <= n <= 37
The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int tribonacci(int n) {
int buf[3] = {0, 1, 1};

if (n <= 2) return buf[n];

int tmp;

for (int i = 3; i <= n; i++) {
tmp = buf[0] + buf[1] + buf[2];

buf[0] = buf[1];
buf[1] = buf[2];
buf[2] = tmp;
}

return tmp;
}
};