刷题记录

Problem: Given a (singly) linked list with head node  root , write a function to split the linked list into  k  consecutive linked list "parts". The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null. The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later. Return a List of ListNode's representing the linked list parts that are formed. Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ] Example 1: Input: root = [1, 2, 3], k = 5 Output: [[1],[2],[3],[],[]] Explanation: The input and each element of the output are ListNodes, not arrays. For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null. The first element output[0] has output[0].val = 1, output[0].next = null....

Problem: Given an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"] , Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] Note: All inputs will be in lowercase. The order of your output does not matter. Analysis: What's in common of anagrams is they are the same if we sort them. So use a map, key is the sorted string, value is the anagram list.  Solution: class Solution { public List< List< String > > groupAnagrams ( String [] strs) { List< List< String > > res = new ArrayList<> (); if (strs == null || strs . length == 0 ) return res; Map< String , List< String > > map = new HashMap<> (); for ( int i = 0 ; i < strs . length; i ++ ) { char [] ch...

Problem: There are  N  rooms and you start in room  0 .  Each room has a distinct number in  0, 1, 2, ..., N-1 , and each room may have some keys to access the next room.  Formally, each room  i  has a list of keys  rooms[i] , and each key  rooms[i][j]  is an integer in  [0, 1, ..., N-1]  where  N = rooms.length .  A key  rooms[i][j] = v  opens the room with number  v . Initially, all the rooms start locked (except for room  0 ).  You can walk back and forth between rooms freely. Return  true  if and only if you can enter every room. Example 1: Input: [[1],[2],[3],[]] Output: true Explanation: We start in room 0, and pick up key 1. We then go to room 1, and pick up key 2. We then go to room 2, and pick up key 3. We then go to room 3. Since we were able to go to every room, we return true. Example 2: Input: [[1,3],[3,0,1],[2],[0]] Output: false Expla...

