Ở đây chúng tôi đi một lần nữa! Hôm qua, tôi đã dành khoảng một giờ để viết blog đầu tiên của mình trên hashnode. Không chậm trễ hơn nữa, hãy xem những gì chúng tôi đã làm!
Tìm kiếm Ma trận 2D
Bài toán này khá đơn giản để hiểu, chúng ta chỉ cần kiểm tra xem có tồn tại một phần tử trong mảng hai chiều đã cho hay không. Một cách tiếp cận đơn giản và đơn giản là sử dụng hai vòng lặp for để duyệt qua toàn bộ ma trận và giải quyết vấn đề, nhưng leetcode đã chỉ định một số thuộc tính của mảng đã cho:
Mỗi hàng được sắp xếp theo thứ tự không giảm.
Số nguyên đầu tiên của mỗi hàng lớn hơn số nguyên cuối cùng của hàng trước đó.
Như bạn có thể thấy, đó là một mảng được sắp xếp với một vài phần chia trong đó. Chúng ta có thể giải quyết tìm kiếm trong một mảng được sắp xếp bằng tìm kiếm nhị phân và đó là những gì chúng ta phải làm ở đây để giải quyết vấn đề này trong O(Log(M * N)).
Chúng ta có thể lấy các con trỏ thấp và cao tại 0 và M * N - 1 nhưng còn phần tử ở giữa vì đây là mảng 2D thì sao? Chà, với một vài lần chạy khô, chúng ta có thể đặt phần tử ở giữa vào vị trí:
SAO CHÉP
mid = (low + (high - low) / 2);
i = mid / n;
j = mid % n;
middleElement = nums[i][j];
Tất cả những thứ khác đều giống như tìm kiếm nhị phân, tức là tăng con trỏ thấp và giảm con trỏ cao tùy thuộc vào so sánh với giá trị mục tiêu của chúng tôi và giữ vòng lặp cho đến mức thấp thấp hơn mức cao.
Pow(x, n)
Vấn đề thứ hai tôi giải quyết cũng dễ dàng như vấn đề đầu tiên với một cách tiếp cận tối ưu. Như tên của bài toán gợi ý, chúng ta phải tìm lũy thừa thứ n của x.
SAO CHÉP
Input: x = 2.00000, n = 10
Output: 1024.00000
Mặc dù chúng ta có thể thực hiện lại với vòng lặp for nhưng chúng ta phải thực hiện điều đó trong thời gian O(Log N). Như chúng ta biết rằng sức mạnh thứ 10 của 2 sẽ là sức mạnh thứ 5 của bốn. Chúng ta có thể sử dụng phương pháp chia lũy thừa này mọi lúc bất cứ khi nào nó là bội số của 2 để giảm số lượng phép tính.
SAO CHÉP
while(nCopy) {
if(nCopy % 2) {
ans = ans * x;
nCopy--;
} else {
x = x * x;
nCopy = nCopy / 2;
}
}
Ở đây, tôi đã sao chép n để tôi có thể xem n có âm không và thực hiện yêu cầu nếu cần.
SAO CHÉP
if(n < 0) return 1/ans;
Yếu tố đa số
Vì vậy, vấn đề cho chúng ta một mảng với một phần tử được lặp lại nhiều hơn kích thước chia cho hai lần. Chúng ta phải tìm phần tử đó và đưa nó về leetcode.
SAO CHÉP
Input: nums = [2,2,1,1,1,2,2]
Output: 2
Hai trong số các cách tiếp cận dễ dàng cho vấn đề này là sử dụng hai vòng lặp for để đếm số lần xuất hiện của mọi phần tử hoặc chúng ta chỉ có thể sử dụng hàm băm hoặc mảng tần số để đếm số lần xuất hiện với độ phức tạp thời gian là O(N) và độ phức tạp không gian là O(N) lại.
Nhưng một cách tiếp cận hiệu quả hơn sẽ là sử dụng Thuật toán bỏ phiếu của Moore .
Bây giờ bạn đã hiểu về trực giác, hãy để tôi cho bạn biết mật mã. Chúng ta có thể lấy một phần tử và số đếm được khởi tạo bằng 0 và với vòng lặp for, chúng ta có thể duyệt qua mọi phần tử và có ba trường hợp:
đếm == 0, trong trường hợp này, chúng ta cần cập nhật phần tử của mình thành phần tử hiện tại (nums[i]) trong mảng.
phần tử == nums[i], thì chúng ta chỉ cần tăng bộ đếm khi xác suất giành được phần tử của chúng ta tăng lên.
phần tử != nums[i], trong trường hợp này do xác suất thắng phần tử của chúng ta đang giảm nên chúng ta có thể giảm bộ đếm.
Phần tử cuối cùng đứng vững sẽ là phần tử đa số.
SAO CHÉP
for(int i = 0; i < nums.size(); i++) {
if(count == 0) {
element = nums[i];
count++;
} else if(element == nums[i]) {
count++;
} else {
count--;
}
}
Phần tử đa số II
Vấn đề thứ tư tôi đã giải quyết là một phiên bản thay thế của vấn đề thứ hai.
SAO CHÉP
Given an integer array of size n, find all elements that appear more than [ n/3 ] times.
Như chúng ta đã biết, không thể có nhiều hơn hai phần tử có đa số xuất hiện trong n/3 lần. Chúng ta có thể đơn giản sử dụng Thuật toán bỏ phiếu của Moore như chúng ta đã sử dụng trong ví dụ trước nhưng với hai phần tử và hai số xác suất. Chúng ta phải tăng và giảm cả hai theo cách tương tự như chúng ta đã làm trước đó.
SAO CHÉP
for(int i = 0; i < size; i++)
{
if(nums[i] == num1)
count1++;
else if(nums[i] == num2)
count2++;
else if(count1 == 0) {
num1 = nums[i];
count1++;
} else if(count2 == 0) {
num2 = nums[i];
count2++;
} else {
count1--;
count2--;
}
}
Nhưng, có một nhược điểm. Mã này sẽ trả về hai phần tử có số lần xuất hiện nhiều nhất nhưng chúng không bắt buộc phải xảy ra nhiều hơn n/3 lần. Để giải quyết vấn đề này, chúng ta cần đặt lại bộ đếm của mình và đếm cụ thể số lần xuất hiện của các phần tử này. Sau đó, chúng ta có thể trả lời câu trả lời của mình.
Đường dẫn duy nhất
Đây là vấn đề cuối cùng tôi giải quyết ngày hôm nay. Vấn đề khá đơn giản để hiểu:
Robot của chúng ta có thể di chuyển sang phải hoặc di chuyển xuống dưới, chúng ta phải trả về số lượng đường đi có thể sử dụng để đi đến cuối lưới tức là tại vị trí lưới [m-1][n-1].
Để giải quyết vấn đề này, chúng ta có thể sử dụng đệ quy (Nó có thể cung cấp cho bạn TLE nhưng có thể hữu ích trong cuộc phỏng vấn)
SAO CHÉP
int countPath(int i, int j, int m, int n) {
if(i == m - 1 && j == n - 1) return 1;
if(i >= m || j >= n) return 0;
else return {
countPath(i+1, j, m, n) + countPath(i, j+1, m, n);
}
}
Chúng ta phải chuyển i và j bằng 0 ban đầu với m và n như hiện tại. Sau đó, chúng tôi sẽ tăng i và j mỗi lần cho đến khi chúng tôi vượt ra khỏi giới hạn hoặc cho đến khi chúng tôi tìm thấy điểm cuối của lưới.
Có nhiều cách tiếp cận lập trình động hơn cho vấn đề này, nhưng tôi không quen thuộc hơn với chúng.
Đó là nó cho ngày hôm nay, hẹn gặp lại vào ngày mai!