 Longest Univalue Path

/**
 * 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:
    int dfs(TreeNode* node, int& lup) {
        int l = node->left ? dfs(node->left, lup) : 0;
        int r = node->right ? dfs(node->right, lup) : 0;
        int resl = node->left && node->left->val == node->val ? l + 1 : 0;
        int resr = node->right && node->right->val == node->val ? r + 1 : 0;
        lup = max(lup, resl + resr);
        return max(resl, resr);
    }

    int longestUnivaluePath(TreeNode* root) {
        int lup = 0;
        if (root) dfs(root, lup);
        return lup;
    }
};

2017/12/22 posted in leetcode

Isomorphic Strings

一开始写的代码，超时版本，用的集合。

bool isIsomorphic(string s, string t) {
    unordered_map<char, set<int>> Smap;
    unordered_map<char, vector<int>> Tmap;
    for (int i = 0; i<s.size(); i++) {
        Smap[s[i]].insert(i);
        Tmap[t[i]].push_back(i);
    }
    if (Smap.size()!=Tmap.size()) {
        return 0;
    }else{
        for (int j = 0; j<s.size(); j++) {
            vector<int> a = Tmap[t[j]];
            set<int> b = Smap[s[j]];
            int len = b.size();
            for (auto num : a) {
                b.insert(num);
                if (len!=b.size()) {
                    return 0;
                }
            }
        }
    }
    
    return 1;
}

修改后的版本。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int m1[256] = {0}, m2[256] = {0}, n = s.size();
        for (int i = 0; i < n; ++i) {
            if (m1[s[i]] != m2[t[i]]) return false;  //判断两个字符串i位置的字符上次出现的位置是否一样。
            m1[s[i]] = i + 1;   //记录上次该字符出现的位置
            m2[t[i]] = i + 1;   //记录上次该字符出现的位置
        }
        return true;
    }
};

2017/12/20 posted in leetcode

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;
    }
};