Problem: Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to  the original place . The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are  R  (Right),  L (Left),  U  (Up) and  D  (down). The output should be true or false representing whether the robot makes a circle. Example 1: Input: "UD" Output: true Example 2: Input: "LL" Output: false Analysis: skip Solution: class Solution { public boolean judgeCircle ( String moves) { int [] pos = new int [ 2 ]; for ( char c : moves . toCharArray()) { switch (c) { case 'U' : pos[ 0 ] -- ; break ; case 'D' : pos[ 0 ] ++ ; break ; case 'L' : pos[ 1 ] -- ; break ; ...

Problem: Given an array of integers and an integer  k , you need to find the number of  unique  k-diff pairs in the array. Here a  k-diff  pair is defined as an integer pair (i, j), where  i  and  j  are both numbers in the array and their  absolute difference  is  k . Example 1: Input: [3, 1, 4, 1, 5], k = 2 Output: 2 Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5). Although we have two 1s in the input, we should only return the number of unique pairs. Example 2: Input: [1, 2, 3, 4, 5], k = 1 Output: 4 Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5). Example 3: Input: [1, 3, 1, 5, 4], k = 0 Output: 1 Explanation: There is one 0-diff pair in the array, (1, 1). Analysis: 通过这道题可以总结一条规律。同向双指针fast pointer不需要去重。 Solution: class Solution { public int findPairs ( int [] nums, int k) { if (nums == null || nums . length =...

Problem: Given a non-empty 2D array  grid  of 0's and 1's, an  island  is a group of  1 's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. Count the number of  distinct  islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other. Example 1: 11000 11000 00011 00011 Given the above grid map, return  1 . Example 2: 11011 10000 00001 11011 Given the above grid map, return  3 . Notice that: 11 1 and 1 11 are considered different island shapes, because we do not consider reflection / rotation. Analysis: The tricky part is how to make same shape the same. We store the diff of each point in the shape by x-axial and y axial separately from the start to a list.  11000 11000 00011 00011 The coordinates of last three points of the first ...

Problem: A string  S  of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts. Example 1: Input: S = "ababcbacadefegdehijhklij" Output: [9,7,8] Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts. Note: S  will have length in range  [1, 500] . S  will consist of lowercase letters ( 'a'  to  'z' ) only. Analysis: Greedy. Use a map the store the last index of each char's appearance. what makes the partition successful is that the last appearance (end) stops to increment. It means no char from start to end appears after end. Solution: class Solution { ...

Problem: Given a binary tree  where every node has a unique value , and a target key  k , find the value of the nearest leaf node to target  k  in the tree. Here,  nearest  to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a  leaf  if it has no children. In the following examples, the input tree is represented in flattened form row by row. The actual  root  tree given will be a TreeNode object. Example 1: Input: root = [1, 3, 2], k = 1 Diagram of binary tree: 1 / \ 3 2 Output: 2 (or 3) Explanation: Either 2 or 3 is the nearest leaf node to the target of 1. Example 2: Input: root = [1], k = 1 Output: 1 Explanation: The nearest leaf node is the root node itself. Example 3: Input: root = [1,2,3,4,null,null,null,5,null,6], k = 2 Diagram of binary tree: 1 / \ 2 3 /...

Problem: Implement a basic calculator to evaluate a simple expression string. The expression string contains only  non-negative  integers,  + ,  - ,  * ,  /  operators and empty spaces  . The integer division should truncate toward zero. Example 1: Input: "3+2*2" Output: 7 Example 2: Input: " 3/2 " Output: 1 Example 3: Input: " 3+5 / 2 " Output: 5 Analysis: Very similar to Basic Calculator I. The idea is to calculate the temp result whenever a sign is met and push into stack. If the prev sign is * or /, grab the stack top calc together. For instance 3 + 2* 2. +: calc +3 push into stack *: calc +2 push into stack string end: calc 2*2 push into stack Solution: Beware that the number might over 1 digit. class Solution { public int calculate ( String s) { Stack< Integer > stack = new Stack<> (); char sign = '+' ; int num = 0 ; for ( int i = 0 ; i < s . leng...

Problem: Find all possible combinations of  k  numbers that add up to a number  n , given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Note: All numbers will be positive integers. The solution set must not contain duplicate combinations. Example 1: Input: k = 3, n = 7 Output: [[1,2,4]] Example 2: Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]] Analysis: Combination sum 马甲题，顺便复习了一下DFS. Solution: class Solution { public List< List< Integer > > combinationSum3 ( int k, int n) { List< List< Integer > > res = new ArrayList<> (); dfs(res, new ArrayList<> (), 1 , n, k); return res; } private void dfs ( List< List< Integer > > res, List< Integer > list, int index, int target, int k) { if (target == 0 && list . size() == k) { res . add( new ArrayList...

Problem: Given a string  s , you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation. Example 1: Input: "aacecaaa" Output: "aaacecaaa" Example 2: Input: "abcd" Output: "dcbabcd" Analysis: 最佳答案是KMP算法，在面试中不可能做得出来。 "abcd" reverse it to dcab, check whether reversed string's substring at the index 0 of s. If yes, the shortest palindrome is r.substring(0, i) + s. i  = 0 sub:dcab i = 1 sub: cab i = 2 sub: ab (qualify res = dc + ab + cd) Solution: class Solution { public String shortestPalindrome ( String s) { if (s == null || s . length() == 0 ) return "" ; StringBuilder sb = new StringBuilder (s); String r = sb . reverse() . toString(); for ( int i = 0 ; i < r . length(); i ++ ) { if (s . startsWith(r . substr...

Problem: There are a total of  n  courses you have to take, labeled from  0  to  n-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 , return the ordering of courses you should take to finish all courses. There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array. Example 1: Input: 2, [[1,0]] Output: [0,1] Explanation:  There are a total of 2 courses to take. To take course 1 you should have finished   course 0. So the correct course order is [0,1] . Example 2: Input: 4, [[1,0],[2,0],[3,1],[3,2]] Output: [0,1,2,3] or [0,2,1,3] Explanation:  There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both cours...