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.
freedom.9 đã nói:
Mấy thằng Can lỏ cùi bắp có tí Hacker rank cũng ko làm đc
zFNuZTA.gif
chúc mừng fen phát cạc thôi.
Lướt xuống thì thấy Hàn, có owp Can ko đi Can đi Hàn làm gì
BdgiW7R.gif


via theNEXTvoz for iPhone
Nhấp để mở rộng...
Đi Can trục trặc anh phi dom à, như mình nói ở trên thì giờ có cơ hội đc đi là đi thôi chứ ko phân biệt nữa, Can thì để có thêm tí kn rồi start lại :sweat::sweat::sweat:

via theNEXTvoz for iPhone
 
Java: 
class Solution {
    public int[] decrypt(int[] code, int k) {
        int n = code.length;
        int[] sum = new int[n];

        if (k == 0) {
            Arrays.fill(sum, 0);
            return sum;
        }

        int curSum = 0;
        for (int i = 0; i < Math.abs(k); i++) {
            curSum += code[i];
        }

        int direction = -1;
        int start = -1;
        if (k > 0) {
            start = n - 1;
            direction = 1;
        } else {
            start = Math.abs(k);
            direction = -1;
        }
        sum[start] = curSum;

        for (int i = 1; i < n; i++) {
            start = (n + start + direction) % n;
            curSum -= code[start];
            curSum += code[ (2 * n + start + k) % n];
            sum[start] = curSum;
        }

        return sum;
    }
}
kElKEVl.gif
kElKEVl.gif
giờ mới làm xong, các bác ngủ ngon
 
aNotHeRNo0b đã nói:
Mã: 
class Solution {
    public int[] sortArray(int[] nums) {
        Stack<Integer> stk = new Stack<>();
        for (int num : nums) {
            stk.add(num);
        }
        for (int i = 0; i < nums.length; i++) {
            sortStack(stk);
        }

        for (int i = nums.length - 1; i >= 0; i--) {
            nums[i] = stk.pop();
        }

        return nums;
    }

    public void sortStack(Stack<Integer> stk) {
        if (stk.isEmpty()) return;

        int top = stk.pop();
        if (!stk.isEmpty() && top < stk.peek()) {
            int temp = stk.pop();
            stk.add(top);
            top = temp;
        }

        sortStack(stk);

        stk.add(top);
    }
}
Em có vể thử thì được bác ạ, chỉ là bị TLE do độ phức tạp cao ấy bác
Nhấp để mở rộng...
Lần trước thấy cách quái dị này nó như là BubbleSort, cài lại thì thấy nó đúng là BubbleSort thật.

Trong cài đặt BubbleSort truyền thống thì cứ swap hai phần tử cạnh nhau, cứ thế tiến lên đến cuối array. Cách dùng stack thì nó cũng vậy, chỉ khác là tiến lên thì nó gọi đệ quy nên mặc dù độ phức tạp vẫn là O(n^2) nhưng rất chậm.

Cài đặt thử lại với F#, mấy ngôn ngữ functional gốc SML này nó có kiểu dữ liệu list rất giống stack, chỉ khác là stack thì lấy và thêm dữ liệu ở cuối, còn list thì lấy và thêm dữ liệu ở đầu.

Đây là cách cài đặt với F# dùng y nguyên cách với Java:

Mã: 
let sortStack list =
    let rec sort stack =
        match stack with
        | x :: y :: substack when x > y -> y :: sort (x :: substack)
        | x :: substack -> x :: sort substack
        | _ -> stack

    List.fold (fun st _ -> sort st) list list

Đổi phiên bản đệ quy này thành phiên bản đệ quy tail recursive thì nhanh hơn được môt chút:

Mã: 
let ssortStack list =
    let rec sort stack sorted =
        match stack with
        | x :: y :: substack when x < y -> sort (x :: substack) (y :: sorted)
        | x :: substack -> sort substack (x :: sorted)
        | _ -> sorted

    List.fold (fun st _ -> sort st List.empty) list list

Để có khái niệm là nó chậm cỡ nào thì thử sort một list 10.000 phần tử, cách cài sortStack mất đến hơn 22s, cách tail recursive nhanh hơn gấp đôi (mất hơn 10s), còn nếu dùng trực tiếp hàm sort thì mất dưới 1s.

1731959173880.png
 
Sửa lần cuối:
vl cái history của bài hôm nay, xưa ngu thật :beat_brick: mà mới submit thử thấy xài C# chạy nhanh hơn Python gấp 10 lần cơ à
Python: 
class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        left = 0
        n = len(nums)
        sumSofar = 0
        count = defaultdict(int)
        ans = 0
        for right in range(n):
            sumSofar += nums[right]
            count[nums[right]] += 1
            if right >= k - 1:
                if len(count) == k:
                    ans = max(ans, sumSofar)

                sumSofar -= nums[left]
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    count.pop(nums[left])
                
                left += 1

        return ans
1731975291019.png
 
