Le Quang Duy

Given a binary tree where each path going from the root to any leaf form a  valid sequence , check if a given string is a  valid sequence  in such binary tree.  We get the given string from the concatenation of an array of integers  arr  and the concatenation of all values of the nodes along a path results in a  sequence  in the given binary tree. Example 1: Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1] Output: true Explanation: The path 0 -> 1 -> 0 -> 1 is a valid sequence (green color in the figure). Other valid sequences are: 0 -> 1 -> 1 -> 0 0 -> 0 -> 0 Example 2: Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,0,1] Output: false Explanation: The path 0 -> 0 -> 1 does not exist, therefore it is not even a sequence. Example 3: Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,1] Output: false Explanation: The path 0 -> 1 -> 1 is a sequence, but it is not a valid sequence. Constraints:

Given a  non-empty  binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain  at least one node  and does not need to go through the root. Example 1: Input: [1,2,3] 1 / \ 2 3 Output: 6 Example 2: Input: [-10,9,20,null,null,15,7]   -10    / \   9   20     /  \     15   7 Output: 42 Đứng tại một nút nào đó, có 2 trường hợp xảy ra là root + left + right > max và root + max(left,right) sau này hoặc hiện tại sẽ lớn hơn max. Căn cứ vào đó ta duyệt DFS để tìm ra. Thấy cái hình này khá dễ hiểu trên Medium: Đây là code trên Java, lâu rồi không biết C/C++, giờ cảm giác quay lại với nó mệt thật, lâu hơn nữa là không viết trên Pascal, dù từng được giải cao với nó. Khi mình học một ngôn ngữ mới thì mình lại gần như quên hết các ngôn ngữ cũ. Nhưng khi vọng khi cần quay lại, vẫn phát huy được phần

