10分钟前的面经 Zenefits

hulahu 发表于 2015-9-1 07:13
楼主， 打错了吗？ eZafhajkefhlZadhflkejhZfagjhfebhh 这有三个Z

补充内容 (2015-9-1 07:14):

标少了...但是答案还是2 因为Y只有两个

不知道要求的时间复杂度是多少，简单想了下，可以用二分。

  public int StringPower(String A, String B) {
    if (A.length() > B.length()) {
      return 0;
    }
    int n = B.length() / A.length();

    int left = 0;
    int right = n;
    while (left + 1 < right) {
      int mid = left + (right - left) / 2;
      if (isValid(A, B, mid)) {
        left = mid;
      } else {
        right = mid;
      }
    }

    if (isValid(A, B, right)) {
      return right;
    }
    return left;
  }

  private boolean isValid(String A, String B, int k) {
    int index = 0;
    for (int i = 0; i < A.length(); i++) {
      for (int j = 0; j < k; j++) {
        while (index < B.length() && A.charAt(i) != B.charAt(index)) {
          index++;
        }
        if (index == B.length()) {
          return false;
        }
        index++;
      }
    }

    return true;
  }

purplesky85 发表于 2015-9-2 05:26
不知道要求的时间复杂度是多少，简单想了下，可以用二分。

  public int StringPower(String A, String  ...

没太看懂, 但是简单的方法可以先从1开始, 判断是否是subseqence, 如果是, power++, 再判断, 直到不是为止.

power = 0;
XYZ是, power++; 然后再 判断 XXYYZZ, 也是, power++;, 再判断XXXYYYZZZ, 结果不是, 此时power = 2

就return了. 时间复杂度是O(N)

public int findK(String a, String b) {
        int[] count_a = new int[256];
        int[] count_b = new int[256];
        for (int i = 0; i < a.length(); i++) {
            count_a[a.charAt(i)]++;
        }
        for (int i = 0; i < b.length(); i++) {
            if (count_a[b.charAt(i)] == 0)
                count_b[b.charAt(i)] --;
            else
                count_b[b.charAt(i)] ++;
        }
        StringBuffer sb_b = new StringBuffer();
        for (int i = 0; i < b.length(); i++) {
            if (count_b[b.charAt(i)] > 0)
                sb_b.append(b.charAt(i));
        }
        String t_b = encode(sb_b.toString());
        int min = Integer.MAX_VALUE;
        for (int i = 0; i <t_b.length(); i++) {
            if (t_b.charAt(i) <= '9' && t_b.charAt(i) >= '0')
                min = Math.min(min, t_b.charAt(i) - '0');
        }
        return min;
    }
    public String encode(String s) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            int counter = 1;
            while (i+1 < s.length() && s.charAt(i) == s.charAt(i+1)) {
                counter++;
                i++;
            }
            sb.append(counter);
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        String a = "XYX";
        String b = "XXadhflakjhelXXzzqqkkpoYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhhXX";
        System.out.println(new Zenefits().findK(a,b));
    }

readman 发表于 2015-9-4 00:51
public int findK(String a, String b) {
        int[] count_a = new int[256];
        int[] count_b ...

XXXYYYXZZZ 的话是否会return 1