图 2016-08-31

[wolfogre]

310. Minimum Height Trees

332. Reconstruct Itinerary

[wolfogre]

// [AC] 310. Minimum Height Trees
public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        ArrayList result = new ArrayList();
        if(n == 1){
            result.add(0);
            return result;
        }
        if(n == 2){
            result.add(0);
            result.add(1);
            return result;
        }
        int[] degree = new int[n];
        HashSet<Integer>[] graph = new HashSet[n];
        for(int i = 0; i < n; ++i){
            graph[i] = new HashSet();
        }
        for(int i = 0; i < edges.length; ++i){
            graph[edges[i][0]].add(edges[i][1]);
            graph[edges[i][1]].add(edges[i][0]);
            ++degree[edges[i][0]];
            ++degree[edges[i][1]];
        }
        LinkedList<Integer> queue = new LinkedList<Integer>();
        for(int i = 0; i < n; ++i){
            if(degree[i] == 1){
                queue.add(i);
            }
        }

        while(!queue.isEmpty()){
            LinkedList<Integer> tempQueue = new LinkedList<Integer>();
            result.clear();
            while(!queue.isEmpty()){
                int node1 = queue.remove();
                if(result.size() < 2)
                    result.add(node1);
                if(graph[node1].size() != 0){
                    int node2 = (Integer)graph[node1].iterator().next();
                    graph[node2].remove(node1);
                    if(--degree[node2] == 1){
                        tempQueue.add(node2);
                    } 
                }

            }
            queue = tempQueue;
        } 
        return result;
    }

}

[wolfogre]

// [AC] 332. Reconstruct Itinerary
public class Solution {
    class LinkedNode{
        public String value;
        public LinkedNode next;
        public LinkedNode(String value, LinkedNode next){
            this.value = value;
            this.next = next;
        }
    }

    public List<String> findItinerary(String[][] tickets) {
        ticketsCount = tickets.length;
        graph = new HashMap<>();
        for(String[] strs : tickets){
            LinkedNode aim = graph.get(strs[0]);
            if(aim == null){
                aim = new LinkedNode("HEAD", null);
                graph.put(strs[0], aim);
            }
            LinkedNode pre = aim;
            LinkedNode p = aim.next;
            while(p != null && p.value.compareTo(strs[1]) < 0){
                pre = p;
                p = p.next;
            }
            pre.next = new LinkedNode(strs[1], p);
        }
        result = new Stack<String>();
        result.push("JFK");
        backtrack("JFK");
        List<String> resultForReturn = new ArrayList<String>(ticketsCount);
        for(String str : result){
            resultForReturn.add(str);
        }
        return resultForReturn;
    }

    private int ticketsCount;
    private Stack<String> result;
    private HashMap<String, LinkedNode> graph;

    private boolean backtrack(String from){
        if(ticketsCount == 0)
            return true;
        LinkedNode pre = graph.get(from);
        if(pre == null)
            return false;
        LinkedNode p = pre.next;
        while(p != null){
            pre.next = p.next;
            result.push(p.value);
            --ticketsCount;
            if(backtrack(p.value))
                return true;
            ++ticketsCount;
            result.pop();
            pre.next = p;
            pre = p;
            p = p.next;
        }
        return false;
    }
}

[zhaokuohaha]

310 - C# - 两遍扫描

public class Solution
{
    int n;
    List<int>[] e;
    private void bfs(int start,int[] dist, int[] pre)
    {
        bool[] visited = new bool[n];
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(start);
        dist[start] = 0;
        visited[start] = true;
        pre[start] = -1;

        while (queue.Any())
        {
            int u = queue.Dequeue();
            foreach(var v in e[u])
            {
                if (!visited[v])
                {
                    queue.Enqueue(v);
                    visited[v] = true;
                    dist[v] = dist[u] + 1;
                    pre[v] = u;
                }
            }
        }
    }
    public IList<int> FindMinHeightTrees(int n, int[,] edges)
    {
        if (n <= 0) return new List<int>();
        this.n = n;
        e = new List<int>[n];
        for(int i=0; i<n; i++)
        {
            e[i] = new List<int>();
        }

        for(int i=0; i<edges.GetLength(0); i++)
        {
            int a = edges[i, 0];
            int b = edges[i, 1];
            e[a].Add(b);
            e[b].Add(a);
        }

        int[] d1 = new int[n];
        int[] d2 = new int[n];
        int[] pre = new int[n];

        bfs(0, d1, pre);
        int u = 0;
        for (int i = 0; i < n; i++)
            if (d1[i] > d1[u])
                u = i;//找到最远的节点

        bfs(u, d2, pre);
        int v = 0;
        for (int i = 0; i < n; i++)
            if (d2[i] > d2[v])
                v = i;//找到距离最长的两个节点

        //将所有节点连成一条链
        List<int> list = new List<int>();
        while(v != -1)
        {
            list.Add(v);
            v = pre[v];
        }

        //返回结果: 奇数长度返回一个节点, 偶数长度返回俩节点
        List<int> res = new List<int>();
        res.Add(list[(list.Count - 1) / 2]);
        if (list.Count % 2 == 0)
            res.Add(list[list.Count / 2]);
        return res;

    }
}

