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

  • Người tạo chủ đề Người tạo chủ đề _Gia_Cat_Luong_
  • Ngày bắt đầu Ngày bắt đầu
Trạng thái
Không mở để trả lời thêm.
anoldvozer1710.v2 đã nói:
Ngày xưa mình từng đọc ở đâu đó(hình như là vnoi), 1 hiền nhân đã tổng quát về tham lam bằng vài ý: :beauty:
  • Dễ nghĩ, dễ cài, chạy nhanh, nhưng chưa chắc đã đúng
  • Tính đúng đắn: Không chứng minh được cách tham lam là đúng thì đừng làm, mắc công sau thằng khác hỏi...
  • Nếu thực thi DP, Bạch Trạch như đi ô tô xe máy trên cao tốc thì thực thi tham lam không khác gì lính đang đi trên bãi mìn vì 1 bài có thể thực thi bằng rất nhiều cách tham lam, nhưng thường chỉ có 1 cách đúng thôi...
  • Tham lam không có cách thực thi tổng quát nào cả, mỗi bài 1 kiểu, làm nhiều thì khôn
  • 1 số dấu hiệu có thể là của bài toán tham lam:
  • Đề bài dài vl, trông có vẻ cực kì khó,
  • Đề bài dữ liệu cực kì lớn, lớn đến nỗi mà O(n^2) cũng fail, bỏ qua được mấy cách DP, Bạch Trạch đi
  • Khó quá đéo làm đc...:amazed:
Nhấp để mở rộng...
Nhiều bài DP làm đc bằng On nha chứ ko hẳn là gặp constrain lớn bỏ qua DP, nhưng mạnh dạn dự đoán cao nhân Kankute tổng quát hóa những mệnh đề này :sweat:

via theNEXTvoz for iPhone
 
anoldvozer1710.v2 đã nói:
Ngày xưa mình từng đọc ở đâu đó(hình như là vnoi), 1 hiền nhân đã tổng quát về tham lam bằng vài ý: :beauty:
  • Dễ nghĩ, dễ cài, chạy nhanh, nhưng chưa chắc đã đúng
  • Tính đúng đắn: Không chứng minh được cách tham lam là đúng thì đừng làm, mắc công sau thằng khác hỏi...
  • Nếu thực thi DP, Bạch Trạch như đi ô tô xe máy trên cao tốc thì thực thi tham lam không khác gì lính đang đi trên bãi mìn vì 1 bài có thể thực thi bằng rất nhiều cách tham lam, nhưng thường chỉ có 1 cách đúng thôi...
  • Tham lam không có cách thực thi tổng quát nào cả, mỗi bài 1 kiểu, làm nhiều thì khôn
  • 1 số dấu hiệu có thể là của bài toán tham lam:
  • Đề bài dài vl, trông có vẻ cực kì khó,
  • Đề bài dữ liệu cực kì lớn, lớn đến nỗi mà O(n^2) cũng fail, bỏ qua được mấy cách DP, Bạch Trạch đi
  • Khó quá đéo làm đc...:amazed:
Nhấp để mở rộng...
Có 1 điểm quan trọng nữa là mấy bài dùng tham lam thì thường sẽ có bước sort đầu tiên, hoặc kiểu sẽ dùng min/max heap, :ah:
 
freedom.9 đã nói:
Nhiều bài DP làm đc bằng On nha chứ ko hẳn là gặp constrain lớn bỏ qua DP, nhưng mạnh dạn dự đoán cao nhân Kankute tổng quát hóa những mệnh đề này :sweat:

via theNEXTvoz for iPhone
Nhấp để mở rộng...
seastar đã nói:
Có 1 điểm quan trọng nữa là mấy bài dùng tham lam thì thường sẽ có bước sort đầu tiên, hoặc kiểu sẽ dùng min/max heap, :ah:
Nhấp để mở rộng...
chung quy thấy thằng này khó vãi c. Thôi khó quá ko giải đc thì đổ cho DNA vậy :angry:
Xưa làm đc mấy bài Hard tham lam, cứ nghĩ mình đẳng cấp lắm, tố chất, iq cow các thứ. :beauty:
Đến lúc 1 thời gian sau ngọng liên tục là xuống đất ngay, kiểu gì mà đọc solution vẫn mơ hồ :too_sad:
 
