目录
100352. 交换后字典序最小的字符串
原题链接
思路分析
签到题，一次遍历O(N)
AC代码
class Solution:
def getSmallestString(self, s: str) -> str:
s = list(s)
n = len(s)
i = 0
for i in range(1, n):
if (int(s[i]) & 1) == (int(s[i - 1]) & 1) and int(s[i]) < int(s[i - 1]):
s[i], s[i - 1] = s[i - 1], s[i]
break
return ''.join(s)100368. 从链表中移除在数组中存在的节点
原题链接
思路分析
这题在搞什么……
链表基础题，不说了……
O(N)
AC代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(-1, head)
pre, cur = dummy, head
st = set(nums)
while cur:
if cur.val in st:
pre.next = cur.next
cur = pre.next
continue
pre = pre.next
cur = pre.next
return dummy.next100361. 切蛋糕的最小总开销 I
原题链接
思路分析
见下道题
AC代码
class Solution:
def minimumCost(self, m: int, n: int, row: List[int], col: List[int]) -> int:
row.sort(reverse=True)
col.sort(reverse=True)
cntr = cntc = 1
i = j = 0
res = 0
while i < m - 1 and j < n - 1:
if row[i] > col[j]:
res += row[i] * cntr
cntc += 1
i += 1
else:
res += col[j] * cntc
cntr += 1
j += 1
while i < m - 1:
res += row[i] * cntr
i += 1
while j < n - 1:
res += col[j] * cntc
j += 1
return res100367. 切蛋糕的最小总开销 II
原题链接
思路分析
原题溯源：[HAOI2009] 巧克力 - 洛谷
我们考虑第一次横着切，竖着的每一刀要切的次数都得加1
竖着同理
那么我们每次对于一块要么横切要么竖切，然后另一个方向上的贡献都得加1
然后如果确定要切一个方向，切的一定是这个方向上最大的那个（贪心，让其贡献最小）
我们得出一个结论：切割操作中，同方向的切割操作的代价是降序的
事实上我们接下来要做的操作相当于合并两个有序数组（降序）
每次取最大的那个，加上其贡献，然后另一个方向上的贡献+1
这样为什么是对的？
假设我们已经得到了若干块，此时从两个数组头部拿出一个最大的，这个值一定是全局最大，那么把这个方向上的这个位置都来一刀是局部最优的
为什么？
假如我们贪心法局部最优是横着切r1，竖着切最小值是c1
我们切r1后c1的贡献会+1，切c1后r1的贡献会加1
前者减后者的差为c1 - r1 < 0，更优
那么对于任意非贪心解，我们都可以临项交换法将其调整为贪心解，于是贪心正确
AC代码
class Solution:
def minimumCost(self, m: int, n: int, row: List[int], col: List[int]) -> int:
row.sort(reverse=True)
col.sort(reverse=True)
cntr = cntc = 1
i = j = 0
res = 0
while i < m - 1 and j < n - 1:
if row[i] > col[j]:
res += row[i] * cntr
cntc += 1
i += 1
else:
res += col[j] * cntc
cntr += 1
j += 1
while i < m - 1:
res += row[i] * cntr
i += 1
while j < n - 1:
res += col[j] * cntc
j += 1
return res
