Day 123, #261 #266 #269 #270, Graph Valid Tree, Palindrome Permutation, Alien Dictionary, Closest Binary Search Tree Value

Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Hint:

1. Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?
2. According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together inedges.

-------------------------------------------------------------
找环和联通
DFS的做法
出错点：
#1 如何建立graph
#2 因为是无向图，参数中要传入parent节点

class Solution {
public:
    bool dfs(vector<bool> &visit,vector<vector<int>> &graph,int node,int parent) {
        if (visit[node]) return false;
        visit[node] = true;
        for (int i = 0; i < graph[node].size(); i++) {
            if (graph[node][i] == parent) continue;
            if (!dfs(visit,graph,graph[node][i],node)) return false;
        }
        
        return true;
    }

    bool validTree(int n, vector<pair<int, int>>& edges) {
        vector<vector<int>> graph(n,vector<int>());
        for (int i = 0; i < edges.size(); i++) {
            graph[edges[i].first].push_back(edges[i].second);
            graph[edges[i].second].push_back(edges[i].first);
        }
        
        vector<bool> visit(n,false);
        if (!dfs(visit,graph,0,0)) return false;
        
        for (int i = 0; i < n; i++) {
            if (!visit[i]) return false;
        }
        
        return true;
    }
};

union find的方法
http://blog.csdn.net/dm_vincent/article/details/7655764

class UnionFind {
public:
    UnionFind(int n) {
        for (int i = 0; i < n; i++) {
            parent.push_back(i);
            size.push_back(1);
        }
        count = n;
    }
    int find(int num) {
        while (num != parent[num]) {
            num = parent[num];
        }
        return num;
    }
    
    void do_union(int num1,int num2) {
        int f1 = find(num1),f2 = find(num2);
        if (f1 == f2) return;
        if (size[f1] > size[f2]) {
            size[f1] += size[f2];
            parent[f2] = f1;
        }else {
            size[f2] += size[f1];
            parent[f1] = f2;
        }
        count--;
    }
    
    bool isTree() {
        return count == 1;
    }
    
private:
    vector<int> parent;
    vector<int> size;
    int count;
};

class Solution {
public:
    bool validTree(int n, vector<pair<int, int>>& edges) {
        UnionFind uf(n);
        for (int i = 0; i < edges.size(); i++) {
            if (uf.find(edges[i].first) == uf.find(edges[i].second)) {
                return false;
            }
            uf.do_union(edges[i].first,edges[i].second);
        }
        
        return uf.isTree();
    }
};

Palindrome Permutation

Given a string, determine if a permutation of the string could form a palindrome.

For example,
"code" -> False, "aab" -> True, "carerac" -> True.

Hint:

1. Consider the palindromes of odd vs even length. What difference do you notice?
2. Count the frequency of each character.
3. If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

----------------------------------------------------------------------

class Solution {
public:
    bool canPermutePalindrome(string s) {
        vector<bool> alph(256,false);
        int single = 0;
        for (int i = 0; i < s.length(); i++) {
            if(!alph[s[i]]) {
                single++;
            }else {
                single--;
            }
            alph[s[i]] = !alph[s[i]];
        }
        
        return single < 2;
    }
};

Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of words from the dictionary, wherewords are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

For example,
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Note:

1. You may assume all letters are in lowercase.
2. If the order is invalid, return an empty string.
3. There may be multiple valid order of letters, return any one of them is fine.

------------------------------------------------------------------------------------
COME_BACK
出错点：16 - 23行，建graph的时候，要遍历所有string
graph的形式也可以用set，适合稀疏型

class Solution {
public:
    void createGraph(vector<string>& words,vector<vector<bool>> &graph,vector<bool> &exist) {
        words.insert(words.begin(),"");
        for (int i = 1; i < words.size(); i++) {
            int j = 0, k = 0;
            string s1 = words[i - 1],s2 = words[i]; 
            while (j < s1.length() && k < s2.length() && s1[j] == s2[k]) {
                exist[s1[j] - 'a'] = true;
                j++;
                k++;
            }
            if (j < s1.length() && k < s2.length()) {
                graph[s1[j] - 'a'][s2[k] - 'a'] = true;
            }
            while (j < s1.length()) {
                exist[s1[j] - 'a'] = true;
                j++;
            }
            while (k < s2.length()) {
                exist[s2[k] - 'a'] = true;
                k++;
            }
        }
    }

    void dfs(vector<vector<bool>> &graph,vector<int> &visit,char node,bool &cycle,string &order) {
        if (visit[node - 'a'] == -1) {
            cycle = true;
            return;
        }
        if (visit[node - 'a'] == 1) return;
        
        visit[node - 'a'] = -1;
        for (char i = 'a'; i <= 'z'; i++) {
            if (graph[node - 'a'][i - 'a']) dfs(graph,visit,i,cycle,order);
        }
        
        visit[node - 'a'] = 1;
        order = node + order;
    }

    string topSort(vector<vector<bool>> &graph,vector<bool> &exist) {
        vector<int> visit(26,0);
        string order = "";
        bool cycle =false;
        
        for (char i = 'a'; i <= 'z'; i++) {
            if (exist[i - 'a']) dfs(graph,visit,i,cycle,order);
        }
        
        if (cycle) return "";
        return order;
    }

    string alienOrder(vector<string>& words) {
        vector<vector<bool>> graph(26,vector<bool>(26,false));
        vector<bool> exist(26,false);
        createGraph(words,graph,exist);

        return topSort(graph,exist);
    }
};

Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

• Given target value is a floating point.
• You are guaranteed to have only one unique value in the BST that is closest to the target.

-----------------------------------------------------------------
递归，注意传入的cur是pass by reference

/**
 * 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 helper(TreeNode* root, double target, TreeNode* &cur) {
        if (root == NULL) return;
        if (cur == NULL || abs(root->val - target) < abs(cur->val - target)) {
            cur = root;
        }
        
        if (root->val > target) {
            helper(root->left,target,cur);
        }else if (root->val < target) {
            helper(root->right,target,cur);
        }
    }

    int closestValue(TreeNode* root, double target) {
        TreeNode *cur = NULL;
        helper(root,target,cur);
        return cur->val;
    }
};

遍历

/**
 * 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 closestValue(TreeNode* root, double target) {
        int closest = root->val;
        while (root) {
            if (abs(root->val - target) < abs(closest - target)) {
                closest = root->val;
            }
            if (root->val < target) {
                root = root->right;
            }else {
                root = root->left;
            }
        }
        return closest;
    }
};