0161-0170

161. One Edit Distance $\star\star$

162. Find Peak Element $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int findPeakElement(vector<int>& nums) {
    int l = 0;
    int r = nums.size() - 1;

    while (l < r) {
      int m = l + (r - l) / 2;
      if (nums[m] > nums[m + 1])
        r = m;
      else
        l = m + 1;
    }

    return l;
  }
};

163. Missing Ranges $\star\star$

164. Maximum Gap $\star\star\star$

165. Compare Version Numbers $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int compareVersion(string version1, string version2) {
    istringstream iss1(version1);
    istringstream iss2(version2);
    int num1;
    int num2;
    char c;

    while (bool(iss1 >> num1) + bool(iss2 >> num2)) {
      if (num1 < num2) return -1;
      if (num1 > num2) return 1;
      iss1 >> c;
      iss2 >> c;
      num1 = 0;
      num2 = 0;
    }

    if (num1 == num2) return 0;

    return 0;
  };
};

166. Fraction to Recurring Decimal $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  string fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0) return "0";

    string ans;

    if (numerator < 0 ^ denominator < 0) ans += "-";

    long n = abs((long)numerator);
    long d = abs((long)denominator);
    ans += to_string(n / d);

    if (n % d == 0) return ans;

    ans += '.';
    unordered_map<int, int> map;

    for (long r = n % d; r; r %= d) {
      if (map.count(r) > 0) {
        ans.insert(map[r], 1, '(');
        ans += ')';
        break;
      }
      map[r] = ans.size();
      r *= 10;
      ans += to_string(r / d);
    }

    return ans;
  }
};

167. Two Sum II - Input array is sorted $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  vector<int> twoSum(vector<int>& numbers, int target) {
    int l = 0;
    int r = numbers.size() - 1;

    while (l < r) {
      int sum = numbers[l] + numbers[r];
      if (sum == target) return {l + 1, r + 1};
      if (sum < target)
        ++l;
      else
        --r;
    }

    throw;
  }
};

168. Excel Sheet Column Title $\star$

1
2
3
4
5
6
7
class Solution {
 public:
  string convertToTitle(int n) {
    return n == 0 ? ""
                  : convertToTitle((n - 1) / 26) + (char)('A' + ((n - 1) % 26));
  }
};

169. Majority Element $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  int majorityElement(vector<int>& nums) {
    int ans;
    int count = 0;

    for (int num : nums) {
      if (count == 0) ans = num;
      count += num == ans ? 1 : -1;
    }

    return ans;
  }
};

170. Two Sum III - Data structure design $\star$