Bài đăng

Đang hiển thị bài đăng từ Tháng 10, 2020

Solution: 132 Pattern

     132 Pattern Solution Given an array of  n  integers  nums , a  132 pattern  is a subsequence of three integers  nums[i] ,  nums[j]  and  nums[k]  such that  i < j < k  and  nums[i] < nums[k] < nums[j] . Return  true  if there is a  132 pattern  in  nums , otherwise, return  false . Follow up:  The  O(n^2)  is trivial, could you come up with the  O(n logn)  or the  O(n)  solution?   Example 1: Input: nums = [1,2,3,4] Output: false Explanation: There is no 132 pattern in the sequence. Example 2: Input: nums = [3,1,4,2] Output: true Explanation: There is a 132 pattern in the sequence: [1, 4, 2]. Example 3: Input: nums = [-1,3,2,0] Output: true Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].   Constraints: n == nums.length 1 <= n <= 10 4 -10 9  <= nums[i] <= 10 9 .. Tìm bộ số thỏa mãn 2 điều kiện là: i<j<k và a[i]<a[k]<a[j] Gọi mảng minArr với minArr[i] là giá trị min trong đoạn (0,i-1), tạ

Solution: Minimum Depth of Binary Tree

Hình ảnh
  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. Note:  A leaf is a node with no children.   Example 1: Input: root = [3,9,20,null,null,15,7] Output: 2 Example 2: Input: root = [2,null,3,null,4,null,5,null,6] Output: 5   Constraints: The number of nodes in the tree is in the range  [0, 10 5 ] . -1000 <= Node.val <= 1000 .. Duyệt DFS đến khi gặp lá thì dừng và tìm min, diễn tả dưới đây. Gọi hàm đệ quy int depth(node):   Nếu node = NULL, không có gì ở đây cả, trả về độ sâu của nút đấy là 0 Nếu node->left = NULL và node->right = NULL, tức là lá, trả về độ sâu nút đó là 1 Nếu node->left = NULL, ta gọi DFS tìm độ sâu của phần bên phải depth(node->right) + 1, +1 là cộng node hiện thời, tương tự với bên trái. Khi node->left và node->right khác NULL thì ta tìm min của hai nhánh đấy, + 1 node hiện thời Sourcecode: 

Solutions Problems October

Hình ảnh
 Cũng gần 3 tháng rồi mình chưa bắt đầu lại thói quen này, viết vậy đủ hiểu độ trì của bản thân.  Minimum Number of Arrows to Burst Balloons There are some spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter, and hence the x-coordinates of start and end of the diameter suffice. The start is always smaller than the end. An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with  x start  and  x end  bursts by an arrow shot at  x  if  x start  ≤ x ≤ x end . There is no limit to the number of arrows that can be shot. An arrow once shot keeps traveling up infinitely. Given an array  points  where  points[i] = [x start , x end ] , return  the minimum number of arrows that must be shot to burst all balloons .   Example 1: Input: points = [[10,16],[2,8],[1,6],[7,12]] Output: 2 Explanation: One way is t