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
class Solution {
public:
struct Trip {
bool start;
int num;
int location;

Trip(bool s, int n, int l) {
start = s;
num = n;
location = l;
}
};

bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<Trip> all_trips;

for (auto v : trips) {
all_trips.push_back(Trip(true, v[0], v[1]));
all_trips.push_back(Trip(false, v[0], v[2]));
}

auto mycomp = [](const Trip &t1, const Trip &t2) {
if (t1.location < t2.location) return true;
if (t1.location > t2.location) return false;
return t1.start < t2.start;
};

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

int total = 0;

for (auto t : all_trips) {
if (t.start)
total += t.num;
if (total > capacity)
return false;
if (!t.start)
total -= t.num;
}

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);
*/

leetcode 1604 - Alert Using Same Key-Card Three or More Times in a One Hour Period

https://leetcode.com/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period/

LeetCode company workers use key-cards to unlock office doors. Each time a worker uses their key-card, the security system saves the worker’s name and the time when it was used. The system emits an alert if any worker uses the key-card three or more times in a one-hour period.

You are given a list of strings keyName and keyTime where [keyName[i], keyTime[i]] corresponds to a person’s name and the time when their key-card was used in a single day.

Access times are given in the 24-hour time format “HH:MM”, such as “23:51” and “09:49”.

Return a list of unique worker names who received an alert for frequent keycard use. Sort the names in ascending order alphabetically.

Notice that “10:00” - “11:00” is considered to be within a one-hour period, while “22:51” - “23:52” is not considered to be within a one-hour period.

Example 1:

Input: keyName = [“daniel”,”daniel”,”daniel”,”luis”,”luis”,”luis”,”luis”], keyTime = [“10:00”,”10:40”,”11:00”,”09:00”,”11:00”,”13:00”,”15:00”]
Output: [“daniel”]
Explanation: “daniel” used the keycard 3 times in a one-hour period (“10:00”,”10:40”, “11:00”).
Example 2:

Input: keyName = [“alice”,”alice”,”alice”,”bob”,”bob”,”bob”,”bob”], keyTime = [“12:01”,”12:00”,”18:00”,”21:00”,”21:20”,”21:30”,”23:00”]
Output: [“bob”]
Explanation: “bob” used the keycard 3 times in a one-hour period (“21:00”,”21:20”, “21:30”).
Example 3:

Input: keyName = [“john”,”john”,”john”], keyTime = [“23:58”,”23:59”,”00:01”]
Output: []
Example 4:

Input: keyName = [“leslie”,”leslie”,”leslie”,”clare”,”clare”,”clare”,”clare”], keyTime = [“13:00”,”13:20”,”14:00”,”18:00”,”18:51”,”19:30”,”19:49”]
Output: [“clare”,”leslie”]

Constraints:

1 <= keyName.length, keyTime.length <= 105
keyName.length == keyTime.length
keyTime are in the format “HH:MM”.
[keyName[i], keyTime[i]] is unique.
1 <= keyName[i].length <= 10
keyName[i] 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
30
31
32
33
34
35
class Solution {
public:
vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
unordered_map<string, vector<int>> maps;

int size = keyName.size();

for (int i = 0; i < size; i++) {
int time = stoi(keyTime[i].substr(0, 2)) * 60 + stoi(keyTime[i].substr(3));
maps[keyName[i]].push_back(time);
}

vector<string> result;

for (auto v : maps) {
sort(v.second.begin(), v.second.end());

int i = 0;
for (int j = 1; j < v.second.size(); j++) {
while (v.second[j] - v.second[i] > 60) {
i++;
}

if (j - i + 1 >= 3) {
result.push_back(v.first);
break;
}
}
}

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

return result;
}
};

leetcode 1608 - Special Array With X Elements Greater Than or Equal X

https://leetcode.com/problems/special-array-with-x-elements-greater-than-or-equal-x/

You are given an array nums of non-negative integers. nums is considered special if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x.

Notice that x does not have to be an element in nums.

Return x if the array is special, otherwise, return -1. It can be proven that if nums is special, the value for x is unique.

Example 1:

Input: nums = [3,5]
Output: 2
Explanation: There are 2 values (3 and 5) that are greater than or equal to 2.
Example 2:

Input: nums = [0,0]
Output: -1
Explanation: No numbers fit the criteria for x.
If x = 0, there should be 0 numbers >= x, but there are 2.
If x = 1, there should be 1 number >= x, but there are 0.
If x = 2, there should be 2 numbers >= x, but there are 0.
x cannot be greater since there are only 2 numbers in nums.
Example 3:

Input: nums = [0,4,3,0,4]
Output: 3
Explanation: There are 3 values that are greater than or equal to 3.
Example 4:

Input: nums = [3,6,7,7,0]
Output: -1

Constraints:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int specialArray(vector<int>& nums) {
int size = nums.size();
vector<int> count(1001, 0);

for (int i : nums)
count[i]++;

int remain = size;
for (int i = 0; i <= 1000; i++) {
if (i == remain)
return i;
remain -= count[i];
}

return -1;
}
};