NguyenQUy1801
Senior Member
nay đc mỗi 3q mà bug tùm lum, đường guardian hơi chậm rồi 
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
seastar
Member
k cần deque đâu. Lúc đầu t cũng nghĩ phức tạp vậy, mà để ý kỹ thì bài đó chả cần dùng gì, loop bt, O(n) thôi.Q2 thì chỉ cần xử lí cái case k >= n thôi em. Còn simulation xài deque là okcơ mà lag quá đếch muốn làm. Chán thật
NguyenQUy1801
Senior Member
Câu 2 e thấy chỉ cần xét đến thằng max trong dãy thôi bác, nếu trước đó mà có thằng nào ăn k ván liên tiếp thì return không thì chỉ cần thằng max :ĐQ2 thì chỉ cần xử lí cái case k >= n thôi em. Còn simulation xài deque là ok
freedom.9
Senior Member
Mình cũng nghĩ thế đó fence, mà implement ko ra nên xài deque cmnl cho nhanh
hieunm3538
Senior Member
Em đặt là gặp max thì return max luôn ýQ2 thì chỉ cần xử lí cái case k >= n thôi em. Còn simulation xài deque là ok
Để tý chạy lại xem fail test nào
vicejuniordev
Senior Member
Python:
class Solution:
def findWinningPlayer(self, skills: List[int], k: int) -> int:
n = len(skills)
if k >= n:
return skills.index(max(skills))
w = 0
c = 0
for i in range(1, n):
if skills[w] > skills[i]:
c += 1
else:
w = i
c = 1
if c == k:
return w
return wvicejuniordev
Senior Member
Q3,4 đọc mãi mới hiểu đề, xoắn vãi trưởng. Q4 TLE 
NguyenQUy1801
Senior Member
các cao nhân cho em xin ý tưởng q4 với ạ
lilleboybk
Senior Member
Q2 may em nhận ra là thằng nào đã thua lần đầu thì ko còn cơ hội thắng nữa nên loop O(n) như mấy bác. Q3 dp 2 trạng thái tưởng ngon ăn mà là ăn 3 bọ
freedom.9
Senior Member
Q3 O(500*500*25) chết là sao nhỉ đm mạt vận leetcode xài lru cache thì cũng toang, chắc phải xài bottom up.
Bọn leetcode cho time complexity rất là ngu, nản vãi.
xài lru cache thì cũng toang, chắc phải xài bottom up.Bọn leetcode cho time complexity rất là ngu, nản vãi.
Python:
class Solution:
def maximumLength(self, nums: List[int], k: int) -> int:
n = len(nums)
cache = [[[-1 for _ in range(26)] for _ in range(n)] for _ in range(n)]
def go(prev, index, total):
if index == n:
return 0
ans = 0
if prev == -1:
ans = max(ans, 1 + go(index, index + 1, total))
else:
if cache[prev][index][total] != -1:
return cache[prev][index][total]
if total < k and nums[prev] != nums[index]:
ans = max(ans, 1 + go(index, index + 1, total + 1))
if nums[prev] == nums[index]:
ans = max(ans, 1 + go(index, index + 1, total))
cache[prev][index][total] = max(ans, go(prev, index + 1, total))
return cache[prev][index][total]
return go(-1, 0, 0)
Sửa lần cuối:
TLE_WA
Junior Member
dp[x][j] lưu độ dài lớn nhất của subsequence kết thúc tại phần tử giá trị x với i indices thỏa điều kiện đề bài.các cao nhân cho em xin ý tưởng q4 với ạ
Bài này bạn có thể sử dụng dp trên map luôn hoặc nén mảng về <= 5 * 10^3 xong dp trên mảng [5001][51] cũng được.
Ý tưởng là tham lam: lưu thêm một mảng mx, mx = độ dài lớn nhất của subsequence với i indices thỏa điều kiện seq != seq[i+1]
Xét phần tử hiện tại là x, số index thỏa mãn là j
=> dp[x][j] = dp[x][j] + 1 (lặp lại nên không ảnh hưởng gì tới j)
và dp[x][j] = max(dp[x][j], mx[j-1] + 1) ( ở đây có thể đắn đo vì lỡ đâu tồn tại dp[x][j] = mx[j] + 1 (mx[j] kết thúc tại x) => Điều này đã được thực hiện ở bước 1 nên không ảnh hưởng kết quả)
Sau đó tại mỗi vòng lặp ta sẽ cố update mx[j] thông qua dp[x][j]
C++:
class Solution {
public:
int dp[5005][55];
int maximumLength(vector<int>& nums, int k) {
unordered_set<int> st;
int n = nums.size();
vector<int> n_nums(nums);
sort(n_nums.begin(), n_nums.end());
unordered_map<int,int> id;
for (int i = 0; i < n; i++) id[n_nums[i]] = i;
for (int i = 0; i < n; i++) nums[i] = id[nums[i]];
vector<int> mx(k+1,0);
for (int i = 0; i < n; i++) {
int x = nums[i];
for (int j = k; j >= 0; j--) {
dp[x][j]++;
if (j) dp[x][j] = max(dp[x][j], mx[j-1] + 1);
mx[j] = max(mx[j], dp[x][j]);
}
}
return *max_element(mx.begin(), mx.end());
}
};
maskup
Senior Member
Em lúc đầu cũng implement cách này, dính mem limit.Q3 O(500*500*25) chết là sao nhỉ đm mạt vận leetcode
Python:class Solution: def maximumLength(self, nums: List[int], k: int) -> int: n = len(nums) cache = [[[-1 for _ in range(26)] for _ in range(n)] for _ in range(n)] def go(prev, index, total): if index == n: return 0 ans = 0 if prev == -1: ans = max(ans, 1 + go(index, index + 1, total)) else: if cache[prev][index][total] != -1: return cache[prev][index][total] if total < k and nums[prev] != nums[index]: ans = max(ans, 1 + go(index, index + 1, total + 1)) if nums[prev] == nums[index]: ans = max(ans, 1 + go(index, index + 1, total)) cache[prev][index][total] = max(ans, go(prev, index + 1, total)) return cache[prev][index][total] return go(-1, 0, 0)
Fix bằng cách giảm 1 tham số, đặt vòng loop trong hàm dp:
Python:
class Solution:
def maximumLength(self, nums: List[int], k: int) -> int:
@cache
def dp(end, k):
if k < 0:
return -math.inf
ans = 1
for i in range(end):
ans = max(ans, 1 + dp(i, k - int(nums[end] != nums[i])))
return ans
n = len(nums)
return max(dp(end, k) for end in range(n))Còn Q4 thì bắt buộc phải code theo hướng bottom-up
seastar
Member
cache vậy chết là đúng rồi. Thử nghĩ xem cache nó có đc re-use nhiều k? hay khi vào thì value trong cache chưa cóQ3 O(500*500*25) chết là sao nhỉ đm mạt vận leetcode
Python:class Solution: def maximumLength(self, nums: List[int], k: int) -> int: n = len(nums) cache = [[[-1 for _ in range(26)] for _ in range(n)] for _ in range(n)] def go(prev, index, total): if index == n: return 0 ans = 0 if prev == -1: ans = max(ans, 1 + go(index, index + 1, total)) else: if cache[prev][index][total] != -1: return cache[prev][index][total] if total < k and nums[prev] != nums[index]: ans = max(ans, 1 + go(index, index + 1, total + 1)) if nums[prev] == nums[index]: ans = max(ans, 1 + go(index, index + 1, total)) cache[prev][index][total] = max(ans, go(prev, index + 1, total)) return cache[prev][index][total] return go(-1, 0, 0)
phuchoang03
Junior Member
các bác có cách nào luyện phần DP không, em làm hết cái leetcode 75 mà cảm giác vẫn không ăn thua
seastar
Member
code ông này nhìn giống code t phết.
Python:
class Solution:
def maximumLength(self, nums: List[int], k: int) -> int:
@cache
def dfs(idx, num_diff):
if num_diff > k or idx == len(nums):
return 0
ret = 1
for i in range(idx + 1, len(nums)):
ret = max(ret, 1 + dfs(i, num_diff + int(nums[idx] != nums[i])))
return ret
return max(dfs(i, 0) for i in range(len(nums)))Mà bài 4 làm ntn bị TLE. tối ưu ntn thế?
LmaoSuVuong
Senior Member
có khóa dp với dp advance(premium) đó bác tổng cộng 100 câu
freedom.9
Senior Member
Python:
class Solution:
def maximumLength(self, nums: List[int], k: int) -> int:
n = len(nums)
@lru_cache(None, False)
def go(index, total):
if index == n:
return 0
ans = 0
for i in range(index + 1, n):
if nums[i] != nums[index] and total < k:
ans = max(ans, go(i, total + 1))
if nums[i] == nums[index]:
ans = max(ans, go(i, total))
return ans + 1
ans = 0
for i in range(n):
ans = max(ans, go(i, 0))
return ansfreedom.9
Senior Member
Nhưng mà mấy thằng C++ vẫn pass đó fence, nhìn đây
C++:
#define ll long long
int dp[503][503][26];
int find(int pos, int prev, int cnt, vector<int> &nums)
{
if(pos == nums.size())
return 0;
int ans = -1;
if(dp[pos][prev+1][cnt] != -1)
return dp[pos][prev+1][cnt];
if(prev == -1) // prev = -1 implies the the subsequence has not started
{
ans = max(ans, find(pos+1, -1, cnt, nums)); // not starting
ans = max(ans, 1 + find(pos+1, pos, cnt, nums)); //starting
}
else
{
if(nums[pos] == nums[prev]) // if prev == curr no need to reduce the cnt when adding to subsequence
{
ans = max(ans, find(pos+1, prev, cnt, nums));
ans = max(ans, 1 + find(pos+1, pos, cnt, nums));
}
else
{
ans = max(ans, find(pos+1, prev, cnt, nums));
if(cnt > 0) // make sure cnt > 0 before adding a number not equal to the previous.
ans = max(ans, 1 + find(pos+1, pos, cnt-1, nums));
}
}
return dp[pos][prev+1][cnt] = ans;
}
class Solution {
public:
int maximumLength(vector<int>& nums, int k) {
memset(dp, -1, sizeof(dp));
int ans = find(0, -1, k, nums);
return ans;
}
};- Trạng thái
Chủ đề tương tự
