thảo luận Leetcode mỗi ngày

freedom.9 · 2/9/23

hungmessi2 đã nói:
Ae cho hỏi học thằng DP như thế nào là ok nhất nhỉ, nghe bảo học từ đệ quy rồi qua. Đang có nguồn học từ leetcode premium hay neetcode mà chưa biết nên coi thằng nào trươc
@freedom.9 trải nghiệm thấy ai ok hơn bác

Mình thấy code leetcode ok, nhưng mà thường thì phải giải từ recursion trước, sau rồi implement topdown, xong rồi mới implement bottom up nó mới lên tay được bác.
Chứ 1 lần nhảy vào bottom up luôn chắc chỉ có siêu nhân.
Dp thì có template sẵn rồi, tìm base case, tìm recursion relation trước nhưng mà tìm ra viết code chưa chắc giải đc.
Dp mình thấy khó nhất cmnr nên phải tập trung luyện nhiều :too_sad:

via theNEXTvoz for iPhone

trinity · 2/9/23

freedom.9 đã nói:
Bài 2 contest nay khó thế nhỉ, xài backtracking hả ae

via theNEXTvoz for iPhone

tạo 2 string ở các vị trí chẵn lẻ, sort xong rồi so sánh bác

freedom.9 · 2/9/23

trinity đã nói:
tạo 2 string ở các vị trí chẵn lẻ, sort xong rồi so sánh bác

Vãi ... Cay thế nhỉ :too_sad:

via theNEXTvoz for iPhone

TLE_WA · 2/9/23

Contest hôm nay chả học được gì mới, biết thế đi chơi cho lành :sweat:

Violet_7 · 2/9/23

freedom.9 đã nói:
Bài 2 contest nay khó thế nhỉ, xài backtracking hả ae

via theNEXTvoz for iPhone

Đi chơi r

. Chắc mai cx thế :big_smile:

freedom.9 · 3/9/23

Violet_7 đã nói:
Đi chơi r . Chắc mai cx thế

Bài 2 dễ vl mà mình nghĩ phức tạp quá :sweat:

thôi nghỉ lễ ae tranh thủ rủ gái gú đi chơi :sexy_girl:

via theNEXTvoz for iPhone

nchhnchh · 3/9/23

Python:

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        paths = [[0] * n for _ in range(m)]

        for i in range(m):
            paths[i][0] = 1
        for j in range(n):
            paths[0][j] = 1
        
        for i in range(1, m):
            for j in range(1, n):
                paths[i][j] = paths[i][j-1] + paths[i-1][j]

        return paths[m-1][n-1]

Violet_7 · 3/9/23

Python:

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m + n - 2, m - 1)

thanbaiks · 3/9/23

JavaScript:

const memoized = {}
var uniquePaths = function(m, n) {
    if (m < 1 || n < 1) {
        return 0;
    }
    if (m == 1 && n == 1) {
        return 1;
    }
    const k = String([m, n])
    memoized[k] ||= uniquePaths(m - 1, n) + uniquePaths(m, n - 1)
    
    return memoized[k];
};

LKDT0357 · 3/9/23

Weekly contest bài 2 tuần này căng phết. Ko khó nhưng nhiều corner case cần check v

def minimumOperations(self, num: str) -> int:
if len(num) == 2:
if num[1] == '0':
if num[0] == '5':
return 0
else:
return 1
elif num[1] == '5':
if num[0] == '2':
return 0
elif num[0] == '7':
return 0
else:
return 2
else:
return 2
if len(num) == 1:
if num[0] == '0':
return 0
else:
return 1
res = 0
flag_0 = False
count_0 = 0
flag_5 = False
count_5 = 0
j = len(num) - 1
while j >= 0:
if num[j] == '0' and not flag_0:
flag_0 = True
count_0 = len(num) - j - 1
count_5 += 1
j -= 1
continue
if num[j] == '5' and not flag_5 and not flag_0:
flag_5 = True
count_5 = len(num) - j - 1
count_0 += 1
j -= 1
continue
if num[j] in ['5', '0'] and flag_0:
return count_0
if num[j] in ['2', '7'] and flag_5:
return count_5
count_0 += 1
count_5 += 1
j -= 1
res = min(count_0, count_5)
if res == len(num) - 1 and not flag_0 and flag_5:
return len(num)
return res

