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

freedom.9 · 6/11/24

Constrain cho hơi thấp

Python:

class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        ans = []
        @lru_cache(None)
        def countBit(num):
            count = 0
            while num > 0:
                count += 1
                num &= num-1

            return count

        current = [nums[0]]
        for i in range(1, len(nums)):
            if countBit(nums[i]) == countBit(nums[i - 1]):
                current.append(nums[i])
            else:
                ans += sorted(current)
                current = [nums[i]]
               
        ans += sorted(current)
        return ans == sorted(nums)

Python:

class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        ans = []
        @lru_cache(None)
        def countBit(num):
            count = 0
            while num > 0:
                count += 1
                num &= num-1

            return count

        preMax = -inf
        currentMin = nums[0]
        currentMax = nums[0]
        for i in range(1, len(nums)):
            if countBit(nums[i]) == countBit(nums[i - 1]):
                currentMax = max(nums[i], currentMax)
                currentMin = min(nums[i], currentMin)
            else:
                preMax = currentMax
                currentMin = nums[i]
                currentMax = nums[i]
            
            if currentMin < preMax:
                return False
            
        return True

thanbaiks · 6/11/24

JavaScript:

var canSortArray = function (nums) {
    const sorted = [...nums].sort((u, v) => u - v);
    const setbits = nums.map((u) => u.toString(2).replaceAll('0', '').length);
    const n = nums.length;
    for (let i = 0, j = 0; i < n; i++) {
        if (i === n - 1 || setbits[i] !== setbits[i + 1]) {
            if (nums.slice(j, i + 1).sort().toString() !== sorted.slice(j, i + 1).sort().toString()) {
                return false;
            }
            j = i + 1;
        }
    }
    return true;
};

Anh Thợ Săn · 6/11/24

C++:

inline int bitCount(int n) {
    int count = 0;
    while (n > 0) {
        if (n & 1)
            count++;
        n = n >> 1;
    }
    return count;
}
bool Solution::canSortArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> setbits(n, -1);
    for (int i = 0; i < n; ++i) {
        setbits[i] = bitCount(nums[i]);
        for (int j = 0; j < i; ++j) {
            if (nums[j] > nums[i] && setbits[j] != setbits[i])
                return false;
        }
    }
    return true;
}

LmaoSuVuong · 6/11/24

Java:

class Solution {
    public boolean canSortArray(int[] nums) {
        int n = nums.length;
        int[] num_bit= new int[257];
        int base =1;
        //O(2^8)
        num_bit[256]=1;
        for(int i = 1 ; i <= 8;i++){
            num_bit[base]=1;
            for(int j = 1 ;j <base;j++){
                num_bit[base+j] = num_bit[base]+num_bit[j];
            }
            base *=2;
        }
       
        for(int i =0 ;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(nums[i]>nums[j] && num_bit[nums[i]]!=num_bit[nums[j]]) return false;
            }
        }
        return true;
    }
}

Java:

class Solution {
    public boolean canSortArray(int[] nums) {
        int n = nums.length;
        int[] cnt_bit= new int[257];
        int base =1;
        //O(2^8)
        cnt_bit[256]=1;
        for(int i = 1 ; i <= 8;i++){
            cnt_bit[base]=1;
            for(int j = 1 ;j <base;j++){
                cnt_bit[base+j] = cnt_bit[base]+cnt_bit[j];
            }
            base *=2;
        }
        int max = nums[0];
        int last =0;
        for(int i =1 ;i<n;i++){
            if(cnt_bit[max]!= cnt_bit[nums[i]]){
                // if(nums[i]<max) return false;
                last =max;
            }
            max = Math.max(max, nums[i]);
            if(last>nums[i]) return false;
        }
        return true;
    }
}

LmaoSuVuong · 6/11/24

freedom.9 đã nói:

Constrain cho hơi thấp

Python:

class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        ans = []
        @lru_cache(None)
        def countBit(num):
            count = 0
            while num > 0:
                count += 1
                num &= num-1

            return count

        current = [nums[0]]
        for i in range(1, len(nums)):
            if countBit(nums[i]) == countBit(nums[i - 1]):
                current.append(nums[i])
            else:
                ans += sorted(current)
                current = [nums[i]]
              
        ans += sorted(current)
        return ans == sorted(nums)

Python:

class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        ans = []
        @lru_cache(None)
        def countBit(num):
            count = 0
            while num > 0:
                count += 1
                num &= num-1

            return count

        preMax = -inf
        currentMin = nums[0]
        currentMax = nums[0]
        for i in range(1, len(nums)):
            if countBit(nums[i]) == countBit(nums[i - 1]):
                currentMax = max(nums[i], currentMax)
                currentMin = min(nums[i], currentMin)
            else:
                preMax = currentMax
                currentMin = nums[i]
                currentMax = nums[i]
           
            if currentMin < preMax:
                return False
           
        return True