Sửa lần cuối:
Bài thấy cũng ko khó khăn lắm :nosebleed: thấy có check duplicate thì có Set là đc
JavaScript: 
function maximumSubarraySum(nums: number[], k: number): number {
    let res = 0, cur = 0, l = 0;
    const set = new Set<number>();
    for (let r = 0; r < nums.length; r++) {
        cur += nums[r];
        while (set.has(nums[r]) || set.size >= k) {
            cur -= nums[l];
            set.delete(nums[l]);
            l++;
        }
        set.add(nums[r]);
        if (set.size === k) {
            res = Math.max(res, cur);
        }
    }

    return res;
};
 
Java: 
class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        long max = 0;
        long slide = 0;

        int fraud = 0;
        Integer t;

        for (int i = 0; i < k; i++) {
            t = map.get(nums[i]);
            if (t == null) {
                map.put(nums[i], 1);
            }
            else {
                if (t == 1)
                    fraud++;

                map.put(nums[i], t + 1);
            }

            slide += nums[i];
        }

        if (fraud == 0)
            max = slide;

        for (int i = k; i < nums.length; i++) {
            t = map.get(nums[i - k]);
            map.put(nums[i - k], t - 1);
            if (t == 2)
                fraud--;

            t = map.get(nums[i]);
            if (t == null) {
                map.put(nums[i], 1);
            }
            else {
                if (t == 1)
                    fraud++;

                map.put(nums[i], t + 1);
            }

            slide -= nums[i - k];
            slide += nums[i];

            if (fraud == 0)
                max = Math.max(max, slide);
        }

        return max;
    }
}
 
Python: 
class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        result = 0
        n, total, currentSubSet = len(nums), sum(nums[:k-1]), defaultdict(int)

        for i in range(k-1):
            currentSubSet[nums[i]] += 1

        for i in range(k-1, n):
            total += nums[i]
            currentSubSet[nums[i]] += 1
            if len(currentSubSet) == k:
                result = max(result, total)
            target = nums[i - k + 1]
            total -= target
            currentSubSet[target] -= 1
            if currentSubSet[target] == 0:
                del currentSubSet[target]
        return result
 
bài hôm nay AC thấp v ta. nhìn vào chắc ai cũng biết giải r. chắc ăn bọ chỗ return long
Java: 
class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        int n = nums.length;
        Map<Integer,Integer> freq = new HashMap<>();
        long cur_sum = 0;
        int l =0;
        long res =0;
        for(int i =0;i<n;i++ ){
            cur_sum+=nums[i];
            freq.put(nums[i],freq.getOrDefault(nums[i],0)+1);
            while(i-l>=k || freq.get(nums[i])>1){
                freq.put(nums[l],freq.get(nums[l])-1);
                if(freq.get(nums[l])==0) freq.remove(nums[l]);
                cur_sum-=nums[l];
                l++;
            }
            if(freq.size()==k) res =Math.max(res, cur_sum);
        }
        return res;
    }
}
 
Mắt Xích Yếu đã nói:
bài hôm nay AC thấp v ta. nhìn vào chắc ai cũng biết giải r. chắc ăn bọ chỗ return long
Java: 
class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        int n = nums.length;
        Map<Integer,Integer> freq = new HashMap<>();
        long cur_sum = 0;
        int l =0;
        long res =0;
        for(int i =0;i<n;i++ ){
            cur_sum+=nums[i];
            freq.put(nums[i],freq.getOrDefault(nums[i],0)+1);
            while(i-l>=k || freq.get(nums[i])>1){
                freq.put(nums[l],freq.get(nums[l])-1);
                if(freq.get(nums[l])==0) freq.remove(nums[l]);
                cur_sum-=nums[l];
                l++;
            }
            if(freq.size()==k) res =Math.max(res, cur_sum);
        }
        return res;
    }
}
Nhấp để mở rộng...
dính 1 bọ edge case :beat_brick:
 
JavaScript: 
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumSubarraySum = function (nums, k) {
    const n = nums.length, m = new Map();
    let ans = 0, s = 0, dupes = 0;
    for (let i = 0; i < n; i++) {
        {
            const v = nums[i], c = (m.get(v) ?? 0) + 1;
            m.set(v, c);
            s += v;
            dupes += c >= 2 ? 1 : 0;
        }
        if (i >= k) {
            const v = nums[i - k], c = m.get(v) - 1;
            m.set(v, c);
            s -= v;
            dupes -= c >= 1 ? 1 : 0;
        }
        if (i >= k - 1 && !dupes) {
            ans = Math.max(ans, s);
        }
    }
    return ans;
};
 
Python: 
class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        hm = {}
        max_sub = 0
        temp_sum = 0
        start = 0
        for end in range(len(nums)):
            while hm.get(nums[end]):
                hm[nums[start]] = False
                temp_sum -= nums[start]
                start += 1
                

            hm[nums[end]] = True
            temp_sum += nums[end]
            if (end - start + 1) == k:
                max_sub = max(max_sub, temp_sum)
                temp_sum -= nums[start]
                hm[nums[start]] = False
                start += 1

        return max_sub
 
