Xoay hình ảnh/ma trận
Vấn đề này yêu cầu chúng ta xoay một ma trận 2D theo cách mà mọi thứ được xoay 90 độ theo chiều kim đồng hồ. Để hiểu rõ hơn, tôi đã thêm các đoạn trích từ chính leetcode.
Như bạn có thể thấy, chúng ta chỉ cần xoay ma trận mà chúng ta đã cho. Đối với đầu vào và đầu ra của trường hợp thử nghiệm sau đây sẽ như sau:
SAO CHÉP
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Vấn đề có thể được giải quyết đơn giản bằng cách sử dụng một mảng hoặc véc tơ xoay giả. Chúng ta chỉ có thể đặt các phần tử để đạt được vòng quay của mình.
SAO CHÉP
rotated[j][n-i-1] = matrix[i][j];
Bạn có thể chỉ cần đặt mọi phần tử của ma trận đầu vào thông qua công thức này và đạt được phép quay, nhưng vấn đề yêu cầu chúng ta thực hiện theo cách tại chỗ. Để làm được theo cách này, chúng ta cần làm quen với phép chuyển vị của ma trận. Có một vấn đề khác trên leetcode là chỉ chuyển vị trí của ma trận .
Nếu bạn quan sát kỹ, chúng ta có thể đạt được phép quay chỉ bằng cách thực hiện chuyển vị của ma trận đầu vào và đảo ngược các hàng. Nó có thể làm điều đó với độ phức tạp về không gian chỉ là O(1) với độ phức tạp về thời gian là O(N*N) + O(N*N) - đầu tiên là để vận chuyển và thứ hai là để đảo chiều.
Để chuyển vị, chúng ta chỉ có thể hoán đổi các phần tử từ chỉ số [ i ] [ j ] sang [ j ] [ i ], trong khi làm như vậy, chúng ta cần đảm bảo rằng chúng ta không chạm vào các phần tử đường chéo và các phần tử khác chỉ được hoán đổi một lần.
SAO CHÉP
for(int i = 0; i < matrix.size(); i++) {
for(int j = 0; j < i; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
Chúng ta có thể đảo ngược các hàng một cách đơn giản bằng chức năng đảo ngược CPP tích hợp sẵn.
SAO CHÉP
for(int i = 0; i < matrix.size(); i++) {
reverse(matrix[i].begin(), matrix[i].end());
}
Vấn đề đầu tiên của chúng tôi đã được giải quyết và chúng tôi đã đề cập đến cả phương pháp tiếp cận mạnh mẽ và tối ưu.
Hợp nhất các khoảng thời gian
Tôi đã giải bài toán này hôm nay lần đầu tiên, và mặc dù lúc đầu nó có vẻ dễ, ở lần thứ hai là trung bình, và dễ một lần nữa thì đó là một bài toán hay.
Sự cố yêu cầu chúng tôi trả về một mảng đã nén không có các cặp chồng chéo. Bạn có thể hình dung vấn đề này đơn giản bằng cách nhìn vào dãy số.
SAO CHÉP
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Trong cách tiếp cận đầu tiên, chúng ta chỉ cần sắp xếp mảng và sử dụng brute force, tức là duyệt qua từng cặp đơn lẻ để có được đầu ra mong muốn. Chúng ta cũng cần tạo một mảng hoặc một vectơ để trả về đầu ra.
SAO CHÉP
int start = intervals[i][0];
int end = intervals[i][1];
Chúng ta chỉ có thể lấy phần đầu là phần tử đầu tiên trong cặp và phần cuối là phần tử thứ hai trong cặp. Nếu đó là phần tử đầu tiên thì chúng ta chỉ cần so sánh nó với các phần tử khác với sự trợ giúp của một vòng lặp for khác.
SAO CHÉP
for(int j = i + 1; j < n; j++) {
if(intervals[j][0] <= end)
end = max(end, intervals[j][1]);
}
end = max(end, intervals[i][1]);
outputArray.push_back({start, end});
Những gì chúng tôi đang làm ở đây là cố gắng đạt được mức tối đa trong khoảng thời gian chồng lấp và đẩy nó vào mảng đầu ra của chúng tôi. Tuy nhiên, nếu nó không phải là phần tử đầu tiên, chúng ta cần quan tâm đến tất cả các phần tử khác bằng cách kiểm tra ranh giới trên hiện có bên trong mảng đầu ra của chúng ta. Với mục đích đó, chúng ta có thể chèn một điều kiện if trước khi duyệt nhưng vẫn ở vòng lặp đầu tiên. Nếu bạn đang bối rối, tôi sẽ đính kèm toàn bộ mã của mình ở cuối.
SAO CHÉP
if(!outputArray.empty()) {
if(start <= op.back()[1]) continue;
}
Chúng tôi chỉ kiểm tra xem cặp này đã tồn tại trong mảng đầu ra của chúng tôi chưa.
Hợp nhất mảng đã sắp xếp
Bài toán đưa ra cho chúng ta hai mảng đã sắp xếp có kích thước m và n, và chúng ta chỉ cần hợp nhất chúng theo cách đã sắp xếp. Mặc dù chúng ta chỉ có thể sử dụng một mảng phụ có kích thước m + n và sắp xếp toàn bộ bằng hàm CPP có sẵn, vấn đề yêu cầu chúng ta không sử dụng mảng phụ. Thay vào đó, nó cho chúng ta biết rằng mặc dù chúng ta có m số phần tử trong mảng đầu tiên, nhưng kích thước thực của mảng đầu tiên là m + n và chúng ta không phải trả về bất kỳ mảng nào khác.
SAO CHÉP
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
Để giải quyết vấn đề này, chúng ta chỉ cần theo dõi cả hai mảng từ vị trí cuối cùng của chúng là m và n và đặt giá trị lớn nhất ở cuối cùng của mảng nums1.
SAO CHÉP
int i = m - 1, j = n - 1, k = m + n - 1;
Tôi đã sử dụng ba con trỏ để theo dõi ba vị trí trong mảng và duyệt qua nó với sự trợ giúp của vòng lặp while.
SAO CHÉP
while(i >= 0 && j >= 0) {
if(nums1[i] < nums2[j]) {
nums1[k--] = nums2[j--];
} else {
nums1[k--] = nums1[i--];
}
}
Đối với các số còn lại không được bao gồm sau vòng lặp này, tôi đã sử dụng một vòng lặp khác để nhập các phần tử đó vào nums1 của chúng tôi.
SAO CHÉP
while(i >= 0) {
nums1[k--] = nums1[i--];
}
while(j >= 0) {
nums1[k--] = nums2[j--];
}
Mỗi lần trong vòng lặp while, chúng tôi phải đảm bảo rằng chúng tôi đang giảm dần con trỏ hoặc trình vòng lặp vì đó không phải là vòng lặp for và điều đó có thể gây ra lỗi bộ nhớ cho bạn.
Tìm số trùng lặp
Đó là bài toán cuối cùng của ngày hôm nay và cũng dễ như bao bài toán khác. Bài toán cho ta một mảng kích thước n+1 với phạm vi từ 1 đến n. Một phần tử trong mảng được lặp lại và chúng ta phải tìm phần tử đó. Mặc dù chúng ta có thể chỉ cần sử dụng hàm sắp xếp và so sánh hai phần tử liên tiếp, nhưng sẽ mất độ phức tạp về thời gian là O(NLogN) để sắp xếp và thêm O(N) để so sánh hai phần tử liên tiếp. Một cách tiếp cận khác mà chúng ta có thể sử dụng là sử dụng hashmap và kiểm tra xem phần tử có bị lặp lại hay không, điều này có thể mất độ phức tạp thời gian là O(N) với độ phức tạp không gian là O(N) để lưu trữ hashmap.
SAO CHÉP
Input: nums = [1,3,4,2,2]
Output: 2
Vấn đề yêu cầu chúng ta không chạm vào mảng và chỉ sử dụng không gian cố định bổ sung mà giải pháp đầu tiên mà chúng ta đã thảo luận không đạt được. Chúng ta có thể sử dụng Thuật toán phát hiện chu kỳ Floyd để phát hiện số trùng lặp với không gian O(1) và thời gian O(N). Để hiểu rõ hơn, tôi khuyên bạn nên xem video này .
Vì phạm vi bắt đầu từ 1 và có một phần tử trùng lặp, nó chắc chắn sẽ tạo một vòng lặp bên trong mảng (nếu chúng ta coi phần tử đó là một địa chỉ). Tôi sẽ phải viết một blog khác chỉ để giải thích thuật toán này nhưng bây giờ, hãy lấy hai con trỏ và bắt đầu chúng từ vị trí nums[0].
SAO CHÉP
int slow = nums[0];
int fast = nums[0];
Di chuyển một con trỏ nhanh hơn (hai lần) như chúng ta làm trong danh sách liên kết để phát hiện vòng lặp.
SAO CHÉP
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
Khi chúng va chạm, chỉ cần gán lại con trỏ nhanh đến vị trí ban đầu, tức là nums[0] và tìm điểm va chạm thứ hai, đó là câu trả lời của chúng tôi.
SAO CHÉP
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
Bạn có thể quay lại chậm hoặc nhanh vì cả hai sẽ chỉ về số trùng lặp.
Phần kết luận
Tôi biết những blog này có nhịp độ nhanh nhưng tôi làm điều này để sử dụng như một công cụ sửa đổi hoặc một công cụ gợi ý cho những người đang gặp khó khăn và chủ yếu muốn tự mình làm điều đó. Hãy để tôi biết suy nghĩ của bạn.