Mấy bài tham lam khó thì nhét cả toán rồi, ai muốn nghĩ ra thì phải có cơ sở toán rồi nhìn ra được vấn đề tham lam luôn. Điển hình như bên codeforces mấy contest bên VN mình ra đề toàn là mấy ông nghĩ ra đề từ một bài toán khó sẵn, thành ra muốn giải thì cũng phải biết định lý toán học mà bài đấy được xây dựng lên :( .
 
Mã: 
class Solution {
public:
    int maximumSwap(int num) {
        string s=to_string(num);
        char cmax=s[s.length()-1],ind=s.length()-1,sw2=-1,sw1=s.length()-1;
        for(int i=s.length()-2;i>=0;i--){
            if(s[i]>cmax){
                cmax=s[i];
                ind=i;
            }
            else if(s[i]<cmax){
                sw1=i;
                sw2=ind;
            }
        }
        if(sw2!=-1) swap(s[sw1],s[sw2]);
        return stoi(s);
    }
};
 
Python: 
class Solution:
    def maximumSwap(self, num: int) -> int:
        a = list(str(num))
        q = []

        for i in range(len(a)):
            heapq.heappush(q, (-int(a[i]), -i ))
        
        for i in range(len(a)):

            if int(a[i]) < -q[0][0] and i < -q[0][1]:
                val, idx = heapq.heappop(q)
                a[i], a[-idx] = str(-val), a[i] 
                return int(''.join(a))
            while q and i >= -q[0][1]:
                heapq.heappop(q)
        return num

Python: 
class Solution:
    def maximumSwap(self, num: int) -> int:
        a = list(str(num))
        n = len(a)
        max_right = [0] * n
        max_right[-1] = n - 1
        for i in range(n - 2, -1, -1):
            if int(a[i]) > int(a[max_right[i + 1]]):
                max_right[i] = i
            else:
                max_right[i] = max_right[i + 1]
        for i in range(n):
            if int(a[i]) < int(a[max_right[i]]):
                a[i], a[max_right[i]] = a[max_right[i]] , a[i]
                return int(''.join(a))
        return num
 
Java: 
class Solution {
    public int maximumSwap(int num) {
        String temp = Integer.toString(num);
        int n = temp.length();
        int[] nums = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = temp.charAt(i) - '0';
        }
        int[] max_right = new int[n];
        max_right[n - 1] = nums[n - 1];

        for (int i = n - 2; i >= 0; i--) {
            max_right[i] = Math.max(max_right[i + 1], nums[i]);
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] < max_right[i]) {
                if (i + 1 >= n)
                    return num;

                for (int j = n-1; j > i; j--) {
                    if (nums[j] == max_right[i]) {
                        nums[i] = nums[i] + nums[j];
                        nums[j] = nums[i] - nums[j];
                        nums[i] = nums[i] - nums[j];
                        break;
                    }
                }
                break;
            }
        }
        int res = 0;
        for (int i : nums) {
            res = res * 10 + i;
        }
        return res;
    }
}
 
hoangi19 đã nói:
C++: 
class Solution {
public:
    int maximumSwap(int num) {
        string s = to_string(num);
        vector<char> max_num(s.size()+1);
        max_num[s.size()] = s.size()-1;

        for (int i = s.size() - 1; i >= 0; i--) {
            max_num[i] = i;
            if (s[i] <= s[max_num[i+1]]) {
                max_num[i] = max_num[i+1];
            }
        }

        for (int i = 0; i < s.size() - 1; i++) {
            if (s[i] < s[max_num[i+1]]) {
                swap(s[i], s[max_num[i+1]]);
                break;
            }
        }
       
        return stoi(s);
    }
};
Xem tệp đính kèm 2737883
Nhấp để mở rộng...
beats 100% trong lần submit đầu tiên, và chỉ cần one pass mới đáng để gáy nhé
1729133604861.png

C++: 
class Solution {
public:
    int maximumSwap(int num) {
        auto s = to_string(num);
        int l = 0, r1 = s.size() - 1, r2 = - 1;
        for (int i = s.size() - 1; i >= 0; --i) {
            if (s[i] > s[r1]) {
                r1 = i;
            }
            
            if (s[i] < s[r1]) {
                l = i;
                r2 = r1;
            }
        }
        
        if (r2 < 0) return num;
        swap(s[l], s[r2]);
        
        return stoi(s);
    }
};
 
