study in leetcode

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 ...