2197. Thay Thế Các Số Không Là Coprime Trong Mảng

Độ Khó: Khó

Chủ Đề: Mảng, Toán Học, Ngăn Xếp, Số Học, Cuộc Thi Tuần 283

Giới thiệu

Bạn được cung cấp một mảng số nguyên nums. Nhiệm vụ của bạn là thực hiện các bước sau:

Tìm bất kỳ hai số kề nhau trong nums mà không phải là coprime.
Nếu không tìm thấy số nào như vậy, dừng lại.
Nếu tìm thấy, xóa hai số đó và thay thế chúng bằng LCM (Bội số chung nhỏ nhất) của chúng.
Lặp lại quá trình này cho đến khi không còn tìm thấy cặp số kề nhau nào không phải là coprime.

Cuối cùng, trả về mảng đã được thay đổi cuối cùng. Có thể chứng minh rằng việc thay thế các số không phải là coprime kề nhau theo bất kỳ thứ tự nào cũng sẽ dẫn đến cùng một kết quả.

Ví dụ 1:

Đầu vào: nums = [6,4,3,2,7,6,2]
Đầu ra: [12,7,6]
Giải thích:
- (6, 4) không phải là coprime với LCM(6, 4) = 12. Bây giờ, nums = [12,3,2,7,6,2].
- (12, 3) không phải là coprime với LCM(12, 3) = 12. Bây giờ, nums = [12,2,7,6,2].
- (12, 2) không phải là coprime với LCM(12, 2) = 12. Bây giờ, nums = [12,7,6,2].
- (6, 2) không phải là coprime với LCM(6, 2) = 6. Bây giờ, nums = [12,7,6].
- Không còn cặp số kề nào không phải là coprime trong nums.
- Vậy mảng đã thay đổi cuối cùng là [12,7,6].

Ví dụ 2:

Đầu vào: nums = [2,2,1,1,3,3,3]
Đầu ra: [2,1,1,3]
Giải thích:
- (3, 3) không phải là coprime với LCM(3, 3) = 3. Bây giờ, nums = [2,2,1,1,3,3].
- (3, 3) không phải là coprime với LCM(3, 3) = 3. Bây giờ, nums = [2,2,1,1,3].
- (2, 2) không phải là coprime với LCM(2, 2) = 2. Bây giờ, nums = [2,1,1,3].
- Không còn cặp số kề nào không phải là coprime trong nums.
- Vậy mảng đã thay đổi cuối cùng là [2,1,1,3].

Ràng Buộc:

1 <= nums.length <= 105
1 <= nums[i] <= 105
Các trường hợp thử nghiệm được tạo ra sao cho các giá trị trong mảng cuối cùng là nhỏ hơn hoặc bằng 108

Gợi ý:

Lưu ý rằng thứ tự hợp nhất hai số thành LCM của chúng không quan trọng, vì vậy chúng ta có thể hợp nhất các phần tử về phía bên trái nếu có thể.
Nếu một giá trị mới được hình thành, chúng ta nên kiểm tra đệ quy xem nó có thể được hợp nhất với giá trị bên trái của nó.
Để mô phỏng việc hợp nhất một cách hiệu quả, chúng ta có thể giữ một ngăn xếp chứa các phần tử đã được xử lý. Khi chúng ta lặp qua mảng, chúng ta chỉ so sánh với phần tử trên cùng của ngăn xếp (giá trị bên trái của nó).

Giải pháp

Chúng ta cần thay thế liên tục bất kỳ hai số kề nhau nào không phải là coprime trong một mảng bằng Bội số chung nhỏ nhất (LCM) của chúng cho đến khi không còn cặp số không phải là coprime nào. Giải pháp này liên quan đến việc xử lý hiệu quả mảng trong khi đảm bảo rằng bất kỳ phép hợp nhất nào cũng được xử lý theo cách có thể yêu cầu các phép hợp nhất tiếp theo với các phần tử trước đó.

Cách tiếp cận

Xử lý Dựa trên Ngăn Xếp: Chúng ta sử dụng một ngăn xếp để xử lý từng phần tử trong mảng. Ngăn xếp giúp theo dõi các phần tử đã được xử lý và cho phép chúng ta kiểm tra và hợp nhất các phần tử kề nhau một cách hiệu quả.
Tính Toán GCD và LCM: Đối với mỗi phần tử mới, chúng ta kiểm tra nó với phần tử trên cùng của ngăn xếp. Nếu chúng không phải là coprime (tức là GCD của chúng lớn hơn 1), chúng ta hợp nhất bằng cách thay thế chúng bằng LCM của chúng. Quá trình này lặp lại với giá trị đã hợp nhất mới và phần tử trên cùng tiếp theo của ngăn xếp cho đến khi không còn phép hợp nhất nào có thể.
Hiệu Suất: Thuật toán xử lý mỗi phần tử một lần và thực hiện các phép hợp nhất chỉ khi cần thiết. Ngăn xếp đảm bảo rằng chúng ta xử lý hiệu quả bất kỳ phản ứng chuỗi nào do các phép hợp nhất gây ra, vì mỗi phép hợp nhất có thể tạo ra một giá trị mới có thể hợp nhất với các phần tử trước đó.

