一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 3096|回复: 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, 求最长长. From 1point 3acres bbs
比如给List<String> dict = {a,ba,bca,bda,bdca} 最长是4:bdca->bda->ba->a;
. 1point3acres.com/bbs.鐣欏璁哄潧-涓

评分

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;-google 1point3acres
  6.                 TreeNode(char inp){. 1point3acres.com/bbs
  7.                         this.value = inp;. from: 1point3acres.com/bbs
  8.                 }
  9.         }
  10.         public String sExp(char[][] pair){
  11.                 // build an adj matrix row is the parent node, col is the child node
  12.                 int len = pair.length;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  13.                 if (len == 0) return "";
  14.                 int[][] adjMat = new int[26][26];
    . from: 1point3acres.com/bbs
  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. From 1point 3acres bbs
  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){. from: 1point3acres.com/bbs
  25.                                 // more than 2 children but not the same edge
  26.                                 return "E1";
  27.                         }else if (adjMat[row][col] == 1){
  28.                                 // duplicated edges-google 1point3acres
  29.                                 return "E2";
  30.                         } else if (myUnion.connected(row, col)){. 鍥磋鎴戜滑@1point 3 acres
  31.                                 // if new link connect two that are already in same union there is loop
  32.                                 return "E3";
  33.                         }
    . 鍥磋鎴戜滑@1point 3 acres
  34.                         adjMat[row][col] = 1;
  35.                         children[row]++;
  36.                         inNode[col]++;
  37.                         myUnion.connect(row, col);
  38.                         connectNodes(pair, nodes, i);
  39.                 }
  40.                
  41.                 // check multiple roots
  42.                 int rNum = 0;
  43.                 TreeNode root = null;.1point3acres缃
  44.                 for (char x : nodes.keySet()){
  45.                         if (inNode[x - 'A'] == 0){
  46.                                 rNum++;.1point3acres缃
  47.                                 if (rNum > 1) return "E4";. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  48.                                 root = nodes.get(x);
  49.                         }. 鍥磋鎴戜滑@1point 3 acres
  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. more info on 1point3acres.com
  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]);. Waral 鍗氬鏈夋洿澶氭枃绔,
  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]);
  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]){. Waral 鍗氬鏈夋洿澶氭枃绔,
  81.                                 parent.right = child;. 鍥磋鎴戜滑@1point 3 acres
  82.                         } else {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  83.                                 parent.right = parent.left;
  84.                                 parent.left = child;
  85.                         }
  86.                 }
  87.         }
  88.        
  89.         public static void main(String[] args){
  90.                 Solution1 sln = new Solution1();
  91.                 // (A(B(D(E(G))))(C(F)))
  92.                 // char[][] pair = {{'B', 'D'}, {'D', 'E'}, {'A', 'B'}, {'C', 'F'}, {'E', 'G'}, {'A', 'C'}};
  93.                 // E3
  94.                 // char[][] pair = {{'A', 'B'}, {'A', 'C'}, {'B', 'D'}, {'D', 'C'}};. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  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. 1point 3acres 璁哄潧
  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) {
  3.         int len = w.length;
  4.         if (len == 0) return 0;
  5.         Queue<String> cBuf = new LinkedList();
  6.         Map<Integer, Set<String>> allWd = new HashMap();. From 1point 3acres bbs
  7.         int maxLen = 0;
  8.         int maxCLen = 0;
  9.         // find the longest length of strings in w
  10.         for (int i = 0; i < w.length; i++){
  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();. 1point3acres.com/bbs
  16.                 curSet.add(w[i]);
  17.                 allWd.put(curLen, curSet);
  18.             }
  19.         }. 鍥磋鎴戜滑@1point 3 acres
  20.         // search from certain length of words.鏈枃鍘熷垱鑷1point3acres璁哄潧
  21.         for (int i = maxLen; i > maxCLen; i--){. visit 1point3acres.com for more.
  22.             cBuf = new LinkedList(allWd.get(i));. Waral 鍗氬鏈夋洿澶氭枃绔,
  23.             // start from initial set of words to search for chain
  24.             int clen = 0;
  25.             while (!cBuf.isEmpty()){
  26.                 clen++;
  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++){-google 1point3acres
  34.                         String tt = t.substring(0, l) + t.substring(l + 1);
  35.                         if (nextSet.contains(tt)){
  36.                             cBuf.offer(tt);
  37.                             nextSet.remove(tt);
  38.                         }
  39.                     }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  40.                 }
  41.             }. 1point3acres.com/bbs
  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) {
    . visit 1point3acres.com for more.
  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();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6.         Map<Integer, Integer> diag2 = new HashMap();
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7.         for (int i = 0; i < len; i++){
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  8.             int col = a[i] - 1;
  9.             if (diag1.containsKey(i - col)){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  10.                 threat[i]++;
  11.                 threat[diag1.get(i - col)]++;
  12.             }
  13.             diag1.put(i - col, i);
  14.             if (diag2.containsKey(i + col)){
  15.                 threat[i]++;
  16.                 threat[diag2.get(i + col)]++;
  17.             }
  18.             diag2.put(i + col, i);
  19.         }
  20.         int maxThreat = 0;. 1point3acres.com/bbs
  21.         for (int i = 0; i < len; i++){
  22.             maxThreat = Math.max(maxThreat, threat[i]);. 1point 3acres 璁哄潧
  23.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  24.         return maxThreat;
  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. 1point 3acres 璁哄潧
  3.                 Arrays.sort(p);
  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];
  22.                 for (int i = 0; i < p.length; i++){
  23.                         if (p[i] != 0){
  24.                                 for (int j = p[i]; j <= Math.min(l, n); j += p[i]){
  25.                                         mark[j] = 1;
  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++;. From 1point 3acres bbs
  35.                         }
  36.                 }
  37.                
  38.                 // find undivisible numbers from 1 to n. 1point 3acres 璁哄潧
  39.                 if (n < l) return count;
  40.                 else{
  41.                         return n / l * count + count1;
    . 鍥磋鎴戜滑@1point 3 acres
  42.                 }
  43.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  44.         int lcm(int a, int b){. Waral 鍗氬鏈夋洿澶氭枃绔,
  45.                 return a * b / gcd(a, b);
  46.         }
  47.         int gcd(int a, int b){
  48.                 if (a < b) return gcd(b, a);.1point3acres缃
  49.                 return b == 0 ? a : gcd(b, a % b);
  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. from: 1point3acres.com/bbs
  11. ]
  12. //output:
  13. //best merge point: M
  14. 3 + 1 + 3 = 7
  15. . Waral 鍗氬鏈夋洿澶氭枃绔,
  16. Definition: Best merge point: minimal sum of path num between robots and merge point*/
  17. public class Solution{
  18.         class Point{
  19.                 int x;
  20.                 int y;
  21.                 public Point(int x, int y){-google 1point3acres
  22.                         this.x = x;
  23.                     this.y = y;
  24.                 }
  25.         }
  26.         Point bestMergePoint(char[][] mat){. Waral 鍗氬鏈夋洿澶氭枃绔,
  27.          int m = mat.length;
  28.          if (m == 0) return null;
  29.          int n  = mat[0].length;. 鍥磋鎴戜滑@1point 3 acres
  30.        
  31.          // bfs each point that is 1
  32.          int[][] dis = new int[m][n];
  33.          for (int i = 0; i < m; i++){.1point3acres缃
  34.              for (int j = 0; j < n; j++){
  35.                  if (mat[i][j] == '1') bfs(mat, i, j, dis);. from: 1point3acres.com/bbs
  36.              }
  37.          }
  38.          // count number
  39.          int min = Integer.MAX_VALUE;
  40.          Point ret = null;
  41.          for (int i = 0; i < m; i++){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  42.              for (int j = 0; j < n; j++){. From 1point 3acres bbs
  43.                      // if this point is not visited by a robot
  44.                      if (dis[i][j] == 0 && mat[i][j] == '0') continue;
  45.                  if (mat[i][j] != 'X' && dis[i][j] < min){
  46.                      min = dis[i][j];
  47.                      ret = new Point(i, j);
  48.                  }
  49.              }
  50.          }
  51.          return ret;
  52.         }

  53.         //bfs matrix to mark the distance from x and y
  54.         void bfs(char[][] mat, int x, int y, int[][] dis){
  55.                  Queue<Point> path = new LinkedList(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  56.                  int[] dx = {1,-1,0,0};
  57.                  int[] dy = {0,0,1,-1};
  58.                  int m = mat.length;
  59.                  int n = mat[0].length;
  60.                  boolean[][] visited = new boolean[m][n];
  61.                  int ct = 0;
  62.                  System.out.println("Started at: " + x + " " + y);
  63.                  int di = 0;
  64.                  path.offer(new Point(x, y));
  65.                  visited[x][y] = true;
  66.                  while (!path.isEmpty()){. From 1point 3acres bbs
  67.                      int count = path.size();
  68.                      for (int i = 0; i < count; i++){
  69.                          Point cur = path.poll();
  70.                          ct++;
  71.                          // System.out.println(cur.x + " " + cur.y);
  72.                          // visited[cur.x][cur.y] = true;
  73.                          // update cur.value
  74.                          dis[cur.x][cur.y] += di;
  75.                          // check its neighbors
  76.                          for (int j = 0; j < 4; j++){
  77.                              int nx = cur.x + dx[j];
  78.                              int ny = cur.y + dy[j];.1point3acres缃
  79.                              if (nx >= 0 && nx < m && ny >= 0 && ny < m && mat[nx][ny] != 'X' && !visited[nx][ny]){
  80.                                  path.offer(new Point(nx, ny));. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  81.                                  visited[nx][ny] = true;
  82.                              }
  83.                          }. from: 1point3acres.com/bbs
  84.                      }
  85.                      di++;
  86.                  } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  87.                  System.out.println("total points added to queue: " + ct);
  88.         }
  89.         public static void main(String[] args){
  90.                 Solution sln = new Solution();
  91.                 char[][] mat = {{'0', '0', '0', '0', '1'},
  92.                                                 {'0', '1', 'X', '0', '0'},
  93.                                                 {'0', 'X', '0', '0', '0'},
  94.                                                 {'0', '0', '0', '1', '0'},
  95.                                                 {'0', '0', '0', '0', '0'}};
  96.                 Point ret = sln.bestMergePoint(mat);
  97.                 System.out.println(ret.x + " " + ret.y);
  98.         }
  99. }
复制代码
回复 支持 反对

使用道具 举报

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

// Find the largest K such that A^K is a subsequence of B, where A, B are two strings. |A| << |B|.. visit 1point3acres.com for more.

// Power of a string:.鐣欏璁哄潧-涓浜-涓夊垎鍦
// Let A = xyxz
// Then,. 鍥磋鎴戜滑@1point 3 acres
// A^1 = A = xyxz
// A^2 = xxyyxxzz
// A^3 = xxxyyyxxxzzz
. 1point 3acres 璁哄潧
// Example:
// A = xyxz
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷// B = xabyzxz
.1point3acres缃
// B xaybyxzxxxzz

// A xxyyxxzz
  1. public int findK(String A, String B){
  2.             int len1 = A.length(), len2 = B.length();
  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);. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.             }
  16.             int lo = 0, hi = kMax;
  17.             int ret = 0;
  18.             while (lo <= hi){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  19.                 int med = lo + (hi - lo) / 2;
  20.                 if (isSubSeq(expand(A, med), B)){
  21.                     ret = med;
  22.                     lo = med + 1;. 1point 3acres 璁哄潧
  23.                 } else {
  24.                     hi = med - 1;
  25.                 }
  26.             }. more info on 1point3acres.com
  27.             return ret;
  28.         }-google 1point3acres
  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);. more info on 1point3acres.com
  34.                 for (int j = 0; j < k; j++) sbuf.append(c);
  35.             }
  36.             return sbuf.toString();
  37.         }
  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){
  54.             return A.toLowerCase();
  55.         }
