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

Người quan sát cô đơn said:
Java: 
    public static int numberOfSubarrays(int[] nums, int k) {
        int count,res;
        int i;
        int first = curr = 0;
        int iRight = 1;
        int curr = 0;
        curLeft = curRight =count = res= 0;
        int[] left = new int[nums.length+1];
        int[] right = new int[nums.length+1];
        for(i=0; i<nums.length;i++){
            if(nums[i]%2==1){
                count++;
                if(count == 1)
                    first = i;
                left[count] = i-curr;
                curr = i;
            }
            if(count==k) {
                break;
            }
        }
        if(first ==0) left[1] = 1;
        else left[1]++;
        if(count!=k) return 0;
        i++;
        Arrays.fill(right, 1);
        for(int j =i; j<nums.length;j++){
            if(nums[j]%2==0) right[iRight]++;
            else {
                res+= left[iRight]*right[iRight];
                left[k+iRight]=right[iRight];
                iRight++;
            }
          }
        res+= left[iRight]*right[iRight];
        return res;
}
Nhận ra dùng array code hơi nhọc tí nhưng chạy phải nhanh gấp đôi so với hashmap :adore:
Click to expand...
Người quan sát cô đơn said:
ừ thì access time đều là O(1) cả mà dùng array bao giờ cũng nhanh hơn đhs. :amazed:
Click to expand...
cùng là O(1) nhưng là access phần tử trong array chỉ tốn 1 phép tính
access trong hash map phải đi qua các bước hash, compare, check này nọ 5-6 phép tính vẫn là O(1), gọi n lần thì chậm hơn đúng r fen,
gnnOU6Q.png
mà dùng array nhanh nhưng tốn space dư thừa nhiều hơn hashmap. giải = hash map cũng ko saođâu beat 100% các thứ cũng ko quan trọng lắm
 
seastar said:
Trước t có đi vật nhau với 1 thằng interviewer về vụ này rồi. Đâu phải cứ độ phức tạp nhỏ hơn thì sẽ chạy nhanh hơn trong mọi trường hợp đâu ae. :ah:
Click to expand...
Ừ thì nó còn phụ thuộc vào testcase nữa. Thế nên mới có trường hợp best-case với worst-case mà. Cái này ai học DSA ở trường chả đc ông thầy nói suốt :haha:
 
seastar said:
Nếu vậy thì bản chất của độ phức tạp là gì? Nó nói lên điều gì?
Click to expand...
Bản chất độ phức tạp là số phép toán tích cực để giải bài toán. Cái nó nói chắc là ước lượng diễn biến thời gian chạy của bài toàn nếu testcase là trung hoà. Giống tính lim hồi cấp 3 ấy. Phép toàn 10000/x^2 có thể lớn hơn 1/x trong vài trường hợp nhưng nếu x đủ lớn thì 1/x sẽ lớn hơn.
 
anoldvozer1710.v2 said:
chết gì pa
osCpCsi.png

hashmap dùng cả array và linkedlist, balanced tree nữa mà cũng coi là chung bản chất với array thuần nữa hả
1BW9Wj4.png
Click to expand...
Hashmap không dùng array, nó là array mà, còn linkedlist cũng chỉ là một node thôi nên hashmap cơ bản cũng chỉ là Node[] thôi chứ gì nữa. Thì fen @Ung Thư Gan nói tụi nó chung bản chất đâu có sai đâu :D
 
Người quan sát cô đơn said:
Bản chất độ phức tạp là số phép toán tích cực để giải bài toán. Cái nó nói chắc là ước lượng diễn biến thời gian chạy của bài toàn nếu testcase là trung hoà. Giống tính lim hồi cấp 3 ấy. Phép toàn 10000/x^2 có thể lớn hơn 1/x trong vài trường hợp nhưng nếu x đủ lớn thì 1/x sẽ lớn hơn.
Click to expand...
Vậy nếu có 1 lời giải x cho 1 bài toán y là O(1) chẳng hạn thì ước lượng thời gian chạy như thế nào?
 
seastar said:
K, thằng đó trình còi quá, k cùng hạng cân nên k có đấm nhau với nó làm gì. Vật xíu thấy nó nhầm lẫn mấy cái cơ bản nên thôi.
Click to expand...
Mấy cty VN ngại pv mấy cái này cũng có lí do là sợ bị candidate vật lại lắm. Vì hầu hết cty ở VN các coder đang làm cho cty cũng ko giỏi algorithm nhỉ.
Chắc có mấy Tier1 của cty VN thì may ra
 
Người quan sát cô đơn said:
Thì ta biết lời giải O(1) sẽ nhanh hơn O(n) trong hầu hết các trường hợp.
Click to expand...
Nghe có vẻ hợp lý như thực ra lại sai về bản chất. Rất nhiều người bị nhầm lẫn như vậy.
Giờ giả sử có 2 lời giải cho bài toán đơn giản như sau:
O(n)
Python: 
def is_even(n):
    i = 0
    while i < n:
        i += 2
    return i == n
O(1)
Python: 
def is_even(n):
    # Sleep for one day
    time.sleep(86400)
    return n%2 == 0

Rồi cái O(1) sẽ luôn nhanh hơn cái O(n) trong hầu hết các trường hợp đúng k?
p/s: Code đưa ra chỉ để làm ví dụ, đừng bàn đến tính hợp lý hay k của nó
 

Similar threads

Duy1122
thảo luận [Database] Hiệu Suất Phân Trang Xâu Trong SQL Database
Replies
6
Views
614
heocon0123
heocon0123
domino123
kiến thức PixelTap by Pixelverse
Replies
0
Views
155
domino123
domino123
T
thảo luận PIXELVERSE kèo hot đào trên tele dự kiến list b
Replies
16
Views
424
truonggiang!
T
@_shin
kiến thức PIXELVERSE kèo hot - inbox tele để lấy extension chạy auto đánh boss
Replies
0
Views
127
@_shin
@_shin
D
kiến thức Lộ trình tự học phát triển Website Fullstack - Fullstack Web Development
2
Replies
25
Views
2K
Kieft
Kieft

Share this page

Back
Top