Google Onsite

楼主有结果了吗？

kinggarden2001 发表于 2015-12-28 01:52
leetcode昨天刚加了这个题 用dp算最少个数 同时cache每步的最优解 最后应该能同时得出最少个数以及是哪些硬 ...

怎么cache呢？用hashMap吗？

bounded blocking queue应该还需要是add什么东西吧？不能只有时间吧？

写了下打印树的题，最后输出格式还是有一些差异

1. public class PrintStructrue {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 PrintStructrue ps = new PrintStructrue();
   
5.                 int[][] edges = { { 7, 6 }, { 7, 5 }, { 7, 4 }, { 6, 3 }, { 6, 2 } };
   
6.                 ps.printStructure(edges);
   
7.         }
   
8. 
   
9.         public void printStructure(int[][] edges) {
   
10.                 if (edges == null || edges.length == 0) {
    
11.                         return;
    
12.                 }
    
13.                 HashMap<Integer, HashSet<Integer>> graph = buildGraph(edges);
    
14.                 HashMap<Integer, Integer> counter = new HashMap<Integer, Integer>();
    
15.                 for (HashSet<Integer> set : graph.values()) {
    
16.                         for (int ele : set) {
    
17.                                 if (counter.containsKey(ele)) {
    
18.                                         counter.put(ele, counter.get(ele) + 1);
    
19.                                 } else {
    
20.                                         counter.put(ele, 1);
    
21.                                 }
    
22.                         }
    
23.                 }
    
24.                 Queue<Integer> queue = new LinkedList<Integer>();
    
25.                 for (int ele : graph.keySet()) {
    
26.                         if (!counter.containsKey(ele)) {
    
27.                                 queue.offer(ele);
    
28.                         }
    
29.                 }
    
30.                 while (!queue.isEmpty()) {
    
31.                         int val = queue.poll();
    
32.                         print(val, graph, 0);
    
33.                 }
    
34.         }
    
35. 
    
36.         private void print(int val, HashMap<Integer, HashSet<Integer>> graph,
    
37.                         int len) {
    
38.                 for (int i = 0; i < len; i++) {
    
39.                         if (i == 0) {
    
40.                                 System.out.print(" ");
    
41.                         }
    
42.                         System.out.print("-");
    
43.                 }
    
44.                 System.out.println(val);
    
45.                 for (int i : graph.get(val)) {
    
46.                         print(i, graph, len + 1);
    
47.                 }
    
48.         }
    
49. 
    
50.         private HashMap<Integer, HashSet<Integer>> buildGraph(int[][] edges) {
    
51.                 HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
    
52.                 for (int[] edge : edges) {
    
53.                         if (!map.containsKey(edge[0])) {
    
54.                                 map.put(edge[0], new HashSet<Integer>());
    
55.                         }
    
56.                         if (!map.containsKey(edge[1])) {
    
57.                                 map.put(edge[1], new HashSet<Integer>());
    
58.                         }
    
59.                         map.get(edge[0]).add(edge[1]);
    
60.                 }
    
61.                 return map;
    
62.         }
    
63. }
    

复制代码

bobzhang2004 发表于 2016-1-24 18:02
写了下打印树的题，最后输出格式还是有一些差异

你好，请问这一题的题目是什么意思能和我说下吗，看不明白，谢谢！

第五轮是找硬币题，不过是打印出最少硬币的序列.这个题是要怎么存序列呢？hashmap还是stack

coin题，假设每个硬币只能用一次

1. public class CoinsChangeIII {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int[] coins = { 1, 2, 3, 4, 5, 6, 10 };
   
5.                 List<Integer> res = minChange(coins, 9);
   
6.                 for (int i : res) {
   
7.                         System.out.print(i + " ");
   
8.                 }
   
9.         }
   
10. 
    
11.         public static List<Integer> minChange(int[] coins, int num) {
    
12.                 int[] table = new int[num + 1];
    
13.                 int[] solution = new int[num + 1];
    
14.                 Arrays.fill(table, Integer.MAX_VALUE);
    
15.                 table[0] = 0;
    
16.                 for (int i = 0; i < coins.length; i++) {
    
17.                         for (int j = num; j > 0; j--) {
    
18.                                 if (j >= coins[i] && table[j - coins[i]] != Integer.MAX_VALUE ) {
    
19.                                         if (table[j - coins[i]] + 1 < table[j]) {
    
20.                                                 table[j] = table[j - coins[i]] + 1;
    
21.                                                 solution[j] = i;
    
22.                                         }
    
23.                                 }
    
24.                         }
    
25.                 }
    
26.                
    
27.                 List<Integer> res = new ArrayList<Integer>();
    
28.                 if (table[num] == Integer.MAX_VALUE) {
    
29.                         return res;
    
30.                 }
    
31.                 while (num > 0) {
    
32.                         res.add(coins[solution[num]]);
    
33.                         num -= coins[solution[num]];
    
34.                 }
    
35.                 Collections.reverse(res);
    
36.                 return res;
    
37. 
    
38.         }
    
39. }
    

复制代码

coin题，假设每个硬币可以用多次

1. public class CoinsChangeII {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int[] coins = { 1, 4, 5, 10 };
   
5.                 List<Integer> res = minChange(coins, 8);
   
6.                 for (int i : res) {
   
7.                         System.out.print(i + " ");
   
8.                 }
   
9.         }
   
10. 
    
11.         public static List<Integer> minChange(int[] coins, int num) {
    
12.                 int[] table = new int[num + 1];
    
13.                 int[] solution = new int[num + 1];
    
14.                 for (int i = 1; i <= num; i++) {
    
15.                         int minNum = Integer.MAX_VALUE;
    
16.                         int minIndex = Integer.MAX_VALUE;
    
17.                         for (int j = 0; j < coins.length; j++) {
    
18.                                 if (coins[j] <= i && 1 + table[i - coins[j]] < minNum) {
    
19.                                         minNum = 1 + table[i - coins[j]];
    
20.                                         minIndex = j;
    
21.                                 }
    
22.                         }
    
23.                         table[i] = minNum;
    
24.                         solution[i] = minIndex;
    
25.                 }
    
26. 
    
27.                 List<Integer> res = new ArrayList<Integer>();
    
28.                 if (table[num] == Integer.MAX_VALUE) {
    
29.                         return res;
    
30.                 }
    
31.                 while (num > 0) {
    
32.                         res.add(coins[solution[num]]);
    
33.                         num -= coins[solution[num]];
    
34.                 }
    
35. 
    
36.                 return res;
    
37. 
    
38.         }
    
39. }
    

复制代码

硬币题我是dp时每个点都用一个list来保存路径

补充内容 (2016-5-1 02:55):
不知道面试官希望的是什么样子的？