Java: 
class Solution {
    public int maximumSwap(int num) {
        int n = String.valueOf(num).length();
        int[] nums = new int[n];
        int max = -1;
        int indexSwap = -1;
        for(int i = n - 1; i >= 0; i--) {
            nums[i] = num%10;
            num = num/10;
        }
        for(int i = 0; i < n; i++) {
            for(int j = n - 1; j > i; j--) {
                if(nums[i] < nums[j] && max < nums[j]) {
                    max = nums[j];
                    indexSwap = j;
                }
            }
            if(indexSwap != -1) {
                int temp = nums[i];
                nums[i] = nums[indexSwap];
                nums[indexSwap] = temp;
                break;
            }
        }
        return merge(nums);
    }
    public int merge(int[] nums) {
        int num = 0;
        for(int i = 0; i < nums.length; i++) {
            num = num*10 + nums[i];
        }
        return num;
    }
}
 
Python: 
class Solution:
    def make_num(d: list) -> int:
        n = 0
        for i, v in enumerate(d):
            n += v * (10 ** i)
        return n

    def maximumSwap(self, num: int) -> int:
        maxV = num
        d = []
        while num > 0:
            d.append(num % 10)
            num = num // 10
        for i in range(len(d)):
            for j in range(len(d)):
                p = d.copy()
                if i != j:
                    p[i], p[j] = p[j], p[i]
                    v = Solution.make_num(p)
                    print([i, j], d, p, "=", v)
                    maxV = max(maxV, v)
        return maxV
 
Java: 
class Solution {
    public int maximumSwap(int num) {
        String numStr = String.valueOf(num);
        int max = 0;
        StringBuilder ans = new StringBuilder();
        char[] chars = numStr.toCharArray();
        int[] arr = new int[chars.length];
        boolean swap = false;
        for (int i = 0; i < chars.length; i++) {
            arr[i] = Integer.valueOf(chars[i] - '0');
        }
        int j = 0;
        int k = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i - 1]) {
                j = i - 1;
                break;
            }
        }
        for (int i = j; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            if (arr[i] == max) k = i;
        }
        for (int i = 0; i <= j; i++) {
            if (swap) break;
            if (arr[i] < max) {
                int tmp = arr[i];
                arr[i] = max;
                arr[k] = tmp;
                swap = true;
            }
        }
        for (int i : arr) {
            ans.append(i);
        }
        return Integer.valueOf(ans.toString());
    }
}
3HNQQjb.png
 
JavaScript: 
var maximumSwap = function (num) {
    const n = String(num).split('').map(Number);
    for (let i = 0; i < n.length - 1; i++) {
        let k = null;
        for (let j = n.length - 1; j > i; j--) {
            if (n[j] > n[k ?? i]) {
                k = j;
            }
        }
        if (k) {
            [n[i], n[k]] = [n[k], n[i]];
            return Number(n.join(''));
        }
    }
    return num;
};
 
Python: 
class Solution:
    def maximumSwap(self, num: int) -> int:
        pq = []
        numStr = str(num)
        n = len(numStr)
        for index in range(n - 1, -1, -1):
            pq.append((int(numStr[index]), index))
        pq = sorted(pq, reverse=True)
        charArr = list(numStr)
        for index, char in enumerate(numStr):
            curNum = int(char)
            if curNum < pq[0][0]:
                # swap
                tmp = charArr[index]
                charArr[index] = charArr[pq[0][1]]
                charArr[pq[0][1]] = tmp
                break
            else:
                pq.remove((curNum, index))
        return int(''.join(charArr))
 
freedom.9 đã nói:
Sao thế bác, có biến gì à

via theNEXTvoz for iPhone
Nhấp để mở rộng...
Có tí vấn đề nên phải ở lại VN giải quyết các bác ạ, call cho bên airline nó cho move vé sang năm sau bù thêm bn % đó 🥹🥹🥹
Nhưng mà thấy ở lại cũng hợp lí, mình sang vì vợ rủ quá chứ không thì chưa định đi do search job quá hẻo 🫵🫵🫵
Phải cày thêm tech để đi apply chứ qua đó đứa đi học đứa ở nhà có mà ăn cám 🤭

via theNEXTvoz for iPhone
 
