Dưới đây là một bài toán kiểm tra lập trình đơn giản với logic không quá phức tạp:

Một mảng A chỉ số bắt đầu từ 0 gồm N số nguyên được cho. Một chỉ số cân bằng của mảng này là bất kỳ số nguyên P sao cho 0 ≤ P < N và tổng các phần tử có chỉ số nhỏ hơn bằng tổng các phần tử có chỉ số lớn hơn, tức là:

A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].

Giả sử tổng của không phần tử bằng 0. Điều này có thể xảy ra khi P = 0 hoặc khi P = N−1.

Ví dụ, xem xét mảng A sau gồm N = 7 phần tử:

<tt>A[0] = -7   A[1] =  1   A[2] = 5
A[3] =  2   A[4] = -4   A[5] = 3
A[6] =  0</tt>

P = 3 là một chỉ số cân bằng của mảng này, vì:

• A[0] + A[1] + A[2] = A[4] + A[5] + A[6]

P = 6 cũng là một chỉ số cân bằng, vì:

• A[0] + A[1] + A[2] + A[3] + A[4] + A[5] = 0

và không có phần tử nào có chỉ số lớn hơn 6.

P = 7 không phải là chỉ số cân bằng, vì nó không thỏa mãn điều kiện 0 ≤ P < N.

Viết một hàm

int solution(int A[], int N);

int solution(NSMutableArray *A);

int solution(const vector<int> &A);

class Solution { int solution(int[] A); }

class Solution { public int solution(int[] A); }

object Solution { def solution(A: Array[Int]): Int }

function solution(A);

function solution(A)

function solution($A);

function solution(A: array of longint; N: longint): longint;

def solution(A)

sub solution { my (@A)=@_; ... }

def solution(a)

Private Function solution ( A As Integer() ) as Integer

cho trước một mảng A chỉ số bắt đầu từ 0 gồm N số nguyên, trả về bất kỳ chỉ số cân bằng nào của nó. Hàm nên trả về −1 nếu không tồn tại chỉ số cân bằng.

Giả sử rằng:

• N là một số nguyên trong khoảng [0..10,000,000];
• mỗi phần tử của mảng A là một số nguyên trong khoảng [−2,147,483,648..2,147,483,647].

Ví dụ, cho mảng A sao cho

<tt>A[0] = -7   A[1] =  1   A[2] = 5
A[3] =  2   A[4] = -4   A[5] = 3
A[6] =  0</tt>

hàm có thể trả về 3 hoặc 6, như đã giải thích ở trên.

Độ phức tạp:

• độ phức tạp thời gian trường hợp xấu nhất mong đợi là O(N);
• độ phức tạp không gian trường hợp xấu nhất mong đợi là O(N), ngoài dung lượng lưu trữ đầu vào (không kể dung lượng lưu trữ cần thiết cho các đối số đầu vào).

Các phần tử của mảng đầu vào có thể được sửa đổi.

Ban đầu, tôi đã viết ra đoạn mã sau:

    int j = 0;
    int tongTam = A[0];
    for(j = 1; j<A.Length; j++){
        
        //A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].
        //return P
        if(tongA - tongTam - A[j] == tongTam){
            break;
        }  
        tongTam += A[j];
    }
    if (j == A.Length || j == A.Length - 1)
        return -1;
    else
        return j;
}

}

Tôi được 62/100 điểm vì đã bỏ qua kiểm tra biên và có một sự hiểu lầm.

Vì vậy, tôi đã cập nhật nó thành đoạn mã sau:

//100/100 điểm using System; // bạn cũng có thể sử dụng các import khác, ví dụ: // using System.Collections.Generic; class Solution { public int solution(int[] A) { //N là một số nguyên trong khoảng [0..10,000,000]; if(A.Length <1 || A.Length >10000000) return -1; //một số duy nhất if(A.Length == 1) return 0;

    //mỗi phần tử của mảng A là một số nguyên trong khoảng [−2,147,483,648..2,147,483,647]
    Int64 tongToanBo = 0;
    foreach(int i in A){
        tongToanBo += i;
    }
            
    int j = 0;
    
    //mỗi phần tử của mảng A là một số nguyên trong khoảng [−2,147,483,648..2,147,483,647]
    Int64 tongBenTrai = 0;
    for(; j<A.Length; j++){
        //A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].
        //return P
        if(tongToanBo - tongBenTrai - A[j] == tongBenTrai){
            break;
        }  
        tongBenTrai += A[j];
    }
    //P = 7 không phải là chỉ số cân bằng, vì nó không thỏa mãn điều kiện 0 ≤ P < N
    if (j == A.Length)
        return -1;
    else
        return j;
}

}

Bây giờ, tôi được 100/100 điểm.

Bài toán này đến từ một trang web kiểm tra.