一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2904|回复: 29
收起左侧

Zenefits最近几道难题的解法

[复制链接] |试试Instant~ |关注本帖
kennethinsnow 发表于 2015-10-23 10:35:24 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 博士 全职@zenefits - 内推 - 技术电面 Onsite 在线笔试 |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本人总结了一下最近zenefits面试中出现的难题
OA3
http://www.1point3acres.com/bbs/ ... ;highlight=zenefits
1. Longest Chain
给定一个词典, 对于里面单词删掉任何一个字母,如果新单词还在词典里,就形成一个 chain:old word -> new word, 求最长长
比如给List<String> dict = {a,ba,bca,bda,bdca} 最长是4:bdca->bda->ba->a;. 鍥磋鎴戜滑@1point 3 acres
.鐣欏璁哄潧-涓

评分

7

查看全部评分

本帖被以下淘专辑推荐:

 楼主| kennethinsnow 发表于 2015-10-23 11:09:16 | 显示全部楼层
http://www.1point3acres.com/bbs/thread-131422-1-1.html
valid binary tree
  1. public class Solution1 {
  2.         class TreeNode{
  3.                 char value;
  4.                 TreeNode left;
  5.                 TreeNode right;
  6.                 TreeNode(char inp){
  7.                         this.value = inp;
  8.                 }
  9.         }
  10.         public String sExp(char[][] pair){. more info on 1point3acres.com
  11.                 // build an adj matrix row is the parent node, col is the child node
  12.                 int len = pair.length;
  13.                 if (len == 0) return "";
  14.                 int[][] adjMat = new int[26][26];
  15.                 int[] inNode = new int[26];        // count the incoming edges of each node
  16.                 int[] children = new int[26]; // count the number of children of each node
  17.                 Map<Character, TreeNode> nodes = new HashMap();
  18.                 TreeNode parent, child;
  19.                 UnionFind myUnion = new UnionFind(26);
  20.                 // build binary tree based on pair
  21.                 for (int i = 0; i < len; i++){
  22.                         int row = pair[i][0] - 'A';. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  23.                         int col = pair[i][1] - 'A';
  24.                         if (children[row] == 2 && adjMat[row][col] != 1){
  25.                                 // more than 2 children but not the same edge
  26.                                 return "E1";
  27.                         }else if (adjMat[row][col] == 1){
  28.                                 // duplicated edges
  29.                                 return "E2";
  30.                         } else if (myUnion.connected(row, col)){
  31.                                 // if new link connect two that are already in same union there is loop
  32.                                 return "E3";. 鍥磋鎴戜滑@1point 3 acres
  33.                         }
  34.                         adjMat[row][col] = 1;
  35.                         children[row]++;
  36.                         inNode[col]++;
  37.                         myUnion.connect(row, col);
  38.                         connectNodes(pair, nodes, i);
  39.                 }
  40.                 .1point3acres缃
  41.                 // check multiple roots
  42.                 int rNum = 0;
  43.                 TreeNode root = null;
  44.                 for (char x : nodes.keySet()){
  45.                         if (inNode[x - 'A'] == 0){
  46.                                 rNum++;
  47.                                 if (rNum > 1) return "E4";
  48.                                 root = nodes.get(x);
  49.                         }
  50.                 }
  51.                 if (root == null) return "E5";
  52.                
  53.                 // convert it to s-expression
  54.                 return toSExpression(root);
  55.         }
  56.        
  57.         // convert it to s-expression. Waral 鍗氬鏈夋洿澶氭枃绔,
  58.         String toSExpression(TreeNode root){
  59.                 if (root == null) return "";
  60.                 return "(" + root.value + toSExpression(root.left) + toSExpression(root.right) + ")";
  61.         }
  62.        
  63.         // connect parent and child node
  64.         private void connectNodes(char[][] pair, Map<Character, TreeNode> nodes,
  65.                         int i) {
  66.                 TreeNode parent;
  67.                 TreeNode child;
  68.                 if (nodes.containsKey(pair[i][0])) parent = nodes.get(pair[i][0]);
  69.                 else{
  70.                         parent = new TreeNode(pair[i][0]);
  71.                         nodes.put(pair[i][0], parent);
  72.                 }
  73.                 if (nodes.containsKey(pair[i][1])) child = nodes.get(pair[i][1]);
  74.                 else{
  75.                         child = new TreeNode(pair[i][1]);. Waral 鍗氬鏈夋洿澶氭枃绔,
  76.                         nodes.put(pair[i][1], child);
  77.                 }
  78.                 if (parent.left == null) parent.left = child;
  79.                 else {
  80.                         if (parent.left.value < pair[i][1]){
  81.                                 parent.right = child;
  82.                         } else {
  83.                                 parent.right = parent.left;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  84.                                 parent.left = child;-google 1point3acres
  85.                         }
    . 鍥磋鎴戜滑@1point 3 acres
  86.                 }
  87.         }
  88.        
  89.         public static void main(String[] args){
  90.                 Solution1 sln = new Solution1();
  91.                 // (A(B(D(E(G))))(C(F))). Waral 鍗氬鏈夋洿澶氭枃绔,
  92.                 // char[][] pair = {{'B', 'D'}, {'D', 'E'}, {'A', 'B'}, {'C', 'F'}, {'E', 'G'}, {'A', 'C'}};. 1point 3acres 璁哄潧
  93.                 // E3
  94.                 // char[][] pair = {{'A', 'B'}, {'A', 'C'}, {'B', 'D'}, {'D', 'C'}};. 鍥磋鎴戜滑@1point 3 acres
  95.                 // (A(B(D)(G))(C(E(F))(H))). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  96.                 // char[][] pair = {{'A', 'B'}, {'A', 'C'}, {'B', 'G'}, {'C', 'H'}, {'E', 'F'}, {'B', 'D'}, {'C', 'E'}};
  97.                 // E1
  98.                 // char[][] pair = {{'A', 'B'}, {'A', 'C'}, {'B', 'D'}, {'A', 'E'}};
  99.                 // E2
  100.                 // char[][] pair = {{'A', 'B'}, {'A', 'C'}, {'B', 'D'}, {'A', 'C'}};
  101.                 // E4
  102.                 char[][] pair = {{'A', 'B'}, {'A', 'C'}, {'B', 'G'}, {'C', 'H'}, {'E', 'F'}, {'B', 'D'}};
  103.                 System.out.println(sln.sExp(pair));
  104.         }
  105. }
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 10:36:22 | 显示全部楼层
  1. public class Solution {
  2.         int longest_chain(String[] w) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  3.         int len = w.length;. Waral 鍗氬鏈夋洿澶氭枃绔,
  4.         if (len == 0) return 0;
  5.         Queue<String> cBuf = new LinkedList();
  6.         Map<Integer, Set<String>> allWd = new HashMap();
  7.         int maxLen = 0;
  8.         int maxCLen = 0;. 1point3acres.com/bbs
  9.         // find the longest length of strings in w
  10.         for (int i = 0; i < w.length; i++){. more info on 1point3acres.com
  11.             int curLen = w[i].length();
  12.             maxLen = Math.max(maxLen, curLen);
  13.             if (allWd.containsKey(curLen)) allWd.get(curLen).add(w[i]);
  14.             else{
  15.                 Set<String> curSet = new HashSet();. From 1point 3acres bbs
  16.                 curSet.add(w[i]);
  17.                 allWd.put(curLen, curSet);
  18.             }
  19.         }
  20.         // search from certain length of words
  21.         for (int i = maxLen; i > maxCLen; i--){
  22.             cBuf = new LinkedList(allWd.get(i));. more info on 1point3acres.com
  23.             // start from initial set of words to search for chain
  24.             int clen = 0;
  25.             while (!cBuf.isEmpty()){
  26.                 clen++;. 1point3acres.com/bbs
  27.                 Set<String> nextSet = allWd.get(i - clen);
  28.                 if (nextSet == null) break;
  29.                 int count = cBuf.size();
  30.                 for (int h = 0; h < count; h++){
  31.                     String t = cBuf.poll();
  32.                     // get next string by deleting one letter
  33.                     for (int l = 0; l < t.length(); l++){
  34.                         String tt = t.substring(0, l) + t.substring(l + 1);
  35.                         if (nextSet.contains(tt)){. more info on 1point3acres.com
  36.                             cBuf.offer(tt);
  37.                             nextSet.remove(tt);
  38.                         }
  39.                     }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  40.                 }
  41.             }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  42.             maxCLen = Math.max(maxCLen, clen);
  43.             i -= Math.max(clen - 1, 0);
  44.         }
  45.         return maxCLen;
  46.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 10:38:36 | 显示全部楼层
nqueen变形
棋盘上放queen 已经保证同一行或者同一列不会出现2个queen,求出对于每个Queen最大的威胁次数威胁指只要一个queen所能移动的范围(对于这道题就是对角线)内有别的queen就算威胁。
  1.         int maxThreats(int[] a) {
  2.         int len = a.length;
  3.         if (len == 0) return 0;
  4.         int[] threat = new int[len]; // max threats for queen in each row
  5.         Map<Integer, Integer> diag1 = new HashMap();. from: 1point3acres.com/bbs
  6.         Map<Integer, Integer> diag2 = new HashMap();
  7.         for (int i = 0; i < len; i++){
  8.             int col = a[i] - 1; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  9.             if (diag1.containsKey(i - col)){
  10.                 threat[i]++;-google 1point3acres
  11.                 threat[diag1.get(i - col)]++;
  12.             }
  13.             diag1.put(i - col, i);
  14.             if (diag2.containsKey(i + col)){. From 1point 3acres bbs
  15.                 threat[i]++;
  16.                 threat[diag2.get(i + col)]++;
  17.             }
  18.             diag2.put(i + col, i);
  19.         }
  20.         int maxThreat = 0;
  21.         for (int i = 0; i < len; i++){
  22.             maxThreat = Math.max(maxThreat, threat[i]);
  23.         }
  24.         return maxThreat;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  25.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 10:43:13 | 显示全部楼层
虫吃叶子 给定一个int作为叶子的数量,再给一个数组,其中每个数代表一个虫行走的步数, 求没有被吃掉的叶子数量。 比如n = 100, bug = {2,5}, 那么一百片叶子中号码是2或者5的倍数的叶子全部被吃掉了。
  1. int numberOfUneaten(int n, int[] p){
  2.                 // find non divisible numbers in p
  3.                 Arrays.sort(p);. visit 1point3acres.com for more.
  4.                 for (int i = 0; i < p.length; i++){
  5.                         for (int j = 0; j < i; j++){
  6.                                 if (p[j] != 0 && p[i] % p[j] == 0){
  7.                                         p[i] = 0;
  8.                                         break;
  9.                                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  10.                         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  11.                 }
  12.                 // find lcm of numbers in p
  13.                 int l = 1;
  14.                 for (int i = 0; i < p.length; i++){
  15.                         if (p[i] != 0){
  16.                                 l = lcm(l, p[i]);
  17.                         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  18.                 }
  19.                 int res = n % l;
  20.                 // find undivisible numbers from 1 to min(lcm, n)
  21.                 int[] mark = new int[Math.min(l, n) + 1];. From 1point 3acres bbs
  22.                 for (int i = 0; i < p.length; i++){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  23.                         if (p[i] != 0){. Waral 鍗氬鏈夋洿澶氭枃绔,
  24.                                 for (int j = p[i]; j <= Math.min(l, n); j += p[i]){
  25.                                         mark[j] = 1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  26.                                 }
  27.                         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  28.                 }
  29.                 int count = 0;
  30.                 int count1 = 0;
  31.                 for (int i = 1; i < Math.min(l, n); i++){
  32.                         if (mark[i] == 0){
  33.                                 count++;
  34.                                 if (i <= res) count1++;
  35.                         }
  36.                 }
  37.                
  38.                 // find undivisible numbers from 1 to n
  39.                 if (n < l) return count;
  40.                 else{
  41.                         return n / l * count + count1;
  42.                 }
  43.         }.1point3acres缃
  44.         int lcm(int a, int b){
  45.                 return a * b / gcd(a, b);
  46.         }
  47.         int gcd(int a, int b){
  48.                 if (a < b) return gcd(b, a);
  49.                 return b == 0 ? a : gcd(b, a % b);. 1point 3acres 璁哄潧
  50.         }
复制代码
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 10:45:06 | 显示全部楼层
机器人距离和最小问题 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
注意问题参见 http://www.1point3acres.com/bbs/thread-145166-1-1.html
  1. /*//problem: robot merge point
  2. //input:
  3. //robot: 1
  4. //obstacle: X
  5. [
  6. 0   0   0   M   1
  7. 0   1   X   0   0
  8. 0   X   0   0   0
  9. 0   0   0   1   0
  10. 0   0   0   0   0
  11. ]. visit 1point3acres.com for more.
  12. //output:
  13. //best merge point: M-google 1point3acres
  14. 3 + 1 + 3 = 7. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  15. Definition: Best merge point: minimal sum of path num between robots and merge point*/
  16. public class Solution{
  17.         class Point{
  18.                 int x;
  19.                 int y;
  20.                 public Point(int x, int y){
  21.                         this.x = x;
  22.                     this.y = y;
  23.                 }
  24.         }
  25.         Point bestMergePoint(char[][] mat){
  26.          int m = mat.length;
  27.          if (m == 0) return null;
  28.          int n  = mat[0].length;
  29.        
  30.          // bfs each point that is 1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  31.          int[][] dis = new int[m][n];
  32.          for (int i = 0; i < m; i++){. more info on 1point3acres.com
  33.              for (int j = 0; j < n; j++){
  34.                  if (mat[i][j] == '1') bfs(mat, i, j, dis);
  35.              }
  36.          }
  37.          // count number
  38.          int min = Integer.MAX_VALUE;. 1point 3acres 璁哄潧
  39.          Point ret = null;. from: 1point3acres.com/bbs
  40.          for (int i = 0; i < m; i++){
  41.              for (int j = 0; j < n; j++){
  42.                      // if this point is not visited by a robot
  43.                      if (dis[i][j] == 0 && mat[i][j] == '0') continue;
  44.                  if (mat[i][j] != 'X' && dis[i][j] < min){
  45.                      min = dis[i][j];
  46.                      ret = new Point(i, j);
  47.                  }
  48.              }
  49.          }. Waral 鍗氬鏈夋洿澶氭枃绔,
  50.          return ret;. 1point 3acres 璁哄潧
  51.         }

  52.         //bfs matrix to mark the distance from x and y
  53.         void bfs(char[][] mat, int x, int y, int[][] dis){
  54.                  Queue<Point> path = new LinkedList();
  55.                  int[] dx = {1,-1,0,0};
  56.                  int[] dy = {0,0,1,-1};-google 1point3acres
  57.                  int m = mat.length;. from: 1point3acres.com/bbs
  58.                  int n = mat[0].length;
  59.                  boolean[][] visited = new boolean[m][n];
  60.                  int ct = 0;
  61.                  System.out.println("Started at: " + x + " " + y);
  62.                  int di = 0;
  63.                  path.offer(new Point(x, y));
  64.                  visited[x][y] = true;
  65.                  while (!path.isEmpty()){
  66.                      int count = path.size();
  67.                      for (int i = 0; i < count; i++){
  68.                          Point cur = path.poll();
  69.                          ct++;-google 1point3acres
  70.                          // System.out.println(cur.x + " " + cur.y);
  71.                          // visited[cur.x][cur.y] = true;
  72.                          // update cur.value
  73.                          dis[cur.x][cur.y] += di;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  74.                          // check its neighbors
  75.                          for (int j = 0; j < 4; j++){
  76.                              int nx = cur.x + dx[j];. Waral 鍗氬鏈夋洿澶氭枃绔,
  77.                              int ny = cur.y + dy[j];
  78.                              if (nx >= 0 && nx < m && ny >= 0 && ny < m && mat[nx][ny] != 'X' && !visited[nx][ny]){
  79.                                  path.offer(new Point(nx, ny));. 1point3acres.com/bbs
  80.                                  visited[nx][ny] = true;
  81.                              }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  82.                          }
  83.                      }
  84.                      di++;
  85.                  }
  86.                  System.out.println("total points added to queue: " + ct);
  87.         }
  88.         public static void main(String[] args){
  89.                 Solution sln = new Solution();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  90.                 char[][] mat = {{'0', '0', '0', '0', '1'},
  91.                                                 {'0', '1', 'X', '0', '0'},
  92.                                                 {'0', 'X', '0', '0', '0'},
  93.                                                 {'0', '0', '0', '1', '0'},
  94.                                                 {'0', '0', '0', '0', '0'}};
  95.                 Point ret = sln.bestMergePoint(mat);
  96.                 System.out.println(ret.x + " " + ret.y);
  97.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  98. }
复制代码
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-10-23 10:50:05 | 显示全部楼层
赞,楼主很用心啊
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 10:53:33 | 显示全部楼层
kennethinsnow 发表于 2015-10-23 10:45
机器人距离和最小问题
注意问题参见 http://www.1point3acres.com/bbs/thread-145166-1-1.html
.1point3acres缃
// Find the largest K such that A^K is a subsequence of B, where A, B are two strings. |A| << |B|.

// Power of a string:
// Let A = xyxz
// Then,
// A^1 = A = xyxz
// A^2 = xxyyxxzz
// A^3 = xxxyyyxxxzzz
. 1point 3acres 璁哄潧
// Example:
// A = xyxz
// B = xabyzxz.鏈枃鍘熷垱鑷1point3acres璁哄潧

// B xaybyxzxxxzz. 1point 3acres 璁哄潧
.鏈枃鍘熷垱鑷1point3acres璁哄潧
// A xxyyxxzz
  1. public int findK(String A, String B){. from: 1point3acres.com/bbs
  2.             int len1 = A.length(), len2 = B.length();
    . more info on 1point3acres.com
  3.             if (len1 > len2) return 0;
  4.             if (len1 <= 0) return 0;
  5.             // remove space weird characters, capital to lower case etc if needed.
  6.             A = preprocess(A);
  7.             // find signature for each A and B and get the max possible value for k
  8.             int[] sigA = new int[256];
  9.             int[] sigB = new int[256];
  10.             for (int i = 0; i < len1; i++) sigA[A.charAt(i)]++;
  11.             for (int i = 0; i < len2; i++) sigB[B.charAt(i)]++;
  12.             int kMax = Integer.MAX_VALUE;
  13.             for (int i = 0; i < len1; i++){
  14.                 if (sigA[A.charAt(i)] != 0) kMax = Math.min(sigB[A.charAt(i)] / sigA[A.charAt(i)], kMax);
  15.             } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  16.             int lo = 0, hi = kMax;
  17.             int ret = 0;
  18.             while (lo <= hi){
  19.                 int med = lo + (hi - lo) / 2;. visit 1point3acres.com for more.
  20.                 if (isSubSeq(expand(A, med), B)){
  21.                     ret = med;
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  22.                     lo = med + 1;
  23.                 } else {
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  24.                     hi = med - 1;.1point3acres缃
  25.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  26.             }
  27.             return ret;
  28.         }
  29.        
  30.         String expand(String A, int k){
  31.             StringBuilder sbuf = new StringBuilder();
  32.             for (int i = 0; i < A.length(); i++){
  33.                 char c = A.charAt(i);
  34.                 for (int j = 0; j < k; j++) sbuf.append(c);. more info on 1point3acres.com
  35.             }
  36.             return sbuf.toString();
  37.         }. From 1point 3acres bbs
  38.        
  39.         boolean isSubSeq(String A, String B){
  40.             int len1 = A.length(), len2 = B.length();
  41.             int a = 0, b = 0;
  42.             while (a < len1 && b < len2){
  43.                 if (A.charAt(a) == B.charAt(b)){
  44.                     a++;
  45.                     b++;
  46.                 } else {
  47.                     b++;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  48.                 }
  49.             }
  50.             return a == len1;
  51.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  52.        
  53.         String preprocess(String A){. from: 1point3acres.com/bbs
  54.             return A.toLowerCase();
  55.         }
复制代码
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 10:54:45 | 显示全部楼层
/*一个正方形的矩阵,左上角的位置保证是0,其他的每个坐标位置上都有一个大于等于0的数。
* 一个人最初携带着的钱数为K,然后要从左上角走到右下角,每次只能向右或者向下走,
* 每到一个位置上就需要花掉该位置上对应的钱数,要求编程看看这个人能不能走到右下角,
* 如果不能,就返回-1,如果能,那就要找到一个解法,使得这个人剩余的钱数尽可能少,
* 也就是最终剩余的钱数要大于等于0,并且尽可能接近于0.*/
  1. public class Solution {
  2.         public int findMaxSpent(int[][] mat, int k){
  3.                 // dp[i][j][n] is the max mount spent at i,j but less than n 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  4.                 // dp[i][j][n] = max(dp[i - 1][j][n - mat[i][j]], dp[i][j - 1][n - mat[i][j]]). Waral 鍗氬鏈夋洿澶氭枃绔,
  5.                 int m = mat.length;
  6.                 if (m == 0) return -1;
  7.                 int n = mat[0].length;
  8.                 int[][] dp1 = new int[n + 1][k + 1];
  9.                 int[][] dp2 = new int[n + 1][k + 1];
  10.                 // when i == -1; edge case. from: 1point3acres.com/bbs
  11.                 for (int j = 0; j < n; j++){
  12.                         for (int h = 0; h <= k; h++){
  13.                                 dp1[j + 1][h] = -1;
  14.                         }
  15.                 }
  16.                 // when j = -1 edge case
  17.                 for (int h = 0; h <= k; h++){
  18.                         dp2[0][h] = -1;
  19.                 }
  20.                 . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  21.                 for (int i = 0; i < m; i++){. more info on 1point3acres.com
  22.                         for (int j = 0; j < n; j++){
  23.                                 for (int h = 0; h <= k; h++){
  24.                                         if (i == 0 && j == 0) dp2[j + 1][h] = 0;. visit 1point3acres.com for more.
  25.                                         else if (h < mat[i][j]) dp2[j + 1][h] = -1;
  26.                                         else {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  27.                                                 int pre1 = dp2[j][h - mat[i][j]];. From 1point 3acres bbs
  28.                                                 int pre2 = dp1[j + 1][h - mat[i][j]];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  29.                                                 if (pre1 == -1 && pre2 == -1) dp2[j + 1][h] = -1;
  30.                                                 else dp2[j + 1][h] = Math.max(pre1, pre2) + mat[i][j];
    . more info on 1point3acres.com
  31.                                         }
  32.                                 }
  33.                         }
  34.                         dp1 = Arrays.copyOf(dp2, n + 1);
  35.                 }
  36.                 return dp1[n][k];
  37.         }
  38.        
  39.         public static void main(String[] args){
  40.                 Solution sln = new Solution();
  41.                 int[][] mat = {{0,4,5}, {1,3,2}, {0,1,1}};
  42.                 System.out.println(sln.findMaxSpent(mat, 12));
  43.         }
  44. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 11:10:38 | 显示全部楼层
String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";. Waral 鍗氬鏈夋洿澶氭枃绔,
String s2 = "a+b+c-";

s2的形式是一个字母加上一个符号,正号代表有两个前面的字符,负号代表有四个,也就是说s2其实是"aabbcccc",不考虑invalid。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
在s1中,找出连续或者不连续的s2,也就是说从s1中找出"aa....bb.....cccc",abc顺序不能变,但是之间可以有零个或多个字符,返回共有多少个。在上面这个例子中,有四个。
  1. public class Solution {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2.         public int findMatches(String s1, String s2){
  3.        int len1 = s1.length(), len2 = s2.length();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.        if (len2 > len1) return 0;
  5.        if (len2 == 0 || len2 %2 != 0) return 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6.        // DP matches each pattern
  7.        // number of matches between s1.substring(0, i + 1) and s2.substring(j * 2, j * 2 + 2)
  8.        int[][] dp = new int[len1 + 1][len2 / 2 + 1];
  9.        // no match for dp[0][j]. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  10.        for (int i = 1; i < len1; i++){
  11.            dp[i + 1][0] = 1;
  12.            for (int j = 0; j < len2 / 2; j++){. more info on 1point3acres.com
  13.                dp[i + 1][j + 1] = dp[i][j + 1];
  14.                if (isMatch(s1, s2, i, j)){
  15.                    if (s2.charAt(2*j + 1) == '+')-google 1point3acres
  16.                        dp[i + 1][j + 1] += dp[i - 1][j];
  17.                    else
    . 鍥磋鎴戜滑@1point 3 acres
  18.                        dp[i + 1][j + 1] += dp[i - 3][j];
  19.                }
  20.            }
  21.        }
  22.        return dp[len1][len2 / 2];
  23.    }

  24.    boolean isMatch(String s1, String s2, int i, int j){
  25.        char c = s2.charAt(j * 2);-google 1point3acres
  26.        char p = s2.charAt(j * 2 + 1);
  27.        int len = p == '+' ? 2 : 4;
  28.        if (i - len < -1) return false;
  29.        for (int h = i - len + 1; h <= i; h++){
  30.            if (s1.charAt(h) != c) return false;
  31.        }
  32.        return true;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  33.    }
  34.    
  35.    public static void main(String[] args){
  36.            Solution sln = new Solution();. 1point 3acres 璁哄潧
  37.            // 4. from: 1point3acres.com/bbs
  38.            System.out.println(sln.findMatches("waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c-"));. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  39.            // 5
  40.            System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-"));
  41.    }
  42. }
复制代码
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-10-26 10:14:57 | 显示全部楼层
kennethinsnow 发表于 2015-10-23 10:53
// Find the largest K such that A^K is a subsequence of B, where A, B are two strings. |A|

如果 A 和 B 的长度都是0的话,也是返回0吗?还是返回1?
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-10-26 10:19:19 | 显示全部楼层
Chasego 发表于 2015-10-26 10:14
如果 A 和 B 的长度都是0的话,也是返回0吗?还是返回1?

不过这样很像,不符合 |A| << |B|
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-26 10:24:27 | 显示全部楼层
Chasego 发表于 2015-10-26 10:14
如果 A 和 B 的长度都是0的话,也是返回0吗?还是返回1?

            if (len1 > len2) return 0;
            if (len1 <= 0) return 0;
我返回0,具体要和面试官沟通
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-10-26 10:27:05 | 显示全部楼层
kennethinsnow 发表于 2015-10-26 10:24
if (len1 > len2) return 0;
            if (len1

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 嗯,我是看到这一行。不过沟通就没问题了。
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-10-26 10:55:35 | 显示全部楼层
kennethinsnow 发表于 2015-10-23 10:53-google 1point3acres
// Find the largest K such that A^K is a subsequence of B, where A, B are two strings. |A|

第14行,sigA[A.charAt(i)] != 0 这个判断应该没必要吧?
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-26 12:09:12 | 显示全部楼层
Chasego 发表于 2015-10-26 10:55
第14行,sigA[A.charAt(i)] != 0 这个判断应该没必要吧?

恩,可以去掉
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-10-27 00:50:45 | 显示全部楼层
kennethinsnow 发表于 2015-10-23 11:09
http://www.1point3acres.com/bbs/thread-131422-1-1.html
valid binary tree

第24行 if (children[row] == 2 && adjMat[row][col] != 1){.
是不是应该改成 children[row] == 1,意思是对于row已经有一个孩子了,而保证col不是它已有的孩子才返回E1
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-10-27 01:32:55 | 显示全部楼层
kennethinsnow 发表于 2015-10-23 11:09
http://www.1point3acres.com/bbs/thread-131422-1-1.html
valid binary tree
. From 1point 3acres bbs
代码很不错,赞楼主一个!

我当时想到“E5”情况应该是不存在,因为前面四种错误已经涵括所有情况。

第51行实际是永远不会执行的吗?
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-10-27 10:22:37 | 显示全部楼层
kennethinsnow 发表于 2015-10-23 11:10
String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+ ...

29行: if (i - len < -1) return false;

这里是不是应该改成 i - len < 0 ???
回复 支持 反对

使用道具 举报

zhuo 发表于 2015-10-27 23:15:53 | 显示全部楼层
我也来贴俩题 最近在准备电面 好没底儿。。。。。。。。。。。。

Find the largest K such that A^K is a subsequence of B, where A, B are two strings.
http://www.1point3acres.com/bbs/ ... p;highlight=zenefit
  1. public class largestAK {
  2.         . 1point 3acres 璁哄潧
  3.         public int findLargestK(String s1, String s2){
  4.                 if(s1.length() < 1 || s1.length() > s2.length())
  5.                         return -1;
  6.                 int k = 1;
  7.                 int left = 1, right = s2.length() / s1.length();. 1point3acres.com/bbs
  8.                 int lastK = -1;
  9.                 while(left <= right){. visit 1point3acres.com for more.
  10.                         k = left + (right - left)/2;
  11.                         String akString = generateKth(s1, k);
  12.                         if(isSub(akString, s2)){
  13.                                 lastK = k;
  14.                                 left = k + 1;. visit 1point3acres.com for more.
  15.                         }else{. From 1point 3acres bbs
  16.                                 right = k - 1;
  17.                         }
  18.                 }. 鍥磋鎴戜滑@1point 3 acres
  19.                 return lastK;
  20.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  21.        
  22.         private String generateKth(String s, int k){
  23.                 StringBuilder temp = new StringBuilder();
  24.                 for(int i = 0; i < s.length(); i++){
  25.                         for(int j = 0; j < k; j++){
  26.                                 temp.append(s.charAt(i));
  27.                         }
  28.                 }
  29.                 return temp.toString();
  30.         }
  31.        
  32.         private boolean isSub(String s1, String s2){
  33.                 int i = 0;
  34.                 int j = 0;
  35.                 while(i < s1.length() && j < s2.length()){. from: 1point3acres.com/bbs
  36.                         if(s1.charAt(i) == s2.charAt(j)){. 1point 3acres 璁哄潧
  37.                                 i++;
  38.                         }
  39.                         j++;
  40.                 }
  41.                 if(i == s1.length())
  42.                         return true;
  43.                 return false;
  44.         }

  45.         public static void main(String[] args) {
  46.                 // TODO Auto-generated method stub
  47.                 largestAK ak = new largestAK();
  48.                 String s1 = "ab";
  49.                 String s2 = "acaaabcbbb";
  50.                 String s3 = "xyxz";
  51.                 String s4 = "xxyyxxzz";
  52.                 System.out.println(ak.findLargestK(s3, s4));
  53.         }

  54. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 10:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表