Path Sum II

运用前序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void findPaths(TreeNode* node, int sum, vector<int>& path, vector<vector<int> >& paths) {
        if (!node) return;
        path.push_back(node -> val);
        if (!(node -> left) && !(node -> right) && sum == node -> val)
            paths.push_back(path);
        findPaths(node -> left, sum - node -> val, path, paths);
        findPaths(node -> right, sum - node -> val, path, paths);
        path.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int> > paths;
        vector<int> path;
        findPaths(root, sum, path, paths);
        return paths;
    }
};

2017/12/19 posted in leetcode

Path Sum

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == NULL) return false;
        if (root->val == sum && root->left ==  NULL && root->right == NULL) return true;
        
        return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
    }
};

2017/12/19 posted in leetcode

Linked List Cycle II

题目链接：https://leetcode.com/problems/linked-list-cycle-ii/description/

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head==NULL||head->next==NULL) {
            return NULL;
        }
        ListNode *slow = head;
        ListNode *fast = head;
        ListNode *entry = head;
        while (fast->next&&fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast==slow) {
                while (slow!=entry) {
                    slow = slow->next;
                    entry = entry->next;
                }
                return entry;;
            }
        }
        return NULL;
    }
};

2017/12/16 posted in leetcode

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

使用快慢两个指针来判断是否有环，当有环的时候，快指针会停留在环内知道慢指针赶上与之相等。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head==NULL||head->next==NULL) {
            return 0;
        }
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast->next&&fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast==slow) {
                return 1;
            }
        }
        return 0;
    }
};

2017/12/16 posted in leetcode

 Convert a Number to Hexadecimal

class Solution {
public:
    string toHex(int num) {
        const string HEX ="0123456789abcdef";
        if (num==0) return "0";
        string res ="";
        int count  = 0;
        while (num&&count++<8) {
            //&0xf表示取二进制的低四位
            res = HEX[(num&0xf)]+res;
            num>>=4;
        }
        return res;
    }
};

2017/12/13 posted in leetcode

Number of Boomerangs

class Solution {
public:
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int res = 0;
        for (int i =0; i<points.size(); i++) {
            unordered_map<long, int> map(points.size());
            for (int j = 0; j<points.size(); j++) {
                if (j==i) continue;
                int dy = points[j].second - points[i].second;
                int dx = points[j].first - points[i].first;

                int dis = dy*dy + dx*dx;
                map[dis]++;
            }

            for (auto p : map) {
                if (p.second>1) {
                    /*
                     * for all the groups of points,
                     * number of ways to select 2 from n =
                     * nP2 = n!/(n - 2)! = n * (n - 1)
                     */
                    res+=p.second*(p.second-1);
                }
            }
        }
        return res;
    }
};