[zhaokuohaha]

没通过, 思路到这里尽了, dfs不会写

public class Solution
{
    public IList<string> FindItinerary(string[,] tickets)
    {
        SortedDictionary<string, List<string>> e = new SortedDictionary<string, List<string>>();
        for(int i=0; i<tickets.GetLength(0); i++)
        {
            if (e.ContainsKey(tickets[i, 0]))
                e[tickets[i, 0]].Add(tickets[i, 1]);
            else
                e.Add(tickets[i, 0], new List<string>() { tickets[i, 1] });
        }
        foreach(var item in e)
        {
            item.Value.Sort();
        }

        List<string> res = new List<string>();
        dfs(e, e.First().Key, res, 0);
        return res;
    }

    private bool dfs(SortedDictionary<string, List<string>> e, string key, List<string> res, int count)
    {
        if (count >= e.Count) return true;
        if (!res.Contains(key))
        {   
            count++;
        }
        res.Add(key);
        for(int i=0; i<e[key].Count; i++)
        {
            string item = e[key][i];
            e[key].RemoveAt(i);
            if (dfs(e, item, res, count))
                return true; ;
            e[key].Add(item);
        }
        res.Remove(key);
        return false;
    }
}

[zhaokuohaha]

332 - C# - 来自别人的代码

public class Solution
{
    public IList<string> FindItinerary(string[,] tickets)
    {
        Dictionary<string, List<string>> e = new Dictionary<string, List<string>>();
        for (int i = 0; i < tickets.GetLength(0); i++)
        {
            if (!e.ContainsKey(tickets[i, 0]))
                e.Add(tickets[i, 0], new List<string>());
            e[tickets[i, 0]].Add(tickets[i, 1]);
        }
        foreach (var list in e.Values)
            list.Sort();
        return dfs("JFK", tickets.GetLength(0), e);
    }

    private List<string> dfs(string key, int count, Dictionary<string, List<string>> e)
    {
        if(e.ContainsKey(key) && e[key].Count > 0)
        {
            for(int i=0; i<e[key].Count; i++)
            {
                var item = e[key][i];
                e[key].RemoveAt(i);
                count--;

                var best = dfs(item, count, e);
                e[key].Insert(i, item);
                count++;

                if(best != null)
                {
                    best.Insert(0, key);
                    return best;
                }
            }
            return null;
        }
        if (count == 0)
            return new List<string> { key };
        return null;
    }
}

[SnackMen]

/*
*[AC]310. Minimum Height Trees
*/
public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> List = new ArrayList<Integer>();
        if(n==0)
            return new ArrayList<>();
        if(n==1){
            List<Integer> list = new ArrayList<Integer>();
            list.add(0);
            return list;
        }
        List<Integer> []lists = new ArrayList[n];
        for(int i=0;i<n;i++)
            lists[i] = new ArrayList<> ();

        for(int i=0;i<edges.length;i++){
            int num1 = edges[i][0];
            int num2 = edges[i][1];
            lists[num1].add(num2);
            lists[num2].add(num1);
        }

        List<Integer> leave = new ArrayList<Integer> ();
        for(int i=0;i<n;i++){
            if(lists[i].size()==1)
                leave.add(i);
        }

        int count = n;
        while(count>2){
            int size = leave.size();
            count-=size;
            List<Integer> newLeave = new ArrayList<Integer>();
            for(int i=0;i<size;i++){
                int lef = leave.get(i);
                for(int j=0;j<lists[lef].size();j++){
                    int remove = lists[lef].get(j);
                    lists[remove].remove(Integer.valueOf(lef));
                    if(lists[remove].size()==1)
                        newLeave.add(remove);
                }
            }
            leave=newLeave;
        }
        return leave;

    }
}