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;
}
};

leetcode 179 - Largest Number

https://leetcode.com/problems/largest-number/

Given a list of non-negative integers nums, arrange them such that they form the largest number.

Note: The result may be very large, so you need to return a string instead of an integer.

Example 1:

Input: nums = [10,2]
Output: “210”
Example 2:

Input: nums = [3,30,34,5,9]
Output: “9534330”
Example 3:

Input: nums = [1]
Output: “1”
Example 4:

Input: nums = [10]
Output: “10”

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 109

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
class Solution {
public:
string largestNumber(vector<int>& nums) {
auto mycomp = [](int i, int j) {
string s1 = to_string(i);
string s2 = to_string(j);

s1 = s1 + s2;
s2 = s2 + s1;

for (int i = 0; i < (int)s1.size(); i++) {
if (s1[i] > s2[i]) return true;
if (s1[i] < s2[i]) return false;
}

return false;
};

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

string result;

for (int num : nums) {
if (num == 0 && result.empty())
continue;
result += to_string(num);
}

return result.empty() ? "0" : result;
}
};

leetcode 1026 - Maximum Difference Between Node and Ancestor

https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/

Given the root of a binary tree, find the maximum value V for which there exists different nodes A and B where V = |A.val - B.val| and A is an ancestor of B.

(A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.)

Example 1:

[]

Input: [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation:
We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

Note:

The number of nodes in the tree is between 2 and 5000.
Each node will have value between 0 and 100000.

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDiff;

int maxAncestorDiff(TreeNode* root) {
maxDiff = INT_MIN;

minMaxNode(root);

return maxDiff;
}

vector<TreeNode *> minMaxNode(TreeNode *root) {
if (!root)
return {NULL, NULL};

vector<TreeNode *> left = minMaxNode(root->left);
vector<TreeNode *> right = minMaxNode(root->right);

vector<TreeNode *> min_max = {root, root};

if (left[0]) {
maxDiff = max(maxDiff, abs(root->val - left[0]->val));
maxDiff = max(maxDiff, abs(root->val - left[1]->val));

if (left[0]->val < min_max[0]->val)
min_max[0] = left[0];
if (left[1]->val > min_max[1]->val)
min_max[1] = left[1];
}

if (right[0]) {
maxDiff = max(maxDiff, abs(root->val - right[0]->val));
maxDiff = max(maxDiff, abs(root->val - right[1]->val));

if (right[0]->val < min_max[0]->val)
min_max[0] = right[0];
if (right[1]->val > min_max[1]->val)
min_max[1] = right[1];
}

return min_max;
}
};

leetcode 1094 - Car Pooling

https://leetcode.com/problems/car-pooling/

You are driving a vehicle that has capacity empty seats initially available for passengers. The vehicle only drives east (ie. it cannot turn around and drive west.)

Given a list of trips, trip[i] = [num_passengers, start_location, end_location] contains information about the i-th trip: the number of passengers that must be picked up, and the locations to pick them up and drop them off. The locations are given as the number of kilometers due east from your vehicle’s initial location.

Return true if and only if it is possible to pick up and drop off all passengers for all the given trips.

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
Example 3:

Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true
Example 4:

Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
Output: true

Constraints:

trips.length <= 1000
trips[i].length == 3
1 <= trips[i][0] <= 100
0 <= trips[i][1] < trips[i][2] <= 1000
1 <= capacity <= 100000

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:
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<vector<int>> trips_sorted;

#define PICK_UP 1
#define DROP_OFF 0

for (auto &trip : trips) {
trips_sorted.push_back({trip[1], PICK_UP, trip[0]});
trips_sorted.push_back({trip[2], DROP_OFF, trip[0]});
}

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

int passengers = 0;
int size = trips_sorted.size();

for (int i = 0; i < size; i++) {
if (trips_sorted[i][1] == DROP_OFF)
passengers -= trips_sorted[i][2];
else
passengers += trips_sorted[i][2];

if (passengers > capacity)
return false;
}

