LeetCode(103) -- 165, 166

P165. Compare Version Numbers (Medium)

Compare two version numbers version1 and version2. If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.

The . character does not represent a decimal point and is used to separate number sequences.

For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

You may assume the default revision number for each level of a version number to be 0. For example, version number 3.4 has a revision number of 3 and 4 for its first and second level revision number. Its third and fourth level revision number are both 0.

My Solution

class Solution {
    public int compareVersion(String version1, String version2) {
        while (version1.length() > 0 || version2.length() > 0) {
            int v1 = 0, v2 = 0;
            if (version1.length() > 0) {
                int point1 = version1.indexOf(".");
                if (point1 == -1) {
                    v1 = Integer.parseInt(version1);
                    version1 = "";
                } else {
                    v1 = Integer.parseInt(version1.substring(0, point1));
                    version1 = version1.substring(point1 + 1);
                }
            }
            if (version2.length() > 0) {
                int point2 = version2.indexOf(".");
                if (point2 == -1) {
                    v2 = Integer.parseInt(version2);
                    version2 = "";
                } else {
                    v2 = Integer.parseInt(version2.substring(0, point2));
                    version2 = version2.substring(point2 + 1);
                }
            }
            if (v1 > v2) {
                return 1;
            } else if (v1 < v2) {
                return -1;
            }
        }
        return 0;
    }
}

88%

Solution

class Solution {
  public Pair<Integer, Integer> getNextChunk(String version, int n, int p) {
    // if pointer is set to the end of string
    // return 0
    if (p > n - 1) {
      return new Pair(0, p);
    }
    // find the end of chunk
    int i, pEnd = p;
    while (pEnd < n && version.charAt(pEnd) != '.') {
      ++pEnd;
    }
    // retrieve the chunk
    if (pEnd != n - 1) {
      i = Integer.parseInt(version.substring(p, pEnd));
    } else {
      i = Integer.parseInt(version.substring(p, n));
    }
    // find the beginning of next chunk
    p = pEnd + 1;

    return new Pair(i, p);
  }

  public int compareVersion(String version1, String version2) {
    int p1 = 0, p2 = 0;
    int n1 = version1.length(), n2 = version2.length();

    // compare versions
    int i1, i2;
    Pair<Integer, Integer> pair;
    while (p1 < n1 || p2 < n2) {
      pair = getNextChunk(version1, n1, p1);
      i1 = pair.getKey();
      p1 = pair.getValue();

      pair = getNextChunk(version2, n2, p2);
      i2 = pair.getKey();
      p2 = pair.getValue();
      if (i1 != i2) {
        return i1 > i2 ? 1 : -1;
      }
    }
    // the versions are equal
    return 0;
  }
}

看起来很繁琐，感觉用我自己的就可以了。

P166. Fraction to Recurring Decimal (Medium)

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

My Solution

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (denominator == 0) {
            return "";
        }
        if (numerator == 0) {
            return "0";
        }
        boolean negative = false;
        long numeratorLong = numerator, denominatorLong = denominator;
        if (numerator < 0 && denominator > 0) {
            negative = true;
            numeratorLong = -(long)numerator;
        } else if (numerator > 0 && denominator < 0) {
            negative = true;
            denominatorLong = -(long)denominator;
        } else if (numerator < 0) {
            numeratorLong = -(long)numerator;
            denominatorLong = -(long)denominator;
        }
        StringBuilder sb = new StringBuilder();
        if (numeratorLong > denominatorLong && numeratorLong % denominatorLong == 0) {
            return negative ? String.valueOf(-numeratorLong / denominatorLong) : String.valueOf(numeratorLong / denominatorLong);
        }
        sb.append(numeratorLong / denominatorLong).append(".");
        long remainder = numeratorLong % denominatorLong;
        HashMap<Long, Integer> map = new HashMap<>();
        int count = sb.length();
        while (remainder > 0) {
            if (map.containsKey(remainder)) {
                sb.insert(map.get(remainder), "(");
                sb.append(")");
                break;
            }
            map.put(remainder, count);
            remainder *= 10;
            while (remainder < denominatorLong) {
                remainder *= 10;
                sb.append("0");
                count++;
            }
            sb.append(remainder / denominatorLong);
            count++;
            remainder = remainder % denominatorLong;
        }
        if (negative) {
            return "-" + sb.toString();
        }
        return sb.toString();
    }
}

100%

Solution

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }
        StringBuilder fraction = new StringBuilder();
        if (numerator < 0 ^ denominator < 0) {
            fraction.append("-");
        }
        long dividend = Math.abs(Long.valueOf(numerator));
        long divisor = Math.abs(Long.valueOf(denominator));
        fraction.append(String.valueOf(dividend / divisor));
        long remainder = dividend % divisor;
        if (remainder == 0) {
            return fraction.toString();
        }
        fraction.append(".");
        Map<Long, Integer> map = new HashMap<>();
        while (remainder != 0) {
            if (map.containsKey(remainder)) {
                fraction.insert(map.get(remainder), "(");
                fraction.append(")");
                break;
            }
            map.put(remainder, fraction.length());
            remainder *= 10;
            fraction.append(String.valueOf(remainder / divisor));
            remainder %= divisor;
        }
        return fraction.toString();
    }
}

这道题算法没什么特别的，就按小学数学除法做就行了。但是答案的代码比我的简洁干净很多。