本次作业完成力扣《面试经典 150 题》「数组 / 字符串」部分 $11$ 道题目
力扣 面试经典 150 题 - 数组 / 字符串
LeetCode 26. 删除有序数组中的重复项
思路
向前集中即可。
代码
提交记录：4ms (98.00%) / 17.89MB (28.91%)
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int ans = 0;
for (int i = 1, ed = nums.size(); i < ed; ++i)
if (nums[ans] != nums[i]) nums[++ans] = nums[i];
return ans + 1;
}
};
LeetCode 80. 删除有序数组中的重复项 II
思路
同上，添加特判即可。
代码
提交记录：0ms (100.00%) / 10.67MB (40.81%)
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int ans = 0;
for (int i = 1, ed = nums.size(); i < ed; ++i)
if (nums[ans] != nums[i] || !ans || nums[ans - 1] != nums[i]) nums[++ans] = nums[i];
return ans + 1;
}
};
LeetCode 169. 多数元素
思路
让少数元素与多数元素相互抵消，剩下的一定是多数元素。
代码
提交记录：8ms (99.13%) / 19.00MB (39.94%)
class Solution {
public:
int majorityElement(vector<int>& nums) {
int cnt = 0, now;
for (auto i : nums) {
if (cnt == 0) now = i;
cnt += now == i ? 1 : -1;
}
return now;
}
};
LeetCode 189. 轮转数组
思路
从另一角度看，原数组与答案数组的数字修改形成了一条（$k \nmid len$）或多条（$k \mid len$）修改链，模拟遍历这些修改链做修改即可。值得注意的是 $k$ 可能超过 $len$，可以对 $len$ 取模来加快计算速度。
代码
提交记录：20ms (92.68%) / 24.14MB (58.15%)
#define mod(x) x >= sz? x - sz : x
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int sz = nums.size(), i = 0, now = -1, nxt, lst = -1;
for (k %= sz; i < sz; ++i) {
if (now == lst) lst = ++now, nxt = nums[mod(now + sz - k)];
swap(nums[now], nxt);
now = mod(now + k);
}
}
};
LeetCode 121. 买卖股票的最佳时机
思路
保存当前最便宜的股票价格作为买入价，并计算每天卖出的利润，保留最大即为答案。
代码
提交记录：92ms (88.34%) / 89.27MB (63.79%)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0, mi = prices[0];
for (auto i : prices) {
mi = min(mi, i);
ans = max(ans, i - mi);
}
return ans;
}
};
LeetCode 122. 买卖股票的最佳时机 II
思路
因为同一天可以同时买入和卖出，因此我们可以将持续超过一天的买入卖出切分为数次买入和后一天卖出，这样我们就可以贪心地通过是否对答案有贡献来决定是否买入并在后一天卖出。
代码
提交记录：0ms (100.00%) / 12.66MB (69.83%)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
for (int i = 1, ed = prices.size(); i < ed; ++i)
if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1];
return ans;
}
};
LeetCode 55. 跳跃游戏
思路
不断更新当前能够到达的最远距离，当距离不够就停止向前。最后判断最远距离是否到达最后一格即可。
代码
提交记录：48ms (78.28%) / 46.70MB (11.42%)
class Solution {
public:
bool canJump(vector<int>& nums) {
int now = 0, sz = nums.size();
for (int i = 0; i < sz && i <= now; ++i) now = max(now, i + nums[i]);
return now >= sz - 1;
}
};
LeetCode 45. 跳跃游戏 II
思路
我们令 $ans_i$ 表示跳 $i$ 步可以跳到的最远格数，$now$ 为跳到当前格需要的部署。那么我们可以贪心地选择 $ans_{i + 1}$ 为 $ans_i$ 和 $i + nums[i]$ 中的较大值。最后返回 $now$ 即可。
代码
提交记录：8ms (95.65%) / 16.19MB (28.67%)
class Solution {
public:
int jump(vector<int>& nums) {
vector<int> ans = { 0 };
int sz = nums.size(), now = 0;
for (int i = 0; i < sz; ++i) {
if (i > ans[now]) ++now;
if (i + nums[i] > ans.back())
if (now + 1 == ans.size()) ans.emplace_back(i + nums[i]);
else ans.back() = i + nums[i];
}
return now;
}
};
LeetCode 274. H 指数
思路
我们可以将 $citations$ 排序后，从大到小遍历，当引用数不满足文章篇数要求时返回答案即可。
代码
提交记录：0ms (100.00%) / 8.38MB (76.87%)
class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.begin(), citations.end(), [](int a, int b) { return a > b; });
for (int i = 0, ed = citations.size(); i < ed; ++i) if (i + 1 > citations[i]) return i;
return citations.size();
}
};
LeetCode 380. O(1) 时间插入、删除和获取随机元素
思路
使用 unordered_set 简单模拟即可。
代码
提交记录：212ms (50.69%) / 92.80MB (48.40%)
class RandomizedSet {
public:
unordered_set<int> S;
RandomizedSet() {
S.clear();
}
bool insert(int val) {
return S.insert(val).second;
}
bool remove(int val) {
return S.erase(val);
}
int getRandom() {
return *next(S.begin(), rand() % S.size());
}
};
LeetCode 238. 除自身以外数组的乘积
思路
先将前缀和储存到答案数组中，然后从后向前遍历，同时计算后缀和并与答案数组相乘即可，时间复杂度 $O(n)$，空间复杂度 $O(1)$。
代码
提交记录：16ms (94.13%) / 24.07MB (32.54%)
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> out;
for (int i = 0, now = 1; i < nums.size(); ++i) out.emplace_back(now), now *= nums[i];
for (int i = nums.size() - 1, now = 1; i > -1; --i) out[i] *= now, now *= nums[i];
return out;
}
};