return true;
}
};

class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
map<int, int> m;

for (auto &trip : trips) {
m[trip[1]] += trip[0];
m[trip[2]] -= trip[0];
}

for (auto &trip : m) {
capacity -= trip.second;
if (capacity < 0)
return false;
}

return true;
}
};

leetcode 1386 - Cinema Seat Allocation

https://leetcode.com/problems/cinema-seat-allocation/

A cinema has n rows of seats, numbered from 1 to n and there are ten seats in each row, labelled from 1 to 10 as shown in the figure above.

Given the array reservedSeats containing the numbers of seats already reserved, for example, reservedSeats[i] = [3,8] means the seat located in row 3 and labelled with 8 is already reserved.

Return the maximum number of four-person groups you can assign on the cinema seats. A four-person group occupies four adjacent seats in one single row. Seats across an aisle (such as [3,3] and [3,4]) are not considered to be adjacent, but there is an exceptional case on which an aisle split a four-person group, in that case, the aisle split a four-person group in the middle, which means to have two people on each side.

Example 1:

Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
Output: 4
Explanation: The figure above shows the optimal allocation for four groups, where seats mark with blue are already reserved and contiguous seats mark with orange are for one group.
Example 2:

Input: n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
Output: 2
Example 3:

Input: n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
Output: 4

Constraints:

1 <= n <= 10^9
1 <= reservedSeats.length <= min(10*n, 10^4)
reservedSeats[i].length == 2
1 <= reservedSeats[i][0] <= n
1 <= reservedSeats[i][1] <= 10
All reservedSeats[i] are distinct.

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:
int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
unordered_map<int, int> maps;

for (auto v : reservedSeats) {
maps[v[0]] |= (1 << v[1]);
}

int total = 0;
for (auto v : maps) {
int num = v.second;
if ((num & (15 << 2)) == 0) {
total++;
if ((num & (15 << 6)) == 0)
total++;
} else if ((num & (15 << 4)) == 0) {
total++;
} else if ((num & (15 << 6)) == 0) {
total++;
}
}

total += (n - maps.size()) * 2;

return total;
}
};

leetcode 1287 - Element Appearing More Than 25% In Sorted Array

https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.

Return that integer.

Example 1:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

Constraints:

1 <= arr.length <= 10^4
0 <= arr[i] <= 10^5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int findSpecialInteger(vector<int>& arr) {
int size = arr.size();
vector<int> indexs = {size/4, size/2, size*3/4};

for (int i : indexs) {
int num = arr[i];

auto low = lower_bound(arr.begin(), arr.end(), num);
auto high = upper_bound(arr.begin(), arr.end(), num);

if (high - low > size/4)
return num;
}

return -1;
}
};

leetcode 1614 - Maximum Nesting Depth of the Parentheses

https://leetcode.com/problems/maximum-nesting-depth-of-the-parentheses/

A string is a valid parentheses string (denoted VPS) if it meets one of the following:

It is an empty string “”, or a single character not equal to “(“ or “)”,
It can be written as AB (A concatenated with B), where A and B are VPS’s, or
It can be written as (A), where A is a VPS.
We can similarly define the nesting depth depth(S) of any VPS S as follows:

