A Code

Given a binary tree, find all paths that sum of the nodes in the path equals to a given number  target . A valid path is from root node to any of the leaf nodes. Have you met this question in a real interview?    Yes Problem Correction Example Example 1: Input: {1,2,4,2,3} 5 Output: [[1, 2, 2],[1, 4]] Explanation: The tree is look like this: 1 / \ 2 4 / \ 2 3 For sum = 5 , it is obviously 1 + 2 + 2 = 1 + 4 = 要用就用dfs模板，减小出错的可能。 vector < vector < int >> binaryTreePathSum(TreeNode * root, int target) { // write your code here //典型的DFS vector < vector < int >> res; if (root == NULL ){ return res; } vector < int > path; dfs(root, target, res, path); return res; } void dfs (TreeNode *root, int target, vector < vector < int >> &res, vector < int > &path) { if (root ...

Description 中文 English Given a binary tree containing digits from  0-9  only, each root-to-leaf path could represent a number. An example is the root-to-leaf path  1->2->3  which represents the number  123 . Find the total sum of all root-to-leaf numbers. A leaf is a node with no children. Have you met this question in a real interview?    Yes Problem Correction Example Example: Input: [1,2,3] 1 / \ 2 3 Output: 25 Explanation: The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13. Therefore, sum = 12 + 13 = 25. Example 2: Input: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 Output: 1026 Explanation: The root-to-leaf path 4->9->5 represents the number 495. The root-to-leaf path 4->9->1 represents the number 491. The root-to-leaf path 4->0 represents the number 40. Therefore, sum = 495 + 491 + 40 = 1026. class Solu...

For an array A, if i < j, and A [i] > A [j], called (A [i], A [j]) is a reverse pair. return total of reverse pairs in A. Have you met this question in a real interview?    Yes Problem Correction Example Example1 Input: A = [2, 4, 1, 3, 5] Output: 3 Explanation: (2, 1), (4, 1), (4, 3) are reverse pairs Example2 Input: A = [1, 2, 3, 4] Output: 0 Explanation: No reverse pair class Solution { public : /** * @param A: an array * @return: total of reverse pairs */ long long reversePairs ( vector < int > &nums) { // write your code here //和1297. Count of Smaller Numbers After Self一模一样，只是结果输出不同 vector < int > t; vector < int > res(nums.size()); for ( int i = nums.size() - 1 ; i >= 0 ; --i) { int left = 0 , right = t.size(); while (left < right) { int mid = left + (right - left) / 2 ; ...

There are n  coins in a row, each time you want to take a coin from the left or the right side. Take a total of  k  times to write an algorithm to maximize the value of coins. 1 <= k <= n <= 100000 。 The value of the coin is not greater than  10000 。 Have you met this question in a real interview?    Yes Problem Correction Example Given list =  [5,4,3,2,1] , k =  2 , return  9 . Explanation: Take two coins from the left. Given list =  [5,4,3,2,1,6] , k =  3 , return  15 . Explanation: Take two coins from the left and one from the right. class Solution { public : /** * @param list: The coins * @param k: The k * @return: The answer */ int takeCoins ( vector < int > & list , int k) { // Write your code here int n = list .size(); vector < int > prefixSum(n + 1 , 0 ); for ( int i = 0 ; i < n; ...

Code ( Language :C++) Description 中文 English Given a singly linked list L: L 0  → L 1  → … → L n-1  → L n reorder it to: L 0  → L n  → L 1  → L n-1  → L 2  → L n-2  → … Have you met this question in a real interview?    Yes Problem Correction Example Example 1: Input: 1->2->3->4->null Output: 1->4->2->3->null Example 2: Input: 1->2->3->4->5->null   Output: 1->5->2->4->3->null Edit /** * Definition of singly-linked-list: * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public : /** * @param head: The head of linked list. * @return: nothing */ void reorderList (ListNode * head) { // write your code here // 1.find middle ...