thảo luận Leetcode contest, đường tới Guardian

freedom.9 đã nói:

Tuần này tụt hạng nữa rồi, quyết tâm vô top 2k 2 bài contests tuần này bù lại thôi nào

via theNEXTvoz for iPhone

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

freedom.9 đã nói:

Code bài 2

Ruby:

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        kBinary = bin(k)[2:].zfill(32)
        binaryList = []
        for num in nums:
            binaryList.append(bin(num)[2:].zfill(32))
      
        ans = 0
        for i in range(31, -1, -1):
            count = 0
            for item in binaryList:
                if(item[i] == '1'):
                    count+=1
                  
            if count%2 == 1 and kBinary[i] == "0":
                ans+=1
            if count%2 == 0 and kBinary[i] == "1":
                ans+=1
          
        return ans

Code bài 3

Python:

class Solution:
    def minimumOperationsToMakeEqual(self, x: int, y: int) -> int:
        @cache
        def dp(x, y):
            if y > x:
                return y - x
           
            if x == y:
                return 0
           
            ans = 1 + dp(x - 1, y)
            if(x%11 == 0):
                ans = min(ans, 1 + dp(x//11, y), ans)
            else:
                ans = min(ans, 11 - x%11 + 1 + dp((x + 11 - x%11)//11, y))
           
            if(x%5 == 0):
                ans = min(ans, 1 + dp(x//5, y), ans)
            else:
                ans = min(ans, 5 - x%5 + 1 + dp((x + 5 - x%5)//5, y))
           
            return ans
       
        return dp(x, y)

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

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        for (int &d : nums) k ^= d;
        return __builtin_popcount(k);
    }
};

chiyeuemthoi đã nói:

b1 đọc đề ẩu ngồi mãi mới hiểu , b2 phải nhờ bn giảng lại cái XOR mới hiểu , b3 ai cho em xin ít idea với ạ

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

chiyeuemthoi đã nói:

bài 2

Spoiler: bai 2

Python:

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        x = 0
        for num in nums:
            x = x ^ num
        x = x ^ k
        ans = 0
        # dem so bit 1
        while x > 0:
            ans += x % 2
            x //= 2
        return ans

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

trinity đã nói:

bài 2 bác xor vào k rồi tính số bits còn lại của k thôi

Spoiler: c++ xor

C++:

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        for (int &d : nums) k ^= d;
        return __builtin_popcount(k);
    }
};

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

freedom.9 đã nói:

Bài 2 mình cũng nhớ lộn là XOR là 2 phần tử chỉ cần 1 bit 1 là sẽ ra 1 như or operation bình thường. Xong ngồi search lại thì mới ra là 2 bit giống nhau là sẽ về bit 0. Đệt bà
Rất ngại làm mấy bài bitwise vì xưa học explore card còn cái topic này là topic cuối cùng, tuần này quyết tâm ngồi học bitwise với bitmasking thôi cái topic duy nhất mình còn thiếu trong algorithm

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

chiyeuemthoi đã nói:

b1 đọc đề ẩu ngồi mãi mới hiểu , b2 phải nhờ bn giảng lại cái XOR mới hiểu , b3 ai cho em xin ít idea với ạ

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

chiyeuemthoi đã nói:

e quên hết cái đống bit năm 2 có hc môn kĩ thuật số rồi mà em hc vẹt giờ đọc mới ngộ ra

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

freedom.9 đã nói:

Bài 3 thì làm dynamic programming nhiều sẽ nhìn thấy fence ơi, nhanh lắm. Đầu tiên là tìm basecase.
1) Nếu y > x thì ko có cách nào khác ngoài việc tăng x lên => kết quả là y - x
2) Giờ tìm recurrence relation.
Giảm x xuống 1, số operation thì sẽ bằng 1 + dp(x - 1, y)
Chia cho 11 => nếu x%11 == 0 thì kết quả là sẽ bằng 1 + dp(x//11, y), nếu x ko chia hết cho 11 thì còn 1 cách nữa là tăng x lên cho tới khi x chia hết cho 11 thì thôi => kết quả là bằng 1 + (Số operation để tăng lên) + DP(Số tiếp theo /11, x)
Tương tự cho 5
3) Viết thêm base case x == y return 0 nữa. Hàm DP nó sẽ thử hết tất cả các possible solutions thôi.

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

from collections import deque
class Solution(object):
    def minimumOperationsToMakeEqual(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        Que = deque([x])
        visited = [0]*10001
        visited[x] = 0
        if x == y: return 0
        while len(Que):
            if visited[y] > 0:
                return visited[y]
            k = Que.popleft()
            if k < 10000:
                if visited[k+1] == 0:
                    Que.append(k + 1)
                    visited[k+1] = visited[k] + 1
            if k > 0:
                if visited[k-1] == 0:
                    Que.append(k - 1)
                    visited[k-1] = visited[k] + 1
            if k%11 == 0:
                if visited[k//11] == 0:
                    Que.append(k//11)
                    visited[k//11] = visited[k] + 1
            if k%5 == 0:
                if visited[k//5] == 0:
                    Que.append(k//5)
                    visited[k//5] = visited[k] + 1

pikachu_1 đã nói:

Bài 3 mà làm dp là gà.
Làm loang là nhanh nhất. Python mất có 65ms:

Spoiler: py

Python:

from collections import deque
class Solution(object):
    def minimumOperationsToMakeEqual(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        Que = deque([x])
        visited = [0]*10001
        visited[x] = 0
        if x == y: return 0
        while len(Que):
            if visited[y] > 0:
                return visited[y]
            k = Que.popleft()
            if k < 10000:
                if visited[k+1] == 0:
                    Que.append(k + 1)
                    visited[k+1] = visited[k] + 1
            if k > 0:
                if visited[k-1] == 0:
                    Que.append(k - 1)
                    visited[k-1] = visited[k] + 1
            if k%11 == 0:
                if visited[k//11] == 0:
                    Que.append(k//11)
                    visited[k//11] = visited[k] + 1
            if k%5 == 0:
                if visited[k//5] == 0:
                    Que.append(k//5)
                    visited[k//5] = visited[k] + 1

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

trinity đã nói:

accepted là đc rồi bác, còn gà nữa sao

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

pikachu_1 đã nói:

Accept là may mắn thôi.
Dp trường hợp này là O(N^2) cho cả time và space trong trường hợp xấu nhất.
Làm loang thì O(N) thôi.
Với N = 10000 mà N^2 vẫn thoát là rùa.
Cần phải phân tích bài toán trước.

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

freedom.9 đã nói:

Loang là gì, deque chưa học fence

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

pikachu_1 đã nói:

Hàng đợi thím.
deque là 1 cấu trúc có thể thực hiện cả FIFO lẫn LIFO. Tức là nó làm thay ngăn xếp và stack.
Thuật toán loang như kiểu vết dầu loang ý.
Sau 1 ngày nó loang đến đâu, sau 2 ngày nó loang đến đâu...
Cùng lắm là sau N ngày nó loang hết nên cả space lẫn time nó là O(n).
Cái này N = 10^6 vẫn chạy thoải mái.

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

freedom.9 đã nói:

Thì đọc constrain là 3*10^4 mới tính tới dp chứ để lên 10^5 thì ai làm DP chi đâu fence

via theNEXTvoz for iPhone

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