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

Người quan sát cô đơn · 5/11/24

Phó GOAT đã nói:
Mr Tự Do không đi bỏ phiếu à

sao vẫn ngồi code vậy

trong thớt này hình như có @vicejuniordev là có tịch rồi. Quá thượng đẳng :extreme_sexy_girl:

noobdev · 5/11/24

LmaoSuVuong đã nói:
Java:

class Solution { public int minChanges(String s) { int n = s.length(); char last = s.charAt(0); int cnt =1; int res =0; for(int i =1 ; i < n ; i++){ if(s.charAt(i)==last){ cnt++; } else{ last = s.charAt(i); if(cnt%2==1){ res++; cnt=2; } else cnt =1; } } return res; } }

sao nhìn code mấy bác gọn quá v

đồng dâm đây rồi, code bẩn gang :sweat:

Konstante · 5/11/24

C++:

class Solution {
public:
    int minChanges(string s) {
        auto changes = 0; auto last_c = s.front(); auto odd = true;
        std::for_each(s.begin() + 1, s.end(), [&](const char& c) {
            if (last_c != c && odd) changes += 1;
            last_c = c; odd = !odd;
        });
        return odd ? changes + 1 : changes;
    }
};

Phó GOAT · 5/11/24

Java:

class Solution {
    public int minChanges(String s) {
        int[][] dp = new int[s.length()][2];
        for (int i = 0; i < dp.length; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
        dp[0][s.charAt(0) - '0'] = 0;
        dp[0][1 - (s.charAt(0) - '0')] = 1;
        for (int i = 1; i < s.length(); i++) {
            for (int j = 0; j < 2; j++) {
                if (s.charAt(i) != (char) (j + '0')) dp[i][j] = dp[i - 1][j] + 1;
                else dp[i][j] = dp[i - 1][j];
                if (i % 2 == 0) {
                    if (s.charAt(i) != (char) (j + '0')) dp[i][j] = Math.min(dp[i][j], dp[i - 1][1 - j] + 1);
                    else dp[i][j] = Math.min(dp[i][j], dp[i - 1][1 - j]);
                }
            }
        }
        return Arrays.stream(dp[s.length() - 1]).min().getAsInt();
    }
}

Sao ko ai làm bài này bằng dp nhỉ?

LmaoSuVuong · 5/11/24

Phó GOAT đã nói:

Java:

class Solution {
    public int minChanges(String s) {
        int ans = 0;
        int[][] dp = new int[s.length()][2];
        for (int i = 0; i < dp.length; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
        dp[0][s.charAt(0) - '0'] = 0;
        dp[0][1 - (s.charAt(0) - '0')] = 1;
        for (int i = 1; i < s.length(); i++) {
            for (int j = 0; j < 2; j++) {
                if (s.charAt(i) != (char) (j + '0')) dp[i][j] = dp[i - 1][j] + 1;
                else dp[i][j] = dp[i - 1][j];
                if (i % 2 == 0) {
                    if (s.charAt(i) != (char) (j + '0')) dp[i][j] = Math.min(dp[i][j], dp[i - 1][1 - j] + 1);
                    else dp[i][j] = Math.min(dp[i][j], dp[i - 1][1 - j]);
                }
            }
        }
        return Arrays.stream(dp[s.length() - 1]).min().getAsInt();
    }
}

Sao ko ai làm bài này bằng dp nhỉ?

mùa đông long phụng sum vầy à

garanphomai · 5/11/24

LmaoSuVuong đã nói:
Java:

class Solution { public int minChanges(String s) { int n = s.length(); char last = s.charAt(0); int cnt =1; int res =0; for(int i =1 ; i < n ; i++){ if(s.charAt(i)==last){ cnt++; } else{ last = s.charAt(i); if(cnt%2==1){ res++; cnt=2; } else cnt =1; } } return res; } }

sao nhìn code mấy bác gọn quá v

Phó GOAT đã nói:

Java:

class Solution {
    public int minChanges(String s) {
        int[][] dp = new int[s.length()][2];
        for (int i = 0; i < dp.length; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
        dp[0][s.charAt(0) - '0'] = 0;
        dp[0][1 - (s.charAt(0) - '0')] = 1;
        for (int i = 1; i < s.length(); i++) {
            for (int j = 0; j < 2; j++) {
                if (s.charAt(i) != (char) (j + '0')) dp[i][j] = dp[i - 1][j] + 1;
                else dp[i][j] = dp[i - 1][j];
                if (i % 2 == 0) {
                    if (s.charAt(i) != (char) (j + '0')) dp[i][j] = Math.min(dp[i][j], dp[i - 1][1 - j] + 1);
                    else dp[i][j] = Math.min(dp[i][j], dp[i - 1][1 - j]);
                }
            }
        }
        return Arrays.stream(dp[s.length() - 1]).min().getAsInt();
    }
}

Sao ko ai làm bài này bằng dp nhỉ?

anoldvozer1710.v2 · 5/11/24

Người quan sát cô đơn đã nói:
kancute troll ghẻ f63 hả?

troll ghẻ nhiều quá bay mịa hết nick rồi :rap:

LmaoSuVuong · 5/11/24

garanphomai đã nói:

chuẩn bị để tham gia thị trường OS nhột bửn

boztche · 5/11/24

Python:

class Solution:
    def minChanges(self, s: str) -> int:
        res = 0
        for i in range(0, len(s), 2):
            if s[i] != s[i + 1]:
                res += 1
        return res

behitek · 5/11/24

Python:

class Solution:
    def minChanges(self, s: str) -> int:
        return sum(s[i] != s[i+1] for i in range(0, len(s)-1, 2))

LmaoSuVuong · 5/11/24

garanphomai đã nói:
Chạy n lần 1 function O(n) thì tổng độ phức tạp là n * n = n^2 thím

Hoàng tử wind đã nói:

klq, cơ mà các bác cho em hỏi về complexity space với ví dụ em có một function với độ phức tạp là O(n) nhưng em gọi nó n lần ( không phải đệ quy ) thì complexity của cả thuật toán là bao nhiêu v

Nhấp để mở rộng...

Hoàng tử wind đã nói:
hmm nma k phải là nó lưu stack sau khi nó done thì xoá hả thím, r sau đó lưu lại tiếp vào stack. Giống như kiểu thay đổi dữ liệu trong một mảng nhưng vẫn là O(n) đó

thoát khỏi block là nó trả bộ nhớ, v nên chắc là On, bộ tính AI của leetcode thì nó cũng tính là On thôi.

Mỹ Chu Lang · 5/11/24

ngẫm cả tiếng mới ra

gạch hoài, dỗi đấy :shame:

C#:

public class Solution {
    public int MinChanges(string s) {
        int result = 0;
        for(int i = 0; i<s.Length; i+=2)
        {
            if(s[i] != s[i+1])
                result++;
        }
        return result;
    }
}

Hoàng tử wind · 5/11/24

LmaoSuVuong đã nói:
thoát khỏi block là nó trả bộ nhớ, v nên chắc là On, bộ tính AI của leetcode thì nó cũng tính là On thôi.

em cũng nghĩ v nhưng hôm nó em vọc vạch thì không hiểu sao problem này của em lại bị MLE mà k phải TLE ( s.size() < 1000 ). nhưng khi em đổi sang tham chiếu thì lại chạy ok .....

LmaoSuVuong · 5/11/24

Hoàng tử wind đã nói:
em cũng nghĩ v nhưng hôm nó em vọc vạch thì không hiểu sao problem này của em lại bị MLE mà k phải TLE ( s.size() < 1000 )Xem tệp đính kèm 2766286

bác truyền tham trị, mỗi lần gọi nó tạo 1 string mới = s :shame:

cái này hình như gọi là overhead thì phải

Hoàng tử wind · 5/11/24

LmaoSuVuong đã nói:
bác truyền tham trị, mỗi lần gọi nó tạo 1 string mới = s cái này hình như gọi là overhead thì phải

em hiểu rồi nhưng mà nếu theo hướng suỹ nghĩ về space complex ở trên thì space complex chỉ là O(n) thôi chứ sao MLE đc ...

LmaoSuVuong · 5/11/24

Hoàng tử wind đã nói:
em hiểu rồi nhưng mà nếu theo hướng suỹ nghĩ về space complex ở trên thì space complex chỉ là O(n) thôi chứ sao MLE đc ...

ko biết nữa bác, java vẫn chạy dc :matrix:

e ko rành c++ lắm

Phó GOAT · 5/11/24

Phó GOAT đã nói:

Java:

class Solution {
    public int minChanges(String s) {
        int[][] dp = new int[s.length()][2];
        for (int i = 0; i < dp.length; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);
        dp[0][s.charAt(0) - '0'] = 0;
        dp[0][1 - (s.charAt(0) - '0')] = 1;
        for (int i = 1; i < s.length(); i++) {
            for (int j = 0; j < 2; j++) {
                if (s.charAt(i) != (char) (j + '0')) dp[i][j] = dp[i - 1][j] + 1;
                else dp[i][j] = dp[i - 1][j];
                if (i % 2 == 0) {
                    if (s.charAt(i) != (char) (j + '0')) dp[i][j] = Math.min(dp[i][j], dp[i - 1][1 - j] + 1);
                    else dp[i][j] = Math.min(dp[i][j], dp[i - 1][1 - j]);
                }
            }
        }
        return Arrays.stream(dp[s.length() - 1]).min().getAsInt();
    }
}

Sao ko ai làm bài này bằng dp nhỉ?

Móe dùng DP mà sao lắm gạch thế :amazed:

garanphomai · 5/11/24

LmaoSuVuong đã nói:
chuẩn bị để tham gia thị trường OS nhột bửn

Cơ bắp thế này thì mấy a nhựt khoái lúm :shame:

có offer nhớ phát card ae :beauty:

small-lambda · 5/11/24

C-like:

impl Solution {
    pub fn min_changes(s: String) -> i32 {
        let bytes = s.as_bytes();
        let mut count = 0;

        for chunk in bytes.chunks(2) {
            if chunk[0] != chunk[1] {
                count += 1;
            }
        }

        count
    }
}

retarded_user · 5/11/24

Java:

class Solution {
    public int minChanges(String s) {
        int res = 0, count = 1;
        char lastCh = s.charAt(0);

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                if ((count & 1) != 0) {
                    res += 1;
                    i++;
                }
                count = 1;
            } else {
                count++;
            }
        }

        return res;
    }
}

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

Senior Member

Member

Senior Member

Senior Member

Senior Member

Member

Tệp đính kèm

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này