2037. 使每位学生都有座位的最少移动次数
# 2037. 使每位学生都有座位的最少移动次数
class Solution {public: int minMovesToSeat(vector<int>& seats, vector<int>& students) { sort(seats.begin(), seats.end()); sort(students.begin(), students.end()); int ans = 0; for (int i = 0; i < seats.size(); i++) { ans += abs(seats[i] - students[i]); } return ans; }};
855. 考场就座
# 855. 考场就座
struct Comp { bool operator()(const pair<int, int> &p1, const pair<int, int> &p2) { int d1 = p1.second - p1.first, d2 = p2.second - p2.first; return d1 / 2 < d2 / 2 || (d1 / 2 == d2 / 2 && p1.first > p2.first); }};class ExamRoom {private: int n; set<int> seats; priority_queue<pair<int, int>, vector<pair<int, int>>, Comp> pq;public: ExamRoom(int n) : n(n) { ...
2032. 至少在两个数组中出现的值
# 2032. 至少在两个数组中出现的值
class Solution {public: vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) { map<int,int> m; set<int> n; for (auto num : nums1) { m[num] = 1; } for (auto num : nums2) { if (m.count(num) && m[num] == 1) n.insert(num); else m[num] = 2; } for (auto num : nums3) { ...
1750. 删除字符串两端相同字符后的最短长度
# 1750. 删除字符串两端相同字符后的最短长度
class Solution {public: int minimumLength(string s) { int n = s.size(); int left = 0, right = n - 1; while (left < right && s[left] == s[right]) { char c = s[left]; while (left <= right && s[left] == c) { left++; } while (left <= right && s[right] == c) { right--; } } return ri ...
2027. 转换字符串的最少操作次数
class Solution {public: int minimumMoves(string s) { int ans = 0; int flag = 0; int num = 0; for (int i = 0; i < s.length(); i++) { if (s[i] == 'X') { flag++; num++; } else { if (flag != 0) num++; } if (num == 3) { num = 0; flag = 0; ans++; } } if ...
1759. 统计同构子字符串的数目
# 1759. 统计同构子字符串的数目
class Solution {public: int countHomogenous(string s) { long long MOD = 1e9 + 7; int left = 0; long long ans = 0; for (int i = 1; i < s.length(); i++) { if (s[i] != s[left]) { ans += (i - left) * (i - left + 1) / 2; ans %= MOD; left = i; } } ans += (s.length() - left) * (s.length() + 1 - left) / 2; return ans % MOD; }& ...
1739. 放置盒子
# 1739. 放置盒子
class Solution {public: int minimumBoxes(int n) { int cur = 1, i = 1, j = 1; while (n > cur) { n -= cur; i++; cur += i; } cur = 1; while (n > cur) { n -= cur; j++; cur++; } return (i - 1) * i / 2 + j; }};
1754. 构造字典序最大的合并字符串
# 1754. 构造字典序最大的合并字符串
class Solution {public: string largestMerge(string word1, string word2) { string merge; int i = 0, j = 0; while (i < word1.size() || j < word2.size()) { if (i < word1.size() && word1.substr(i) > word2.substr(j)) { merge.push_back(word1[i++]); } else { merge.push_back(word2[j++]); } } return merge; }};
2011. 执行操作后的变量值
# 2011. 执行操作后的变量值
class Solution {public: int finalValueAfterOperations(vector<string>& operations) { int ans = 0; for (auto op : operations) { if (op == "--X" || op == "X--") ans--; if (op == "++X" || op == "X++") ans++; } return ans; }};
复杂度分析
时间复杂度:$O (n)$
空间复杂度:$O (1)$
1799. N 次操作后的最大分数和
# 1799. N 次操作后的最大分数和
class Solution {public: int maxScore(vector<int>& nums) { int m = nums.size(); vector<int> dp(1 << m, 0); vector<vector<int>> gcd_tmp(m, vector<int>(m, 0)); for (int i = 0; i < m; ++i) { for (int j = i + 1; j < m; ++j) { gcd_tmp[i][j] = gcd(nums[i], nums[j]); } } int all = 1 << m; for (int s = 1; s < all ...