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 Show 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ẫnChươ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 C có tốt cho LeetCode không?C, C++, Java, Python được coi là ngôn ngữ lập trình được ưa thích nhất để giải quyết các vấn đề trên Hackerrank, Codechef hoặc LeetCode .
300 câu hỏi LeetCode đã đủ chưa?300 TRĂM TRĂM LÀ NGƯỜI BẮT ĐẦU GIAO DỊCH
. Hầu hết mọi người chuẩn bị cho các cuộc phỏng vấn trong 100-200 vấn đề và sau đó ngừng làm leetcode. Bạn thực hiện một vài phép đánh đổi trong một khoảng thời gian giới hạn và bạn sẽ đạt được 100/150 rất nhanh, nếu bạn làm được nhiều câu hỏi dễ thì bạn còn đạt được điểm đó nhanh hơn.
Bạn có thể xem các giải pháp trong LeetCode không?Ngoài ra, hoàn toàn không có vấn đề gì nếu bạn không thể giải quyết vấn đề LeetCode và xem giải pháp .
Cách nhanh nhất để giải quyết vấn đề LeetCode là gì?Hướng dẫn mài Leetcode . Thực hiện theo một danh sách. . Tránh nhìn vào các giải pháp một cách dễ dàng. . Câu hỏi phỏng vấn không đi kèm với gợi ý. . Hãy nhất quán. . Biến mất động lực thành cơ hội học tập. . Tham gia các cuộc thi. . tiếp tục hối hả |
