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:
Tìm số nguyên tố x gần nhất để nums[j] > nums[j-1]
Nếu ko thể tìm ra x, và nums[j] <= nums[j-1] thì tức là false.
Có cái hàm tìm số nguyên tố đi chôm :ops:
JavaScript: 
function primeSubOperation(nums: number[]): boolean {
    let ok = false, prev = 0;
    const check = (num: number): boolean => {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 === 0 || num % 3 === 0) return false;
        for (let i = 5; i * i <= num; i += 6) {
            if (num % i === 0 || num % (i + 2) === 0) {
                return false;
            }
        }
        return true;
    };

    const find = (num: number, target: number) => {
        if (num < target) return 0;
        for (let i = num - 1; i > 1; i--) {
            if (check(i) && num - i > target) return i
        }
        return 0;
    }

    for (let i = 0; i < nums.length; i++) {
        const val = find(nums[i], prev);
        if (!val && nums[i] <= prev) return false;
        prev = nums[i] - val
    }
    return true;
};
Nhấp để mở rộng...
bác a nô cứu, cái template bi search là tìm minimize thỏa condition thì java làm tròn xuống mid ok, h tìm maximize java không làm tròn lên dính TLE phải làm sao, :adore: mid = l+(r-l+1)/2; thấy nó sai trái quá
 