cái đoạn duyệt qua 1 lần nó có kỹ thuật có tên gì ko bác, ko thấy hướng tiếp cận

noobdev · 6/11/24

bài hôm nay mà giải O(n) là cũng khoai phết đấy :sweat:

noobdev · 6/11/24

LmaoSuVuong đã nói:
cái đoạn duyệt qua 1 lần nó có kỹ thuật có tên gì ko bác, ko thấy hướng tiếp cận

Hình như là sortable segments or segment sort gì đó.

noobdev · 6/11/24

freedom.9 đã nói:

Constrain cho hơi thấp

Python:

class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        ans = []
        @lru_cache(None)
        def countBit(num):
            count = 0
            while num > 0:
                count += 1
                num &= num-1

            return count

        current = [nums[0]]
        for i in range(1, len(nums)):
            if countBit(nums[i]) == countBit(nums[i - 1]):
                current.append(nums[i])
            else:
                ans += sorted(current)
                current = [nums[i]]
              
        ans += sorted(current)
        return ans == sorted(nums)

Python:

class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        ans = []
        @lru_cache(None)
        def countBit(num):
            count = 0
            while num > 0:
                count += 1
                num &= num-1

            return count

        preMax = -inf
        currentMin = nums[0]
        currentMax = nums[0]
        for i in range(1, len(nums)):
            if countBit(nums[i]) == countBit(nums[i - 1]):
                currentMax = max(nums[i], currentMax)
                currentMin = min(nums[i], currentMin)
            else:
                preMax = currentMax
                currentMin = nums[i]
                currentMax = nums[i]
           
            if currentMin < preMax:
                return False
           
        return True

Python có cái .bit_count() built-in đấy bác, từ 3.10 trở lên.

Phó GOAT · 6/11/24

Java:

class Solution {
    public boolean canSortArray(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] <= nums[j]) continue;
                if (Integer.bitCount(nums[i]) != Integer.bitCount(nums[j])) return false;
            }
        }
        return true;
    }
}

alone_wolf · 6/11/24

code này TC là nlogn hay là o(n) thế các bác :confused:

C++:

class Solution {
public:
    bool canSortArray(vector<int>& nums) {
        vector<int> counter(nums.size());
        for (int i = 0; i < nums.size(); i++)
            counter[i] = __builtin_popcount(nums[i]);
     
        int ma = -1;
        int i = 0;
        while (i < nums.size()) {
            int curmin = nums[i];
            int curmax = nums[i];
            int curBits = counter[i];

            while (i < nums.size() && counter[i] == curBits) {
                curmin = min(curmin, nums[i]);
                curmax = max(curmax, nums[i]);
                i++;
            }
         
            if (ma > curmin) return false;
            ma = curmax;
        }
     
        return true;
    }
};

freedom.9 · 6/11/24

LmaoSuVuong đã nói:
cái đoạn duyệt qua 1 lần nó có kỹ thuật có tên gì ko bác, ko thấy hướng tiếp cận

Ko fen, intuition thôi. Tất cả element của thằng segment sau nó phải lớn hơn max element của segment trước nên có thể code được chứ ko cần kĩ thuật gì

noobdev đã nói:
Python có cái .bit_count() built-in đấy bác, từ 3.10 trở lên.

À tự viết thể hiện skill thôi fen :doubt:

chứ mình ko thích xài built in

seastar · 6/11/24

freedom.9 đã nói:

Constrain cho hơi thấp

Python:

class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        ans = []
        @lru_cache(None)
        def countBit(num):
            count = 0
            while num > 0:
                count += 1
                num &= num-1

            return count

        current = [nums[0]]
        for i in range(1, len(nums)):
            if countBit(nums[i]) == countBit(nums[i - 1]):
                current.append(nums[i])
            else:
                ans += sorted(current)
                current = [nums[i]]
              
        ans += sorted(current)
        return ans == sorted(nums)

Python:

class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        ans = []
        @lru_cache(None)
        def countBit(num):
            count = 0
            while num > 0:
                count += 1
                num &= num-1

            return count

        preMax = -inf
        currentMin = nums[0]
        currentMax = nums[0]
        for i in range(1, len(nums)):
            if countBit(nums[i]) == countBit(nums[i - 1]):
                currentMax = max(nums[i], currentMax)
                currentMin = min(nums[i], currentMin)
            else:
                preMax = currentMax
                currentMin = nums[i]
                currentMax = nums[i]
           
            if currentMin < preMax:
                return False
           
        return True