Cài đặt Giải pháp trong PHP

Dưới đây là cách thực hiện giải pháp này trong PHP:

php Copy

<?php
/**
 * @param Integer[] $nums
 * @return Integer[]
 */
function replaceNonCoprimes($nums) {
    $stack = [];
    foreach ($nums as $num) {
        while (!empty($stack) && gcd($stack[count($stack) - 1], $num) > 1) {
            $num = lcm($stack[count($stack) - 1], $num);
            array_pop($stack);
        }
        array_push($stack, $num);
    }
    return $stack;
}

/**
 * @param Integer $a
 * @param Integer $b
 * @return int
 */
function gcd($a, $b) {
    while ($b != 0) {
        $temp = $b;
        $b = $a % $b;
        $a = $temp;
    }
    return $a;
}

/**
 * @param Integer $a
 * @param Integer $b
 * @return int
 */
function lcm($a, $b) {
    return ($a / gcd($a, $b)) * $b;
}

// Các trường hợp thử nghiệm
$nums1 = [6,4,3,2,7,6,2];
print_r(replaceNonCoprimes($nums1)); // Đầu ra: [12, 7, 6]

$nums2 = [2,2,1,1,3,3,3];
print_r(replaceNonCoprimes($nums2)); // Đầu ra: [2, 1, 1, 3]
?>

Giải thích:

Khởi tạo: Bắt đầu với một ngăn xếp rỗng để xử lý mỗi số trong mảng đầu vào.
Xử lý Mỗi Số: Đối với mỗi số trong mảng, chúng ta đặt nó là giá trị hiện tại. Sau đó kiểm tra giá trị này với phần tử trên cùng của ngăn xếp. Nếu chúng không phải là coprime (GCD > 1), chúng ta sẽ lấy phần tử trên cùng ra, tính LCM của giá trị hiện tại và phần tử đã lấy ra, và đặt giá trị hiện tại thành LCM này. Bước này lặp lại cho đến khi giá trị hiện tại và phần tử trên cùng mới của ngăn xếp là coprime.
Đưa vào Ngăn Xếp: Sau khi đảm bảo rằng không còn phép hợp nhất nào có thể, chúng ta đưa giá trị hiện tại vào ngăn xếp.
Tính GCD: Hàm trợ giúp gcd tính toán ước số chung lớn nhất của hai số bằng thuật toán Euclid, đây là phương pháp hiệu quả và được sử dụng rộng rãi cho mục đích này.
Kết quả: Cuối cùng, ngăn xếp chứa tất cả các phần tử sau tất cả các phép hợp nhất có thể, và được trả về như kết quả.

Các Thực Hành Tốt Nhất

Kiểm tra Đầu vào: Luôn đảm bảo rằng mảng đầu vào không rỗng và các phần tử nằm trong giới hạn cho phép.
Tối ưu hóa Hiệu suất: Xem xét cách tính toán GCD và LCM để đảm bảo không sử dụng quá nhiều tài nguyên.

Những Cạm Bẫy Thường Gặp

Không Kiểm Tra GCD Đúng Cách: Đảm bảo rằng bạn luôn kiểm tra GCD trước khi hợp nhất hai số.
Quá Tải Ngăn Xếp: Theo dõi kích thước ngăn xếp để tránh việc chiếm dụng bộ nhớ không cần thiết.

Mẹo Hiệu Suất

Cố gắng giảm số lần tính GCD bằng cách chỉ gọi nó khi cần thiết.
Sử dụng các thuật toán tối ưu cho tính toán LCM và GCD để cải thiện tốc độ.

Liên Kết Liên Hệ
Nếu bạn thấy bài viết này hữu ích, hãy cho repository một ngôi sao trên GitHub hoặc chia sẻ bài viết trên các mạng xã hội yêu thích của bạn 😍. Sự hỗ trợ của bạn sẽ có ý nghĩa rất lớn với tôi!

Nếu bạn muốn nhiều nội dung hữu ích như thế này, hãy theo dõi tôi trên:

LinkedIn
GitHub

Thay Thế Các Số Không Là Coprime Trong Mảng