Zenefits最近几道难题的解法

http://www.1point3acres.com/bbs/ ... p;highlight=zenefit
找出一个string里面长度为n （n小于等于string的长度）的所有组合。
这个比较简单 考虑了一下dupilcate 字母

1. public class WordPermutations {
   
2.         public static void main(String[] args){
   
3.                 String s1 = "abcd";
   
4.                 String s2 = "aab";
   
5.                 ArrayList<String> res = getPermutations(s2, 3);
   
6.                 System.out.println(res.size());
   
7.                 for(String word: res){
   
8.                         //if(word.equals("aab"))
   
9.                         System.out.print(word+" ");
   
10.                 }
    
11.         }
    
12.        
    
13.         private static ArrayList<String> getPermutations(String s, int n){
    
14.                 ArrayList<String> res = new ArrayList<String>();
    
15.                 if(s.length()==0 || s==null || s.length()<n || n<=0)
    
16.                         return res;
    
17.                 int[] visited = new int[s.length()];
    
18.                 char[] word = s.toCharArray();
    
19.                 Arrays.sort(word);
    
20.                 //System.out.print(new String(word)+" ");
    
21.                 helper(word, n, new StringBuilder(), res, visited);
    
22.                 return res;
    
23.         }
    
24.        
    
25.         private static void helper(char[] s, int n, StringBuilder sb, ArrayList<String> res, int[] visited){
    
26.                 if(sb.length()==n){
    
27.                         res.add(sb.toString());
    
28.                         return;
    
29.                 }
    
30.                 for(int i=0; i<s.length; i++){
    
31.                         if(visited[i]==1 || i!=0 && s[i]==s[i-1] && visited[i-1]==0)
    
32.                                 continue;
    
33.                         sb.append(s[i]);
    
34.                         visited[i] = 1;
    
35.                         helper(s, n, sb, res,visited);
    
36.                         sb.deleteCharAt(sb.length()-1);
    
37.                         visited[i] = 0;
    
38.                 }
    
39.                        
    
40.         }
    
41. }

复制代码

如果我有边界条件没考虑到 希望小伙伴们给我指正。。。。
我总是边界条件考虑不全
大家有好的方法么？

zhuo 发表于 2015-10-27 23:17
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=144995&highlight=zenefit
找出一个strin ...

我也写了一个没有优化过的

1. def combine(word, k):
   
2.     if k < 1 or k > len(word):
   
3.         return []
   
4.     if k == 1:
   
5.         return [word[i] for i in range(len(word))]
   
6.     res = combine(word[:-1], k)
   
7.     tmp = combine(word[:-1], k - 1)
   
8.     for t in tmp:
   
9.         res.append(t + word[-1])
   
10.     return res

复制代码

