发一个yelp的skype电面面经，已跪

melody_qyao 发表于 2015-7-20 14:29
new grad，自己勾搭的HR，没有内推

HR你从哪里找到的？

这题还好吧，先sort，然后backtracking
如果start的值已经大于target，直接返回false(默认target是正数)

还有就是同一个得分能否重复使用
如果不能重复使用，就在dfs的循环里面加一个判断
如果可以重复使用，先把数组转存为一个没有duplicate的list

zws0818 发表于 2015-7-20 23:23
HR你从哪里找到的？

Linkedin

FH9410 发表于 2015-7-20 16:42
public boolean isPossible(int[] nums, int target) {
                if (nums == null || nums.length == 0) {
                         ...

for loop里面的递归调用那里，应该是i而不是i+1吧，因为每个possible score都是可以重复用无数次的

notturno 发表于 2015-7-21 01:06
这题还好吧，先sort，然后backtracking
如果start的值已经大于target，直接返回false(默认target是正数)
...

不是什么难题，但我递归写不好，所以卡了很久

谢谢分享，题目真的是思路不难，写起来一遍ｂｕｇ　ｆｒｅｅ很不容易
没有大米给楼主了，分享一个ｃ＋＋　ｄｐ解法

1. #include <iostream>
   
2. #include <vector>
   
3. #include <unordered_set>
   
4. #include <string.h>
   
5. 
   
6. using namespace std;
   
7. 
   
8. bool isPossible(int total_score, vector<int> score_list){
   
9. if(total_score<=0)
   
10. return total_score==0;
    
11. 
    
12. unordered_set<int> score_pool(score_list.begin(),score_list.end());
    
13. bool *valid_score=new bool[total_score+1];
    
14. memset(valid_score,0,total_score+1);
    
15. valid_score[0]=1;
    
16. 
    
17. for(int i=1;i<=total_score;++i){
    
18.         for(int j=0;j<i;++j){
    
19.                 if(valid_score[j])
    
20.                 valid_score[i]=(score_pool.find(i-j)!=score_pool.end());
    
21.                 if(valid_score[i])
    
22.                 break;
    
23.         }
    
24. }
    
25. 
    
26. return valid_score[total_score];
    
27. }
    
28. 
    
29. int main() {
    
30.         vector<int> score_list({3,5,3,3,5});
    
31.         int total_score_list[]={6,11,7,0};
    
32.        
    
33.         for(int i=0;i<sizeof(total_score_list)/sizeof(int);++i){
    
34.                 if(isPossible(total_score_list[i],score_list))
    
35.                 cout<<"candidate score: "<<total_score_list[i]<<", yes"<<endl;
    
36.                 else
    
37.                 cout<<"candidate score: "<<total_score_list[i]<<", no"<<endl;
    
38.         }
    
39.         return 0;
    
40. }

复制代码

这应该是subset sum 问题吧
1. brute force的话 2^n
挨个选，选和不选 是两个选择对于每个数字来说，所以是2^n，iterative 位操作的话可以搞定，递归可以搞定。
2. dp 可以搞定 也就是背包问题 O(nC) n是需要的数字个数，也就是需要几个数字可以到达sum，C就是sum 这是个伪多项式解法，实质还是exponential的。
所以写哪个都可以。

dp方程： dp(i,j) 选i个数字，剩下j 的情况下是否是true
转移方程 dp(i,j) = dp(i+1,j-nums[i])|| dp(i+1,j)
意思就是选择当前数字和不选择当前数字的 or 操作
选择当然数字的话，数字index plus，sum减少，也就是j-nums[i]
不选当然数字的话，sum不减少，数字依旧plus
result就在dp(i,candidate)， i 属于[0, num.length)
只要那一列存在了true，就是true
也就是说 那一列只要有数字可以凑成candidate就返回。

感觉这个题解法基本上和经典硬币题思路一样

public class PossibleScore {
        static boolean res = false;
        public static boolean possible(int[] input, int target){
                if(input == null || input.length == 0){
                        return false;
                }
                Arrays.sort(input);
                helper(input, target, 0);
                return res;
        }

        private static void helper(int[] input, int target, int i) {
                if(res || target == 0){
                        res = true;
                        return;
                }
                if(i >= input.length || input[i] > target){
                        return;
                }
                helper(input, target - input[i], i);
                helper(input, target, i + 1);
        }
}

题主有在hacker rank做题目吗？ 那个题目能够搜索网页做吗