刷题记录

Problem: Given a  non-empty  string  s  and a dictionary  wordDict  containing a list of  non-empty  words, add spaces in  s  to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. 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 = " catsanddog " wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [   "cats and dog",   "cat sand dog" ] Example 2: Input: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: [   "pine apple pen apple",   "pineapple pen apple",   "pine applepen apple" ] Explanation: Note that you are allowed to reuse a dictionary word. Example 3: Input: s = "catsandog...

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