Em lưu 1 cái stack giảm dần, kèm số lượng, thêm 1 số rất lớn ở cuối dãy để chặn.Đệt mẹ bài 4 xài monotonic stack tìm nextGreater + nextSmaller element mà binary search sai hướng cay thế nhỉ
Thế mà làm ko ra buồn quá
Em có dùng thêm 1 cách ạ, em dùng 1 cái mảng left đếm số phần tử phía trước i trong range[0, i-1] có giá trị bằng nums nhưng ở giữa ko có thằng nào lớn hơn nums hết.
int[] left = new int[n];
for (int i = 0; i < n; i++) {
left[i] = 1;
int j = i-1;
while (j >= 0 && nums[j] <= nums[i]) {
if (nums[j] == nums[i]) {
left[i] += left[j];
break;
}
j--;
}
}à ừ nhỉ đếm ngược từ cuối dãy gặp lớn hơn thì ngưng, e đếm xuôi từ 0 ăn tle
for(int j=0;j<=top;j++){
if(stack[j]==stack[top])count++;
}for(int j=top;j>=0;j--){
if(stack[j]==stack[top]) count++;
else break;
}
if (dist[u] != d){ // Sự khác biệt ở đây
continue;
}class Solution {
public:
vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
vector <vector <pair <int, int>>> adj(n);
for (auto &edge: edges){
auto u = edge[0], v = edge[1], w = edge[2];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
const int inf = 1e9 + 7;
vector <int> dist = disappear;
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> pq;
auto transition = [&](int d, int u){
if (dist[u] > d){
dist[u] = d;
pq.emplace(d, u);
}
};
transition(0, 0);
while (not pq.empty()){
auto [d, u] = pq.top(); pq.pop();
if (dist[u] != d){
continue;
}
for (auto &[v, w]: adj[u]){
transition(d + w, v);
}
}
for (auto u = 0; u < n; u++){
if (dist[u] == disappear[u]){
dist[u] = -1;
}
}
return dist;
}
};
câu cuối hôm nay nếu fen làm daily cả tuần nay r thì thấy quen vl
class Solution {
public:
long long numberOfSubarrays(vector<int>& nums) {
vector<pair<int,int>> stack;
long long ret = 0;
for (int i = 0; i < nums.size(); ++i) {
while( !stack.empty() && nums[i] > stack.back().first) {
stack.pop_back();
}
if (!stack.empty() && stack.back().first == nums[i]) {
ret += stack.back().second;
stack.back().second += 1;
} else stack.emplace_back(nums[i], 1);
}
return ret + nums.size();
}
};tuần này trên công ty nhiều task quá, ko ăn cắp thời gian cày leetcode được.
nghĩ đơn giản là lượm tiền rồi huhuhuclass Solution:
def numberOfSubarrays(self, nums: List[int]) -> int:
def binarySearch(leftBoundary, rightBoundary, items):
left = 0
right = len(items) - 1
leftIndex = -1
while left <= right:
mid = (left + right) // 2
if items[mid] >= leftBoundary:
leftIndex = mid
right = mid - 1
else:
left = mid + 1
rightIndex = -1
left = 0
right = len(items) - 1
while left <= right:
mid = (left + right) // 2
if items[mid] <= rightBoundary:
rightIndex = mid
left = mid + 1
else:
right = mid - 1
return rightIndex - leftIndex + 1
n = len(nums)
nextGreater = [n]*n
stack = []
indexes = defaultdict(list)
for i in range(n):
indexes[nums[i]].append(i)
while stack and nums[stack[-1]] < nums[i]:
nextGreater[stack.pop()] = i
stack.append(i)
ans = 0
for i in range(n):
rightBoundary = nextGreater[i] - 1
count = binarySearch(i, rightBoundary, indexes[nums[i]])
ans += count
return ansclass Solution {
public long numberOfSubarrays(int[] nums) {
long ans = 0;
int[] stack = new int[100001];
int top = -1;
HashMap<Integer, Integer> freq = new HashMap();
for (int i = 0; i < nums.length; i++) {
if (top < 0) {//stack empty
top++;
stack[top] = nums[i];
} else {
if (nums[i] > stack[0]) {
top = -1;
freq = new HashMap();
} else {
while (top >= 0 && nums[i] > stack[top]) {
freq.put(stack[top],freq.get(stack[top])-1);
top--;
}
}
top++;
stack[top] = nums[i];
}
freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);
ans += freq.get(nums[i]);
}
return ans;
}
}Câu 3 dijktra phải early continue nếu visitedAt != inf thì mới pass, ăn 2 cái TLE.câu 3 dùng dijsktra mà éo ra khó chịu thế nhỉ, cày lc để làm OA th chứ contest xin thua
Sáng nay em vừa làm lại Q3, hôm qua em đọc đề thì cứ tưởng là node disappear tại thời gian T thì sau đó T+1 sẽ appear lại, nhưng thật ra là nó disappear mãi mãi từ thời gian TCâu 3 dijktra phải early continue nếu visitedAt != inf thì mới pass, ăn 2 cái TLE.
Làm 2 bài 7ph hí hửng tưởng ngon trym rồi ai ngờ làm xong bài 3 vẫn rank 4k hơn ko được + điểm nào, chua vl
