Chương trình giải pháp LeetCode Creek Phiên bản 0. 0 Nội dung 1 Xoay mảng trong Java 7 2 Đánh giá ký hiệu đánh bóng ngược
Lượt xem 5,276 Tải xuống 1,225 Kích thước tệp 2MB
TẢI TẬP TIN
Đề xuất câu chuyệnXem trước trích dẫn
Chương trình giải pháp LeetCode Creek Phiên bản 0. 0
nội dung
1
Xoay mảng trong Java
7
2
Đánh giá ký hiệu đánh bóng ngược
9
3
Giải pháp của chuỗi con Palindromic dài nhất trong Java
11
4
Giải pháp ngắt từ
15
5
Phá vỡ lời nói II
18
6
thang từ
20
7
Trung bình của hai mảng được sắp xếp Java
23
8
Kết hợp biểu thức chính quy trong Java
25
9
Hợp nhất các khoảng thời gian
27
10 Chèn khoảng thời gian
29
11 Hai Tổng
31
12 Hai Tổng II Mảng đầu vào được sắp xếp
32
13 Hai Tổng III Thiết kế cấu trúc dữ liệu
33
14 3Tổng
34
15 4Sum
36
16 3Tổng gần nhất
38
17 Chuỗi thành Số nguyên (atoi)
39
18 Hợp nhất mảng đã sắp xếp
40
19 dấu ngoặc đơn hợp lệ
42
20 Triển khai strStr()
43
2. 181
nội dung
21 Đặt số không ma trận
44
22 Tìm kiếm Chèn Vị trí
46
23 Chuỗi liên tiếp dài nhất Java
47
24 Palindrome hợp lệ
49
25 Ma Trận Xoắn Ốc
52
26 Tìm kiếm Ma trận 2D
55
27 Xoay hình ảnh
56
28 Tam giác
58
29 dãy con riêng biệt Tổng
60
30 phân đoạn tối đa
62
31 Phân nhóm sản phẩm tối đa
63
32 Loại bỏ các bản sao khỏi mảng đã sắp xếp
64
33 Loại bỏ các dữ liệu trùng lặp khỏi mảng đã sắp xếp II
67
34 chuỗi con dài nhất không có ký tự lặp lại
69
35 chuỗi con dài nhất chứa 2 ký tự duy nhất
71
36 Phân vùng Palindrome
73
37 từ đảo ngược trong một chuỗi
75
38 Tìm giá trị nhỏ nhất trong mảng được sắp xếp xoay
76
39 Tìm giá trị nhỏ nhất trong mảng được sắp xếp xoay vòng II
77
40 Tìm phần tử đỉnh
78
Ngăn xếp 41 phút
79
42 Phần Tử Đa Số
80
43 Tổng kết hợp
82
44 Thời Điểm Tốt Nhất Để Mua Bán Cổ Phiếu
83
45 Thời Điểm Tốt Nhất Để Mua Bán Cổ Phiếu II
84
lạch chương trình
3. 181
nội dung
46 Thời Điểm Tốt Nhất Để Mua Bán Cổ Phiếu III
85
47 Thời Điểm Tốt Nhất Để Mua Bán Cổ Phiếu IV
86
48 Tiền tố chung dài nhất
88
49 Số Lớn Nhất
89
50 kết hợp
90
51 So sánh số phiên bản
92
Cây xăng 52
93
53 Kẹo
95
Trò chơi nhảy 54
96
55 Tam giác Pascal
97
56 Bình Chứa Nhiều Nước Nhất
98
57 Đếm và Nói
99
58 Chuỗi DNA lặp lại
100
59 Cộng Hai Số
101
60 Sắp xếp lại danh sách
105
61 Chu trình danh sách liên kết
109
62 Sao chép danh sách bằng con trỏ ngẫu nhiên
111
63 Hợp nhất hai danh sách đã sắp xếp
114
64 Hợp nhất k Danh sách đã sắp xếp
116
65 Loại bỏ các bản sao khỏi danh sách đã sắp xếp
117
66 Danh sách phân vùng
119
67 Bộ nhớ đệm LRU
121
68 Giao của hai danh sách liên kết
124
69 Ví dụ về lớp PriorityQueue trong Java
125
70 Giải pháp cho Traversal sắp xếp trước cây nhị phân trong Java
127
4. 181
lạch chương trình
nội dung
71 Giải pháp Traversal theo thứ tự cây nhị phân trong Java
128
72 Giải pháp duyệt cây nhị phân theo thứ tự lặp trong Java
130
73 Xác thực cây tìm kiếm nhị phân
131
74 Làm phẳng cây nhị phân thành danh sách liên kết
133
75 tổng đường dẫn
134
76 Xây dựng cây nhị phân từ Inorder và Postorder Traversal
136
77 Chuyển mảng đã sắp xếp thành cây tìm kiếm nhị phân
137
78 Chuyển đổi danh sách đã sắp xếp thành cây tìm kiếm nhị phân
138
79 Độ sâu tối thiểu của cây nhị phân
140
80 Cây nhị phân Tổng đường dẫn tối đa
142
81 Cây Nhị Phân Cân Bằng
143
82 Cây đối xứng
145
83 Bản sao đồ thị Java
146
84 Các Nhà phát triển Sắp xếp trong Java như thế nào?
149
85 Giải Pháp Hợp Nhất Sắp Xếp Danh Sách Liên Kết Trong Java
151
86 Mảng Quicksort trong Java
154
87 Giải pháp Sắp xếp danh sách liên kết bằng sắp xếp chèn trong Java
156
88 Khoảng Cách Tối Đa
158
89 Lặp đi lặp lại so với. Đệ quy trong Java
160
90 Chỉnh sửa khoảng cách trong Java
163
91 số duy nhất
165
92 Độc Thân Số II
166
93 Twitter Codility Vấn đề Khoảng cách nhị phân tối đa
166
94 Số 1 Bit
167
95 bit đảo ngược
168
lạch chương trình
5. 181
nội dung
96 Hoán vị
169
97 Hoán vị II
171
98 Dãy Hoán Vị
173
99 Tạo dấu ngoặc đơn
175
100 số nguyên đảo ngược
176
101 Số Palindrome
178
102 Pow(x, n)
179
6. 181
lạch chương trình
1 Xoay Mảng trong Java Có thể bạn đã sử dụng Java được một thời gian. Bạn có nghĩ rằng một câu hỏi về mảng Java đơn giản có thể là một thách thức không? . Vấn đề. Xoay mảng n phần tử sang phải k bước. Ví dụ, với n = 7 và k = 3, mảng [1,2,3,4,5,6,7] được xoay thành [5,6,7,1,2,3,4]. Bạn biết bao nhiêu cách khác nhau để giải quyết vấn đề này?
1. 1 Giải pháp 1 - Mảng trung gian Nói một cách đơn giản, chúng ta có thể tạo một mảng mới rồi sao chép các phần tử sang mảng mới. Sau đó thay đổi mảng ban đầu bằng cách sử dụng Hệ thống. bản sao mảng (). public void rotate(int[] nums, int k) { if(k > nums. chiều dài) k=k%nums. chiều dài; . chiều dài]; . độ dài-k+i];
Tuy nhiên, thời gian là O(n*k)
1. 3 Giải pháp 3 - Đảo ngược Chúng ta có thể làm điều này trong không gian O(1) và trong thời gian O(n) không? . Giả sử chúng ta được cho 1,2,3,4,5,6 và thứ tự 2. Ý tưởng cơ bản là. 1. 2. 3. 4
Chia Xoay Xoay Xoay
mảng hai phần. 1,2,3,4 và 5, 6 phần đầu. 4,3,2,1,5,6 phần thứ hai. 4,3,2,1,6,5 cả mảng. 5,6,1,2,3,4
public static void rotate(int[] arr, int order) { order = order % arr. chiều dài; . thứ tự < 0) { ném IllegalArgumentException mới ("Đối số bất hợp pháp. "); } //độ dài của phần đầu tiên trong mảng =. chiều dài - thứ tự; . chiều dài-1); . chiều dài-1); . mảng. chiều dài == 1) trả về;
số 8. 181
lạch chương trình
} }
2 Đánh giá ký hiệu đánh bóng ngược Vấn đề. Đánh giá giá trị của một biểu thức số học trong Reverse Polish Notation. Các toán tử hợp lệ là +, -, *, /. Mỗi toán hạng có thể là một số nguyên hoặc một biểu thức khác. Vài ví dụ. ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/
2. 1 Cách tiếp cận ngây thơ Vấn đề này đơn giản. Sau khi hiểu vấn đề, chúng ta nên nhanh chóng nhận ra rằng vấn đề này có thể được giải quyết bằng cách sử dụng ngăn xếp. Chúng ta có thể lặp qua từng phần tử trong mảng đã cho. Khi nó là một số, đẩy nó vào ngăn xếp. Khi nó là toán tử, hãy lấy hai số từ ngăn xếp, thực hiện phép tính và đẩy lùi kết quả
Sau đây là mã. Nó chạy tuyệt vời bằng cách cho ăn một bài kiểm tra nhỏ. Tuy nhiên, mã này
9. 181
2 Đánh giá ký hiệu đánh bóng ngược
chứa lỗi biên dịch trong leetcode. Tại sao? . ngoài. println(evalRPN(token)); . mã thông báo) { nếu (. nhà khai thác. chứa (t)) { ngăn xếp. đẩy(t); . valueOf(ngăn xếp. nhạc pop()); . valueOf(ngăn xếp. nhạc pop()); . cây rơm. đẩy (Chuỗi. valueOf(a + b)); . cây rơm. đẩy (Chuỗi. valueOf(b - a)); . cây rơm. đẩy (Chuỗi. valueOf(a * b)); . cây rơm. đẩy (Chuỗi. valueOf(b / a)); . valueOf(ngăn xếp. nhạc pop());
Vấn đề là câu lệnh chuỗi chuyển đổi chỉ khả dụng từ JDK 1. 7. Leetcode rõ ràng sử dụng các phiên bản bên dưới đó
10. 181
lạch chương trình
2. 2 Giải pháp được chấp nhận
Nếu bạn muốn sử dụng câu lệnh chuyển đổi, bạn có thể chuyển đổi phần trên bằng cách sử dụng đoạn mã sau sử dụng chỉ mục của chuỗi "+-*/". giải pháp lớp công khai { public int evalRPN(String[] tokens) { int returnValue = 0; . mã thông báo) { nếu (. nhà khai thác. chứa(t)){ ngăn xếp. đẩy(t); . valueOf(ngăn xếp. nhạc pop()); . valueOf(ngăn xếp. nhạc pop()); . indexOf(t); . cây rơm. đẩy (Chuỗi. valueOf(a+b)); . cây rơm. đẩy (Chuỗi. valueOf(b-a)); . cây rơm. đẩy (Chuỗi. valueOf(a*b)); . cây rơm. đẩy (Chuỗi. valueOf(b/a)); . valueOf(ngăn xếp. nhạc pop());
11. 181
3 Giải pháp của chuỗi con Palindromic dài nhất trong Java
3 Giải pháp cho chuỗi con Palindromic dài nhất trong Java Tìm chuỗi con palindromic dài nhất là một vấn đề kinh điển của phỏng vấn lập trình. Trong bài đăng này, tôi sẽ tóm tắt 3 giải pháp khác nhau cho vấn đề này
3. 1 Cách tiếp cận ngây thơ Một cách ngây thơ, chúng ta có thể chỉ cần kiểm tra mọi chuỗi con và kiểm tra xem nó có phải là đối xứng hay không. Độ phức tạp thời gian là O(nˆ3). Nếu điều này được gửi tới LeetCode onlinejudge, một thông báo lỗi sẽ được trả về - "Vượt quá giới hạn thời gian". Do đó, cách tiếp cận này mới chỉ là bước khởi đầu, chúng ta cần một thuật toán tốt hơn. chuỗi tĩnh công khai dài nhấtPalindrome1 (Chuỗi s) { int maxPalinLength = 0; . chiều dài(); . chuỗi con(i, j + 1); . chiều dài () - 1; . charAt(i). = s. charAt(s). chiều dài () - 1 - i)) { trả về sai;
12. 181
lạch chương trình
3 Giải pháp của chuỗi con Palindromic dài nhất trong Java
3. 2 Lập trình động Gọi s là chuỗi đầu vào, i và j là hai chỉ số của chuỗi. Xác định một "bảng" mảng 2 chiều và đặt table[i][j] biểu thị xem chuỗi con từ i đến j có phải là palindrome hay không. điều kiện bắt đầu. bảng[i][i] == 1; . charAt(i) == s. charAt(i+1)
thay đổi điều kiện. bảng[i+1][j-1] == 1 && s. charAt(i) == s. charAt(j) => bảng[i][j] == 1
Thời gian O(nˆ2) Không gian O(nˆ2) public static Chuỗi dài nhấtPalindrome2(String s) { if (s == null) return null; . length() = 0 && end 0-(i-1) có thể được phân đoạn bằng từ điển • Trạng thái ban đầu t[0] == true public class Solution { public boolean wordBreak(String s, Set dict) { boolean[] t = new . chiều dài()+1]; . chiều dài ()) tiếp tục; . chuỗi con(i, kết thúc). bằng(a)){ t[end] = true; . chiều dài()];
Thời gian. O(chiều dài chuỗi * kích thước chính tả) Một phần khó khăn của giải pháp này là trường hợp. ĐẦU VÀO. "programcreek", ["programcree","program","creek"]
Chúng ta nên lấy tất cả các trận đấu có thể, không dừng lại ở "chương trình"
4. 3 Biểu thức chính quy Vấn đề được cho là tương đương với việc khớp biểu thức chính quy (leet. code)*, mà ˆ và thực thi nó trong O(n). có nghĩa là nó có thể được giải quyết bằng cách xây dựng DFA trong O(2m) (Nhờ hdante. ) Mặc dù vậy, thẩm phán trực tuyến Leetcode không cho phép sử dụng lớp Mẫu. public static void main(String[] args) { HashSet dict = new HashSet(); . thêm ("đi"); . thêm ("mục tiêu"); . add("bàn thắng"); . thêm ("đặc biệt"); . chính tả){ sb. nối thêm (s + ". "); } Mẫu chuỗi = sb. toString(). chuỗi con(0, sb. chiều dài()-1);
lạch chương trình
17. 181
mẫu = "("+mẫu+")*"; . biên dịch (mẫu); . matcher("bàn thắng đặc biệt"); . trận đấu()){ Hệ thống. ngoài. println("so khớp");
4. 4 The More Interesting Problem
Giải pháp động có thể cho chúng ta biết liệu chuỗi có thể được chia thành các từ hay không, nhưng không thể cho chúng ta biết chuỗi bị chia thành những từ nào. So how to get those words? Check out Word Break II
Phá Vỡ 5 Chữ II
Đưa ra một chuỗi s và một từ điển các từ chính tả, hãy thêm khoảng trắng vào s để tạo một câu trong đó mỗi từ là một từ từ điển hợp lệ. Return all such possible sentences. Ví dụ: cho s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"], giải pháp là ["cats and dog", "cat sand dog"]
5. 1 Giải Pháp Java - Lập Trình Động
Vấn đề này rất giống với Word Break. Thay vì sử dụng một mảng boolean để theo dõi các vị trí khớp, chúng ta cần theo dõi các từ thực tế. Sau đó, chúng ta có thể sử dụng tìm kiếm theo chiều sâu để có được tất cả các đường dẫn có thể, tôi. e. , the list of strings. The following diagram shows the structure of the tracking array
18 . 181
Phá Vỡ 5 Chữ II
public static List wordBreak(String s, Set dict) { //create an array of ArrayList List dp[] = new ArrayList[s. length()+1]; dp[0] = new ArrayList(); for(int i=0; i s. length()) continue; if(s. substring(i,end). equals(word)){ if(dp[end] == null){ dp[end] = new ArrayList(); } dp[end]. add(word); } } } List result = new LinkedList(); if(dp[s. length()] == null) return result;
lạch chương trình
19 . 181
ArrayList temp = new ArrayList(); dfs(dp, s. length(), result, temp); return result; } public static void dfs(List dp[],int end,List result, ArrayList tmp){ if(end =0; i--){ path += " " + tmp. get(i) ; } result. add(path); return; } for(String str . dp[end]){ tmp. add(str); dfs(dp, end-str. length(), result, tmp); tmp. remove(tmp. size()-1); } }
6 Word Ladder The problem. Cho hai từ (bắt đầu và kết thúc) và một từ điển, hãy tìm độ dài của chuỗi biến đổi ngắn nhất từ đầu đến cuối, sao cho. Only one letter can be changed at a time Each intermediate word must exist in the dictionary For example, Given. start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" ->"hot" ->"dot" ->"dog" ->"cog", the program should return its length 5. Note. Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. This problem is a classic problem that has been asked frequently during interviews
20 . 181
6 Word Ladder
The following are two Java solutions
6. 1 Naive Approach In a simplest way, we can start from start word, change one character each time, if it is in the dictionary, we continue with the replaced word, until start == end. public class Solution { public int ladderLength(String start, String end, HashSet dict) { int len=0; HashSet visited = new HashSet(); for(int i=0; i false
13. 1 Java Solution Since the desired class need add and get operations, HashMap is a good option for this purpose. public class TwoSum { private HashMap elements = new HashMap(); public void add(int number) { if (elements. containsKey(number)) { elements. put(number, elements. get(number) + 1); } else { elements. put(number, 1); } }
33 . 181
public boolean find(int value) { for (Integer i . elements. keySet()) { int target = value - i; if (elements. containsKey(target)) { if (i == target && elements. get(target) < 2) { continue; } return true; } } return false; } }
14 3Sum Problem. Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note. Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets. For example, given array S = {-1 0 1 2 -1 -4}, A solution set is. (-1, 0, 1) (-1, -1, 2)
14. 1 Naive Solution Naive solution is 3 loops, and this gives time complexity O(nˆ3). Apparently this is not an acceptable solution, but a discussion can start from here. public class Solution { public ArrayList threeSum(int[] num) { //sort array Arrays. sort(num); ArrayList result = new ArrayList(); ArrayList each = new ArrayList();
34 . 181
14 3Tổng
for(int i=0; i 0) break; for(int j=i+1; j 0 && num[j] > 0) break; for(int k=j+1; k1 to use same element only once. public ArrayList threeSum(int[] num) { ArrayList result = new ArrayList(); if (num. length < 3) return result; // sort array Arrays. sort(num); for (int i = 0; i < num. length - 2; i++) { // //avoid duplicate solutions if (i == 0 . num[i] > num[i - 1]) {
lạch chương trình
35 . 181
int negate = -num[i]; int start = i + 1; int end = num. length - 1; while (start < end) { //case 1 if (num[start] + num[end] == negate) { ArrayList temp = new ArrayList(); temp. add(num[i]); temp. add(num[start]); temp. add(num[end]); result. add(temp); start++; end--; //avoid duplicate solutions while (start < end && num[end] == num[end + 1]) end--; while (start < end && num[start] == num[start - 1]) start++; //case 2 } else if (num[start] + num[end] < negate) { start++; //case 3 } else { end--; } } } } return result; }
15 4Sum Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note. Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d) The solution set must not contain duplicate quadruplets
36 . 181
15 4Sum
For example, given array S = {1 0 -1 0 -2 2}, and target = 0. A solution set is. (-1, 0, 0, 1) (-2, -1, 1, 2) (-2, 0, 0, 2)
15. 1 Suy nghĩ Một bài toán k-sum điển hình. Time is N to the poser of (k-1)
15. 2 Java Solution public ArrayList fourSum(int[] num, int target) { Arrays. sort(num); HashSet hashSet = new HashSet(); ArrayList result = new ArrayList(); for (int i = 0; i < num. length; i++) { for (int j = i + 1; j < num. length; j++) { int k = j + 1; int l = num. length - 1; while (k < l) { int sum = num[i] + num[j] + num[k] + num[l]; if (sum > target) { l--; } else if (sum < target) { k++; } else if (sum == target) { ArrayList temp = new ArrayList(); temp. add(num[i]); temp. add(num[j]); temp. add(num[k]); temp. add(num[l]); if (. hashSet. contains(temp)) { hashSet. add(temp); result. add(temp); } k++; l--; }
lạch chương trình
37 . 181
} } } return result; }
Here is the hashCode method of ArrayList. It makes sure that if all elements of two lists are the same, then the hash code of the two lists will be the same. Since each element in the ArrayList is Integer, same integer has same hash code. int hashCode = 1; Iterator i = list. iterator(); while (i. hasNext()) { E obj = i. next(); hashCode = 31*hashCode + (obj==null ? 0 . obj. hashCode()); }
16 3Sum Closest Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution. For example, given array S = -1 2 1 -4, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2)
16. 1 Thoughts This problem is similar with 2 Sum. This kind of problem can be solve by using similar approach, i. e. , two pointers from both left and right
16. 2 Java Solution public class Solution { public int threeSumClosest(int[] num, int target) { int min = Integer. MAX_VALUE; int result = 0; Arrays. sort(num); for (int i = 0; i < num. chiều dài;
38 . 181
int k trong khi int int
= số. chiều dài - 1; . abs(tổng - mục tiêu);
nếu (khác == 0) trả về 0; . charAt(i) >= '0' && str. charAt(i) Số nguyên. MAX_VALUE) trả về Số nguyên. GIÁ TRỊ TỐI ĐA; . MIN_VALUE) return Integer. MIN_VALUE; return (int) result; }
Thanks to the comment below. The solution above passes LeetCode online judge, but it haven’t considered other characters. I will update this later
40 . 181
18 Hợp nhất mảng đã sắp xếp
18 Merge Sorted Array Problem. Given two sorted integer arrays A and B, merge B into A as one sorted array. Note. You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively
18. 1 Thoughts for This Problem The key to solve this problem is moving element of A and B backwards. If B has some elements left after A is done, also need to handle that case. The takeaway message from this problem is that the loop condition. This kind of condition is also used for merging two sorted linked list
18. 2 Java Solution 1 public class Solution { public void merge(int A[], int m, int B[], int n) { while(m > 0 && if(A[m-1] > A[m+n-1] m--; }else{ A[m+n-1] n--; } }
n > 0){ B[n-1]){ = A[m-1];
= B[n-1];
while(n > 0){ A[m+n-1] = B[n-1]; n--; } } }
18. 3 Java Solution 2 The loop condition also can use m+n like the following. public void int i = m int j = n int k = m
merge(int A[], int m, int B[], int n) { - 1; - 1; + n - 1;
lạch chương trình
41 . 181
while (k >= 0) { if (j < 0 . (i >= 0 && A[i] > B[j])) A[k--] = A[i--]; else A[k--] = B[j--]; } }
19 Valid Parentheses Problem. Given a string containing just the characters ’(’, ’)’, ’’, ’’, ’[’ and ’]’, determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]" are all valid but "(]" and "([)]" are not
19. 1 Thoughts about This Problem Character is not a frequently used class, so need to know how to use it
19. 2 Java Solution public static boolean isValid(String s) { HashMap map = new HashMap(); map. put(’(’, ’)’); map. put(’[’, ’]’); map. put(’{’, ’}’); Stack stack = new Stack(); for (int i = 0; i < s. length(); i++) { char curr = s. charAt(i); if (map. keySet(). contains(curr)) { stack. push(curr); } else if (map. values(). contains(curr)) { if (. stack. empty() && map. get(stack. peek()) == curr) { stack. pop(); } else { return false; } }
42 . 181
} return stack. empty(); }
19. 3 Simplified Java Solution Almost identical, but convert string to char array at the beginning. public static boolean isValid(String s) { char[] charArray = s. toCharArray(); HashMap map = new HashMap(); map. put(’(’, ’)’); map. put(’[’, ’]’); map. put(’{’, ’}’); Stack stack = new Stack(); for (Character c . charArray) { if (map. bộ chìa khoá(). contains(c)) { stack. push(c); } else if (map. values(). contains(c)) { if (. stack. isEmpty() && map. get(stack. peek()) == c) { stack. pop(); } else { return false; } } } return stack. isEmpty(); }
20 Implement strStr() Problem. Implement strStr(). Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack
43 . 181
20. 1 Thoughts First, need to understand the problem correctly, the pointer simply means a sub string. Second, make sure the loop does not exceed the boundaries of two strings
20. 2 Java Solution public String strStr(String haystack, String needle) { int needleLen = needle. length(); int haystackLen = haystack. length(); if (needleLen == haystackLen && needleLen == 0) return ""; if (needleLen == 0) return haystack; for (int i = 0; i < haystackLen; i++) { // make sure in boundary of needle if (haystackLen - i + 1 < needleLen) return null; int k = i; int j = 0; while (j < needleLen && k < haystackLen && needle. charAt(j) == haystack. charAt(k)) { j++; k++; if (j == needleLen) return haystack. substring(i); } } return null; }
From Tia. You have to check if a String == null before call length(), otherwise it will throw NullPointerException
44 . 181
21 Đặt số không ma trận
21 Set Matrix Zeroes Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place
21. 1 Thoughts about This Problem This problem can solve by following 4 steps. • check if first row and column are zero or not • mark zeros on first row and column • use mark to set elements • set first column and row by using marks in step 1
21. 2 Java Solution public class Solution { public void setZeroes(int[][] matrix) { boolean firstRowZero = false; boolean firstColumnZero = false; //set first row and column zero or not for(int i=0; i b3
begin to intersect at node c1
68. 2 Java Solution First calculate the length of two lists and find the difference. Then start from the longer list at the diff offset, iterate though 2 lists and find the node. /** * Definition for singly-linked list. * public class ListNode { int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * * } */ public class Solution {
124 . 181
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int len1 = 0; int len2 = 0; ListNode p1=headA, p2=headB; if (p1 == null . p2 == null) return null; while(p1 . = null){ len1++; p1 = p1. next; } while(p2 . =null){ len2++; p2 = p2. next; } int diff = 0; p1=headA; p2=headB; if(len1 > len2){ diff = len1-len2; int i=0; while(iright child
128 . 181
71 Giải pháp Traversal theo thứ tự cây nhị phân trong Java
• Use a stack to track nodes • Understand when to push node into the stack and when to pop node out of the stack
//Definition for binary tree public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { public ArrayList inorderTraversal(TreeNode root) { // IMPORTANT. Please reset any member data you declared, as // the same Solution instance will be reused for each test case. ArrayList lst = new ArrayList(); if(root == null) return lst; Stack stack = new Stack(); //define a pointer to track nodes TreeNode p = root; while(. stack. empty() . p . = null){ // if it is not null, push to stack //and go down the tree to left if(p . = null){ stack. push(p); p = p. left;
lạch chương trình
129 . 181
// if no left child // pop stack, process the node // then let p point to the right }else{ TreeNode t = stack. pop(); lst. add(t. val); p = t. right; } } return lst; } }
72 Solution of Iterative Binary Tree Postorder Traversal in Java The key to to iterative postorder traversal is the following. • The order of "Postorder" is. left child ->right child ->parent node. • Tìm mối quan hệ giữa nút đã truy cập trước đó và nút hiện tại • Sử dụng ngăn xếp để theo dõi các nút Khi chúng ta đi xuống cây, hãy kiểm tra nút đã truy cập trước đó. Nếu nó là cha của nút hiện tại, chúng ta nên thêm nút hiện tại vào ngăn xếp. When there is no children for current node, pop it from stack. Then the previous node become to be under the current node for next loop. //Definition for binary tree public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
public class Solution { public ArrayList postorderTraversal(TreeNode root) { ArrayList lst = new ArrayList(); if(root == null)
130 . 181
return lst; Stack stack = new Stack(); stack. push(root); TreeNode prev = null; while(. stack. empty()){ TreeNode curr = stack. peek(); // go down the tree. //check if current node is leaf, if so, process it and pop stack, //otherwise, keep going down if(prev == null . prev. left == curr . prev. right == curr){ //prev == null is the situation for the root node if(curr. left . = null){ stack. push(curr. left); }else if(curr. right . = null){ stack. push(curr. right); }else{ stack. pop(); lst. add(curr. val); } //go up the tree from left node //need to check if there is a right child //if yes, push it to stack //otherwise, process parent and pop stack }else if(curr. left == prev){ if(curr. right . = null){ ngăn xếp. push(curr. right); }else{ stack. pop(); lst. add(curr. val); } //go up the tree from right node //after coming back from right node, process parent node and pop stack. }else if(curr. right == prev){ stack. pop(); lst. add(curr. val); } prev = curr; } return lst; } }
131 . 181
73 Xác thực cây tìm kiếm nhị phân
73 Validate Binary Search Tree Problem. Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows. • The left subtree of a node contains only nodes with keys less than the node’s key. • The right subtree of a node contains only nodes with keys greater than the node’s key. • Both the left and right subtrees must also be binary search trees
73. 1 Thoughts about This Problem All values on the left sub tree must be less than root, and all values on the right sub tree must be greater than root
73. 2 Java Solution // Definition for binary tree class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { public static boolean isValidBST(TreeNode root) { return validate(root, Integer. MIN_VALUE, Integer. MAX_VALUE); } public static boolean validate(TreeNode root, int min, int max) { if (root == null) { return true; } // not in range
132 . 181
lạch chương trình
if (root. val = max) { return false; } // left subtree must be < root. val && right subtree must be > root. val return validate(root. left, min, root. val) && validate(root. right, root. val, max); } }
74 Flatten Binary Tree to Linked List Given a binary tree, flatten it to a linked list in-place. For example, Given 1 / \ 2 5 / \ \ 3 4 6
The flattened tree should look like. 1 \ 2 \ 3 \ 4 \ 5 \ 6
74. 1 Thoughts Go down through the left, when right is not null, push right to stack
74. 2 Java Solution
133 . 181
/** * Definition for binary tree * public class TreeNode { int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * * } */ public class Solution { public void flatten(TreeNode root) { Stack stack = new Stack(); TreeNode p = root; while(p . = null . . stack. empty()){ if(p. right . = null){ stack. push(p. right); } if(p. left . = null){ p. right = p. left; p. left = null; }else if(. stack. empty()){ TreeNode temp = stack. pop(); p. right=temp; } p = p. right; } } }
75 Path Sum Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. For example. Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4
134 . 181
75 tổng đường dẫn
/ \ 7 2
\ 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22
75. 1 Java Solution 1 - Using Queue Add all node to a queue and store sum value of each node to another queue. When it is a leaf node, check the stored sum value. For the tree above, the queue would be. 5 - 4 - 8 - 11 - 13 - 4 - 7 - 2 - 1. It will check node 13, 7, 2 and 1. This is a typical breadth first search(BFS) problem. /** * Definition for binary tree * public class TreeNode { int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * * } */ public class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root == null) return false; LinkedList nodes = new LinkedList(); LinkedList values = new LinkedList(); nodes. add(root); values. add(root. val); while(. nodes. isEmpty()){ TreeNode curr = nodes. poll(); int sumValue = values. poll(); if(curr. left == null && curr. right == null && sumValue==sum){ return true; } if(curr. left . = null){ nodes. add(curr. left); values. add(sumValue+curr. left. val); } if(curr. right . = null){ nodes. add(curr. right); values. add(sumValue+curr. right. val); } }
lạch chương trình
135 . 181
return false; } }
75. 2 Java Solution 2 - Recursion public boolean hasPathSum(TreeNode root, int sum) { if (root == null) return false; if (root. val == sum && (root. left == null && root. right == null)) return true; return hasPathSum(root. left, sum - root. giá trị). hasPathSum(root. right, sum - root. val); }
Thanks to nebulaliang, this solution is wonderful
76 Construct Binary Tree from Inorder and Postorder Traversal Given inorder and postorder traversal of a tree, construct the binary tree
76. 1 Throughts This problem can be illustrated by using a simple example. in-order. 4 2 5 (1) 6 7 3 8 post-order. 4 5 2 6 7 8 3 (1)
From the post-order array, we know that last element is the root. We can find the root in in-order array. Then we can identify the left and right sub-trees of the root from in-order array. Using the length of left sub-tree, we can identify left and right sub-trees in post-order array. Recursively, we can build up the tree
76. 2 Java Solution //Definition for binary tree
136 . 181
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { int inStart = 0; int inEnd = inorder. length-1; int postStart =0; int postEnd = postorder. length-1; return buildTree(inorder, inStart, inEnd, postorder, postStart, postEnd); } public TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd){ if(inStart > inEnd . postStart > postEnd) return null; int rootValue = postorder[postEnd]; TreeNode root = new TreeNode(rootValue); int k=0; for(int i=0; i< inorder. length; i++){ if(inorder[i]==rootValue){ k = i; break; } } root. left = buildTree(inorder, inStart, k-1, postorder, postStart, postStart+k-(inStart+1)); // Becuase k is not the length, it it need to -(inStart+1) to get the length root. right = buildTree(inorder, k+1, inEnd, postorder, postStart+k-inStart, postEnd-1); // postStart+k-inStart = postStart+k-(inStart+1) +1 return root; } }
137 . 181
77 Convert Sorted Array to Binary Search Tree Given an array where elements are sorted in ascending order, convert it to a height balanced BST
77. 1 Thoughts Straightforward. Đệ quy thực hiện công việc
77. 2 Java Solution // Definition for binary tree class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { public TreeNode sortedArrayToBST(int[] num) { if (num. length == 0) return null; return sortedArrayToBST(num, 0, num. length - 1); } public TreeNode sortedArrayToBST(int[] num, int start, int end) { if (start > end) return null; int mid = (start + end) / 2; TreeNode root = new TreeNode(num[mid]); root. left = sortedArrayToBST(num, start, mid - 1); root. right = sortedArrayToBST(num, mid + 1, end); return root; } }
138 . 181
78 Chuyển đổi danh sách đã sắp xếp thành cây tìm kiếm nhị phân
78 Convert Sorted List to Binary Search Tree Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST
78. 1 Thoughts If you are given an array, the problem is quite straightforward. But things get a little more complicated when you have a singly linked list instead of an array. Now you no longer have random access to an element in O(1) time. Therefore, you need to create nodes bottom-up, and assign them to its parents. The bottom-up approach enables us to access the list in its order at the same time as creating nodes
78. 2 Java Solution // Definition for singly-linked list. class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } // Definition for binary tree class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { static ListNode h; public TreeNode sortedListToBST(ListNode head) { if (head == null) return null;
lạch chương trình
139 . 181
h = head; int len = getLength(head); return sortedListToBST(0, len - 1); } // get list length public int getLength(ListNode head) { int len = 0; ListNode p = head; while (p . = null) { len++; p = p. next; } return len; } // build tree bottom-up public TreeNode sortedListToBST(int start, int end) { if (start > end) return null; // mid int mid = (start + end) / 2; TreeNode left = sortedListToBST(start, mid - 1); TreeNode root = new TreeNode(h. val); h = h. next; TreeNode right = sortedListToBST(mid + 1, end); root. left = left; root. right = right; return root; } }
79 Minimum Depth of Binary Tree Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node
140 . 181
79 Độ sâu tối thiểu của cây nhị phân
79. 1 Thoughts Need to know LinkedList is a queue. add() and remove() are the two methods to manipulate the queue
79. 2 Java Solution /** * Definition for binary tree * public class TreeNode { int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * * } */ public class Solution { public int minDepth(TreeNode root) { if(root == null){ return 0; } LinkedList nodes = new LinkedList(); LinkedList counts = new LinkedList(); nodes. add(root); counts. add(1); while(. nodes. isEmpty()){ TreeNode curr = nodes. remove(); int count = counts. remove(); if(curr. left . = null){ nodes. add(curr. left); counts. add(count+1); } if(curr. right . = null){ nodes. add(curr. right); counts. add(count+1); } if(curr. left == null && curr. right == null){ return count; } } return 0; }
lạch chương trình
141 . 181
}
80 Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree. For example. Given the below binary tree, 1 / \ 2 3
Return 6
80. 1 Thoughts 1) Recursively solve this problem 2) Get largest left sum and right sum 2) Compare to the stored maximum
80. 2 Java Solution 1 // Definition for binary tree class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { //store max value int max; public int maxPathSum(TreeNode root) { max = (root == null) ? 0 . root. val; findMax(root); return max; }
142 . 181
public int findMax(TreeNode node) { if (node == null) return 0; // recursively get sum of left and right path int left = Math. max(findMax(node. trái), 0); . max(findMax(node. right), 0); //update maximum here max = Math. max(node. val + left + right, max); // return sum of largest path of current node return node. val + Math. max(left, right); } }
80. 3 Java Solution 2 We can also use an array to store value for recursive methods. public class Solution { public int maxPathSum(TreeNode root) { int max[] = new int[1]; max[0] = Integer. MIN_VALUE; calculateSum(root, max); return max[0]; } public int calculateSum(TreeNode root, int[] max) { if (root == null) return 0; int left = calculateSum(root. left, max); int right = calculateSum(root. right, max); int current = Math. max(root. val, Math. max(root. val + left, root. val + right)); max[0] = Math. max(max[0], Math. max(current, left + root. val + right)); return current; } }
143 . 181
81 Cây Nhị Phân Cân Bằng
81 Balanced Binary Tree Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1
81. 1 Thoughts A typical recursive problem for solving tree problems
81. 2 Java Solution // Definition for binary tree class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { public boolean isBalanced(TreeNode root) { if (root == null) return true; if (getHeight(root) == -1) return false; return true; } public int getHeight(TreeNode root) { if (root == null) return 0; int left = getHeight(root. left); int right = getHeight(root. right); if (left == -1 . right == -1) return -1; if (Math. abs(left - right) > 1) { return -1;
144 . 181
lạch chương trình
} return Math. max(left, right) + 1; } }
82 Symmetric Tree 82. 1 Problem Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric. 1 / \ 2 2 / \ / \ 3 4 4 3
But the following is not. 1 / \ 2 2 \ \ 3 3
82. 2 Java Solution - Recursion This problem can be solve by using a simple recursion. The key is finding the conditions that return false, such as value is not equal, only one node(left or right) has value. public boolean isSymmetric(TreeNode root) { if (root == null) return true; return isSymmetric(root. left, root. right); } public boolean isSymmetric(TreeNode l, TreeNode r) {
145 . 181
if (l == null && r == null) { return true; . l == null) { return false; } if (l. val . = r. val) return false; if (. isSymmetric(l. left, r. right)) return false; if (. isSymmetric(l. right, r. trái)) trả về sai;
83 Bản sao đồ thị Java
LeetCode Problem
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors
146. 181
83 Bản sao đồ thị Java
83. 1 chìa khóa để giải quyết vấn đề này
• Một hàng đợi được sử dụng để thực hiện chuyển động thở đầu tiên
• một bản đồ được sử dụng để lưu trữ các nút đã truy cập. Đây là bản đồ giữa nút gốc và nút được sao chép
Sẽ rất hữu ích nếu bạn vẽ sơ đồ và hình dung vấn đề
lạch chương trình
147. 181
83 Bản sao đồ thị Java
/** * Định nghĩa cho đồ thị vô hướng. * lớp UndirectedGraphNode { nhãn int; . nhãn); . thêm (nút); . đặt (nút, newHead);
148. 181
lạch chương trình
trong khi(. xếp hàng. isEmpty()){ UndirectedGraphNode curr = queue. nhạc pop(); . người hàng xóm; . currNeighbors){ if(. bản đồ. containsKey(aNeighbor)){ UndirectedGraphNode copy = new UndirectedGraphNode(aNeighbor. label); map. put(aNeighbor,copy); map. get(curr). neighbors. add(copy); queue. add(aNeighbor); }else{ map. get(curr). neighbors. add(map. get(aNeighbor)); } } } return newHead; } }
84 How Developers Sort in Java? While analyzing source code of a large number of open source Java projects, I found Java developers frequently sort in two ways. One is using the sort() method of Collections or Arrays, and the other is using sorted data structures, such as TreeMap and TreeSet
84. 1 Using sort() Method If it is a collection, use Collections. sort() method. // Collections. sort List list = new ArrayList(); Collections. sort(list, new Comparator() { public int compare(ObjectName o1, ObjectName o2) { return o1. toString(). compareTo(o2. toString()); } });
If it is an array, use Arrays. sort() method
149 . 181
84 Các Nhà phát triển Sắp xếp trong Java như thế nào?
// Arrays. sort ObjectName[] arr = new ObjectName[10]; Arrays. sort(arr, new Comparator() { public int compare(ObjectName o1, ObjectName o2) { return o1. toString(). compareTo(o2. toString()); } });
This is very convenient if a collection or an array is already set up
84. 2 Using Sorted Data Structures If it is a list or set, use TreeSet to sort. // TreeSet Set sortedSet = new TreeSet(new Comparator() { public int compare(ObjectName o1, ObjectName o2) { return o1. toString(). compareTo(o2. toString()); } }); sortedSet. addAll(unsortedSet);
If it is a map, use TreeMap to sort. TreeMap is sorted by key. // TreeMap - using String. CASE_INSENSITIVE_ORDER which is a Comparator that orders Strings by compareToIgnoreCase Map sortedMap = new TreeMap(String. CASE_INSENSITIVE_ORDER); sortedMap. putAll(unsortedMap);
//TreeMap - In general, defined comparator Map sortedMap = new TreeMap(new Comparator() { public int compare(ObjectName o1, ObjectName o2) { return o1. toString(). compareTo(o2. toString()); } }); sortedMap. putAll(unsortedMap);
Cách tiếp cận này rất hữu ích, nếu bạn thực hiện nhiều thao tác tìm kiếm cho bộ sưu tập. The sorted data structure will give time complexity of O(logn), which is lower than O(n)
84. 3 Bad Practices There are still bad practices, such as using self-defined sorting algorithm. Take the code below for example, not only the algorithm is not efficient, but also it is not
150 . 181
lạch chương trình
readable. This happens a lot in different forms of variations. double t; for (int i = 0; i < 2; i++) for (int j = i + 1; j < 3; j++) if (r[j] < r[i]) { t = r[i]; r[i] = r[j]; r[j] = t; }
85 Solution Merge Sort LinkedList in Java LeetCode - Sort List. Sort a linked list in O(n log n) time using constant space complexity
85. 1 Keys for solving the problem • Break the list to two in the middle • Recursively sort the two sub lists • Merge the two sub lists This is my accepted answer for the problem. package algorithm. sort; class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } public class SortLinkedList { // merge sort public static ListNode mergeSortList(ListNode head) { if (head == null . head. next == null) return head;
151 . 181
85 Giải Pháp Hợp Nhất Sắp Xếp Danh Sách Liên Kết Trong Java
// count total number of elements int count = 0; ListNode p = head; while (p . = null) { count++; p = p. next; } // break up to two list int middle = count / 2; ListNode l = head, r = null; ListNode p2 = head; int countHalf = 0; while (p2 . = null) { countHalf++; ListNode next = p2. next; if (countHalf == middle) { p2. next = null; r = next; } p2 = next; } // now we have two parts l and r, recursively sort them ListNode h1 = mergeSortList(l); ListNode h2 = mergeSortList(r); // merge together ListNode merged = merge(h1, h2); return merged; } public static ListNode merge(ListNode l, ListNode r) { ListNode p1 = l; ListNode p2 = r; ListNode fakeHead = new ListNode(100); ListNode pNew = fakeHead; while (p1 . = null . p2 . = null) { if (p1 == null) { pNew. next = new ListNode(p2. val); p2 = p2. next; pNew = pNew. next; } else if (p2 == null) {
152 . 181
lạch chương trình
85 Giải Pháp Hợp Nhất Sắp Xếp Danh Sách Liên Kết Trong Java
pNew. next = new ListNode(p1. val); p1 = p1. next; pNew = pNew. next; } else { if (p1. val < p2. val) { // if(fakeHead) pNew. next = new ListNode(p1. val); p1 = p1. next; pNew = pNew. next; } else if (p1. val == p2. val) { pNew. next = new ListNode(p1. val); pNew. next. next = new ListNode(p1. val); pNew = pNew. next. next; p1 = p1. next; p2 = p2. next; } else { pNew. next = new ListNode(p2. val); p2 = p2. next; pNew = pNew. next; } } } // printList(fakeHead. next); return fakeHead. next; } public static ListNode n1 ListNode n2 ListNode n3
void main(String[] args) { = new ListNode(2);
ListNode n4 = new ListNode(3); ListNode n5 = new ListNode(4); ListNode n6 = new ListNode(5); n1. next n2. n3 tiếp theo. next n4. tiếp theo n5. next
= = = = =
n2;
n1 = mergeSortList(n1); . = không){
lạch chương trình
153. 181
Hệ thống. ngoài. in(x. val + " "); . tiếp theo. = null) { Hệ thống. ngoài. in(x. Kế tiếp. val + " "); . Kế tiếp; . ngoài. println();
đầu ra. 233445
86 Mảng Quicksort trong Java Quicksort là thuật toán chia để trị. Đầu tiên nó chia một danh sách lớn thành hai danh sách con nhỏ hơn và sau đó sắp xếp đệ quy hai danh sách con. Nếu chúng ta muốn sắp xếp một mảng mà không có thêm khoảng trống, Quicksort là một lựa chọn tốt. Trung bình, độ phức tạp thời gian là O(n log(n)). Bước cơ bản để sắp xếp một mảng như sau. • Chọn một trục, thường là trục ở giữa • Từ cả hai đầu, hoán đổi các phần tử và làm cho tất cả các phần tử ở bên trái nhỏ hơn trục và tất cả các phần tử ở bên phải lớn hơn trục • Sắp xếp đệ quy thuật toán gói phần bên trái và phần bên phải. loại; . chiều dài - 1;
154. 181
nếu (mảng == null. mảng. chiều dài == 0) trở lại; . x) Hệ thống. ngoài. in(a + " "); . ngoài. println();
đầu ra. 9 2 4 7 3 7 10 2 3 4 7 7 9 10 Lỗi tôi mắc phải là chọn phần tử ở giữa. Phần tử ở giữa không phải là (thấp+cao)/2, mà là thấp + (cao-thấp)/2. Đối với các phần khác của chương trình, chỉ cần làm theo hướng dẫn
155. 181
87 Giải pháp Sắp xếp danh sách liên kết bằng sắp xếp chèn trong Java
thuật toán
87 Giải pháp Sắp xếp danh sách liên kết bằng sắp xếp chèn trong Java Danh sách sắp xếp chèn. Sắp xếp danh sách liên kết bằng sắp xếp chèn. Đây là câu trả lời được chấp nhận của tôi cho sự cố LeetCode - Sắp xếp danh sách được liên kết bằng sắp xếp chèn trong Java. Nó là một chương trình hoàn chỉnh. Trước khi mã hóa cho điều đó, đây là một ví dụ về sắp xếp chèn từ wiki. Bạn có thể biết được thế nào là sắp xếp chèn
Mã số. thuật toán gói. loại;
156. 181
lạch chương trình
87 Giải pháp Sắp xếp danh sách liên kết bằng sắp xếp chèn trong Java
nếu (đầu == null. cái đầu. tiếp theo == null) trả lại đầu; . giá trị); . Kế tiếp; . = null) { // chèn phần tử này vào danh sách mới ListNode innerPulum = newHead; . Kế tiếp; . val con trỏ bên trong. val && con trỏ. val con trỏ bên trong. val) { con trỏ bên trong. tiếp theo = con trỏ; . tiếp theo = null;
void main(String[] args) { = new ListNode(2);
ListNode n4 = ListNode mới(3);
lạch chương trình
157. 181
ListNode n6 = ListNode mới(5); . tiếp theo n2. n3 tiếp theo. n4 tiếp theo. tiếp theo n5. Kế tiếp
= = = = =
n2;
n1 = insertionSortList(n1); . = null){ Hệ thống. ngoài. in(x. val + " "); . Kế tiếp. = null) { Hệ thống. ngoài. in(x. tiếp theo. val + " "); . Kế tiếp; . ngoài. println();
đầu ra. 233445
88 Khoảng Cách Tối Đa 88. 1 Bài toán Cho một mảng chưa sắp xếp, hãy tìm hiệu lớn nhất giữa các phần tử liên tiếp trong dạng đã sắp xếp của nó. Cố gắng giải nó trong thời gian/không gian tuyến tính. Trả về 0 nếu mảng chứa ít hơn 2 phần tử. Bạn có thể cho rằng tất cả các phần tử trong mảng là số nguyên không âm và nằm trong phạm vi số nguyên có dấu 32 bit
88. 2 Giải pháp Java 1 - Sắp xếp Một giải pháp đơn giản sẽ sắp xếp mảng trước (O(nlogn) rồi tìm khoảng cách tối đa. Ý tưởng cơ bản là chiếu từng phần tử của mảng thành một mảng
158. 181
88 Khoảng Cách Tối Đa
xô. Mỗi nhóm theo dõi các yếu tố tối đa và tối thiểu. Cuối cùng, quét danh sách nhóm, chúng ta có thể nhận được khoảng cách tối đa. Phần quan trọng là để có được khoảng thời gian. Từ. khoảng * (num[i] - min) = 0 và khoảng * (max -num[i]) = n khoảng = num. chiều dài / (tối đa - tối thiểu)
Xem bình luận nội bộ để biết thêm chi tiết
88. 3 Giải pháp Java 2 - Sắp xếp nhóm Chúng ta có thể sử dụng thuật toán giống như sắp xếp nhóm để giải quyết vấn đề này trong thời gian O(n) và không gian O(n). nhóm lớp{ int thấp; . con số. độ dài < 2){ trả về 0; . = 0) { quay lại n^= (1