A Code

There are  n  stones between the starting point and the end point. The distance between the starting point and the  ith  (i starts from 0) stone is  d[i] . And the distance between the starting point and end point is  target . From the starting point, we can only jump to the  adjacent  stone until the end point. Now you can remove at most  m  stones. Return the maximum value of the shortest jump distance in your jumping from start point to end point. 0 \leq m \leq n \leq 50,000 0 ≤ m ≤ n ≤ 5 0 , 0 0 0 1 \leq target \leq 1,000,000,000 1 ≤ t a r g e t ≤ 1 , 0 0 0 , 0 0 0 , 0 0 0 These stones are given in order from small to large distances from the starting point, and no two stones will appear in the same place. Have you met this question in a real interview?    Yes Problem Correction Example Example 1: Input: n = 5, m = 2, target = 25, d = [2,11,14,17,21] Output: 4 Explanation: Remove th...

Code ( Language :C++) Edit /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public : /** * @param root: the root * @param k: an integer * @return: the value of the nearest leaf node to target k in the tree */ unordered_map <TreeNode*, TreeNode*> parent; TreeNode * search (TreeNode* root, int k) { if (root == NULL ){ return NULL ; } TreeNode *res = root; if (root->left){ parent[root->left] = root; TreeNode *tmp = search(root->left, k);//这里的目的是遍历完真个tree，不是找到k就结束了 if (tmp->val == k){ res = tmp; } } if (root->right){ parent[root->right] = root; TreeNode *tmp = s...

Code ( Language :C++) Edit class Solution { public : /** * @param stones: a list of stones' positions in sorted ascending order * @return: true if the frog is able to cross the river or false */ bool canCross ( vector < int > &stones) { // write your code here const int size = stones.size(); if (size <= 1 ){ return true ; } if (stones[ 0 ] + 1 != stones[ 1 ]){ return false ; } unordered_map < int , unordered_set < int >> mp; for ( auto i : stones){ mp[i] = unordered_set < int >(); } mp[stones[ 1 ]].insert( 1 ); for ( int i = 1 ; i < size; i++){ int pos = stones[i]; for ( auto k : mp[pos]){ if (k - 1 > 0 ){ if (mp.count(pos + k - 1 )){ mp[pos + k - 1 ].insert(k - 1 ); ...

Code ( Language :C++) Edit /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public : /** * @param root: the root * @return: the maximum width of the given tree */ int widthOfBinaryTree (TreeNode * root) { // Write your code here // 類似與竖排的遍历 if (root == NULL ){ return 0 ; } std :: queue <pair<TreeNode*, int >> q; q.push(make_pair(root, 0 )); int maxWidth = 1 ; while (!q.empty()){ int sizeQ = q.size(); int left; for ( int i = 0 ; i < sizeQ; i++){ pair<TreeNode*, int > tmp = q.front(); q.pop(); if (i == 0 ){ left = tmp.second; ...

Code ( Language :C++) Edit class Solution { public : /** * @param words: List[str] * @return: return List[str] */ vector < string > findAllConcatenatedWordsInADict( vector < string > &words) { // write your code here unordered_set < string > hset; int maxLen = 0 ; int minLen = INT_MAX; /*for(auto i : words){ hset.insert(i); int tmp = i.size(); minLen = min(minLen, tmp); maxLen = max(maxLen, tmp); } */ hset.insert(words.begin(), words.end()); vector < string > res; for ( auto word : words){ /*if(word.size() == minLen){ continue; } */ int n = word.size(); vector < bool > dp(n + 1 ); dp[ 0 ] = true ; for ( int i = 0 ; i < n; ++i) { if (dp[i] == 0 ) { ...

Code ( Language :C++) Edit class Solution { public : /** * @param rooms: m x n 2D grid * @return: nothing */ struct node { int x, y; node( int a, int b){ x = a; y = b; } }; const vector < int > dx = { -1 , 1 , 0 , 0 }; const vector < int > dy = { 0 , 0 , -1 , 1 }; const int dir = 4 ; void wallsAndGates ( vector < vector < int >> &rooms) { // write your code here //BFS 层层剥洋葱；target入栈;全部target入栈 const int m = rooms.size(); if (m == 0 ){ return ; } const int n = rooms[ 0 ].size(); std :: queue <node> q; for ( int i = 0 ; i < m; i++){ for ( int j = 0 ; j < n; j++){ if (rooms[i][j] == 0 ){ q.push(node(i, j)); } } } // BFS with queue 模板 while (!q...

Code ( Language :C++) Edit class Solution { public : /** * @param str: s string * @return: return an integer, denote the number of the palindromic substrings */ int countPalindromicSubstrings ( string &str) { // write your code here //解放思想。用DP[i][j]表示起始第i和结尾第j个元素是否pali。 // transfer: if(str[i - 1] == str[j - 1] && DP[i + 1][j-1]) DP[i][j] = true; //initial: dp[i][i] = true; const int n = str.size(); if (n == 0 ){ return 0 ; } std :: vector < vector < bool >> DP(n + 1 , vector < bool >(n + 1 , false )); for ( int i = 0 ; i <= n; i++){ DP[i][i] = true ; } int res = 0 ; for ( int i = n; i >= 1 ; i--){ for ( int j = i; j <= n; j++){ if (j == i + 1 ){ DP[i][j] = (str[i - 1 ] == str[j - 1 ]); } else ...

Code ( Language :C++) Edit class Solution { public : /** * @param A: a sparse matrix * @param B: a sparse matrix * @return: the result of A * B */ vector < vector < int >> multiply( vector < vector < int >> &A, vector < vector < int >> &B) { // write your code here vector < vector < int >> res; const int mA = A.size(); const int mB = B.size(); if (mA == 0 || mB == 0 ){ return res; } const int nA = A[ 0 ].size(); const int nB = B[ 0 ].size(); if (nA != mB){ return res; } // search non 0 in each row of B; vector < vector < int >> non0B(mB, vector < int >()); for ( int j = 0 ; j < mB; j++){ for ( int i = 0 ; i < nB; i++){ if (B[j][i]){ non0B[j].push_back(i); ...

Code ( Language :C++) Edit class Solution { public : /** * @param str: the given string * @return: the maximum value */ int calcMaxValue ( string &str) { // write your code here ///这个题很有代表性。开始时，想的特别复杂，DFS, 每个位置放 * 还是+，括号放哪里，特别复杂。 //实际本题就是DP解，每一步有两个action * or +，基于上一步的最大值，在两个action中选当前最大值。 //解法思想。别老想着DFS，所有可能。 const int n = str.size(); if (n == 0 ){ return 0 ; } int res = 0 ; for ( int i = 0 ; i < n; i++){ int v = str[i] - '0' ; res = max(res + v, res * v); } return res; } };