2422. Merge Operations to Turn Array Into a Palindrome

Approach

Cần kết hợp kĩ thuật two pointers và tính tổng động từ hai đầu mảng

Khởi tạo pointer và tổng ban đầu

Pointer trái i ở vị trí đầu mảng, tổng trái a = nums[i]

Pointer phải j ở cuối mảng, tổng b = nums[j]

Biến đếm phép merger ans = 0

So sánh và điều chỉnh tổng

Nếu a < b: Di chuyển pointer left sang phải, cộng phần tử mới vào a, tăng ans (merge phần tử trái)

typescripttypescript

1i += 1
2a += nums[i]
3ans += 1

Nếu a > b: Di chuyển pointer right sang trái, cộng phần tử mới vào b, tăng ans (merge phần tử phải)

typescripttypescript

1j -= 1
2b += nums[j]
3ans += 1

Khi a === b : Di chuyển cả hai pointer vào trong và cập nhật lại a, b (không tăng ans)

Dừng khi các pointer gặp nhau

Quá trình tiếp tục cho đến khi i ≥ j

Solution

typescripttypescript

1function minimumOperations(nums: number[]): number {
2    let i = 0;
3    let j = nums.length - 1
4    let operations = 0;
5
6    while (i < j) {
7        if (nums[i] === nums[j]) {
8            i++;
9            j--
10        } else if (nums[i] < nums[j]) {
11            nums[i + 1] += nums[i];
12            i++;
13            operations++
14        } else {
15            nums[j - 1] += nums[j]
16            j--;
17            operations++;
18        }
19    }
20    return operations
21};

Loading content...