1. 移除指定数字得到的最大结果
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
既然字符串中可能有多个digit，而我们要只删除一个来使其达到最大值，那么就要思考删除满足哪种条件的digit最合适。
多举几个例子不难发现，从左往右遍历，如果digit右边是比它大的数字，那么删除这一位digit后，数字会变得更大。如果不删除这一位， 那么总是要删除后面出现的下一个digit，整体数字的位数不变，而高位的数字相比前一种情况更小。
所以我们从左到右遍历，遇到digit小于右侧数字则删除，否则把最后见到的digit位置记录下来，遍历完成时删除最后一个。
代码
class Solution:
def removeDigit(self, number: str, digit: str) -> str:
n = len(number)
last = -1
for i in range(n):
if number[i] == digit:
last = i
if (i == n - 1 or number[i] < number[i + 1]):
break
return number[0:last] + number[last + 1:]2. 必须拿起的最小连续卡牌数
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
如果有超过两张相同卡片，显然我们只考虑两两“相邻”的距离，所以每遇到一张卡片，只需要考虑它上一次出现的位置离现在的位置距离即可。
故只需要一个last数组记录每个卡片上次出现的位置与当前位置间的距离，取最小值即可。
因为数字最大到10的6次方，用字典能省点空间（也许）。
时间O(n)，空间O(1)。
代码
class Solution:
def minimumCardPickup(self, cards: List[int]) -> int:
last = {}
n = len(cards)
ans = inf
for i in range(n):
if cards[i] not in last: last[cards[i]] = i
else:
ans = min(ans, i - last[cards[i]] + 1)
last[cards[i]] = i
if ans == inf: return -1
else: return ans3. 含最多 K 个可整除元素的子数组
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
两层循环记录当前连续段的计数，当计数小于等于k时将该段计入map，实际只是将其映射为值1，所以重复子数组不会重复计数。最后返回map大小。当然用set也是一样的。
由于python的set和map都是无序的，切回cpp写了。
虽然两层循环只有n的平方，但map或者set需要n的对数（大概是），所以总体在n的平方乘n的对数复杂度。
代码
class Solution {
public:
int countDistinct(vector<int>& nums, int k, int p) {
int n = nums.size();
map<vector<int>, int> ans;
vector<vector<int>> cnt(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) {
if (nums[i] % p == 0) cnt[i][i] = 1;
if (cnt[i][i] <= k) ans[{nums[i]}] = 1;
for (int j = i + 1; j < n; ++j) {
if (nums[j] % p == 0) cnt[i][j] = cnt[i][j - 1] + 1;
else cnt[i][j] = cnt[i][j - 1];
if (cnt[i][j] <= k) ans[vector<int>(nums.begin() + i, nums.begin() + j + 1)] = 1;
else break;
}
}
return ans.size();
}
};4. 字符串的总引力
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
参考这篇
给出了子串题目的通用思路
代码
5. 统计是给定字符串前缀的字符串数目
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
s的长度有限，将其前缀存到set中，遍历words即可。
代码
class Solution:
def countPrefixes(self, words: List[str], s: str) -> int:
preSet = set()
for i in range(len(s)):
preSet.add(s[0:i + 1])
ans = 0
for word in words:
if word in preSet: ans += 1
return ans6. 最小平均差
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
注意python整数除法默认结果是浮点数
代码
class Solution:
def minimumAverageDifference(self, nums: List[int]) -> int:
n = len(nums)
preSum = 0
afterSum = sum(nums)
ans = -1
minDiff = inf
for i in range(n):
preSum += nums[i]
afterSum -= nums[i]
if i < n - 1: cur = abs(int(preSum / (i + 1)) - int(afterSum / (n - i - 1)))
else: cur = preSum / (i + 1)
if cur < minDiff:
ans = i
minDiff = cur
return ans7. 统计网格图中没有被保卫的格子数
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
先把每个守卫和墙的位置标出来，然后针对每个守卫的四个方向进行遍历，遇到值为0的格子标记为1，计数加一（被保卫的格子数），当遇到墙或守卫的时候停止遍历。
最后用总的格子数减去守卫数和墙数以及计数即可。
需要注意python的坑，不能用 pic[[0] * n] * m 来创建二维数组，否则产生的二维数组行都是对第一行的浅拷贝，操作某一元素时每一行的该列元素都会被操作。
代码
class Solution:
def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
pic = [[0 for i in range(n)] for j in range(m)]
ans = 0
for guard in guards: pic[guard[0]][guard[1]] = -1
for wall in walls: pic[wall[0]][wall[1]] = -1
for guard in guards:
# up
for i in range(guard[0] - 1, -1, -1):
if pic[i][guard[1]] == -1: break
elif pic[i][guard[1]] == 0:
pic[i][guard[1]] = 1
ans += 1
# down
for i in range(guard[0] + 1, m):
if pic[i][guard[1]] == -1: break
elif pic[i][guard[1]] == 0:
pic[i][guard[1]] = 1
ans += 1
# left
for i in range(guard[1] - 1, -1, -1):
if pic[guard[0]][i] == -1: break
elif pic[guard[0]][i] == 0:
pic[guard[0]][i] = 1
ans += 1
# right
for i in range(guard[1] + 1, n):
if pic[guard[0]][i] == -1: break
elif pic[guard[0]][i] == 0:
pic[guard[0]][i] = 1
ans += 1
return m * n - ans - len(guards) - len(walls)8. 检查是否有合法括号字符串路径
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
我的思路是回溯法检查所有路径，用栈来判断路径。但看到一种做法是用一个整数记录路径的平衡度，遇左加一遇右减一。平衡度总大于等于0，且存在上限，这样做确实能优化许多。
代码
Comments NOTHING