倒序思想|hash

lc3817

枚举结尾索引

class Solution {
public:
vector<int> goodIndices(string s) {
vector<int> res;
for (int i = 0; i < s.length(); i++) {
string toMatch = to_string(i);
if (!s.compare(i + 1 - toMatch.length(), toMatch.length(), toMatch)) {
res.push_back(i);
}
}
return res;
}
};

lc3822

hash表的基本使用

struct Order {
int orderId, price;
string orderType;
Order(int oi, string ot, int p) : orderId(oi), orderType(ot), price(p) {};
};

class OrderManagementSystem {
unordered_map<int, Order*> map;
public:
OrderManagementSystem() {}

void addOrder(int orderId, string orderType, int price) {
Order* o = new Order(orderId, orderType, price);
map[orderId] = o;
}

void modifyOrder(int orderId, int newPrice) {
map[orderId]->price = newPrice;
}

void cancelOrder(int orderId) {
map.erase(orderId);
}

vector<int> getOrdersAtPrice(string orderType, int price) {
vector<int> ans;
for(const auto& p : map)
if(p.second->orderType == orderType && p.second->price == price)
ans.push_back(p.first);
return ans;
}
};

lc3807

二分+bfs

class Solution:
def minCost(self, n: int, edges: List[List[int]], k: int) -> int:
g = [[] for _ in range(n)]
for x, y, w in edges:
g[x].append((y, w))
g[y].append((x, w))

vis = [-1] * n
def check(mx: int) -> bool:
q = [0]
left = k
while q and left:
tmp = q
q = []
for x in tmp:
for y, w in g[x]:
if w > mx:
continue
if y == n - 1:
return True
if vis[y] != mx:
vis[y] = mx
q.append(y)
left -= 1
return False

mx = max(e[2] for e in edges)
ans = bisect_left(range(mx + 1), True, key=check)
return -1 if ans > mx else ans

lc3817

hash计数+倒序遍历

class Solution {
public:
vector<int> delayedCount(vector<int>& nums, int k) {
int n = nums.size(), counts[100001] = {0}; //[i+k+1, n-1]元素频率
vector<int> ans(n, 0);
for (int i = n - 1; i >= 0; --i) { //从后往前遍历
int j = i + k + 1; //进入有效统计范围的元素下标
if (j < n) counts[nums[j]]++; //哈希计数
ans[i] = counts[nums[i]]; //在i+k之后有相等的元素
}
return ans;
}
};