freedom.9 · 3/9/23

LKDT0357 đã nói:
Weekly contest bài 2 tuần này căng phết. Ko khó nhưng nhiều corner case cần check v

def minimumOperations(self, num: str) -> int:
if len(num) == 2:
if num[1] == '0':
if num[0] == '5':
return 0
else:
return 1
elif num[1] == '5':
if num[0] == '2':
return 0
elif num[0] == '7':
return 0
else:
return 2
else:
return 2
if len(num) == 1:
if num[0] == '0':
return 0
else:
return 1
res = 0
flag_0 = False
count_0 = 0
flag_5 = False
count_5 = 0
j = len(num) - 1
while j >= 0:
if num[j] == '0' and not flag_0:
flag_0 = True
count_0 = len(num) - j - 1
count_5 += 1
j -= 1
continue
if num[j] == '5' and not flag_5 and not flag_0:
flag_5 = True
count_5 = len(num) - j - 1
count_0 += 1
j -= 1
continue
if num[j] in ['5', '0'] and flag_0:
return count_0
if num[j] in ['2', '7'] and flag_5:
return count_5
count_0 += 1
count_5 += 1
j -= 1
res = min(count_0, count_5)
if res == len(num) - 1 and not flag_0 and flag_5:
return len(num)
return res

Bài 3 khó vl, n^2 mà TLE thì làm kiểu gì. Chuyển về O(n) bằng gì được nhỉ, khó vãi cức huhu
Còn bài 2 mình làm đơn giản hơn fence

C#:

public class Solution {
    public int MinimumOperations(string num) {
        var minOperation = num.Length;
        for(int i = num.Length - 1; i >= 0; i--)
        {
            for(int j = i - 1; j >= 0; j--)
            {
                string pairs = $"{num[j]}{num[i]}";
                if(pairs == "00" || pairs == "25" || pairs == "50" || pairs == "75")
                {
                    minOperation = Math.Min(num.Length - j - 2, minOperation);
                }
            }
        }
        
        if(num.IndexOf('0') != -1)
        {
            minOperation = Math.Min(minOperation, num.Length - 1);
        }
        
        return minOperation;
    }
}

TLE_WA · 3/9/23

LKDT0357 đã nói:
Weekly contest bài 2 tuần này căng phết. Ko khó nhưng nhiều corner case cần check v

Do cách implement thôi

freedom.9 · 3/9/23

C#:

public class Solution {
    public long CountInterestingSubarrays(IList<int> nums, int modulo, int k) {
        var ans = 0;
        for(int i = 0; i < nums.Count ; i++)
        {
            var count = 0;
            for(int j = i; j< nums.Count; j++)
            {
                if(nums[j]%modulo == k)
                {
                    count++;
                }
                
                if(count%modulo == k)
                {
                    ans++;
                }
            }
        }
        
        return ans;
    }
}

