LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 有序数组，复杂度 O(log n)，应当使用二分查找，STL 提供了如下二分查找函数
  • std::binary_search：检查元素是否位于范围内，返回 bool
  • std::lower_bound：查找第一个不小于目标值的元素的迭代器，不存在则返回尾后迭代器
  • std::upper_bound：查找第一个大于目标值的元素的迭代器，不存在则返回尾后迭代器

class Solution {
 public:
  vector<int> searchRange(vector<int>& nums, int target) {
    if (!binary_search(begin(nums), end(nums), target)) {
      return {-1, -1};
    }
    int l = lower_bound(begin(nums), end(nums), target) - begin(nums);
    int r = upper_bound(begin(nums), end(nums), target) - begin(nums) - 1;
    return {l, r};
  }
};

• 二分查找的写法关键在于左右区间的选择，右边界的选择和循环判断中的条件一致即可。建议采用左闭右开区间，即当前范围包含左边界但不包含右边界

int binarySearch(vector<int>& nums, int target) {
  int l = 0;
  int r = size(nums);  // 右边界为最后一个元素的后一位置
  while (l != r) {  // 只要左右区间不重合，就说明范围中有元素
    int m = l + (r - l) / 2;  // 防溢出所以不写 (l + r) / 2
    if (nums[m] == target) {
      return m;  // 找到则返回
    } else if (nums[m] > target) {
      r = m;  // 下一范围右边界不包含 m
    } else {
      l = m + 1;  // 下一范围左边界不包含 m
    }
  }           // 结束时 l == r，[l, r) 内不包含任何元素
  return -1;  // 未找到返回 -1
}

• 左闭右闭区间写法如下，显然不如上一种方便

int binarySearch(vector<int>& nums, int target) {
  int l = 0;
  int r = size(nums) - 1;  // 右边界为最后一个元素
  while (l <= r) {         // 包含右边界，所以应该有等号
    int m = l + (r - l) / 2;
    if (nums[m] == target) {
      return m;
    } else if (nums[m] > target) {
      r = m - 1;
    } else {
      l = m + 1;
    }
  }
  return -1;
}

• 在二分查找的基础上，稍微改动即可查找满足某个条件的元素，比如查找第一个不小于目标的元素位置

int lowerBound(vector<int>& nums, int target) {
  int l = 0;
  int r = size(nums);
  while (l != r) {
    int m = l + (r - l) / 2;
    if (nums[m] >= target) {
      r = m;  // 满足条件则继续左压
    } else {
      l = m + 1;
    }
  }  // r 是满足条件的右边界，最后一次左压结束时 r 恰好是第一个满足条件的位置
  // 比如数组只有一个元素且满足条件，则左压一次 l 和 r 都为 0
  // r 恰好落在第一个满足条件的位置
  // 结束时l == r，下面用到的 l 都可以换成 r
  if (l == size(nums)) {  // 没有左压过
    return -1;            // 不会有满足条件的值
  }
  return l;
}

• 可以发现，只要满足条件就缩小右边界，最后得到的就是第一个满足条件的值

template <typename F>
int binarySearch(vector<int>& nums, int n, F check) {
  int l = 0;
  int r = size(nums);
  while (l != r) {
    int m = l + (r - l) / 2;
    if (check(nums[m])) {  // 满足条件则继续左压
      r = m;
    } else {  // 不满足条件则右压
      l = m + 1;
    }
  }
  if (l == size(nums)) {  // 没有左压过
    return -1;            // 不会有满足条件的值
  }
  return l;
}

• 根据此模板实现查找第一个大于目标的元素位置的函数

int upperBound(vector<int>& nums, int target) {
  int l = 0;
  int r = size(nums);
  while (l < r) {
    int m = l + (r - l) / 2;
    if (nums[m] > target) {
      r = m;
    } else {
      l = m + 1;
    }
  }
  if (l == size(nums)) {
    return -1;
  }
  return l;
}

• 最后此题的完整解法如下，注意题目要求的是，与目标相等的第一个和最后一个的元素位置，目标必须存在，和上述实现的函数有一些区别

class Solution {
 public:
  vector<int> searchRange(vector<int>& nums, int target) {
    int a = lowerBound(nums, 0, size(nums), target);
    int b = upperBound(nums, 0, size(nums), target);
    return {a, b};
  }

  int lowerBound(vector<int>& nums, int l, int r, int target) {
    while (l != r) {
      int m = l + (r - l) / 2;
      if (nums[m] >= target) {
        r = m;
      } else {
        l = m + 1;
      }
    }
    return l < size(nums) && nums[l] == target ? l : -1;
  }

  int upperBound(vector<int>& nums, int l, int r, int target) {
    while (l != r) {
      int m = l + (r - l) / 2;
      if (nums[m] > target) {
        r = m;
      } else {
        l = m + 1;
      }
    }
    return l > 0 && nums[l - 1] == target ? l - 1 : -1;
  }
};