mới coi qua, bài 4 khó chứ 3 bài đầu luyện thường xuyên sẽ làm dc.
thảo luận Leetcode contest, đường tới Guardian
- Người tạo chủ đề freedom.9
- Ngày bắt đầu
- Trạng thái
Violet_7
Member
Nay vào muộn nên ko tham gia, đọc qua bài 4 khoai thật. Đọc solution mấy lần mới hiểu và implement đc 
Python:
class Solution:
def findPermutation(self, nums: List[int]) -> List[int]:
n = len(nums)
nexts = [[float('inf')] * n for _ in range(1 << n)]
@cache
def dp(mask, first):
nonlocal nexts
if mask == (1 << first):
return abs(first - nums[0])
min_dp = float('inf')
for after_first in range(n):
if after_first == first or ((1 << after_first) & mask) == 0:
continue
next_mask = mask - (1 << first)
curr_dp = abs(first - nums[after_first]) + dp(next_mask, after_first)
if curr_dp < min_dp:
min_dp = curr_dp
nexts[mask][first] = after_first
return min_dp
res = []
curr_mask = (1 << n) -1
curr_first = 0
dp(curr_mask, curr_first)
while curr_mask:
res.append(curr_first)
next_mask = curr_mask - (1 << curr_first)
next_first = nexts[curr_mask][curr_first]
curr_mask, curr_first = next_mask, next_first
return res
i-am-groot
Senior Member
mình nghĩ là do test yếu nên backtracking vẫn AC được
LmaoSuVuong
Senior Member
dễ hay ko bác cứ check accepted rate ấy. thấy chỉ số này phản ánh đúng độ khó của bài r. med ma chỉ loanh quanh 2x% cũng khoai lắm.
NguyenQUy1801
Senior Member
Bài 4 e thấy nhiều ông làm kiểu sinh hết permutation cũng pass :Đ
humanversion9x
Senior Member
Mình nghĩ họ phải có điều kiện để kết thúc nhánh sớm thì mới pass được.
NguyenQUy1801
Senior Member
có mỗi chỗ nếu phí hiện tại lớn hơn cái nhỏ nhất thì kết thúc ạ, cái này thì cũng dễ nhìn ra
class Solution
{
public:
vector<int> findPermutation(vector<int> &nums)
{
int n = nums.size();
int min_cost = numeric_limits<int>::max();
vector<int> best_permutation;
vector<bool> used(n, false);
vector<int> perm;
dfs(perm, used, 0, nums, min_cost, best_permutation);
return best_permutation;
}
private:
void dfs(vector<int> &perm, vector<bool> &used, int current_cost, const vector<int> &nums, int &min_cost, vector<int> &best_permutation)
{
int n = nums.size();
if (perm.size() == n)
{
int final_cost = current_cost + abs(perm.back() - nums[perm[0]]);
if (final_cost < min_cost)
{
min_cost = final_cost;
best_permutation = perm;
}
return;
}
for (int i = 0; i < n; ++i)
{
if (!used)
{
if (!perm.empty())
{
int next_cost = current_cost + abs(perm.back() - nums);
if (next_cost < min_cost)
{
used = true;
perm.push_back(i);
dfs(perm, used, next_cost, nums, min_cost, best_permutation);
perm.pop_back();
used = false;
}
}
else
{
used = true;
perm.push_back(i);
dfs(perm, used, 0, nums, min_cost, best_permutation);
perm.pop_back();
used = false;
}
}
}
}
};
Sửa lần cuối:
i need her k19
Junior Member
Em lần đầu tới với thằng leetcode, em là gốc chuyên tin, mấy thím cho em hỏi là ranking tính kiểu sao mà em lại chả thấy update ở đâu cả. Không như codeforce là sẽ hiện cho mình rằng đã tham gia vào contest nào. Hình ảnh contest lúc sáng:
mấy bài div2 khó vl thật
hieunm3538
Senior Member
Ranking update vào khoảng thứ 5 nhé bác, check ranking có thể dùng lccn hoặc clist để check ngay sau khi contest xong cũng được
JustAnOtherClone
Senior Member
nay tình cờ đọc được cái này, top 4000 đã có 900 ông cheat thì chơi bời gì nữa
i-am-groot
Senior Member
mục đích của mấy ông cheat này là gì nhỉ?
maskup
Senior Member
honda stone
Junior Member
Em thấy việc để profile Leetcode vào CV nó hơi ...Xem tệp đính kèm 2496148hình như tụi nó muốn kiếm Knight bỏ vào CV
Ví dụ đi phỏng vấn thì bên công ty người ta sẽ dễ dàng check được là profile thằng này làm bài như thế nào, hardcore hơn thì có thể check chép code như mấy ông trong thread kia.
Ngoài ra nữa, người ta còn biết được mình chưa làm những bài nào và sẽ có thể lôi những bài đấy ra để hỏi
LmaoSuVuong
Senior Member
team 2 câu nên chắc tạm nghỉ contest 1 thời gian bao h nội công thâm hậu hơn quay lại
chứ làm 2 câu cũng ko dc + rank
JustAnOtherClone
Senior Member
tính ra 900 đứa là copy paste nguyên mới bị bắt, còn mấy đứa biết sửa tên biến với format lại code nữa, khéo đến nửa mấy bố top là cheater mất.
honda stone
Junior Member
À dạ, em quên mất
freedom.9
Senior Member
Kệ mẹ tụi nó, làm thật ăn thật thôi các fence.
Mấy contest vừa rồi bị triggered làm tệ quá, tuần này mới tu luyện mấy chục bài rating > 2k hi vọng phục thù
via theNEXTvoz for iPhone
Mấy contest vừa rồi bị triggered làm tệ quá, tuần này mới tu luyện mấy chục bài rating > 2k hi vọng phục thù
via theNEXTvoz for iPhone
humanversion9x
Senior Member
Mình cũng có cùng câu hỏi? Xác định đi thi đấu là để kiểm tra trình độ bản thân mà còn gian lận thì vừa không kiểm tra được trình độ của bản thân vừa mất thời gian.
- Trạng thái
Chủ đề tương tự