Sửa lần cuối:
ko biết O mấy nma beat 100% :)
C#: 
public class Solution {
    public bool PrimeSubOperation(int[] nums) {
        var limit = nums.Max() - 1;
        bool[] isPrime = new bool[limit + 1];
        for (int i = 2; i <= limit; i++)
            isPrime[i] = true;

        for (int i = 2; i * i <= limit; i++)
        {
            if (isPrime[i])
            {
                for (int j = i * i; j <= limit; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }

        List<int> primes = new List<int>();
        for (int i = 2; i <= limit; i++)
        {
            if (isPrime[i])
                primes.Add(i);
        }
        for (int i = nums.Length - 2; i >= 0; i--)
        {
            if (nums[i] >= nums[i + 1])
            {
                var gap = nums[i] - nums[i + 1];
                bool check = false;
                foreach (var prime in primes)
                {
                    if (prime > gap && prime < nums[i])
                    {
                        nums[i] -= prime;
                        check = true;
                        break;
                    }
                }

                if (!check)
                {
                    return false;
                }
            }
        }

        return true;
    }
}
 
EzLink đã nói:
ko biết O mấy nma beat 100% :)
C#: 
public class Solution {
    public bool PrimeSubOperation(int[] nums) {
        var limit = nums.Max() - 1;
        bool[] isPrime = new bool[limit + 1];
        for (int i = 2; i <= limit; i++)
            isPrime[i] = true;

        for (int i = 2; i * i <= limit; i++)
        {
            if (isPrime[i])
            {
                for (int j = i * i; j <= limit; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }

        List<int> primes = new List<int>();
        for (int i = 2; i <= limit; i++)
        {
            if (isPrime[i])
                primes.Add(i);
        }
        for (int i = nums.Length - 2; i >= 0; i--)
        {
            if (nums[i] >= nums[i + 1])
            {
                var gap = nums[i] - nums[i + 1];
                bool check = false;
                foreach (var prime in primes)
                {
                    if (prime > gap && prime < nums[i])
                    {
                        nums[i] -= prime;
                        check = true;
                        break;
                    }
                }

                if (!check)
                {
                    return false;
                }
            }
        }

        return true;
    }
}
Nhấp để mở rộng...
đi pvan cái quan trọng thứ nhì ngoài cách giải là tính độ phức tạp time space nha fen xì, có beat 100% mà ko tính dc complexity = rớt.:sexy_girl:
 
LmaoSuVuong đã nói:
bác a nô cứu, cái template bi search là tìm minimize thỏa condition thì java làm tròn xuống mid ok, h tìm maximize java không làm tròn lên dính TLE phải làm sao, :adore: mid = l+(r-l+1)/2; thấy nó sai trái quá
Java: 
class Solution {
    public boolean primeSubOperation(int[] nums) {
        boolean[] is_prime = new boolean[1000];
        int[] prime = new int[170];
        int index =0;
        is_prime[1]=true;
        for (int i = 2; i * i <1000; i++) {
            if (!is_prime[i]) {
                for (int j = i * i; j <1000; j += i) {
                    is_prime[j] = true;
                }
            }
        }
        for(int i =0;i<1000;i++){
            if(!is_prime[i]){
                prime[index++]=i;
            }
        }
        int min=0;
        for(int num:nums){
            int p = find(prime, num-min);
            if(p==-1) return false;
            min = num-p;
        }

        return true;
    }
    public int find(int[] prime, int n){
        if(n<=0) return -1;
        int l =0;
        int r =168;
        while(l<r){
            int mid = l+(r-l+1)/2;
            if(prime[mid]>=n){
                r=mid-1;
            }else{
                l=mid;
            }
        }
        return prime[l];
    }
}
Nhấp để mở rộng...
Ở topic này đã lâu rồi mà bi search ko biết viết, đáng bị ăn gạch thay vì đc cứu
zFNuZTA.gif


via theNEXTvoz for iPhone
 
Java: 
class Solution {
    public boolean primeSubOperation(int[] nums) {
        boolean[] is_prime = new boolean[1000];
        int[] prime = new int[170];
        int index =0;
        is_prime[1]=true;
        for (int i = 2; i * i <1000; i++) {
            if (!is_prime[i]) {
                for (int j = i * i; j <1000; j += i) {
                    is_prime[j] = true;
                }
            }
        }
        for(int i =0;i<1000;i++){
            if(!is_prime[i]){
                prime[index++]=i;
            }
        }
        int min=0;
        for(int num:nums){
            int p = find(prime, num-min);
            if(p==-1) return false;
            min = num-p;
        }

        return true;
    }
    public int find(int[] prime, int n){
        if(n<=0) return -1;
        int l =0;
        int r =168;
        while(l<r){
            int mid = l+(r-l+1)/2;
            if(prime[mid]>=n){
                r=mid-1;
            }else{
                l=mid;
            }
        }
        return prime[l];
    }
}
 
Mắt Xích Yếu đã nói:
e người mới đây có cứu được không ạ
3Iy8P2x.gif
Nhấp để mở rộng...
Đi ngủ rồi mai dậy cứu nha mai fen
zFNuZTA.gif

Dùng template left <= right, mid = left + (right-left)/2
Nums[mid] > target thì mark ans = mid rồi right = mid - 1, else left = mid + 1.
Kết quả là sẽ ra index của số prime cần tìm, nếu index == -1 or primes[index] >= nums thì trả về false

via theNEXTvoz for iPhone
 
Mã: 
var primeSubOperation = function (nums) {
    const primes = [];
    out: for (let i = 2; i < 1000; i++) {
        for (let j = 2; j * j <= i; j++) {
            if (i % j === 0) {
                continue out;
            }
        }
        primes.push(i);
    }
    const n = nums.length;
    for (let i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] <= nums[i - 1]) {
            return false;
        }
        const k = _.sortedIndex(primes, nums[i] - (nums[i - 1] ?? 0)) - 1;
        if (k >= 0) {
            nums[i] -= primes[k];
        }
    }
    return true;
};
 
Java: 
class Solution {
    public boolean primeSubOperation(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int bound;
            if (i == 0) bound = nums[0];
            else bound = nums[i] - nums[i - 1];
            if (bound <= 0) return false;
            int prime = 0;
            for (int j = bound - 1; j > 1; j--) {
                if (isPrime(j)) {
                    prime = j;
                    break;
                }
            }
            nums[i] -= prime;
        }
        return true;
    }