复制代码
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 10:54:45 | 显示全部楼层
/*一个正方形的矩阵,左上角的位置保证是0,其他的每个坐标位置上都有一个大于等于0的数。
* 一个人最初携带着的钱数为K,然后要从左上角走到右下角,每次只能向右或者向下走,
* 每到一个位置上就需要花掉该位置上对应的钱数,要求编程看看这个人能不能走到右下角,.1point3acres缃
* 如果不能,就返回-1,如果能,那就要找到一个解法,使得这个人剩余的钱数尽可能少,
* 也就是最终剩余的钱数要大于等于0,并且尽可能接近于0.*/
  1. public class Solution {. 1point 3acres 璁哄潧
  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]])
  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
  11.                 for (int j = 0; j < n; j++){
  12.                         for (int h = 0; h <= k; h++){
  13.                                 dp1[j + 1][h] = -1;-google 1point3acres
  14.                         }
  15.                 }
  16.                 // when j = -1 edge case.1point3acres缃
  17.                 for (int h = 0; h <= k; h++){
  18.                         dp2[0][h] = -1;
  19.                 }
  20.                
  21.                 for (int i = 0; i < m; i++){
  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;
  25.                                         else if (h < mat[i][j]) dp2[j + 1][h] = -1;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  26.                                         else {
  27.                                                 int pre1 = dp2[j][h - mat[i][j]];
  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];
  31.                                         }
  32.                                 }
  33.                         }
  34.                         dp1 = Arrays.copyOf(dp2, n + 1);.1point3acres缃
  35.                 }. 1point 3acres 璁哄潧
  36.                 return dp1[n][k];. From 1point 3acres bbs
  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";
