27
4
Địa chỉ câu hỏi: https://leetcode.com/problems/increasing-triplet-subsequence/description/
Cho một mảng chưa được sắp xếp trả về xem dãy con tăng dần có độ dài 3 có tồn tại hay không trong mảng.
Về mặt hình thức, hàm này nên:
Trả về true nếu tồn tại i, j, k sao cho arr[i] < arr[j] < arr[k] cho trước 0 ≤ i < j < k ≤ n-1 nếu không trả về false.
Thuật toán của bạn phải chạy ở độ phức tạp thời gian O(n) và độ phức tạp không gian O(1).
Trung tâm cá nhân
Điều phát hành
từ bỏVí dụ: Cho [1, 2, 3, 4, 5], trả về true. Cho [5, 4, 3, 2, 1], trả về false.
Xác định xem một mảng không có thứ tự có chứa chuỗi có độ dài tăng dần 3 hay không.
Nó chắc chắn có thể được thực hiện bằng giải pháp của LIS, nhưng nó không đáp ứng được độ phức tạp về thời gian O(n) được đưa ra trong câu hỏi. Sau khi đọc giải pháp của người khác, tôi thấy họ thực sự rất thông minh. Chúng ta hoàn toàn có thể bỏ DP và dfs. Khi viết code, tôi chỉ cần dùng con thoi, tôi chỉ cần lấy bàn phím và thực hiện!
Vì bắt buộc phải duyệt từ trước ra sau nên khi duyệt ta lưu giá trị nhỏ nhất và giá trị nhỏ thứ 2 đã thấy rồi tìm ra tồn tại giá trị nhỏ thứ 3 lớn hơn 2 giá trị này nghĩa là có độ dài là dãy con tăng dần bằng 3.
Tất nhiên, đối với trường hợp này:
4 5 1 2 6
Có hai loại dãy con tăng dần có độ dài 3, nhưng vì chúng ta lưu dãy con nhỏ nhất trước nên kết quả cuối cùng là nhóm 1 2 6.
Ý tưởng tổng thể thực sự rất linh hoạt, điều được tiết kiệm là thời gian truyền tảiđã xemNhỏ nhất và nhỏ thứ hai, vì vậy đừng bao giờ sử dụng các hàm tĩnh tối thiểu và tối đa.
Mã số:
Giải pháp lớp(đối tượng): def tăngTriplet(self, nums): """ :type nums: List[int] :rtype: bool """ first, two = float('inf'), float('inf') for num trong nums: if num <= first: first = num elif num <= two: two = num else: return Đúng trả về Sai
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
DDKK.COM Brother Kuaikan-hướng dẫn, trang thông tin lập trình dành cho lập trình viên, bản quyền thuộc về tác giả gốc
Bài viết này được viết bởi:nến tuyết tiêu cực Được ủy quyền xuất bản, không tổ chức, cá nhân nào được chuyển tiếp nếu không có sự cho phép của tác giả
27
4
0
Tôi đang triển khai một thuật toán trong đó khi người dùng nhập một chuỗi, mỗi ký tự trong chuỗi (nếu đó là bảng chữ cái) sẽ được tăng theo một giá trị nhất định (ở đây là một công cụ quay vòng). Tôi đang chơi với mã này trong 2 giờ và không thể hiểu tại sao khi tôi tăng công cụ quay vòng theo giá trị, nó lại nhấn công cụ quay vòng
Tôi có 1.0.5. Làm cách nào để tăng nó lên 1.0.6? Đã thử nó, nhưng nó không hoạt động. echo 1.0.5 0.0.1 | awk '{sum=$1+$2; printf"%0.2f\n", sum }' Câu trả lời hay nhất
Câu hỏi này đã có câu trả lời ở đây: Hành vi của toán tử tăng và giảm trong Python (11 câu trả lời) Tại sao không có ++
Đã đóng cửa. Câu hỏi này không tuân thủ nguyên tắc Stack Overflow. Câu trả lời không được chấp nhận vào thời điểm này. Câu hỏi này có vẻ lạc đề vì nó thiếu đủ thông tin để chẩn đoán vấn đề. Mô tả vấn đề của bạn chi tiết hơn hoặc bao gồm một bản tóm tắt nhỏ
Tôi đang cố gắng cải thiện C của mình, tôi có đoạn mã sau, nó hoạt động khi tôi sử dụng i offset chứ không phải Hold++, tôi không hiểu tại sao tôi nghĩ họ cũng làm điều tương tự? Đây là phiên bản tôi không thể làm việc được: char* Reversestri
Tôi cần tăng/giảm thời gian trong cơ sở dữ liệu PostgreSQL. Dưới đây là đầu ra của bảng chứa loại cột "dấu thời gian không có múi giờ". Tôi cũng cần thay đổi ngày nếu thời gian lớn hơn 24 giờ. làm ơn giúp đỡ
Tôi có một bảng tên là temp_rfm trong đó col1 thực sự là ID khách hàng (tôi gặp sự cố kết hợp bất hợp pháp) và calc_date là ngày bắt đầu của tháng được tăng lên. CHỌN * TỪ temp_rfm co;
Tôi hiện đang nghiên cứu các tùy chọn cho ứng dụng của mình và tôi phải đặt một góc. Giá trị mặc định là khoảng 30° và người dùng có thể điều chỉnh góc này để phù hợp nhất. Thay vì chỉ tạo EditTextPreference bình thường, tôi muốn nó hoạt động giống như trong các ứng dụng khác
Câu hỏi này đã có câu trả lời: Tăng một số bằng toán tử tiền tố và hậu tố (1 câu trả lời) Đã đóng vào năm ngoái. Tôi đang cố gắng hiểu các hoạt động tăng dần của Javascript
Tôi đang sử dụng javascript sau để tải lại đệ quy DIV mục tiêu với id="outPut", kết quả của truy vấn dữ liệu khi truyền tham số tới getData.php >. Vấn đề là fadeTo sẽ làm mờ giá trị trả về của mỗi lần gọi lặp
Câu hỏi này đã có câu trả lời ở đây: đã đóng cửa 10 năm trước. Có thể trùng lặp: Jquery Draggable + Đưa ra phía trước Tôi có một trang web nơi người dùng có thể mở nhiều cuộc trò chuyện
Tôi phải xác định một hàm trong đó: Bắt đầu với số nguyên dương gốc, tiếp tục nhân số gốc với n và tính toán
Tôi đang ghi lại một số số liệu thống kê trong ứng dụng của mình. Một trong những số liệu thống kê là kích thước của BigDataStructure. Tôi có hai tùy chọn: tạo bộ đếm và tăng/giảm bộ đếm mỗi khi có thêm/xóa cấu trúc dữ liệu lớn. Mỗi lần bạn thêm/xóa khỏi
Trong chương trình ví dụ Java sau đây, tôi nhận được một vòng lặp vô hạn và tôi không hiểu tại sao: public class Time { public static int next(int v) { re
Tôi đã thêm một hành vi không mong muốn từ C#/WPF riêng tư void ButtonUp_Click(object sender, RoutedEventArgs e) {
Tôi muốn tăng chữ số cuối cùng của chuỗi do người dùng cung cấp trong Python 2.7. Tôi có thể thay thế số đầu tiên như thế này: def tăng_hostname(name): try: tê
Tôi đang thực hiện tìm kiếm mạnh mẽ cho một số float có các thuộc tính nhất định (lỗi làm tròn nhỏ là sin(a)^2+cos(a)^2-1). Vì vậy, tôi muốn lặp lại vùng lân cận của một float nhất định bằng cách tăng phần định trị. Có cách nào dễ dàng để làm điều này trong C
Tiêu chuẩn C định nghĩa _Bool là loại không dấu chứa 0 hoặc 1. Nếu giá trị của loại _Bool được tăng thêm 1, theo như tôi biết, có hai tùy chọn: giá trị nằm trong khoảng từ 1 đến 0 và giá trị tăng lên 2, khác 0 và do đó được chuyển đổi trở lại _B
Tôi có tệp INI lưu trữ một số số nguyên cho cài đặt. Một phần của tên được lưu trữ như sau: [ColorScheme_2] name=Dark Purple gradient BackgroundColor=224 B
Tôi có phương pháp này trong ứng dụng của mình: - (void)initializeTimer{ self.myTimer = [NSTimer SchedulerWithTimeInterval:th
Tôi là một lập trình viên xuất sắc, rất giỏi!