depth(“”) = 0
depth(A + B) = max(depth(A), depth(B)), where A and B are VPS’s
depth(“(“ + A + “)”) = 1 + depth(A), where A is a VPS.
For example, “”, “()()”, and “()(()())” are VPS’s (with nesting depths 0, 1, and 2), and “)(“ and “(()” are not VPS’s.

Given a VPS represented as string s, return the nesting depth of s.

Example 1:

Input: s = “(1+(2*3)+((8)/4))+1”
Output: 3
Explanation: Digit 8 is inside of 3 nested parentheses in the string.
Example 2:

Input: s = “(1)+((2))+(((3)))”
Output: 3
Example 3:

Input: s = “1+(2*3)/(2-1)”
Output: 1
Example 4:

Input: s = “1”
Output: 0

Constraints:

1 <= s.length <= 100
s consists of digits 0-9 and characters ‘+’, ‘-‘, ‘*’, ‘/‘, ‘(‘, and ‘)’.
It is guaranteed that parentheses expression s is a VPS.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int maxDepth(string s) {
int max_depth = 0, depth = 0;

for (char c : s) {
if (c == '(') {
depth++;
max_depth = max(max_depth, depth);
} else if (c == ')') {
depth--;
}
}

return max_depth;
}
};

leetcode 1267 - Count Servers that Communicate

https://leetcode.com/problems/count-servers-that-communicate/

You are given a map of a server center, represented as a m * n integer matrix grid, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.

Return the number of servers that communicate with any other server.

Example 1:

Input: grid = [[1,0],[0,1]]
Output: 0
Explanation: No servers can communicate with others.
Example 2:

Input: grid = [[1,0],[1,1]]
Output: 3
Explanation: All three servers can communicate with at least one other server.
Example 3:

Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Explanation: The two servers in the first row can communicate with each other. The two servers in the third column can communicate with each other. The server at right bottom corner can’t communicate with any other server.

Constraints:

m == grid.length
n == grid[i].length
1 <= m <= 250
1 <= n <= 250
grid[i][j] == 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
int countServers(vector<vector<int>>& grid) {
int r = grid.size();
int c = grid[0].size();

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

for (int i = 0; i < r; i++) {
int count = 0;
for (int j = 0; j < c; j++) {
if (grid[i][j] == 1) {
if (++count > 1) {
rows[i] = 1;
break;
}
}
}
}

for (int i = 0; i < c; i++) {
int count = 0;
for (int j = 0; j < r; j++) {
if (grid[j][i] == 1) {
if (++count > 1) {
cols[i] = 1;
break;
}
}
}
}

int total = 0;

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

return total;
}
};

leetcode 460 - LFU Cache

https://leetcode.com/problems/lfu-cache/

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Note that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.get(3); // returns 3.
cache.put(4, 4); // evicts key 1.
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
class LFUCache {
public:
struct Node {
int key;
int val;
int count;
Node *prev, *next;

Node (int k) {
key = k;
count = 0;
prev = next = NULL;
}
};

map<int, Node *> freqMap;
unordered_map<int, Node *> keyValue;
int capacity;

LFUCache(int capacity) {
this->capacity = capacity;
}

int get(int key) {
if (keyValue.count(key) == 0)
return -1;
Node *node = keyValue[key];
remove(node);
node->count++;
insert(node);
return node->val;
}

void put(int key, int value) {
if (capacity <= 0)
return;

Node *node;
if (keyValue.count(key) == 0) {
if ((int)keyValue.size() == capacity) {
evict();
}
node = new Node(key);
} else {
node = keyValue[key];
remove(node);
}

node->count++;
node->val = value;
insert(node);
}

void remove(Node *node) {
int count = node->count;

Node *prev = node->prev;
Node *next = node->next;
prev->next = next;
next->prev = prev;

Node *head = freqMap[count];
if (head == node) {
if (prev == node)
freqMap.erase(count);
else
freqMap[count] = next;
}

int key = node->key;
keyValue.erase(key);
}

void insert(Node *node) {
int count = node->count;

Node *head = freqMap[count];
if (head) {
node->next = head;
Node *tail = head->prev;
node->prev = tail;
head->prev = node;
tail->next = node;
} else {
node->prev = node;
node->next = node;
}

freqMap[count] = node;
keyValue[node->key] = node;
}

void evict() {
auto it = freqMap.begin();
Node *head = it->second;
Node *tail = head->prev;
remove(tail);
delete tail;
}
};

/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache* obj = new LFUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/