String s2 = "a+b+c-";
. from: 1point3acres.com/bbs
s2的形式是一个字母加上一个符号,正号代表有两个前面的字符,负号代表有四个,也就是说s2其实是"aabbcccc",不考虑invalid。. from: 1point3acres.com/bbs
在s1中,找出连续或者不连续的s2,也就是说从s1中找出"aa....bb.....cccc",abc顺序不能变,但是之间可以有零个或多个字符,返回共有多少个。在上面这个例子中,有四个。
  1. public class Solution {. From 1point 3acres bbs
  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;
  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]. 1point 3acres 璁哄潧
  10.        for (int i = 1; i < len1; i++){
  11.            dp[i + 1][0] = 1;
  12.            for (int j = 0; j < len2 / 2; j++){
  13.                dp[i + 1][j + 1] = dp[i][j + 1];
  14.                if (isMatch(s1, s2, i, j)){
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.                    if (s2.charAt(2*j + 1) == '+')
  16.                        dp[i + 1][j + 1] += dp[i - 1][j];.1point3acres缃
  17.                    else
  18.                        dp[i + 1][j + 1] += dp[i - 3][j];
  19.                }
  20.            }
  21.        }
  22.        return dp[len1][len2 / 2];
  23.    }.鏈枃鍘熷垱鑷1point3acres璁哄潧

  24.    boolean isMatch(String s1, String s2, int i, int j){
  25.        char c = s2.charAt(j * 2);. more info on 1point3acres.com
  26.        char p = s2.charAt(j * 2 + 1);
  27.        int len = p == '+' ? 2 : 4;
  28.        if (i - len < -1) return false;. from: 1point3acres.com/bbs
  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();
  37.            // 4
  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
// 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

代码很不错,赞楼主一个!

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

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

使用道具 举报

Chasego 发表于 2015-10-27 10:22:37 | 显示全部楼层
kennethinsnow 发表于 2015-10-23 11:10
String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+ ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
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.        
  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();-google 1point3acres
  8.                 int lastK = -1;
  9.                 while(left <= right){
  10.                         k = left + (right - left)/2;. visit 1point3acres.com for more.
  11.                         String akString = generateKth(s1, k);
  12.                         if(isSub(akString, s2)){
  13.                                 lastK = k;
  14.                                 left = k + 1;. 鍥磋鎴戜滑@1point 3 acres
  15.                         }else{. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  16.                                 right = k - 1;. from: 1point3acres.com/bbs
  17.                         }
  18.                 }
  19.                 return lastK;
  20.         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  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));-google 1point3acres
  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()){
  36.                         if(s1.charAt(i) == s2.charAt(j)){. visit 1point3acres.com for more.
  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.1point3acres缃
  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, 2017-1-20 14:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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