You have a queue of integers, you need to retrieve the first unique integer in the queue. Implement the  FirstUnique  class: FirstUnique(int[] nums)  Initializes the object with the numbers in the queue. int showFirstUnique()  returns the value of  the first unique  integer of the queue, and returns  -1  if there is no such integer. void add(int value)  insert value to the queue. Example 1: Input: ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[2,3,5]],[],[5],[],[2],[],[3],[]] Output: [null,2,null,2,null,3,null,-1] Explanation: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); // return 2 firstUnique.add(5); // the queue is now [2,3,5,5] firstUnique.showFirstUnique(); // return 2 firstUnique.add(2);            // the queue is now [2,3,5,5,2] firstUnique.showFirstUnique(); // return 3 fir

  Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area. Example: Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4 Gần như bài hôm qua, vẽ cái bảng ra là bạn sẽ thấy công thức truy hồi: dp[i][j] = matrix[i][j] = 0 ->  min(dp[i-1][j],[dp[i][j-1],dp[i-1][j-1] + 1 | 0 Hãy tưởng tượng nếu đứng ở một vị trí bất kỳ [i][j], nếu có một hình vuông với góc trái trên cùng là [i][j] thì ba cái [i+1][j], [i][j+1], [i+1][j+1] phải đều bằng 1 và bản thân [i][j] cũng phải bằng 1. Lý do ta lấy min vì ta muốn chắc chắn rằng cả ba cạnh này đều bằng nhau. Khó nhất phần tìm ra công thức truy hồi thôi. Còn đây là code Java của mình, độ phức tạp là O(M*N) và độ phức tạp không gian là O(N) như bài hôm qua. Hết rồi. Hẹn gặp lại bạn ngày mai. Cảm ơn !

Given two strings  text1  and  text2 , return the length of their longest common subsequence. A  subsequence  of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A  common subsequence  of two strings is a subsequence that is common to both strings. If there is no common subsequence, return 0. Example 1: Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3. Example 2: Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is "abc" and its length is 3. Example 3: Input: text1 = "abc", text2 = "def" Output: 0 Explanation: There is no such common subsequence, so the result is 0.

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example 1: Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum   jump length is 0, which makes it impossible to reach the last index. .Đứng tại một vị trí x sẽ nhảy được <=nums[x]. Giả sử đang đứng ở vị trí 3 trong dãy [2,3,0,1,4]. 3+1 >=4, vì thế từ 3 luôn nhảy được tới 4, vì thế từ giờ ta coi luôn đích sẽ là 3. Đứng ở vị trí 2, 2+0<3, ta không làm gì cả. Vị trí 1, 1+3>=3, cập nhật lại 1, vị trí 0, 0+2>=1, cập nhật lại 0. Nếu cuối cùng x = 0 tức kết quả bài toán sẽ là true. Cảm ơn.

Design and implement a data structure for  Least Recently Used (LRU) cache . It should support the following operations:  get  and  put . get(key)  - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value)  - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. The cache is initialized with a  positive  capacity. Follow up: Could you do both operations in  O(1)  time complexity? Đây là một bài toán cực kỳ hay và tôi đã chinh phục được nó trong một buổi tối, toàn sai mấy cái không đáng có. LRU - Least Recently Used Cache, ta sẽ loại bỏ khỏi Cache phần từ lâu chưa được dùng tới nhất. Thao tác get(key) và put(key,value), chúng ta sẽ dùng hai cấu trúc dữ liệu Doubly Linked List và HashTable theo tôi tìm hiểu là tối ưu nhất thời điểm này. Phần tử đầu list chính là phần tử lâu chưa được dùng tới nhấ

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. Example 1: Input: [5,7] Output: 4 Example 2: Input: [0,1] Output: 0 Bit ơi là bit. Giả sử dãy [80,85] hệ nhị phân thành: [1010000, 1010001, 1010010, 1010011, 1010100, 1010101]. Viết theo hàng dọc: 1010|000 1010|001 1010|010 1010|011 1010|100  1010|101  Phần bên trái khi tác động toán tử & sẽ không ảnh hưởng gì cả. Vậy 1010000 chính là kết quả của bài toán theo tính chất &. Bài toán trở nên rất đơn giản, dịch bit về bên phải cho đến khi  đoạn đầu và đoạn cuối bằng nhau, ở đây là 1010000 và 1010101. Ghi nhớ số lần dịch là carry. Kết quả bài toán là dịch ngược bên trái lại bằng số lần đã dịch bên phải. Cảm ơn !

Given an array of integers and an integer  k , you need to find the total number of continuous subarrays whose sum equals to  k . Example 1: Input: nums = [1,1,1], k = 2 Output: 2 Note: The length of the array is in range [1, 20,000]. The range of numbers in the array is [-1000, 1000] and the range of the integer  k  is [-1e7, 1e7]. Không biết ngày xưa nghĩ thế nào, nhưng giờ mình viết bài này chưa tới 5 dòng .. Với [1,1,1] cộng cuốn chiếu được sum = [1,2,3], trên mảng sum, giống như đề bài cũ tôi làm tìm đoạn dài nhất 0,1. Ta thêm 0 [1,2,3] . Nếu sum-k tồn tại trong map, biến res = res + map(sum-k). Nếu sum = 1,2,3 đã tồn tại trong map, ta sẽ cộng sum thêm 1. Ví dụ [0,0,0] với tổng bằng 0, thì ta có bảng map (0,1), res = 1 rồi (0,2), res = 3 rồi (0,3), res = 6. Cảm ơn bạn !

ecall that a binary search tree is a binary tree where for every  node , any descendant of  node.left  has a value  <   node.val , and any descendant of  node.right  has a value  >   node.val .  Also recall that a preorder traversal displays the value of the  node  first, then traverses  node.left , then traverses  node.right .) Example 1: Input: [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12] Note:   1 <= preorder.length <= 100 The values of  preorder  are distinct. Đồ thị và cây là hai mảng yếu nhất của tôi, chắc chắn tôi phải làm nhiều những bài như thế này hơn. Trong bài toán này, nút gốc root luôn là nút đầu mảng theo tính chất của preorder. Sẽ có hai trường hợp xảy ra khi duyệt mảng sau nút gốc là nhỏ hơn hoặc lớn hơn root. Trường hợp nhỏ hơn, ta thêm vào bên trái root, ngược lại ta thêm vào bên phải. Như ví dụ trên: 5 < 8 nên 8.left = 5 . 1 <5 nên 5.left = 1. Như vậy, ta có một stack để lưu nốt hiện thời. Phần tạo cây bên phải đã được giải quy

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e.,  [0,1,2,4,5,6,7]  might become  [4,5,6,7,0,1,2] ). You are given a target value to search. If found in the array return its index, otherwise return  -1 . You may assume no duplicate exists in the array. Your algorithm's runtime complexity must be in the order of  O (log  n ). Example 1: Input: nums = [ 4,5,6,7,0,1,2] , target = 0 Output: 4 Example 2: Input: nums = [ 4,5,6,7,0,1,2] , target = 3 Output: -1 Ban đầu tôi cũng khá là thắc mắc làm thế nào để implement bài này với O(logn), nếu đề bài cho chỉ số rồi bắt tìm chẳng hạn, với rotate array thì tôi sẽ tìm công thức. Nhưng đây lại cho giá trị. Tìm kiếm phị phân ? Trên một mảng không sắp xếp ? Thực ra nếu ta mặc định mảng này là không sắp xếp thì sẽ không làm được bài này. Key của bài này ở chỗ ta hiểu mảng của đề bài luôn có thể chia làm hai phần, một phần tăng, và một phẩn giảm. Giả sử [4,5,6,7,0,1,2] ta c

