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

Bleach & Sarcasm · 7/8/23

C++:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        vector<int> ft;
        int n = matrix.size();
        for(int i = 0; i < n; i++){
            ft.push_back(matrix[i][0]);
        }
        int id = upper_bound(ft.begin(),ft.end(),target) - ft.begin() - 1;
        if (id < 0 || id >= n) return false;
        auto pt = lower_bound(matrix[id].begin(),matrix[id].end(),target);
        if (pt == matrix[id].end()) return false;
        return *pt == target;
    }
};

C++:

        for(int i = 0; i < n; i++){
            ft.push_back(matrix[i][0]);
        }

cái lày là O(m) với m là số dòng rồi rồi đâu phải O(log(mn))

Aristides · 8/8/23

Binary search mà tán

Bài nghe phức tạp chứ giờ concatenate cái matrix thành cái mảng 1d là hiểu vấn đề liền

O(log(m*n)) chả qua cái m * n = số phần tử trong matrix

Violet_7 · 8/8/23

Python:

class Solution:
    def search(self, nums: List[int], target: int) -> int:       
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = (right + left) // 2

            if nums[mid] == target:
                return mid
            
            # target and nums[mid] is different side
            elif nums[mid] <= nums[-1] < target:
                right = mid - 1
            elif nums[mid] >= nums[0] > target:
                left = mid + 1
            
            # target and nums[mid] is same side
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

thanbaiks · 8/8/23

JavaScript:

var search = function(nums, target) {
  let l = 0, r = nums.length, m;

  while (l < r) {
    m = (l + r) >> 1;
    if (nums[m] === target) {
      return m;
    }
    if (nums[l] < nums[r]) {
      if (nums[m] > target) {
        r = m;
      } else {
        l = m + 1;
      }
    } else {
      if (nums[l] < nums[m]) {
        if (target < nums[m] && target >= nums[l]) {
          r = m;
        } else {
          l = m + 1;
        }
      } else {
        if (target > nums[m] && target <= nums[r - 1]) {
          l = m + 1;
        } else {
          r = m;
        }
      }
    }
  }
  
  return -1;
};

afatnan · 8/8/23

C-like:

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        fn binary_search_min_index(nums: &Vec<i32>, mut lo: usize, mut hi: usize) ->usize {
            while lo < hi {
                let mid = (lo + hi) / 2;
                if nums[mid] >= nums[lo] && nums[mid] > nums[hi] {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            return hi;
        }
        fn binary_search(nums: &Vec<i32>, mut lo: usize, mut hi: usize, target: i32) -> i32 {
            while lo <= hi {
                let mid = (lo + hi) / 2;
                if nums[mid] == target {
                    return mid as i32;
                }
                if target < nums[mid] {
                    if mid == 0 {
                        return -1;
                    }
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }
            return -1;
        }
        let n = nums.len();
        let p = binary_search_min_index(&nums, 0, n - 1);
        if target >= nums[0] && p != 0 {
            return binary_search(&nums, 0, p - 1, target);
        }
        return binary_search(&nums, p, n - 1, target);
    }
}

hoangminh.pianist · 8/8/23

Luyện lại thuật toán, newbie xin tham gia cùng các cao thủ ở đây ạ

Mã:

func search(nums []int, target int) int {
    left := 0
    right := len(nums) - 1

    for left <= right {
        mid := (left + right) / 2
        if nums[mid] == target {
            return mid
        } else if nums[mid] >= nums[left] { // Left subarray nums[left ~ mid] is sorted
            if target >= nums[left] && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else { // Right subarray nums[left ~ mid] is sorted
            if target > nums[mid] && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }

    return -1
}

hungmessi2 · 8/8/23

Mã:

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int mid = l + (r - l)/2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] <= nums[nums.length - 1] && nums[nums.length - 1] < target){
                r = mid - 1;
            } else if(nums[mid] >= nums[0] && nums[0] > target){
                l = mid + 1;
            } else if(nums[mid] < target){
                l = mid + 1;
            } else r = mid - 1;
        }
        return -1;
    }
}

TLE_WA · 8/8/23

Bleach & Sarcasm đã nói:
C++:

for(int i = 0; i < n; i++){ ft.push_back(matrix[i][0]); }

cái lày là O(m) với m là số dòng rồi rồi đâu phải O(log(mn))

Cảm ơn anh đã nhắc :cry:

anoldvozer1710.v2 · 8/8/23

JavaScript:

function search(nums: number[], target: number): number {
    const bs = (l: number, r: number) => {
        while (l <= r) {
            const m = (l + r) >> 1;
            if (nums[m] === target) return m;
            else if (nums[m] > target) r = m - 1;
            else l = m + 1;
        }
        return -1;
    }
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        const m = (left + right) >> 1;
        if (nums[m] > nums[nums.length -1]) left = m + 1;
        else right = m - 1
    }
    const findLeft = bs(0, left);
    if (findLeft > -1) return findLeft;
    else return bs(left, nums.length - 1)
};

Bleach & Sarcasm · 8/8/23

cưỡng ép xài STL

ko có mid+1 mid-1 gì hết

C++:

template <class RandomIter>
static int searchRotated(RandomIter first, RandomIter last, int target) {
    if (distance(first, last) == 0) return -1;
    RandomIter mid = first + distance(first, last) / 2;
    if (*first < *mid) {
        if (*first <= target && target < *mid) {
            if (auto it = lower_bound(first, mid, target); it != mid && *it == target)
                return distance(first, it);
        } else if (int searchRight = searchRotated(mid, last, target); searchRight != -1) {
            return distance(first, mid) + searchRight;
        }
    } else {
        if (*mid <= target && target <= last[-1]) {
            if (auto it = lower_bound(mid, last, target); it != last && *it == target)
                return distance(first, it);
        } else {
            return searchRotated(first, mid, target);
        }
    }
    return -1;
}