    private boolean isPrime(int num) {
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
}
DNA bị giới hạn nên chỉ biết brute-force :hungry:
 
Viết như này mới đúng @Mắt Xích Yếu lần sau hỏi bài log clone khác nữa vô hỏi thì mới trả lời nha :shame: chắc tròn 10 năm mới code lại Java
Java: 
class Solution {
    public boolean primeSubOperation(int[] nums) {
        boolean[] is_prime = new boolean[1000];
        int[] prime = new int[170];
        int index =0;
        is_prime[1]=true;
        for (int i = 2; i * i <1000; i++) {
            if (!is_prime[i]) {
                for (int j = i * i; j <1000; j += i) {
                    is_prime[j] = true;
                }
            }
        }
        for(int i =0;i<1000;i++){
            if(!is_prime[i]){
                prime[index++]=i;
            }
        }
        for (int i = nums.length - 2; i >= 0; i --){
            if(nums[i] >= nums[i + 1])
            {
                int curr = find(prime, nums[i] - nums[i + 1]);
                if(curr == -1 || curr >= nums[i])
                {
                    return false;
                }
                nums[i] = nums[i] - curr;
            }
        }

        return true;
    }
    public int find(int[] prime, int n){
        int l =0;
        int r = prime.length - 1;
        int ans = -1;
        while(l<=r){
            int mid = l+ (r-l)/2;
            if(prime[mid]>n){
                r=mid-1;
                ans = mid;
            }else{
                l=mid + 1;
            }
        }

        if (ans == -1)
        {
            return ans;
        }
       
        return prime[l];
    }
}
 
Someone... đã nói:
nhiều nhất cũng chỉ trong 32 phần tử thôi, bởi vì càng OR thì càng bật bit 1 lên, mà đã bật lên thì đâu có tắt được nữa, cho nên cùng lắm 32 phần tử
Nhấp để mở rộng...
ví dụ 1001010, mình bật thêm 1 bit vào các số 0 thì có 4 cách chọn mà fen, riêng 1 cái bit đã có 4 cách chọn rồi, 32 phần tử sẽ có 2^32 chứ
 
C++: 
class Solution {
public:
    bool primeSubOperation(vector<int>& nums) {
        for (int k = nums[0] - 1; k >= 2; k--) {
            if (isPrime(k)) {
                nums[0] -= k;
                break;
            }
        }

        for (int i = 1; i < nums.size(); i++) {
            for (int k = nums[i] - nums[i - 1] - 1; k >= 2; k--) {
                if (isPrime(k)) {
                    nums[i] -= k;
                    break;
                }
            }
        }

        for (int i = 1; i < nums.size(); i++) {
            if (nums[i - 1] >= nums[i]) {
                return false;
            }
        }

        return true;
    }

    bool isPrime(int n) {
        for (int i = 2; i*i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }
};
1731299704584.png
 
sáng t2 code bẩn quá :beat_brick:


Python: 
class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        def gen_primes(n):
            # Step 1: initialize a list to mark a number is prime or not
            is_prime = [True] * (n + 1)

            # Base case: 0 and 1 are not primes
            is_prime[0] = False
            is_prime[1] = False

            for i in range(2, int(n**0.5) + 1):
                if is_prime[i]:
                    for j in range(i*i, n + 1, i):
                        is_prime[j] = False
            return [i for i in range(2, n+1) if is_prime[i]]       
    
        def search(num):
            l, r = 0, len(primes) - 1
            while l <= r:
                mid = (l + r) // 2
                if primes[mid] >= num:
                    r = mid - 1
                else:
                    l = mid + 1
            return r
        
        primes = gen_primes(max(nums))
        nums = [float("-inf")] + nums
        n = len(nums)
        for i in range(1, n):
            idx = search(nums[i])
            while idx >= 0 and nums[i-1] >= nums[i] - primes[idx]:
                idx -= 1
            if idx >= 0 and nums[i] - primes[idx] > nums[i-1] and primes[idx] < nums[i]:
                nums[i] -= primes[idx]
        for i in range(1, n-1):
            if nums[i] >= nums[i+1]:
                return False

        return True
 
C++: 
class Solution {
private:
    int maxPrimeLessThan(int bound) {
        for (auto i = bound - 1; i >= 2; --i) {
            auto s = static_cast<int>(floor(sqrt(i))); auto isPrime = true;
            for (auto d = 2; d <= s; ++d) {
                if (i % d != 0) continue;
                isPrime = false; break;
            }
            if (isPrime) return i;
        }
        return -1;
    }

public:
    bool primeSubOperation(vector<int>& nums) {
        int bound = 0;
        for (auto &num : nums) {
            if (num <= bound) return false;
            auto p = maxPrimeLessThan(num - bound);
            if (p == -1) bound = num;
            else bound = num - p;
        }
        return true;
    }
};
 
chả nhớ lần cuối implement sàng nguyên tố là bao giờ nữa, may và vẫn nhớ:sexy_girl:
C++: 
vector<int> eratosthenes_sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;