Mé ngu chỉ cần chuyển qua 2 passes xong mẹ rồi, ý tưởng xài prefix num mà mãi ko làm ra =((

TLE_WA · 3/9/23

Bài 4 hôm nay dùng LCA là ăn được mà không kiếm nổi cái template ra hồn để copy vào :beat_brick:

trinity · 3/9/23

freedom.9 đã nói:

C#:

public class Solution {
    public long CountInterestingSubarrays(IList<int> nums, int modulo, int k) {
        var ans = 0;
        for(int i = 0; i < nums.Count ; i++)
        {
            var count = 0;
            for(int j = i; j< nums.Count; j++)
            {
                if(nums[j]%modulo == k)
                {
                    count++;
                }
               
                if(count%modulo == k)
                {
                    ans++;
                }
            }
        }
       
        return ans;
    }
}

Mé ngu chỉ cần chuyển qua 2 passes xong mẹ rồi, ý tưởng xài prefix num mà mãi ko làm ra =((

Cách này O(n2) sao pass đc hết test bác?

freedom.9 · 3/9/23

trinity đã nói:
Cách này O(n2) sao pass đc hết test bác?

Ko rõ nữa, mình thấy TLE với lại còn vài test cases chưa pass thôi ko biết dính edge cases gì ko

sai thì chắc do đọc đề ko kĩ chỗ nào rồi

TLE_WA · 3/9/23

C++:

// I copy template from this page: https://cp-algorithms.com/graph/lca_binary_lifting.html#implementation
int n, l;
const int N = 1e4 + 1;
vector<int> adj[N];
vector<pair<int,int>> adj2[N];
int timer;
vector<int> tin, tout;
vector<vector<int>> up;

void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

    for (int u : adj[v]) {
        if (u != p)
            dfs(u, v);
    }

    tout[v] = ++timer;
}

bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = l; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}

void preprocess(int root) {
    tin.resize(n);
    tout.resize(n);
    timer = 0;
    l = ceil(log2(n));
    up.assign(n, vector<int>(l + 1));
    dfs(root, root);
}
class Solution {
public:
    int cnt[N][27];
    void dfs2(int u, int fa){
        for (auto& p : adj2[u]){
            int v = p.first, w = p.second;
            if (v != fa){
                for (int i = 1; i <= 26; i++) cnt[v][i] = cnt[u][i];
                cnt[v][w]++;
                dfs2(v,u);
            }
        }
    }
    vector<int> minOperationsQueries(int n_, vector<vector<int>>& edges, vector<vector<int>>& queries) {
        vector<int> ans;
        n = n_;
        for (int i = 0; i < n; i++) adj[i].clear(), adj2[i].clear();
        for (auto & p: edges){
            int u = p[0], v = p[1], w = p[2];
            adj2[u].push_back({v,w});
            adj2[v].push_back({u,w});
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        preprocess(0);
        dfs2(0,-1);
        for (auto& p: queries){
            int a = p[0], b = p[1];
            int u = lca(a,b);
            vector<int> cur(27);
            long long tot = 0;
            for (int i = 1; i <= 26; i++){
                cur[i] = cnt[a][i] + cnt[b][i] - 2 * cnt[u][i];
                tot += cur[i];
                //cout << cur[i] << ' ';
            }
            ans.push_back(tot - *max_element(cur.begin(),cur.end()));
        }
        return ans;
    }
};

nashwade · 3/9/23

freedom.9 đã nói:
Ko rõ nữa, mình thấy TLE với lại còn vài test cases chưa pass thôi ko biết dính edge cases gì ko sai thì chắc do đọc đề ko kĩ chỗ nào rồi

1e5 thì chỉ có O(N) hoặc O(Nlog) thôi chứ O(N^2) hiển nhiên là không pass rồi thím

Character_L · 3/9/23

C++:

class Solution {
public:
    int uniquePaths(int m, int n) {
        int a[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i==0 || j == 0) {
                    a[i][j] = 1;
                    continue;
                }
                a[i][j] = a[i][j-1] + a[i-1][j];
            }
        }
        return a[m-1][n-1];
        }
};

Du Học Sinh Cali · 3/9/23

mấy thím cho em hỏi 1 câu hỏi với: static trong C vị trí nó ở data. vậy giả sử em define nó trong function (stack) thì khi ko call hàm lên thì biến nó có nằm trong data ko các thím.

thảo luận Leetcode mỗi ngày

Senior Member

Senior Member

Senior Member

Junior Member

Member

Senior Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Junior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này