You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

Example 1:

Input: n = 5, edges = [[0,1],[1,2],[3,4]] Output: 2 Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]] Output: 1

Constraints:

1 <= n <= 2000 1 <= edges.length <= 5000 edges[i].length == 2 0 <= ai <= bi < n ai != bi There are no repeated edges.

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example 1:

Input: [[1,1],2,[1,1]] Output: 8 Explanation: Four 1’s at depth 1, one 2 at depth 2. Example 2:

Input: [1,[4,[6]]] Output: 17 Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 13 + 42 + 6*1 = 17.

/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * class NestedInteger { * public: * // Constructor initializes an empty nested list. * NestedInteger(); * * // Constructor initializes a single integer. * NestedInteger(int value); * * // Return true if this NestedInteger holds a single integer, rather than a nested list. * bool isInteger() const; * * // Return the single integer that this NestedInteger holds, if it holds a single integer * // The result is undefined if this NestedInteger holds a nested list * int getInteger() const; * * // Set this NestedInteger to hold a single integer. * void setInteger(int value); * * // Set this NestedInteger to hold a nested list and adds a nested integer to it. * void add(const NestedInteger &ni); * * // Return the nested list that this NestedInteger holds, if it holds a nested list * // The result is undefined if this NestedInteger holds a single integer * const vector<NestedInteger> &getList() const; * }; */ //Two passes classSolution { public: intdepthSumInverse(vector<NestedInteger>& nestedList){ int depth = getDepth(nestedList); int sum = dfs(nestedList, depth); return sum; }

private: intdfs(vector<NestedInteger>& nestedList, int depth){ int sum = 0; for (auto &nest : nestedList) { if (!nest.isInteger()) sum += dfs(nest.getList(), depth-1); else sum += depth * nest.getInteger(); } return sum; } intgetDepth(vector<NestedInteger>& nestedList){ int depth = 1; for (auto &nest : nestedList) { if (!nest.isInteger()) depth = max(depth, getDepth(nest.getList()) + 1); } return depth; } };

//One pass BFS classSolution { public: intdepthSumInverse(vector<NestedInteger>& nestedList){ queue<NestedInteger> q; int total_sum = 0; int prev = 0; for (auto &nested : nestedList) q.push(nested); while (!q.empty()) { int size = q.size(); int level_sum = 0; for (int i = 0; i < size; i++) { auto nested = q.front(); q.pop(); if (nested.isInteger()) level_sum += nested.getInteger(); else { for (auto n : nested.getList()) q.push(n); } } prev += level_sum; total_sum += prev; } return total_sum; } };

//One pass DFS classSolution { public: intdepthSumInverse(vector<NestedInteger>& nestedList){ max_depth = 0; flat_sum = 0; int sum = depth_sum(nestedList, 1); return (max_depth+1)*flat_sum - sum; } intdepth_sum(vector<NestedInteger>& nestedList, int depth){ int sum = 0; max_depth = max(max_depth, depth); for (auto &nested : nestedList) { if (nested.isInteger()) { sum += depth * nested.getInteger(); flat_sum += nested.getInteger(); } else sum += depth_sum(nested.getList(), depth+1); } return sum; } private: int max_depth; int flat_sum; };

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]] Example 3:

matrix.length == n matrix[i].length == n 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000

1 2 3 4 5 6 7 8 9 10 11 12

classSolution { public: voidrotate(vector<vector<int>>& matrix){ int n = matrix.size(); reverse(matrix.begin(), matrix.end()); for (int r = 0; r < n; r++) for (int c = r + 1; c < n; c++) swap(matrix[r][c], matrix[c][r]); } };

Given a binary string s (a string consisting only of ‘0’s and ‘1’s), we can split s into 3 non-empty strings s1, s2, s3 (s1+ s2+ s3 = s).

Return the number of ways s can be split such that the number of characters ‘1’ is the same in s1, s2, and s3.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: s = “10101” Output: 4 Explanation: There are four ways to split s in 3 parts where each part contain the same number of letters ‘1’. “1|010|1” “1|01|01” “10|10|1” “10|1|01” Example 2:

Input: s = “1001” Output: 0 Example 3:

Input: s = “0000” Output: 3 Explanation: There are three ways to split s in 3 parts. “0|0|00” “0|00|0” “00|0|0” Example 4:

A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix’s end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2].

Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.

Example 1:

Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]] Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]] Example 2:

Input: mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]] Output: [[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]

Constraints:

m == mat.length n == mat[i].length 1 <= m, n <= 100 1 <= mat[i][j] <= 100

classSolution { public: vector<vector<int>> diagonalSort(vector<vector<int>>& mat) { int rows = mat.size(), cols = mat[0].size(); for (int r = 0; r < rows; r++) { int x = r, y = 0; vector<int> nums; while (x < rows && y < cols) nums.push_back(mat[x++][y++]); sort(nums.begin(), nums.end()); int i = 0; x = r; y = 0; while (x < rows && y < cols) mat[x++][y++] = nums[i++]; } for (int c = 1; c < cols; c++) { int x = 0, y = c; vector<int> nums; while (x < rows && y < cols) nums.push_back(mat[x++][y++]); sort(nums.begin(), nums.end()); int i = 0; x = 0; y = c; while (x < rows && y < cols) mat[x++][y++] = nums[i++]; } return mat; } };

classSolution { public: vector<vector<int>> diagonalSort(vector<vector<int>>& mat) { unordered_map<int, priority_queue<int, vector<int>, greater<int>>> maps; int rows = mat.size(), cols = mat[0].size(); for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) maps[r - c].push(mat[r][c]); for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { mat[r][c] = maps[r - c].top(); maps[r - c].pop(); } } return mat; } };

//Time O(logN), Space O(logN) classSolution { public: doublemyPow(double x, int n){ if (n == 0) return1; long nn = abs(n); double res = helper(x, nn); if (n < 0) res = 1.0/res; return res; } doublehelper(double x, long n){ if (n == 1) return x; double res = helper(x, n/2); res *= res; if (n % 2 == 1) res *= x; return res; } };

//Time O(logN), Space O(1) classSolution { public: doublemyPow(double x, int n){ if (n == 0) return1; long nn = n; if (nn < 0) { x = 1.0/x; nn = -nn; } doublepow = x; double result = 1; while (nn) {//101 if (nn & 1) result *= pow; nn = nn >> 1; pow = pow * pow; } return result; } };

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.

Example 1:

Input: words = [“hello”,”leetcode”], order = “hlabcdefgijkmnopqrstuvwxyz” Output: true Explanation: As ‘h’ comes before ‘l’ in this language, then the sequence is sorted. Example 2:

Input: words = [“word”,”world”,”row”], order = “worldabcefghijkmnpqstuvxyz” Output: false Explanation: As ‘d’ comes after ‘l’ in this language, then words[0] > words[1], hence the sequence is unsorted. Example 3:

Input: words = [“apple”,”app”], order = “abcdefghijklmnopqrstuvwxyz” Output: false Explanation: The first three characters “app” match, and the second string is shorter (in size.) According to lexicographical rules “apple” > “app”, because ‘l’ > ‘∅’, where ‘∅’ is defined as the blank character which is less than any other character (More info).

Constraints:

1 <= words.length <= 100 1 <= words[i].length <= 20 order.length == 26 All characters in words[i] and order are English lowercase letters.