IXL电面已跪

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

zzzhu 发表于 2017-9-29 05:12
额这我也不知道了。。。

domain reduction具体怎么用丫

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

看着可以用动态规划，其实是背包问题的变种

用HashMap构建target, 然后用backtracking计算level. 取最小的level? 感觉不是0/1背包问题 因为sticker可以拆开

楼主你好，例子是要用English 和 story 两个词build嘛？

byeu 发表于 2017-10-1 02:59
楼主你好，例子是要用English 和 story 两个词build嘛？

是这个意思

dahuo2013 发表于 2017-9-30 19:10
用HashMap构建target, 然后用backtracking计算level. 取最小的level? 感觉不是0/1背包问题 因为sticker可以 ...

我也没啥好的方法，就是backtracking一个一个试

尝试写了一下代码，若有问题求指正。

1.   public static void main(String[] args) {
   
2.         String[] words = new String[] {"math","english","story"};
   
3.         String target = "history";
   
4.         min(words,target);
   
5.         System.out.println(result);
   
6.     }
   
7. 
   
8.     static int result = Integer.MAX_VALUE;
   
9. 
   
10.     static void min (String[] words, String target) {
    
11.         search(words, target, 0, new HashSet<String>());
    
12.     }
    
13. 
    
14.     static void search(String[] words, String target, int start, Set<String> source) {
    
15. 
    
16.         if (start == words.length) {
    
17.             return;
    
18.         }
    
19. 
    
20.         for (int i = start; i < words.length; i++) {
    
21.             source.add(words[i]);
    
22.             if (valid(target,source)) {
    
23.                 result = Math.min(result, source.size());
    
24.                 return;
    
25.             }
    
26.             search(words,target,i+1,source);
    
27.             source.remove(words[i]);
    
28.         }
    
29. 
    
30.     }
    
31. 
    
32.     static boolean valid(String target, Set<String> res) {
    
33.         int[] map = new int[256];
    
34.         for (String s : res) {
    
35.             for (char c : s.toCharArray()) {
    
36.                 map[c] += 1;
    
37.             }
    
38.         }
    
39.         for (char c : target.toCharArray()) {
    
40.             if(--map[c] < 0) {
    
41.                 return false;
    
42.             }
    
43.         }
    
44.         return true;
    
45.     }
    

复制代码

之前的代码有Bug.
这个代码应该可以了

1. static int result = Integer.MAX_VALUE;
   
2. 
   
3.     static void minSourceWords(String[] words, String target) {
   
4.         search(words, target, 0, new ArrayList<>());
   
5.     }
   
6. 
   
7.     static void search(String[] words, String target, int start, List<String> source) {
   
8. 
   
9.         if (valid(target,source)) {
   
10.             result = Math.min(result, source.size());
    
11.             return;
    
12.         }
    
13. 
    
14.         if (start == words.length) {
    
15.             return;
    
16.         }
    
17. 
    
18.         for (int i = start; i < words.length; i++) {
    
19.             source.add(words[i]);
    
20.             search(words,target,i+1,source);
    
21.             source.remove(source.size()-1);
    
22.         }
    
23. 
    
24.     }
    
25. 
    
26.     static boolean valid(String target, List<String> source) {
    
27.         int[] map = new int[256];
    
28.         for (String s : source) {
    
29.             for (char c : s.toCharArray()) {
    
30.                 map[c] += 1;
    
31.             }
    
32.         }
    
33.         for (char c : target.toCharArray()) {
    
34.             if(--map[c] < 0) {
    
35.                 return false;
    
36.             }
    
37.         }
    
38.         return true;
    
39.     }

复制代码