Java: 
class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long max = 0, sum = 0;
        int l = 0, r = 0;
        Set<Integer> set = new HashSet<>();
        while (r < n) {
            while (set.contains(nums[r]) || r - l + 1 > k) {
                sum -= nums[l];
                set.remove(nums[l]);
                l++;
            }
            sum += nums[r];
            set.add(nums[r]);
            if (r - l + 1 == k) max = Math.max(max, sum);
            r++;
        }
        return max;
    }

}
 
Sửa lần cuối:
freedom.9 đã nói:
vl cái history của bài hôm nay, xưa ngu thật :beat_brick: mà mới submit thử thấy xài C# chạy nhanh hơn Python gấp 10 lần cơ à
Python: 
class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        left = 0
        n = len(nums)
        sumSofar = 0
        count = defaultdict(int)
        ans = 0
        for right in range(n):
            sumSofar += nums[right]
            count[nums[right]] += 1
            if right >= k - 1:
                if len(count) == k:
                    ans = max(ans, sumSofar)

                sumSofar -= nums[left]
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    count.pop(nums[left])
               
                left += 1

        return ans
Xem tệp đính kèm 2789133
Nhấp để mở rộng...
hơn 1 năm r nhìn lại thì chỉ thấy già thêm 1 tuổi :shame: -1 nhà hiền triết đã nói-
 
Swift: 
class Solution {
    func maximumSubarraySum(_ nums: [Int], _ k: Int) -> Int {
        var result = 0
        let k1 = k-1
        var dict:[Int:Int] = [:]
        var curSum = 0
        for (index, num) in nums.enumerated() {
            dict[num, default:0] += 1
            curSum += num
            if index >= k1 {
                if index >= k {
                    let preNum = nums[index-k]
                    if dict[preNum]! <= 1 {
                        dict[preNum] = nil
                    } else {
                        dict[preNum, default:0] -= 1
                    }
                    curSum -= preNum
                }
                if dict.count == k {
                    result = max(result, curSum)
                }
            }
        }
        return result
    }
}
 
PHP: 
class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        visited = set()
        res = 0
        curr = 0
        j = 0

        for i, num in enumerate(nums):
            while num in visited or i - j + 1 > k:
                visited.remove(nums[j])
                curr -= nums[j]
                j += 1
          
            curr += num
            visited.add(num)
              
            if i - j + 1 == k:
                res = max(res, curr)
          
        return res
 
Sửa lần cuối:
ăn 1 bọ vì trả về kiểu int :what:

C#: 
public class Solution
{
    public long MaximumSubarraySum(int[] nums, int k)
    {
        var queue = new Queue<int>();
        var set = new HashSet<int>();
        long sum = 0;
        for (int i = 0; i < k; i++)
        {
            sum += nums[i];
            if (!set.Add(nums[i]))
            {
                queue.Enqueue(nums[i]);
            }
        }

        long res = 0;
        if (set.Count == k)
        {
            res = sum;
        }

        for (int i = 1; i <= nums.Length - k; i++)
        {
            if (queue.TryPeek(out var peek) && peek == nums[i - 1])
            {
                queue.Dequeue();
            }
            else
            {
                set.Remove(nums[i - 1]);
            }

            sum += nums[i + k - 1] - nums[i - 1];
            if (!set.Add(nums[i + k - 1]))
            {
                queue.Enqueue(nums[i + k - 1]);
            }

            if (set.Count == k) res = Math.Max(sum, res);
        }

        return res;
    }
}
 
freedom.9 đã nói:
vl cái history của bài hôm nay, xưa ngu thật :beat_brick: mà mới submit thử thấy xài C# chạy nhanh hơn Python gấp 10 lần cơ à
Python: 
class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        left = 0
        n = len(nums)
        sumSofar = 0
        count = defaultdict(int)
        ans = 0
        for right in range(n):
            sumSofar += nums[right]
            count[nums[right]] += 1
            if right >= k - 1:
                if len(count) == k:
                    ans = max(ans, sumSofar)

                sumSofar -= nums[left]
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    count.pop(nums[left])
               
                left += 1

        return ans
Xem tệp đính kèm 2789133
Nhấp để mở rộng...
nhanh hơn nhiều ấy bác :) :) :)
1731998630152.png
 
freedom.9 đã nói:
vl cái history của bài hôm nay, xưa ngu thật :beat_brick: mà mới submit thử thấy xài C# chạy nhanh hơn Python gấp 10 lần cơ à
Python: 
class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        left = 0
        n = len(nums)
        sumSofar = 0
        count = defaultdict(int)
        ans = 0
        for right in range(n):
            sumSofar += nums[right]
            count[nums[right]] += 1
            if right >= k - 1:
                if len(count) == k:
                    ans = max(ans, sumSofar)

                sumSofar -= nums[left]
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    count.pop(nums[left])
               
                left += 1

        return ans
Xem tệp đính kèm 2789133
Nhấp để mở rộng...
python cái time nó cũng ko stable nữa, mỗi lần chạy 1 time khác nhau luôn :sad:
 
Trạng thái
Không mở để trả lời thêm.
AD · 970×250

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
2K
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
918
giayasics
giayasics
AD · 300×600

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.215.683
AD · 300×600

Chia sẻ trang này

AD · 300×600
Quay lại
Lên đầu trang