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

retarded_user · 8/10/24

Java:

class Solution {
    public int minSwaps(String s) {
        int count = 0;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            if (ch == '[') {
                count++;
            } else {
                if (count != 0) {
                    count--;
                }
            }
        }

        return (count + 1) / 2;
    }
}

anoldvozer1710.v2 · 8/10/24

LmaoSuVuong đã nói:
tháng 10 đẫm máu của mấy bác đâu

sao cả 1 tuần r chưa phải mở tab sol ra bao h

chịu chết

katows · 8/10/24

Các bác có thể giải thích bài hôm nay không, tại sao công thức là [(số lượng không cân bằng + 1) / 2] các bác nhỉ. Em không chứng minh được công thức. Nhìn đơn giản mà em chưa hiểu lắm

LmaoSuVuong · 8/10/24

katows đã nói:
Các bác có thể giải thích bài hôm nay không, tại sao công thức là [(số lượng không cân bằng + 1) / 2] các bác nhỉ. Em không chứng minh được công thức. Nhìn đơn giản mà em chưa hiểu lắm

swap 1 lượt ] đứng sai với 1 [ đứng sai thì sẽ có 2 cặp được trả đúng vị trí (bước/2), nếu số cặp lẻ thì vẫn phải swap thêm phát nữa (+1). ko chứng minh được nó đúng, cảm giác nó như v test thử pass thì nghỉ thôi

anoldvozer1710.v2 · 8/10/24

katows đã nói:
Các bác có thể giải thích bài hôm nay không, tại sao công thức là [(số lượng không cân bằng + 1) / 2] các bác nhỉ. Em không chứng minh được công thức. Nhìn đơn giản mà em chưa hiểu lắm

Để xử lý trường hợp số lẻ đó.
Đổi 1 lần thì đc max là 2 cái, nếu số cặp là lẻ, kiểu gì cũng phải cần swap thêm 1 cặp nữa

katows · 8/10/24

LmaoSuVuong đã nói:
swap 1 lượt ] đứng sai với 1 [ đứng sai thì sẽ có 2 cặp được trả đúng vị trí (bước/2), nếu số cặp lẻ thì vẫn phải swap thêm phát nữa (+1). ko chứng minh được nó đúng, cảm giác nó như v test thử pass thì nghỉ thôi

anoldvozer1710.v2 đã nói:
Để xử lý trường hợp số lẻ đó.
Đổi 1 lần thì đc max là 2 cái, nếu số cặp là lẻ, kiểu gì cũng phải cần swap thêm 1 cặp nữa

cảm ơn bác, nhờ các bác em hiểu sơ sơ rồi

seastar · 8/10/24

Công thức phức tạp làm gì, chỉ cần đếm bt là đc.

C++:

class Solution {
public:
    int minSwaps(string s) {
        int ret = 0, num = 0;
        for (auto x : s) {
            num += x == '[' ? 1 : -1;
            if (num < 0) {
                ret += 1;
                num = 1;
            }
        }
        return ret;
    }
};

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

Python:

class Solution:
    def minSwaps(self, s: str) -> int:
        count = 0
        swap = 0
        for i in range(len(s)):
            if s[i] == ']':
                count-=1
            else:
                count+=1
            if count<0:
                swap+=1
                count=1
        return swap

noobdev · 8/10/24

seastar đã nói:
Công thức phức tạp làm gì, chỉ cần đếm bt là đc.

C++:

class Solution { public: int minSwaps(string s) { int ret = 0, num = 0; for (auto x : s) { num += x == '[' ? 1 : -1; if (num < 0) { ret += 1; num = 1; } } return ret; } };

Cái khó là chứng minh cách đếm này nó đúng ấy bác.

nchhnchh · 9/10/24

Python:

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        result, count = 0, 0
        for c in s:
            if c == '(':
                count += 1
            elif count > 0:
                count -= 1
            else:
                result += 1
        
        result += count
        return result

Takeitiz · 9/10/24

C++:

class Solution {
public:
    int minAddToMakeValid(string s) {
        int numsOpen = 0, ans = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') numsOpen++;
            else {
                if (numsOpen > 0) numsOpen--;
                else ans++;
            }
        }
        return ans + numsOpen;
    }
};

freedom.9 · 9/10/24

Python:

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        leftCounts = 0
        ans = 0
        for char in s:
            if char == "(":
                leftCounts += 1
            else:
                if leftCounts > 0:
                    leftCounts -= 1
                else:
                    ans += 1

        return ans + leftCounts

___Cyber___ · 9/10/24

PHP:

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function minAddToMakeValid($s) {
        $o = "(";
        $c = ")";
        $stack = [];
        for ($i=0; $i<strlen($s); $i++) {
            if (count($stack) == 0) {
                $stack[] = $s[$i];
                continue;
            }

            $prev = array_pop($stack);
            if ($s[$i] == $c && $prev == $o) continue;

            $stack[] = $prev;
            $stack[] = $s[$i];
        }

        return count($stack);
    }
}

hoangi19 · 9/10/24

Python:

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        count = 0
        res = 0
        for c in s:
            if c == '(':
                count += 1
            else:
                count -= 1
            if count < 0:
                res += 1
                count = 0
        return res + count

anoldvozer1710.v2 · 9/10/24

medium gì vậy trời :ops:

JavaScript:

function minAddToMakeValid(s: string): number {
    let count = 0, res = 0
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') count++;
        else {
            if (count < 1) res++
            else count--
        }
    }   
    return res + count;
};

behitek · 9/10/24

Python:

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stack = []
        error = 0
        for i, c in enumerate(s):
            if c == '(':
                stack.append(c)
            else:
                if stack:
                    stack.pop()
                else:
                    error += 1
        return error + len(stack)

Phó GOAT · 9/10/24

Java:

class Solution {
    public int minAddToMakeValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (!stack.empty() && stack.peek() == '(' && c == ')') stack.pop();
            else stack.push(c);
        }
        return stack.size();
    }
}

Python:

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stack = []
        for i in range(len(s)):
            if (stack and stack[-1] == '(' and s[i] == ')'):
                stack.pop()
            else:
                stack.append(s[i])
        return len(stack)

Éo khác bài hôm qua là mấy

noobdev · 9/10/24

Bài hôm nay rating có 1242

méo hiểu còn thấp hơn cả mấy bài Easy nữa

để cái tag Medium giống lùa gà quá ta

garanphomai · 9/10/24

noobdev đã nói:
Bài hôm nay rating có 1242 méo hiểu còn thấp hơn cả mấy bài Easy nữa để cái tag Medium giống lùa gà quá ta

Chắc chạy đề cho đủ kpi

katows · 9/10/24

medium hình như hơi sai sai.

Mã:

class Solution {
public:
    int minAddToMakeValid(string s) {
        int st = 0;
        int k = 0;
        for(char c : s) {
            if(c == '(') {
                st++;
            }
            else {
                if (st > 0)
                    st--;
                else
                    k++;
            }
        }
        return st + k;
    }
};

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

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này