Given the root of a binary tree, find the maximum average value of any subtree of that tree.

(A subtree of a tree is any node of that tree plus all its descendants. The average value of a tree is the sum of its values, divided by the number of nodes.)

Example 1:

Input: [5,6,1] Output: 6.00000 Explanation: For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4. For the node with value = 6 we have an average of 6 / 1 = 6. For the node with value = 1 we have an average of 1 / 1 = 1. So the answer is 6 which is the maximum.

Note:

The number of nodes in the tree is between 1 and 5000. Each node will have a value between 0 and 100000. Answers will be accepted as correct if they are within 10^-5 of the correct answer.

Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.

Example 1:

Input: [1,0,1,0,1] Output: 1 Explanation: There are 3 ways to group all 1’s together: [1,1,1,0,0] using 1 swap. [0,1,1,1,0] using 2 swaps. [0,0,1,1,1] using 1 swap. The minimum is 1. Example 2:

Input: [0,0,0,1,0] Output: 0 Explanation: Since there is only one 1 in the array, no swaps needed. Example 3:

Input: [1,0,1,0,1,0,0,1,1,0,1] Output: 3 Explanation: One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].

You are asked to design a file system which provides two functions:

createPath(path, value): Creates a new path and associates a value to it if possible and returns True. Returns False if the path already exists or its parent path doesn’t exist. get(path): Returns the value associated with a path or returns -1 if the path doesn’t exist. The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, /leetcode and /leetcode/problems are valid paths while an empty string and / are not.

structNode { unordered_map<string, Node *> children; int value; };

classFileSystem { public: FileSystem() { root = new Node; } boolcreatePath(string path, int value){ if (path[0] != '/') returnfalse; size_t curr = 1; size_t next; Node *node = root; string name; do { next = path.find("/", curr); if (next == string::npos) { name = path.substr(curr); break; } else { name = path.substr(curr, next - curr); curr = next + 1; if (node->children.count(name) == 0) returnfalse; node = node->children[name]; } } while (next != string::npos); if (node->children.count(name)) returnfalse; Node *new_node = new Node; new_node->value = value; node->children[name] = new_node; returntrue; } intget(string path){ if (path[0] != '/') return-1; size_t curr = 1; size_t next; Node *node = root; string name; do { next = path.find("/", curr); if (next == string::npos) { name = path.substr(curr); } else { name = path.substr(curr, next - curr); curr = next + 1; } if (node->children.count(name) == 0) return-1; node = node->children[name]; } while (next != string::npos); return node->value; } private: Node *root; };

/** * Your FileSystem object will be instantiated and called as such: * FileSystem* obj = new FileSystem(); * bool param_1 = obj->createPath(path,value); * int param_2 = obj->get(path); */

You have some sticks with positive integer lengths.

You can connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y. You perform this action until there is one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

classSolution { public: intsmallestCommonElement(vector<vector<int>>& mat){ int row = mat.size(), col = mat[0].size(); vector<int> idx(row, 0); auto mycomp = [&](const pair<int,int> &p1, const pair<int,int> &p2) { return mat[p1.first][p1.second] > mat[p2.first][p2.second]; };

typedef priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(mycomp)> pq_t; pq_t pq(mycomp); for (int r = 0; r < row; r++) pq.push({r, 0}); while (!pq.empty()) { if (check(mat, idx)) return mat[0][idx[0]]; auto p = pq.top(); pq.pop(); if (++p.second < col) { pq.push(p); idx[p.first] = p.second; } } return-1; } boolcheck(vector<vector<int>>& mat, vector<int> &idx){ int row = mat.size(); for (int r = 1; r < row; r++) { int c = idx[r]; if (mat[r][c] != mat[0][idx[0]]) returnfalse; } returntrue; } };

You are given an array colors, in which there are three colors: 1, 2 and 3.

You are also given some queries. Each query consists of two integers i and c, return the shortest distance between the given index i and the target color c. If there is no solution return -1.

Example 1:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]] Output: [3,0,3] Explanation: The nearest 3 from index 1 is at index 4 (3 steps away). The nearest 2 from index 2 is at index 2 itself (0 steps away). The nearest 1 from index 6 is at index 3 (3 steps away). Example 2:

Input: colors = [1,2], queries = [[0,3]] Output: [-1] Explanation: There is no 3 in the array.

Given two binary search trees, return True if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3], target = 5 Output: true Explanation: 2 and 3 sum up to 5. Example 2:

A Stepping Number is an integer such that all of its adjacent digits have an absolute difference of exactly 1. For example, 321 is a Stepping Number while 421 is not.

Given two integers low and high, find and return a sorted list of all the Stepping Numbers in the range [low, high] inclusive.

Example 1:

Input: low = 0, high = 21 Output: [0,1,2,3,4,5,6,7,8,9,10,12,21]

classSolution { public: vector<int> countSteppingNumbers(int low, int high) { vector<int> res; queue<int> q; for (int i = 1; i <= 9; i++) q.push(i); if (low == 0) res.push_back(0); while (!q.empty()) { int n = q.front(); q.pop(); int d = n % 10; long next; if (d > 0) { next = (long)n * 10 + d - 1; if (next <= high) q.push(next); } if (d < 9) { next = (long)n * 10 + d + 1; if (next <= high) q.push(next); } if (n >= low && n <= high) res.push_back(n); } return res; } };

Given the availability time slots arrays slots1 and slots2 of two people and a meeting duration duration, return the earliest time slot that works for both of them and is of duration duration.

If there is no common time slot that satisfies the requirements, return an empty array.

The format of a time slot is an array of two elements [start, end] representing an inclusive time range from start to end.

It is guaranteed that no two availability slots of the same person intersect with each other. That is, for any two time slots [start1, end1] and [start2, end2] of the same person, either start1 > end2 or start2 > end1.

1 <= prob.length <= 1000 0 <= prob[i] <= 1 0 <= target <= prob.length Answers will be accepted as correct if they are within 10^-5 of the correct answer.

/* 2D space */ classSolution { public: doubleprobabilityOfHeads(vector<double>& prob, int target){ int n = prob.size(); vector<vector<double>> dp(n, vector<double>(target+2));

dp[0][0] = 1 - prob[0]; dp[0][1] = prob[0];

for (int i = 1; i < n; i++) { for (int j = 0; j <= target; j++) { dp[i][j] = dp[i-1][j] * (1 - prob[i]); if (j > 0) dp[i][j] += dp[i-1][j-1] * prob[i]; } }

return dp[n-1][target]; } };

/* 1D space */ classSolution { public: doubleprobabilityOfHeads(vector<double>& prob, int target){ int n = prob.size(); vector<double> dp(target+2);

dp[0] = 1 - prob[0]; dp[1] = prob[0];

for (int i = 1; i < n; i++) { for (int j = 0; j <= target; j++) { double tmp = dp[j] * (1 - prob[i]); if (j > 0) tmp += dp[j-1] * prob[i]; dp[j] = tmp; } }