hungmessi2 đã nói:
Có tí vấn đề nên phải ở lại VN giải quyết các bác ạ, call cho bên airline nó cho move vé sang năm sau bù thêm bn % đó 🥹🥹🥹
Nhưng mà thấy ở lại cũng hợp lí, mình sang vì vợ rủ quá chứ không thì chưa định đi do search job quá hẻo 🫵🫵🫵
Phải cày thêm tech để đi apply chứ qua đó đứa đi học đứa ở nhà có mà ăn cám 🤭

via theNEXTvoz for iPhone
Nhấp để mở rộng...
Job market bên Can hẻo lắm, apply vài trăm cái CV may ra được cái interview
 
Mã: 
public class Solution {
    public string Swap(string str, int i, int j) {
        char[] charArray = str.ToCharArray();
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        
        return new string(charArray);
    }
    public int MaximumSwap(int num) {
        string str = num.ToString();
        int maxVal = num;

        for(int i = 0; i < str.Length -1; i++){
            for(int j = i +1; j < str.Length; j++) {
                str = Swap(str,i,j);
                maxVal = Math.Max(maxVal, int.Parse(str));
                str = Swap(str,i,j);
            }
        }

        return maxVal;
    }
}
 
hungmessi2 đã nói:
Đúng rồi fency, còn phải lựa bang dễ để có đường sau này kiếm PR
mà bang dễ thì là bang ko ai ở :))))
Nên công ty cũng ko có.
Thấy job remote nào cũng 300+ đơn 😗

via theNEXTvoz for iPhone
Nhấp để mở rộng...
Xưa mình cũng kiếm mà ko có, mình còn ko có Visa. Thôi ôn leetcode tiếp đi kiểu gì cũng có cơ hội, ko thì ngó qua Stockholm hay UK cũng ổn

via theNEXTvoz for iPhone
 
Java: 
class Solution {
    public int maximumSwap(int num) {
        String numStr = String.valueOf(num);

        for (int i = 0; i < numStr.length() - 1; i++) {
            char ch = numStr.charAt(i);
            char maxCh = findMaxDigit(numStr.substring(i + 1));

            if (maxCh > ch) {
                for (int j = numStr.length() - 1; j >= i; j--) {
                    if (numStr.charAt(j) == maxCh) {
                        String res = numStr.substring(0, i) + maxCh
                        + numStr.substring(i + 1, j) + ch + numStr.substring(j + 1);
                        return Integer.parseInt(res);
                    }
                }
            }
        }

        return num;
    }

    private char findMaxDigit(String str) {
        int max = 0;
        for (char ch : str.toCharArray()) {
            max = Math.max(max, ch);
        }

        return (char) max;
    }
}
 
Python: 
class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        maxXor = 0
        for num in nums:
            maxXor = maxXor | num
        
        n = len(nums)
        @lru_cache(None)
        def dp(i, currentXor):
            if i == n:
                return int(currentXor == maxXor)
            notTake = dp(i + 1, currentXor)
            take = dp(i + 1, currentXor | nums[i])
            return take + notTake
        return dp(0, 0)
 
Sửa lần cuối:
Trạng thái
Không mở để trả lời thêm.

Chủ đề tương tự

Thach Sanh Mat Riu
Điều gì xảy ra nếu bạn uống nước chè xanh mỗi ngày?
2
Trả lời
22
Lượt xem
1K
dattenmoi
D
megume
thảo luận Hôm nay, buổi bình minh của AI robot đã đến
Trả lời
4
Lượt xem
1K
Toc Hong
Toc Hong
Lộc Tục
(Dịch) Cuộc điều tra của CBC/Radio-Canada tiết lộ công ty Việt Nam nhắm vào người Canada bằng tin giả AI để kiếm lời
2
Trả lời
30
Lượt xem
5K
dukeng995
dukeng995
Ti Amo
[Dịch] Công ty Việt Nam dùng tin giả do AI tạo ra để kiếm tiền — nhắm vào độc giả Canada
Trả lời
0
Lượt xem
1K
Ti Amo
Ti Amo
Gấu Ted
Độc giả ngày càng tin nhà báo hơn thương hiệu báo chí
Trả lời
10
Lượt xem
862
giayasics
giayasics

Thống kê chủ đề

Ngày tạo
_Gia_Cat_Luong_,
Người trả lời cuối
Vipluckystar,
Trả lời
17.755
Lượt xem
1.213.602

Chia sẻ trang này

Quay lại
Lên đầu trang