Xin chào. Khi tôi tiếp tục tìm kiếm công việc của mình, tôi đang thực hành các câu hỏi về thuật toán của mình trên Leetcode. Vì vậy, tôi nghĩ rằng tôi sẽ viết blog về một số vấn đề về Leetcode khi tôi giải quyết chúng
Là một người tốt nghiệp Bootcamp, tôi không được thực hành nhiều về các thuật toán, vì vậy, việc nhận ra các mẫu và sai sót là một trải nghiệm rất thú vị và đôi khi khiến tôi nản lòng, tối ưu hóa mã của tôi để nhanh hơn [nhìn bạn Big-O], học cách phá vỡ . Tôi đã thực hành chúng bằng JavaScript
Vì tôi còn khá mới với các vấn đề về thuật toán, nên tôi đã bắt đầu với Bộ sưu tập dễ dàng các câu hỏi phỏng vấn hàng đầu của họ. Vì vậy, trong Chứa trùng lặp
Cho một mảng số nguyên nums
, trả về true
nếu bất kỳ giá trị nào xuất hiện ít nhất hai lần trong mảng và trả về false
nếu mọi phần tử đều khác biệt
ví dụ
Input: nums = [1,2,3,1]
Output: trueInput: nums = [1,2,3,4]
Output: falseInput: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Đơn giản, nếu bất kỳ số nào trong mảng xuất hiện nhiều lần trong mảng, tôi cần trả về true
. Bây giờ, tôi chắc chắn sẽ cần tìm ra cách để so sánh một số với các số khác. Ngoài ra, rất có thể tôi sẽ cần lặp qua mảng để tôi có quyền truy cập vào từng số để sau đó so sánh nó với các số khác
Đầu tiên, tôi nghĩ rằng tôi có thể lặp qua mảng và ở mỗi trường hợp, tôi lặp qua một vòng lặp khác của các số nguyên còn lại và so sánh chúng để xem có số nào bằng nhau không [===]. Tuy nhiên, theo hiểu biết mới bắt đầu của tôi về Big-O, điều này sẽ mang lại cho tôi độ phức tạp thời gian không thuận lợi là O[n²]
Sau đó, tôi nghĩ rằng tôi có thể tạo một đối tượng và đếm xem một số trong mảng xuất hiện bao nhiêu lần. Bằng cách này, sau đó tôi có thể kiểm tra xem liệu có bất kỳ số nào có tổng số lớn hơn 1 không. Nếu vậy, tôi có thể trả lại true
nếu không tôi sẽ trả lại false
var containsDuplicate = function[nums] {
hash = {}
let i = 0
while [i < nums.length] {
if [hash[nums[i]]] {
hash[nums[i]] += 1
} else {
hash[nums[i]] = 1
}
i++
}
values = Object.values[hash] for [let j = 0; j < values.length; j++]{
if [values[j] > 1] {
return true
}
}
return false
};
Và điều đó hiệu quả. giải quyết. Và độ phức tạp về thời gian sẽ là O[2n], nhanh hơn kế hoạch ban đầu của tôi. Tuy nhiên, tôi tự hỏi liệu tôi có thể dọn sạch thứ này và cải thiện một chút thời gian chạy Big-O của mình không?
Điều tôi nhận ra là tôi đã tạo một đối tượng khi tôi lặp qua mảng và tôi có thể trả về true
ngay khi tôi tìm thấy bất kỳ số nào xuất hiện nhiều lần. Vì vậy, thay vì lặp qua toàn bộ mảng và sau đó kiểm tra các bản sao, tôi có thể làm điều đó cùng một lúc. Khi tôi lặp lại mảng, nếu nó không tồn tại trong đối tượng của tôi, thì tôi sẽ thêm nó vào. Nếu nó đã tồn tại trong đối tượng, thì tôi có thể trả lại true
và kết thúc. Cuối cùng, nếu tôi chạy qua toàn bộ vòng lặp mà không nhấn vào câu lệnh return true
, thì tôi sẽ trả về false
var containsDuplicate = function[nums] {
hash = {}
for [let i = 0; i < nums.length; i++] {
if [hash[nums[i]]] {
return true
} else {
hash[nums[i]] = 1
}
}
return false
};
Bây giờ, điều đó có vẻ tốt hơn rất nhiều. Và nó chạy với độ phức tạp thời gian O[n] khá. Tôi tưởng tượng vẫn còn nhiều cách tốt hơn và nhanh hơn để giải quyết vấn đề này, vì vậy hãy để lại nhận xét cho tôi nếu mã của tôi có thể được cải thiện hoặc hướng dẫn tôi một cách mới để giải quyết vấn đề này [Tôi rất thích điều đó. ]
Tôi hy vọng điều này sẽ giúp ích cho bạn nếu bạn gặp khó khăn khi giải quyết vấn đề này và tìm kiếm thêm các giải pháp Leetcode trong tương lai
Cho một mảng số nguyên nums, trả về true nếu bất kỳ giá trị nào xuất hiện ít nhất hai lần trong mảng và trả về false nếu mọi phần tử đều khác biệt
Dung dịch
Độ phức tạp về thời gian. O[n]
Độ phức tạp của không gian. O[n]
var containsDuplicate = function[nums] {
const map = {}
for[const num of nums] {
// If we have seen this num before return true
if[map[num]] return true
map[num] = true
}
return false
};
Vào chế độ toàn màn hình Thoát chế độ toàn màn hình
Nhận xét hàng đầu [0]
Vương miệnSắp xếp thảo luận
Đã chọn Sắp xếp Tùy chọn Lên trên
Những bình luận được bình chọn nhiều nhất và có liên quan sẽ được xếp đầu tiên
Muộn nhất
Những bình luận gần đây nhất sẽ là đầu tiên
Cũ nhất
Những bình luận cũ nhất sẽ được đầu tiên
Đặt mua
Người dùng cá nhân đáng tin cậy
Mẫu cho phép bạn nhanh chóng trả lời Câu hỏi thường gặp hoặc lưu trữ đoạn mã để sử dụng lại
Gửi bản xem trước Bỏ qua
Quy tắc ứng xử • Báo cáo lạm dụng
Bạn có chắc chắn muốn ẩn bình luận này?