    is_prime[0] = is_prime[1] = false;
    for (int i=2; i<=n; ++i) {
        if (!is_prime[i]) {
            continue;
        }
        primes.push_back(i);
        for (int j=i*i; j<=n; j+=i) {
            is_prime[j] = false;
        }
    }
    return primes;
}

class Solution {
public:
    bool primeSubOperation(vector<int>& nums) {
        const vector<int> &primes = eratosthenes_sieve(*max_element(nums.begin(), nums.end()));
        for (int i=nums.size()-2; i>=0; --i) {
            if (nums[i] < nums[i+1]) {
                continue;
            }
            const int index = upper_bound(primes.begin(), primes.end(), nums[i] - nums[i+1]) - primes.begin();

            if (index == primes.size() || primes[index] >= nums[i]) {
                return false;
            }
            nums[i] -= primes[index];
        }

        return true;
    }
};
 
freedom.9 đã nói:
Viết như này mới đúng @Mắt Xích Yếu lần sau hỏi bài log clone khác nữa vô hỏi thì mới trả lời nha :shame: chắc tròn 10 năm mới code lại Java
Java: 
class Solution {
    public boolean primeSubOperation(int[] nums) {
        boolean[] is_prime = new boolean[1000];
        int[] prime = new int[170];
        int index =0;
        is_prime[1]=true;
        for (int i = 2; i * i <1000; i++) {
            if (!is_prime[i]) {
                for (int j = i * i; j <1000; j += i) {
                    is_prime[j] = true;
                }
            }
        }
        for(int i =0;i<1000;i++){
            if(!is_prime[i]){
                prime[index++]=i;
            }
        }
        for (int i = nums.length - 2; i >= 0; i --){
            if(nums[i] >= nums[i + 1])
            {
                int curr = find(prime, nums[i] - nums[i + 1]);
                if(curr == -1 || curr >= nums[i])
                {
                    return false;
                }
                nums[i] = nums[i] - curr;
            }
        }

        return true;
    }
    public int find(int[] prime, int n){
        int l =0;
        int r = prime.length - 1;
        int ans = -1;
        while(l<=r){
            int mid = l+ (r-l)/2;
            if(prime[mid]>n){
                r=mid-1;
                ans = mid;
            }else{
                l=mid + 1;
            }
        }

        if (ans == -1)
        {
            return ans;
        }
    
        return prime[l];
    }
}
Nhấp để mở rộng...
duyệt mảng nums ngược từ sau về đầu thì nó lại về bài toán minimize condition r template của bác a nô cân ngon ơ :pudency: , e duyệt từ đầu tới cuối thì phải tìm tham lam maximize ở từng vị trí 1 áp template python vào java nó hong có chạy do cơ chế làm tròn (?maybe vd l=2, r=3 ->mid=2 condition true l=mid=2 -> loop tới TLE) :sad:
 
Sửa lần cuối:
Python: 
valid = [True] * 1001
valid[0] = valid[1] = False
for i in range(2, len(valid)):
    if valid[i]:
        for j in range(i * i, len(valid), i):
            valid[j] = False
primes = [i for i in range(len(valid)) if valid[i]]


class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        def bl(primes, x):
            l = 0
            r = len(primes)
            while l < r:
                m = l + (r-l)//2
                if primes[m] >= x: # Tìm số nguyên tố đầu tiến >= x
                    r = m
                else:
                    l = m + 1
         
            return l

        prev = 0
        for num in nums:
            if num <= prev:
                return False
            i = bl(primes, num - prev) - 1 # số phía trước của số nguyên tố đầu tiên >=x là số nguyên tố lớn nhất không vượt quá x
            if i != -1:
                num -= primes[i]
            prev = num
        return True

Không tính phần generte bảng số nguyên tố vì nó ko phụ thuộc vào nums, thì thuật TC = O(N logM) với N là số lượng nums và M là số lượng số nguyên tố
 
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
845
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.088

Chia sẻ trang này

Quay lại
Lên đầu trang