struct Solution {
    int search(vector<int>& nums, int target) {
        return searchRotated(begin(nums), end(nums), target);
    }
};

anoldvozer1710.v2 · 9/8/23

Lại là Binary Search, nhưng khó hơn ở chỗ điều kiện greedy, bài này tính ra cũng khoai :canny:

JavaScript:

function minimizeMax(nums: number[], p: number): number {
    nums.sort((a, b) => a - b);
     let n = nums.length, l = 0, r = nums[n - 1] - nums[0];
        while (l < r) {
            let m = (l + r) >> 1, k = 0;
            for (let i = 1; i < n && k < p; i++) {
                if (nums[i] - nums[i - 1] <= m) {
                    k++;
                    i++;
                }
            }
            if (k >= p)
                r = m;
            else
                l = m + 1;
        }
        return l;
};

afatnan · 9/8/23

Luc dau minh dung cai Recursion + BS, nhung bi TLE, nhin lai moi thay
1 + solve(i + 2, threshold) >= solve(i + 1, threshold) vi num[i...] luon nhieu phan tu hon num[i+1..] nen so cap (pairs) se khong it hon duoc.

C++:

class Solution {
public:
    int minimizeMax(vector<int>& nums, int p) {
        sort(begin(nums), end(nums));
        int n = nums.size();
        // return number of pairs given a difference threshold
        function<int(int, int)> solve = [&](int i, int threshold) -> int {
            if (i >= n) return 0;
            if (i + 1 < n && nums[i + 1] - nums[i] <= threshold)
                return 1 + solve(i + 2, threshold); // include
            return solve(i + 1, threshold); // not include
        };
        int lo = 0, hi = nums.back() - nums[0];
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (solve(0, mid) >= p)
                hi = mid;
            else
                lo = mid + 1;
        }
        return hi;
    }
};

thanbaiks · 9/8/23

JavaScript:

var minimizeMax = function(nums, p) {
    nums.sort((u, v) => u - v);
    console.log(nums)
    const go = max => {
        let res = 0, last = null;
        for (const n of nums) {
            if (last !== null && n - last <= max) {
                res++;
                last = null;
            } else {
                last = n;
            }
        }
        return res;
    };
    let l = 0, r = 1e9 + 5;
    while (l < r) {
        const m = Math.trunc((l + r) / 2);
        if (go(m) >= p) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    return l;
};

anoldvozer1710.v2 · 10/8/23

lại là BS, mà tưởng nó giống bài hôm trước, sửa lại tí rồi return boolean luôn, fail sml :big_smile:

hóa ra nhìn lại mới nhìn thấy nó có điều kiện có thể duplicate

JavaScript:

function search(nums: number[], target: number): boolean {
    let l = 0, r = nums.length - 1;
    while (l <= r) {
        const m = (l + r) >> 1;
        if (nums[m] === target) return true;
        if (nums[l] === nums[m] && nums[r] === nums[m]) l++, r--;
        else if (nums[l] <= nums[m]) {
            if (nums[l] <= target && nums[m] > target) r = m - 1;
            else l = m + 1;
        }
        else {
            if (nums[m] < target && nums[r] >= target) l = m + 1;
            else r = m - 1;
        }
    }
    return false;
};

Kiếp sống đầu · 10/8/23

tuần này BS nhiều thế nhỉ, ai biết BS thì là easy chứ ko phải medium nữa.

Python:

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        return target in nums

0beronkt · 10/8/23

Em vào một số bài của Leetcode thì màn hình trắng trơn là bị sao vậy các bác @@

hungmessi2 · 10/8/23

Kiếp sống đầu đã nói:
tuần này BS nhiều thế nhỉ, ai biết BS thì là easy chứ ko phải medium nữa.

Python:

class Solution: def search(self, nums: List[int], target: int) -> bool: return target in nums

vkl python code ảo chó thế :')

midnight_sun · 10/8/23

hungmessi2 đã nói:
vkl python code ảo chó thế :')

bài này dùng mấy hàm check element trong array pass full mà

khéo linear search cx pass

Kiếp sống đầu · 10/8/23

anoldvozer1710.v2 đã nói:
lại là BS, mà tưởng nó giống bài hôm trước, sửa lại tí rồi return boolean luôn, fail sml
hóa ra nhìn lại mới nhìn thấy nó có điều kiện có thể duplicate

JavaScript:

function search(nums: number[], target: number): boolean { let l = 0, r = nums.length - 1; while (l <= r) { const m = (l + r) >> 1; if (nums[m] === target) return true; if (nums[l] === nums[m] && nums[r] === nums[m]) l++, r--; else if (nums[l] <= nums[m]) { if (nums[l] <= target && nums[m] > target) r = m - 1; else l = m + 1; } else { if (nums[m] < target && nums[r] >= target) l = m + 1; else r = m - 1; } } return false; };

giật tí câu view à bác, nầy O(N) worstcase mà

anoldvozer1710.v2 · 10/8/23

Kiếp sống đầu đã nói:
giật tí câu view à bác, nầy O(N) worstcase mà

Giật tit gì bác nhỉ :surrender:

Mình có ghi TC bài này là O(logn) đâu mà giật tit. Chỉ là giải dựa trên bài hôm trước thôi

via theNEXTvoz for iPhone

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

Senior Member

Senior Member

Member

Senior Member

Senior Member

Junior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Đã tốn tiền

Senior Member

Senior Member

Junior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này