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

• 对于粘贴操作，之前必须进行一次复制，若要粘贴到文本长度为现在的 n 倍，则需要 1 次复制和 n - 1 次粘贴，共 n 次操作。为了减少操作次数，应该尽可能多的复制，而当前长度必须是复制前长度的整数倍，因此分解质因数，所有质因数的和即为结果

class Solution {
 public:
  int minSteps(int n) {
    vector<int> t{primers(n)};
    int res = 0;
    while (n > 1) {
      for (auto& x : t) {
        if (n % x == 0) {
          n /= x;
          res += x;
          break;
        }
      }
    }
    return res;
  }

  vector<int> primers(int n) {
    vector<int> res;
    if (n < 2) {
      return res;
    }
    vector<bool> dp(n + 1, true);
    for (int i = 2; i < size(dp); ++i) {
      if (dp[i]) {
        res.emplace_back(i);
      }
      for (int j = 0; j < size(res) && i * res[j] < size(dp); ++j) {
        dp[i * res[j]] = false;
        if (i % res[j] == 0) {
          break;
        }
      }
    }
    return res;
  }
};