study in leetcode

Medium Given a  non-empty  string  s  and a dictionary  wordDict  containing a list of  non-empty  words, determine if  s  can be segmented into a space-separated sequence of one or more dictionary words. Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1: Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code" . Example 2: Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: true Explanation: Return true because " applepenapple " can be segmented as " apple pen apple " .   Note that you are allowed to reuse a dictionary word. Example 3: Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "a...

Easy Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree  [1,2,2,3,4,4,3]  is symmetric: 1 / \ 2 2 / \ / \ 3 4 4 3 But the following  [1,2,2,null,3,null,3]  is not: 1 / \ 2 2 \ \ 3 3 Solution: Take two trees as an argument, return true if two trees are mirror. class Solution { public boolean isSymmetric(TreeNode root) { if(root == null) return true; return isSymmetric(root.left,root.right); } public boolean isSymmetric(TreeNode root1, TreeNode root2){ if(root1 == null && root2 == null){ return true; } if(root1 == null || root2 == null){ return false; } if(root1.val != root2.val){ return false; }else{ return isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left); } }...

Medium Given an undirected  graph , return  true  if and only if it is bipartite. Recall that a graph is  bipartite  if we can split it's set of nodes into two independent subsets A and B such that  every edge in the graph has one node in A and another node in B. The graph is given in the following form:  graph[i]  is a list of indexes  j  for which the edge between nodes  i  and  j  exists .  Each node is an integer between  0  and  graph.length - 1 .  There are no self edges or parallel edges:  graph[i]  does not contain  i , and it doesn't contain any element twice. Example 1: Input: [[1,3], [0,2], [1,3], [0,2]] Output: true Explanation: The graph looks like this: 0----1 | | | | 3----2 We can divide the vertices into two groups: {0, 2} and {1, 3}. Example 2: Input: [[1,2,3], [0,2], [0,1,3], [0,2]] Output: false Explanation: The graph looks...

Hard Implement a basic calculator to evaluate a simple expression string. The expression string may contain open  (  and closing parentheses  ) , the plus  +  or minus sign  - ,  non-negative  integers and empty spaces  . Example 1: Input: "1 + 1" Output: 2 Example 2: Input: " 2-1 + 2 " Output: 3 Example 3: Input: "(1+(4+5+2)-3)+(6+8)" Output: 23 Solution: Digit: when scan one digit, we can start one new number. when number is over, add this number to sum. Because this number must have sign and previous result. +: assign 1 to sign for next number. -:  assign -1 to sign for next numer. (: push the previous result before this parenthesis and the sign for the result of this parenthesis into stack. set sum to 0, just calculate the new result with the parethesis. ):pop up two numbers from stack. the first is the sign before parenthesis, the second is the temporary result before the pair of parenthesis. we add...

Medium Given an encoded string, return it's decoded string. The encoding rule is:  k[encoded_string] , where the  encoded_string  inside the square brackets is being repeated exactly  k  times. Note that  k  is guaranteed to be a positive integer. You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers,  k . For example, there won't be input like  3a  or  2[4] . Examples: s = "3[a]2[bc]", return "aaabcbc". s = "3[a2[c]]", return "accaccacc". s = "2[abc]3[cd]ef", return "abcabccdcdcdef". My code: class Solution { public String decodeString(String s) { if(s == null) return null; if(s.length() == 0) return s; int n = s.length(); return decodeString(s,0,n-1); } public...

Medium In an exam room, there are  N  seats in a single row, numbered  0, 1, 2, ..., N-1 . When a student enters the room, they must sit in the seat that maximizes the distance to the closest person.  If there are multiple such seats, they sit in the seat with the lowest number.  (Also, if no one is in the room, then the student sits at seat number 0.) Return a class  ExamRoom(int N)  that exposes two functions:  ExamRoom.seat()  returning an  int  representing what seat the student sat in, and  ExamRoom.leave(int p)  representing that the student in seat number  p  now leaves the room.  It is guaranteed that any calls to  ExamRoom.leave(p)  have a student sitting in seat  p . Example 1: Input: ["ExamRoom","seat","seat","seat","seat","leave","seat"] , [[10],[],[],[],[],[4],[]] Output: [null,0,9,4,2,null,5] Explanation : ExamRoom(10) -> null seat() -> 0, no one is in t...

Hard There are two sorted arrays  nums1  and  nums2  of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume  nums1  and  nums2  cannot be both empty. Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 Solution: the median means divide the set into two equal length set, or one set always has one more element than the other set. Let's cut A into two set at random i left_A | right_A A [0] , A [1] , ..., A [i-1] | A [i] , A [i+1] , ..., A [m-1] 0 1 i-1 i i+1 m-1 m Since A has m elements, so there are m+1 ways of cutting. when index = 0, length(left_A) = 0, when index = m, length(left_A) = m With the same way, cut  B  into two parts at a random position  j : left_B ...

Medium Given a C++ program, remove comments from it. The program  source  is an array where  source[i]  is the  i -th line of the source code. This represents the result of splitting the original source code string by the newline character  \n . In C++, there are two types of comments, line comments, and block comments. The string  //  denotes a line comment, which represents that it and rest of the characters to the right of it in the same line should be ignored. The string  /*  denotes a block comment, which represents that all characters until the next (non-overlapping) occurrence of  */  should be ignored. (Here, occurrences happen in reading order: line by line from left to right.) To be clear, the string  /*/  does not yet end the block comment, as the ending would be overlapping the beginning. The first effective comment takes precedence over others: if the string  //  occurs in a blo...

Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example: 1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB ... Example 1: Input: 1 Output: "A" Example 2: Input: 28 Output: "AB" Example 3: Input: 701 Output: "ZY" Wrong code: test case: 52 class Solution { public String convertToTitle(int n) { char[] map = {' ','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}; StringBuilder sb = new StringBuilder(); while(n!=0){ int last = n % 26; if(last == 0){ last = 26; char lastC = map[last]; ...

You are given an  n  x  n  2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Note: You have to rotate the image  in-place , which means you have to modify the input 2D matrix directly.  DO NOT  allocate another 2D matrix and do the rotation. Example 1: Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ], rotate the input matrix in-place such that it becomes: [ [7,4,1], [8,5,2], [9,6,3] ] Example 2: Given input matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ], rotate the input matrix in-place such that it becomes: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ] wrong code: class Solution { public void rotate(int[][] matrix) { int n = matrix.length; for(int i = 0; i < n ; i++){ rotateOneLayer(matrix,0,n-1); } } public void rotateOneLayer(int[][] matrix, int start, int end){ fo...

Share 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. class Solution { public class CharFre{ public char c; public int fre; public CharFre(ch...