thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.
- Người tạo chủ đề freedom.9
- Ngày bắt đầu
)
freedom.99
Senior Member
Đề mấy nay dễ mà toàn làm ngáo đét, còn 40 điểm là lên đc group cuối cùng mà làm rất ngáo. Chắc cuối năm nay ko kịp lên rồi.
Mấy câu 6 điểm cơ bản mà cũng ko làm được
Mấy câu 6 điểm cơ bản mà cũng ko làm được
aNotHeRNo0b
Senior Member
Q3 mà không Circular thì giải kiểu quái gì nhỉ??
JakovichTimViec
Senior Member
Left sài stack
Right thì lấy pointer ,
Làm for loop từ trái sang phải.
Nếu cur >0 thì nhét index của nó vào stack và bước tiếp.
Nếu cur <0 thì xét index pointer với stack hiện tại.
Thằng nào đang có khoảng cách bé hơn thì ưu tiền lấy thằng đó trước, nếu bằng thì ưu tiên left
aNotHeRNo0b
Senior Member
bác chắc chưaThì làm 2 pointer 2 đầu thôi bác. Em nghĩ nếu ko circular thì đề dễ hơn nhiều ý,
Left sài stack
Right thì lấy pointer ,
Làm for loop từ trái sang phải.
Nếu cur >0 thì nhét index của nó vào stack và bước tiếp.
Nếu cur <0 thì xét index pointer với stack hiện tại.
Thằng nào đang có khoảng cách bé hơn thì ưu tiền lấy thằng đó trước, nếu bằng thì ưu tiên left
JakovichTimViec
Senior Member
bác chắc chưacó khi nào không bằng mà vẫn ưu tiên lấy thằng left (dù thằng left lớn hơn không).
aNotHeRNo0b
Senior Member
Ví dụ tại vị trí i, phải của nó là j, trái của nó là t, bác thấy thằng phải gần hơn, nên bác lấy từ nó. Nma lỡ đâu tồn tại 1 thằng h > j mà phải lấy từ thằng trái t đề bù vào thì sao?
JakovichTimViec
Senior Member
aNotHeRNo0b
Senior Member
Bài hôm nay em giải bằng cách bác nói do circular nên nó mới đúng chứ nhỉ :v hay là do test yếu nhỉ?Thì làm 2 pointer 2 đầu thôi bác. Em nghĩ nếu ko circular thì đề dễ hơn nhiều ý,
Left sài stack
Right thì lấy pointer ,
Làm for loop từ trái sang phải.
Nếu cur >0 thì nhét index của nó vào stack và bước tiếp.
Nếu cur <0 thì xét index pointer với stack hiện tại.
Thằng nào đang có khoảng cách bé hơn thì ưu tiền lấy thằng đó trước, nếu bằng thì ưu tiên left
Java:
class Solution {
public long minMoves(int[] balance) {
long negative = 0;
long positive = 0;
for (int i = 0; i < balance.length; i += 1) {
if (balance[i] < 0) {
negative += balance[i];
} else {
positive += balance[i];
}
}
if (Math.abs(negative) > positive) {
return -1;
}
if (negative == 0) {
return 0;
}
TreeSet<Integer> positivePtr = new TreeSet<>();
for (int i = 0; i < 3 * balance.length; i += 1) {
if (balance[i % balance.length] > 0) {
positivePtr.add(i);
}
}
long move = 0;
int i = balance.length;
int length = balance.length;
while (i < 2 * length) {
if (balance[i % length] < 0) {
int higher = (positivePtr.higher(i) == null) ? 1_000_000_000 : positivePtr.higher(i);
int lower = (positivePtr.lower(i) == null) ? -1_000_000_000 : positivePtr.lower(i);
int selected = (Math.abs(i - higher) >= Math.abs(i - lower)) ? lower : higher;
int gap = Math.min(balance[selected % length], 0 - balance[i % length]);
move += 1L * gap * Math.abs(selected - i);
balance[i % length] += gap;
balance[selected % length] -= gap;
if (balance[selected % length] == 0) {
positivePtr.remove(selected);
positivePtr.remove(selected + balance.length);
positivePtr.remove(selected + 2 * balance.length);
}
continue;
}
i += 1;
}
return move;
}
}JakovichTimViec
Senior Member
Test yếu thật mà bác vì đề chỉ có <=1 số âm thôi
Sửa lần cuối:
aNotHeRNo0b
Senior Member
:v đề nhiều số ấm cũng nhức đầu phết bác, chắc do <= 1 nên mới passTest yếu thật mà bác vì đề chỉ có <=1 số âm thôi
Cái này bác nghĩ theo hướng BFS ấy, cùng khoảng cách thì ưu tiên như nhau. Lấy hết từ khoảng cách 1 xong thì qua 2, và tăng dần. Sau khi kiểm tra các edge case(không thể hoặc không cần phải dịch chuyển) thì cứ tự tin while True th
Python:
class Solution:
def minMoves(self, balance: List[int]) -> int:
total = sum(balance)
if total < 0:
return -1
n_index = None
for i, b in enumerate(balance):
if b < 0:
n_index = i
break
if n_index is None:
return 0
target = -balance[n_index]
l = n_index - 1
r = n_index + 1
factor = 1
n = len(balance)
res = 0
while target > 0:
l %= n
r %= n
value = 0
if l != r:
value += balance[l] + balance[r]
else:
value += balance[r]
add_value = min(value, target)
res += add_value * factor
target -= add_value
l -= 1
r += 1
factor += 1
#print(l, r, add_value, target, factor)
return resJakovichTimViec
Senior Member
athxzz
Senior Member
đánh virtual khỏe thật
Q4 chơi BIT cũng khoai
C++:
struct FenwickTree
{
vector<int> bit; // binary indexed tree
int n;
FenwickTree(int n)
{
this->n = n;
bit.assign(n, 0);
}
FenwickTree(vector<int> const &a) : FenwickTree(a.size())
{
for (size_t i = 0; i < a.size(); i++)
add(i, a[i]);
}
int sum(int r)
{
int ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1)
ret += bit[r];
return ret;
}
int sum(int l, int r)
{
return sum(r) - sum(l - 1);
}
void add(int idx, int delta)
{
for (; idx < n; idx = idx | (idx + 1))
bit[idx] += delta;
}
};
class Solution
{
public:
vector<int> minDeletions(string s, vector<vector<int>> &queries)
{
int n = s.size();
FenwickTree d(n);
for (int i = 1; i < n; i++) {
if(s[i] == s[i - 1]) {
d.add(i, 1);
}
}
vector<int> ans;
for(auto &q: queries) {
if(q[0] == 1) {
int index = q[1];
if(index > 0 && s[index - 1] == s[index]) {
d.add(index, -1);
}
if(index > 0 && s[index - 1] != s[index]) {
d.add(index, 1);
}
if(index < n - 1 && s[index] == s[index + 1]) {
d.add(index + 1, -1);
}
if(index < n - 1 && s[index] != s[index + 1]) {
d.add(index + 1, 1);
}
if(s[index] == 'A') s[index] = 'B';
else s[index] = 'A';
} else {
int l = q[1];
int r = q[2];
if((r - l + 1) == 1) ans.push_back(0);
else ans.push_back(d.sum(l + 1, r));
}
}
return ans;
}
};freedom.99
Senior Member
Ủa ko circular thì vẫn giải như thường thôi, greedy lấy từ 2 bên trái phải liên tục vì số steps là như nhau mà, dùng hết values trái phải để transform qua thằng middle thôi chứ đâu cần quan tâm.
via theNEXTvoz for iPhone
via theNEXTvoz for iPhone
analogy.2
Senior Member
Em đọc thì thấy ý thím đó hiểu nhầm đề bài là có thể có n>1 số âm trong chuỗi
Chủ đề tương tự