Given a  m  x  n  grid filled with non-negative numbers, find a path from top left to bottom right which  minimizes  the sum of all numbers along its path. Note:  You can only move either down or right at any point in time. Example: Input: [   [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum. Ban đầu tôi nghĩ đến dùng Dijkstra, nhưng sau một hồi quan sát thì thấy nó rất giống bài Kim tự tháp ngày xưa tôi từng làm, vâng, và tôi sẽ implement nó bằng quy hoạch động. Đề bài chỉ cho xuất phát từ điểm đầu góc trái, bắt đi đến điểm cuối góc phải, vì thế quy hoạch động càng dễ hơn. Thêm nữa là chỉ được phép đi xuống dưới, hoặc đi sang phải, thế thì nghiệm tại vị trí bất kỳ [i][j] sẽ bằng min điểm xuống dưới đã có nghiệm gần nhất (chính là điểm trên nó) + grid[i][j] hoặc điểm bên phải tương tự. Suy ra ta có công thức truy hồi: dp[i][j] = min (dp[i-1][j],dp[i][j-1]) + grid[i][j]. Xong rồi nhé. Đây là code trên Java: Hết rồi,

   Number of Islands Given a 2d grid map of  '1' s (land) and  '0' s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1: Input: 11110 11010 11000 00000 Output:  1 Example 2: Input: 11000 11000 00100 00011 Output: 3 Duyệt trên ma trận, nếu gặp số 1, chạy DFS trên nó theo bốn hướng như đề bài, nhớ khi chạy phải đánh dấu là đã duyệt rồi để không bị trùng lặp về sau. Độ phức tạp là độ phức tạp của không gian ma trận. O(m*n). Code implement by Java: Hết rồi, hẹn gặp Leetcode vào ngày mai. Cảm ơn bạn !

   Valid Parenthesis String Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules: Any left parenthesis  '('  must have a corresponding right parenthesis  ')' . Any right parenthesis  ')'  must have a corresponding left parenthesis  '(' . Left parenthesis  '('  must go before the corresponding right parenthesis  ')' . '*'  could be treated as a single right parenthesis  ')'  or a single left parenthesis  '('  or an empty string. An empty string is also valid. Example 1: Input: "()" Output: True Example 2: Input: "(*)" Output: True Example 3: Input: "(*))" Output: True Note: The string size will be in the range [1, 100]. Cách làm thường thấy đối với bài này là quy hoạch động nhưng với O(N*N). Khô