京东笔试AC 大小写切换 && 合唱队
1. 大小写切换，DP，O(n)
def countPress(s): n = len(s) # dp[0] lower case # dp[1] upper case dp = [[n-i for i in range(n)] for _ in range(2)] if s[-1].isupper(): dp[0][-1] += 1 else: dp[1][-1] += 1 for i in range(2, n+1): ch = s[-i] if ch.isupper(): dp[0][-i] = min(dp[0][-i+1] + 2, dp[1][-i+1] + 2) dp[1][-i] = min(dp[0][-i+1] + 2, dp[1][-i+1] + 1) else: dp[0][-i] = min(dp[0][-i+1] + 1, dp[1][-i+1] + 2) dp[1][-i] = min(dp[0][-i+1] + 2, dp[1][-i+1] + 2) return dp[0][0]
稍微解释一下
典型的DP，重点在于如何划分状态：
- dp[state][i]表示当前大小写状态为state情况下，完成字符串s[i:n)输入所需的最小按键次数。定义state=0表示当前为小写状态，state=1表示当前为大写状态。
- 边界条件：dp[0][n-1]以及dp[1][n-1]，与最后一个字符的大小写有关。
- 状态转移：backward pass。从dp[state][i+1]到dp[state][i]的转移表示，在保持大小写状态state不变的情况下（不按CAPLOCK键），多输入一个s[i]字符所需要增加的按键次数（结合字符的大小写、当前状态考虑需不需要按shift）；类似地，从dp[state][i+1]到dp[~state][i]则表示按下CAPLOCK键，并正确输入s[i]所需增加的按键次数。
- 要求的答案即dp[0][0]
2. 合唱队分组，排序，贪心分组，O(nlogn)
from collections import defaultdict def divideGroups(heights): sorted_h = sorted(heights) count = 0 m = defaultdict(lambda:0) for h, t in zip(heights, sorted_h): m[h] += 1 m[t] -= 1 if m[h] == 0: del m[h] if m[t] == 0: del m[t] if len(m) == 0: count += 1 return count
感觉这题比较trick，观察后可以发现，要满足条件，那么每个分组的队员只需要组内交换，就可以到达各自在全组有序序列中的位置。题目给的n范围不大 105，因此可以考虑对比排序后与初始情况的差别。
- 初始数组排序，O(nlogn)
- 每个人都需要分组，简单起见可以直接从前向后考虑，每次贪心地划分规模最小的分组。
- 举个例子，初始 [2,1,3,2]，最终顺序应该是 [1,2,2,3]。我们可以同时在两个数组加一个滑动的窗口考虑，当窗口覆盖到的两数组元素种类、数量相同时，可以划为一个分组。比如各自的前两个元素：[2,1]和[1,2]，只需要组内交换，一定能达到最终应有的顺序。
- 确定可以划分为一个分组时，清空窗口继续向后寻找；否则窗口左端点不动，右端向后移动即可。
- 技术上来说，可以维护一个map，表示窗口下两个数组元素各种类数量差。如果所有种类数量差均为0，则表示完全相同。这样维护map的时间开销是O(1)。
投递腾讯等公司10个岗位 >
