A Code

class Solution { public : /** * @param inorder: A list of integers that inorder traversal of a tree * @param postorder: A list of integers that postorder traversal of a tree * @return: Root of a tree */ unordered_map < int , int > mp; TreeNode * buildTree ( vector < int > &preorder, vector < int > &inorder) { // write your code here // preorder: 根左右 // inorder: 左根右 // 根据preoder中的根，找到inorder中position, then the left side is the left substree, the right side is the right substree // recursion TreeNode *res; int sizeN = preorder.size(); if (sizeN == 0 ){ return NULL ; } for ( int i = 0 ; i < sizeN; i++){ mp[inorder[i]] = i; } return build(preorder, 0 , preorder.size() - 1 , inorder, 0 , inorder.size() - 1 ); } TreeNode * build ( vector < int > &preorder, int...

缘起: 该类型是从sring中提炼出想要的string，比如去掉空格，不合要求的字符，然后结果输出一个新的提炼后的字符串。可以用一个string vector在遍历原来string的时候，把每个比如空格之前的字符放入这个vector中，然后整理这个vector，得出想要的字符串。 步骤: 1,遍历原来string，在遍历中去掉不合法的字符。 坑点： 1，注意index不要越界，只要有while的地方，条件里一定要带着 i < size. 2,  在while里面的while结束，要判断if(i == size)， 然后进行相应操作。 3，最外面的while结束后，在return前，想想是否需要额外操作处理结尾处。 题目： 53. Reverse Words in a String 421. Simplify Path 1394. Goat Latin string simplifyPath ( string &path) { // write your code here // 主体就是找 / 之间的string const int size = path.size(); if (size == 0 ){ return "/" ; } std :: vector < string > strs; int i = 0 ; while (i < size){ while (i < size && path[i] == '/' ){ i++; } if (i == size){ break ; } int start = i; while (i < size && path[i] != '/' ){ i++...

string simplifyPath ( string &path) { // write your code here const int size = path.size(); if (size == 0 ){ return "/" ; } std :: vector < string > strs; int i = 0 ; while (i < size){ while (i < size && path[i] == '/' ){ i++; } if (i == size){ break ; } int start = i; while (i < size && path[i] != '/' ){ i++; } string sub = path.substr(start, i - start); if (sub == "." ){ continue ; } else if (sub == ".." ){ if (!strs.empty()){ strs.pop_back(); } } else { strs.push_back(sub); } } if (strs.size() == 0 ){ ...

class Solution { public : /** * @param A: A list of integers * @return: A boolean */ bool canJump ( vector < int > &A) { // write your code here const int size = A.size(); if (size == 0 ){ return false ; } int longest = 0 + A[ 0 ]; for ( int i = 1 ; i < size; i++){ if (longest >= i){ longest = max(longest, i + A[i]); } } return longest >= size - 1 ; } };

ListNode * swapPairs (ListNode * head) { // write your code here //要用dummy, 要打断三个link，也就重建三个link。dummy->1->2->3,变成dummy -> 2->1->3 if (head == NULL || head->next == NULL ){ return head; } ListNode *dummy = new ListNode( 0 ); dummy->next = head; ListNode *pre = dummy; while (head != NULL && head->next != NULL ){ ListNode *temp = head->next->next; head->next->next = head; //重建第一个link pre->next = head->next; //重建第二个link head->next = temp; //重建第三个link pre = head; //更新，准备下一次的重建 head = temp; } return dummy->next; }

class Solution { public : /** * @param root: The root of binary tree. * @return: An integer */ struct resType { int root2Any; int any2Any; }; int maxPathSum (TreeNode * root) { // write your code here if (root == NULL ){ return 0 ; } resType res = pathSum(root); return res.any2Any; } resType pathSum (TreeNode *root) { resType res; res.root2Any = INT_MIN; res.any2Any = INT_MIN; if (root == NULL ){ return res; } resType left = pathSum(root->left); resType right = pathSum(root->right); res.root2Any = max(max(left.root2Any, right.root2Any), 0 ) + root->val; res.any2Any = max(max(left.any2Any, right.any2Any), root->val + max(left.root2Any, 0 ) + max(right.root2Any, 0 )); return res; } };

ListNode * detectCycle (ListNode * head) { // write your code here if (head == NULL ){ return head; } ListNode *slow = head; ListNode *fast = head; while (fast != NULL && fast->next != NULL ){ slow = slow->next; fast = fast->next->next; if (slow == fast){ break ; } } if (fast == NULL || fast->next == NULL ){ return NULL ; } while (head != slow){ head = head->next; slow = slow->next; } return head; }

class Solution { public : /** * @param matrix: a matrix of m x n elements * @return: an integer list */ vector < int > spiralOrder( vector < vector < int >> &matrix) { // write your code here vector < int > res; const int m = matrix.size(); if (m == 0 ){ return res; } const int n = matrix[ 0 ].size(); int count = 0 ; while (count * 2 < n && count * 2 < m){ for ( int j = count; j < n - count; j++){ res.push_back(matrix[count][j]); } for ( int i = count + 1 ; i < m - count; i++){ res.push_back(matrix[i][n - 1 - count]); } if (m - 2 * count == 1 || n - 2 * count == 1 ){ break ; } for ( int j = n - 2 - count; j >= count; j--){ res.push_back(matrix[m - 1 - count][j]); ...