lậm cache quá thím, thay vì tính luôn thì lưu vào cache, lần sau muốn access thì lại phải tính hash rồi so sánh các kiểu mới ra đc value, nhiều khi tính luôn nó nhanh hơn dùng cache luôn ấy.
Chưa kể có đk này:

1 <= nums.length <= 100
1 <= nums <= 2^8

thì t nghĩ cái cache k có hit rate cao đâu,

freedom.9 · 6/11/24

seastar đã nói:
lậm cache quá thím, thay vì tính luôn thì lưu vào cache, lần sau muốn access thì lại phải tính hash rồi so sánh các kiểu mới ra đc value, nhiều khi tính luôn nó nhanh hơn dùng cache luôn ấy.
Chưa kể có đk này:

1 <= nums.length <= 100

1 <= nums <= 2^8

thì t nghĩ cái cache k có hit rate cao đâu,

Thì mình kiểm tra mỗi index và index - 1 nên mỗi index nó bị hít vô 2 lần rồi còn gì fen, cache lại là khỏi phải tính lại dù ko đáng bao nhiêu, do làm contest hay bị TLE nên hay để ý phần cache này chứ bài này constrain thấp như muỗi mà giải On^3 cũng pass nữa

seastar · 6/11/24

freedom.9 đã nói:
À tự viết thể hiện skill thôi fen chứ mình ko thích xài built in

t review thằng nào tự viết những cái built in có sẵn là t sẽ bắt sửa lại. 1 bên là built-in đc viết bởi cộng đồng, có test, review đủ thứ, bao nhiêu người dùng, 1 bên là code do 1 ng viết, chưa chắc đã đc test kỹ, chưa nói thì cũng biết cái nào tín hơn rồi, :doubt:

freedom.9 · 6/11/24

seastar đã nói:
t review thằng nào tự viết những cái built in có sẵn là t sẽ bắt sửa lại. 1 bên là built-in đc viết bởi cộng đồng, có test, review đủ thứ, bao nhiêu người dùng, 1 bên là code do 1 ng viết, chưa chắc đã đc test kỹ, chưa nói thì cũng biết cái nào tín hơn rồi,

Đấy là code thực tế chứ code algorithm thì viết ra cho hiểu bản chất vấn đề chứ :doubt:

Nay Sao biển comeback để lên guardian à :doubt:

seastar · 6/11/24

freedom.9 đã nói:
Thì mình kiểm tra mỗi index và index - 1 nên mỗi index nó bị hít vô 2 lần rồi còn gì fen, cache lại là khỏi phải tính lại dù ko đáng bao nhiêu, do làm contest hay bị TLE nên hay để ý phần cache này chứ bài này constrain thấp như muỗi mà giải On^3 cũng pass nữa

nếu chỉ vậy thì dùng 1 biến lưu lại cái count bit của element phía trước là đc mà, cần gì làm phức tạp thế, :beat_brick:

nghia_tran_tuan · 6/11/24

Mã:

func canSortArray(nums []int) bool {
    sort.SliceStable(nums, func(i, j int) bool {
        return bits.OnesCount(uint(nums[i])) == bits.OnesCount(uint(nums[j])) && nums[i] < nums[j]
    })
    return slices.IsSorted(nums)
}

seastar · 6/11/24

freedom.9 đã nói:
Đấy là code thực tế chứ code algorithm thì viết ra cho hiểu bản chất vấn đề chứ
Nay Sao biển comeback để lên guardian à

k, biết mình có cố cũng k đc nên tốt nhất là k cố. Già rồi nên phải chọn cái nào đấm đc mới đấm, :doubt:

freedom.9 · 6/11/24

seastar đã nói:
nếu chỉ vậy thì dùng 1 biến lưu lại cái count bit của element phía trước là đc mà, cần gì làm phức tạp thế,

Ví dụ 2 2 5 7 2 thì thằng 2 cuối cùng nó cũng bị hit lại 1 phát còn gì :canny:

cache lại đổi qua ít memory nhưng mà nhanh hơn được tí :shame:

via theNEXTvoz for iPhone

Dreamwalker · 6/11/24

C-like:

impl Solution {
    pub fn can_sort_array(nums: Vec<i32>) -> bool {
        for i in 0..nums.len() {
            for j in (i + 1)..nums.len() {
                if nums[i] > nums[j] && nums[i].count_ones() != nums[j].count_ones() {
                    return false;
                }
            }
        }

        true
    }
}

2 for mà còn 100% runtime với memory. :after_boom:

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

Senior Member

Senior Member

Member

Senior Member

Senior Member

Member

Member

Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Member

Senior Member

Member

Senior Member

Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này