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.

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.

classSolution { public: structTrip { bool start; int num; int location; Trip(bool s, int n, int l) { start = s; num = n; location = l; } }; boolcarPooling(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) returntrue; if (t1.location > t2.location) returnfalse; 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) returnfalse; if (!t.start) total -= t.num; } returntrue; } };

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.

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.

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

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

voidevict(){ 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 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:

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.

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

classSolution { public: intspecialArray(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; } };