Problem A - 回文链表
方法一：贪心
先将链表转为数组再进行处理。
从两端开始，如果能够匹配，就一直贪心地进行匹配。
- 如果最终匹配成功，也即原本就是回文，此时在删去中间位置的数（长度为偶数时可以删去中间两个中的任意一个），仍是回文串。
- 如果无法匹配成功：
- 尝试删去当前左侧的字符，也即左侧向后推进一位，继续匹配；
- 尝试删去当前右侧的字符，也即右侧往前推进一位，继续匹配。
复杂度：
- 时间复杂度 。
- 空间复杂度 。
参考代码（Python 3）
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
nums = []
while head != None:
nums.append(head.val)
head = head.next
n = len(nums)
l = 0
r = n - 1
while l <= r and nums[l] == nums[r]:
l += 1
r -= 1
if l > r:
return True
return nums[l+1:r+1] == nums[l+1:r+1][::-1] or nums[l:r] == nums[l:r][::-1]Problem B - 优惠活动系统
方法一：模拟
按要求模拟即可。
具体各操作的复杂度不再一一列出。
参考代码（C++）
struct Activity {
int priceLimit, discount, number, userLimit;
unordered_map<int, int> cnt;
};
class DiscountSystem {
unordered_map<int, Activity> activities;
public:
DiscountSystem() {
}
void addActivity(int actId, int priceLimit, int discount, int number, int userLimit) {
activities[actId] = Activity{priceLimit, discount, number, userLimit};
}
void removeActivity(int actId) {
activities.erase(actId);
}
int consume(int userId, int cost) {
int best_id = INT_MAX;
int best_discount = 0;
for (auto [i, a] : activities) {
if (a.number > 0 && a.cnt[userId] < a.userLimit && cost >= a.priceLimit) {
if (a.discount > best_discount) {
best_discount = a.discount;
best_id = i;
}
}
}
if (best_id != INT_MAX) {
auto &a = activities[best_id];
a.number--;
a.cnt[userId]++;
}
return cost - best_discount;
}
};Problem C - 理财产品
方法一：二分答案
我们可以首先二分答案求出买到不少于 limit 个产品时最低价值的理财产品的价值。
此时有两种情况：
- 二分得到的答案是零，表明此时所有产品的个数加起来不到
limit个，直接返回总价值即可（注意取模）。 - 二分得到的答案是正数。此时所有价值不小于答案的产品的个数加起来大于等于
limit个，我们先求出它们的总和，再减去多算的价值刚好等于答案的产品即可。
- 时间复杂度，其中 为价值的最大值。
- 空间复杂度。
参考代码（Python 3）
class Solution:
def maxInvestment(self, product: List[int], limit: int) -> int:
lo = 1
hi = int(1e7)
while lo <= hi:
mid = (lo + hi) >> 1
cnt = 0
for p in product:
cnt += max(0, p - mid + 1)
if cnt < limit:
hi = mid - 1
else:
lo = mid + 1
if hi == 0:
return sum(p * (p + 1) // 2 for p in product) % 1000000007
cnt = 0
ans = 0
for p in product:
if p >= hi:
ans += (p + hi) * (p - hi + 1) // 2
cnt += p - hi + 1
ans -= (cnt - limit) * hi
return ans % 1000000007
Problem D - 合作开发
方法一：枚举子集+计数
我们尝试找出所有不能合作的员工对。
- 技能完全一致的员工不能合作。我们将员工按照技能分组统计，并减去同一组内员工形成的对。
- 一个人的技能被另一个人的技能真包含时，两人不能合作。对于这种情况，我们可以枚举每一个技能组的子集，并去除当前技能组与其各个子集形成的对。
最后就可以得到答案。
- 时间复杂度。
- 空间复杂度。
参考代码（Python 3）
from itertools import chain, combinations
def powerset(lst):
return chain.from_iterable(combinations(lst,n) for n in range(len(lst)))
class Solution:
def coopDevelop(self, skills: List[List[int]]) -> int:
cnt = collections.Counter()
n = len(skills)
for skill in skills:
cnt[tuple(skill)] += 1
ans = n * (n - 1) // 2
for m in cnt.values():
ans -= m * (m - 1) // 2
for skill in cnt:
for sub in powerset(skill):
if sub in cnt:
ans -= cnt[skill] * cnt[sub]
return ans % 1000000007评论 (3)