补充内容 (2015-10-27 23:23):
这个没有考虑dup， 不过这个帖子里面说不用考虑dup(http://www.1point3acres.com/bbs/ ... p;page=1#pid2031821), 考虑的话直接明了的方法是通过set去重

kennethinsnow 发表于 2015-10-23 10:54
/*一个正方形的矩阵，左上角的位置保证是0，其他的每个坐标位置上都有一个大于等于0的数。
* 一个人最初 ...

楼主你看这是我的代码，用的dfs，能否指点一下看对不对呢？多谢啦

int findMinMoney(vector<vector<int>> fee, int k){

        if(fee.empty())

                return -1;

        int ret = dfs(fee, k, 0, 0);

        return ret;

}

int dfs(vector<vector<int>>& fee, int k, int i, int j){

        if(i==fee.size()||j==fee[0].size())

                return -1;

        if(fee[i][j] > k)

                return -1;

        if(dfs(fee, k-fee[i][j], i+1, j)== -1 &&dfs(fee,k-fee[i][j],i, j+1)==-1)

                return -1;

        if(i==fee.size()-1&&j==fee[0].size()-1)

                return k-fee[i][j];

        if(dfs(fee, k-fee[i][j], i+1, j)== -1)

                return dfs(fee,k-fee[i][j],i, j+1);

        else if(dfs(fee,k-fee[i][j],i, j+1) == -1)

                return dfs(fee,k-fee[i][j],i+1, j)

        else

                return min(dfs(fee, k-fee[i][j], i+1, j), dfs(fee,k-fee[i][j],i, j+1));

}

kennethinsnow 发表于 2015-10-23 10:54
/*一个正方形的矩阵，左上角的位置保证是0，其他的每个坐标位置上都有一个大于等于0的数。
* 一个人最初 ...

问下lz这题不是需要返回一个路径么？

MCwong 发表于 2015-11-4 13:08
问下lz这题不是需要返回一个路径么？

不是路径，返回－1或者满足条件的开始携带的钱数

要求编程看看这个人能不能走到右下角，如果不能，就返回-1，如果能，那就要找到一个解法，使得这个人剩余的钱数尽可能少。

补充内容 (2015-11-4 13:46):
如果要找路径，是一个思路，再把dp数组trace一遍

补充内容 (2015-11-4 13:48):
如果理解成路径，似乎和返回－1有点矛盾。不过如果返回路径的话，就需要再扫一次所有的dp数组

kennethinsnow 发表于 2015-11-4 13:44
不是路径，返回－1或者满足条件的开始携带的钱数

要求编程看看这个人能不能走到右下角，如果不能，就 ...

懂了，thx

kennethinsnow 发表于 2015-10-23 10:36

楼主longest chain那题， 最后 i -= Math.max(clen -1, 0); 这里是不是不应该有这一行。考虑z zz zzz zzzz zzzzz zzzzzz zzzzzzzz zzzzzzzz 和 abcdefgh abcdefghi abcdefghij.如果从最大的开始找，第一次chain终止在 abcdefgh, curlen = 3，这时候如果i-=Math.max(clen-1,0) 然后i--的话，不是跳到 i=7 开始。就忽略了i=8的情况。得到的结果就不对了吗？

cocaptainco 发表于 2015-11-13 06:54
楼主longest chain那题， 最后 i -= Math.max(clen -1, 0); 这里是不是不应该有这一行。考虑z zz zzz zzz ...

我也这么觉得呀，，不能跳呀。。

你好！  这个findMatches解法跑出来结果好象不对
比如 findMatches("aaaaaa","a+a-") 运行结果为0，正确答案应该是1
另外  为什么findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-")结果是5？感觉结果应该是2

public class Solution {. from: 1point3acres.com/bbs
        public int findMatches(String s1, String s2){.鏈?枃鍘熷垱鑷�1point3acres璁哄潧
       int len1 = s1.length(), len2 = s2.length();
       if (len2 > len1) return 0;
       if (len2 == 0 || len2 %2 != 0) return 0;. 鍥磋?鎴戜滑@1point 3 acres
       // DP matches each pattern
       // number of matches between s1.substring(0, i + 1) and s2.substring(j * 2, j * 2 + 2)
       int[][] dp = new int[len1 + 1][len2 / 2 + 1];
       // no match for dp[0][j]
       for (int i = 1; i < len1; i++){
           dp[i + 1][0] = 1;
           for (int j = 0; j < len2 / 2; j++){
               dp[i + 1][j + 1] = dp[i][j + 1];
               if (isMatch(s1, s2, i, j)){
                   if (s2.charAt(2*j + 1) == '+'). 1point 3acres 璁哄潧
                       dp[i + 1][j + 1] += dp[i - 1][j];
-google 1point3acres                   else
                       dp[i + 1][j + 1] += dp[i - 3][j];
               }
           }
       }
       return dp[len1][len2 / 2];
   }
. 鍥磋?鎴戜滑@1point 3 acres
   boolean isMatch(String s1, String s2, int i, int j){
       char c = s2.charAt(j * 2);
       char p = s2.charAt(j * 2 + 1);. From 1point 3acres bbs
       int len = p == '+' ? 2 : 4;
       if (i - len < -1) return false;
       for (int h = i - len + 1; h <= i; h++){.鐣欏?璁哄潧-涓