Bài đăng

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

MayChallenge (61) | Edit Distance

Hình ảnh
Given two words  word1  and  word2 , find the minimum number of operations required to convert  word1  to  word2 . You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a character Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') Example 2: Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u') In book of Le Minh Hoang, the problem is type Dynamid Programing. Build the matrix word2.length() row and word1.length() colum. While wo

MayChallenge (59) (60) | Course Schedule And K Closest To Point Origin

Hình ảnh
There are a total of  numCourses  courses you have to take, labeled from  0  to  numCourses-1 . Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:  [0,1] Given the total number of courses and a list of prerequisite  pairs , is it possible for you to finish all courses? Example 1: Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation:  There are a total of 2 courses to take.   To take course 1 you should have finished course 0. So it is possible. Example 2: Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation:  There are a total of 2 courses to take.   To take course 1 you should have finished course 0, and to take course 0 you should   also have finished course 1. So it is impossible. Constraints: The input prerequisites is a graph represented by  a list of edges , not adjacency matrices. Read more about  how

MayChalenge (53-54-55-56-57-58)

Hình ảnh
Given two lists of  closed  intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. (Formally, a closed interval  [a, b]  (with  a <= b ) denotes the set of real numbers  x  with  a <= x <= b .  The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval.  For example, the intersection of [1, 3] and [2, 4] is [2, 3].) Example 1: Input: A = [[0,2],[5,10],[13,23],[24,25]] , B = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]] Note: 0 <= A.length < 1000 0 <= B.length < 1000 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9 I am busy, so i only show my code, the explain will coming: Return the root node of a binary  search  tree that matches the given  preorder  traversal. (Recall that a binary search tree is a binary tree where for every  node , any de

MayChallenge (52) | Sort Character By Frequently

Hình ảnh
Given a string, sort it in decreasing order based on the frequency of characters. Example 1: Input: "tree" Output: "eert" Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer. Example 2: Input: "cccaaa" Output: "cccaaa" Explanation: Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer. Note that "cacaca" is incorrect, as the same characters must be together. Example 3: Input: "Aabb" Output: "bbAa" Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters. If you use arr to save the map, a program will be allocate a memory consecutive, it is not good idea for space memory. So, we are

MayChallenge (51) } | Kth Smallest Element in a BST

Hình ảnh
Given a binary search tree, write a function  kthSmallest  to find the  k th smallest element in it. Example 1: Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \   2 Output: 1 Example 2: Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 Output: 3 Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine? Constraints: The number of elements of the BST is between  1  to  10^4 . You may assume  k  is always valid,  1 ≤ k ≤ BST's total elements . I use binary search tree to solve this problem, this important is function count(), let view code: Find Kth Smallest in BST Given a  m * n  matrix of ones and zeros, return how many  square  submatrices have all ones. Example 1: Input: matrix = [   [0,1,1,1],   [1,1,1,1],   [0,1,1,1] ] Output: 15 Explanation: There are 10 squares of s

MayChallenge (48) (49) | Permution in String & Online Stock Span

Hình ảnh
Given two strings  s1  and  s2 , write a function to return true if  s2  contains the permutation of  s1 . In other words, one of the first string's permutations is the  substring  of the second string. Example 1: Input: s1 = "ab" s2 = "eidbaooo" Output: True Explanation: s2 contains one permutation of s1 ("ba"). Example 2: Input: s1= "ab" s2 = "eidboaoo" Output: False Note: The input strings only contain lower case letters. The length of both given strings is in range [1, 10,000]. Similar the previous problem, i was apcepted it, it approach optimize sliding window but i can understand, so, i wil say it it another article. Write a class  StockSpanner   which collects daily price quotes for some stock, and returns the   span  of that stock's price for the current day. The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for w