1. 移除字母异位词后的结果数组
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
给每个单词都建一个字典统计每个字符数即可。
代码
class Solution:
def removeAnagrams(self, words: List[str]) -> List[str]:
wordsDic = []
n = len(words)
for i in range(n):
dic = {}
for ch in words[i]:
if ch not in dic: dic[ch] = 1
else: dic[ch] += 1
wordsDic.append(dic)
ans = [words[0]]
start = 0
for i in range(1, n):
if wordsDic[i] != wordsDic[start]:
start = i
ans.append(words[i])
return ans2. 不含特殊楼层的最大连续楼层数
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
本来想直接逐层判断，太慢了。
先把数组排序，然后初始化ans为底层到首个特殊楼层的距离。遍历数组，两个特殊楼层间距离是空闲区域，取最大即可。最后还要判断当前最大距离和顶层到最后一个特殊楼层的距离哪个大。（说距离不太准确，数组首尾和楼层底层、顶层直接减即可，因为包含顶层和底层，特殊楼层间相减需要再减一，因为两边都不包含）
代码
class Solution:
def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
n = len(special)
special.sort()
ans = special[0] - bottom
for i in range(1, n):
ans = max(ans, special[i] - special[i - 1] - 1)
ans = max(ans, top - special[n - 1])
return ans3. 按位与结果大于零的最长组合
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
举例看看，把例子中每个数转为等长的二进制形式，观察其特点，发现如果要按位与结果大于0，则必须使得集合中数字都有一个相同的位为1。那么要使得集合最大，就找集合中数字在哪一位上1最多。我们用一个数组来统计每一位上1的个数（即数字个数），由于数字最大为10的7次方，只要24位就足够了，然后遍历每个数字的每一位即可。时间复杂度是数组长度乘以数字的二进制位长，空间复杂度为常数。
代码
class Solution:
def largestCombination(self, candidates: List[int]) -> int:
num = [0] * 24
for ca in candidates:
pos = 0
while ca != 0:
if (ca & 1) == 1: num[pos] += 1
ca >>= 1
pos += 1
return max(num)
# 再贴一个dalao的优雅版本
class Solution:
def largestCombination(self, candidates: List[int]) -> int:
return max(sum(num >> i & 1 for num in candidates) for i in range(24))4.
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
代码
5. 找到一个数字的 K 美丽值
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
遍历一遍即可。py的字符串是真爽。
代码
class Solution:
def divisorSubstrings(self, num: int, k: int) -> int:
ans = 0
sNum = str(num)
for i in range(len(sNum) - k + 1):
sub = int(sNum[i: k + i])
if sub != 0 and num % sub == 0: ans += 1
return ans6. 分割数组的方案数
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
维护两个数，一个是前半部分的和，一个是后半部分的和。前者从0开始累加，后者从总和开始逐个减，模拟即可。
代码
class Solution:
def waysToSplitArray(self, nums: List[int]) -> int:
total = sum(nums)
n = len(nums)
ans = 0
cur = 0
for i in range(n - 1):
cur += nums[i]
total -= nums[i]
if (cur >= total): ans += 1
return ans7. 毯子覆盖的最多白色砖块数
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
把问题想复杂了，导致要考虑很多细节。
看到连续固定长度，就应该想到用滑动窗口法。或者说，要去枚举终点而不是起点。
cover保存覆盖到的每段瓷砖的总和（可能长度会暂时超出一部分）。每轮加入新的一段，然后如果右端点到左端点的长度超过了毯子长度，那么需要把左端点所在的瓷砖段滑出，移动左端点。在每一轮末尾更新ans，新的实际能cover到的瓷砖长度应当是cover减去一个值，如果左端点在瓷砖段中间，那么我们要减去这段瓷砖起点到左端点的部分，也就是右端点到这段瓷砖左侧的长度减掉毯子长度，或者左端点不在这段瓷砖中间，那么减0。
代码
class Solution:
def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
tiles.sort(key = lambda x: x[0])
cover = ans = left = 0
for tl, tr in tiles:
cover += tr - tl + 1
while tr - tiles[left][1] + 1 > carpetLen:
cover -= tiles[left][1] - tiles[left][0] + 1
left += 1
ans = max(ans, cover - max(tr - tiles[left][0] + 1 - carpetLen, 0))
return ans8. 最大波动的子字符串
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
参考这篇
把枚举字符串和“最大子数组和”的技巧联动，加上一些特殊处理，值得学习。
代码
class Solution:
def largestVariance(self, s: str) -> int:
ans = 0
for a, b in permutations(ascii_lowercase, 2):
diff, diffWithB = 0, -inf
for ch in s:
if ch == a:
diff += 1
diffWithB += 1
elif ch == b:
diff -= 1
diffWithB = diff
if diff < 0:
diff = 0
if diffWithB > ans:
ans = diffWithB
return ans
Comments NOTHING