刷题记录

5/1/2028 update: The solution below is the best so far. Because fast.next and fast.next.next have been used within the while loop. So the condition of while loop is fast != null and fast.next != null. If we call fast.next when fast == null, there will be null pointer issue. public class Solution { public boolean hasCycle ( ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast . next != null) { fast = fast . next . next; slow = slow . next; if (fast == slow) return true; } return false; } } ------------------------------------------ ------------------------------------------ -------------------------------------- 思路： 一快一慢两个node, 快的走两步，慢的走一步。如果快的和慢的重合，那么这个linkedlist就有cycle。 实现： 先要检查head 和head.next是否为空。然后slow指向head, fast指向head.next。循环条件是fast != slow。在循环里面fast 和slow往下走。如果fast == null  或者fast.next == null则没有cycle。这里检查...

12/20/2017 update When there is left over of l1 or l2, just append it to the result list. no need to use while loop. res.next = l1. ----------------------------------------------------- 思路： 虽然是简单题，但是在linkedlist不熟的情况下自己做出来还是不错的。 两个linked list各取一个分别比大小，小的加入新的Linkedlist。 需要一个dummy node，来保存新的linkedlist的头，方便新的list往后扩展。 实现： while循环判断条件是l1 != null && l2 != null, 然后出去了还得判断，不为空的是那一个list。 如果其中一个不为空那么另外一个list必为空，不然就不会退出while循环了。

思路： 三种情况。 1. x在最大和最小值之间，之间插入。 2. x大于最大数，插入最大和最小之间。 3. x小于最小数，同2。 实现： 在node  == null的时候，记得让新的node.next指向自己。因为是循环链表。

Problem: Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] Analysis: 5/28/2018 Since each for loop the valid number might not start from index 0, if the nums[i - 1] has been used(the upper level), and nums[i] == nums[i -1], we can use nums[i]. --------------------------------- --------------------------------- --------------------------------- ---------------------- 1/23/2018 The numbers on the same level are not used, cuz the used mark will be removed after backtracking. So the used[i - 1] checks whether nums[i - 1] has been used at upper level. Solution: class Solution { public List< List< Integer > > permuteUnique ( int [] nums) { List< List< Integer > > res = new ArrayList<> (); if (nums == null || nums . length == 0 ) { return null; } Arrays . sort(nums);...

3/27/2018 update: 用index肯定比用substring 要快。 1/22/2018 Solution: class Solution { public List< List< String > > partition ( String s) { List< List< String > > res = new ArrayList<> (); if (s == null || s . length() == 0 ) return null; helper(res, new ArrayList<> (), s); return res; } private void helper ( List< List< String > > res, List< String > temp, String s) { if (s . length() == 0 ) { res . add( new ArrayList<> (temp)); return ; } for ( int i = 0 ; i < s . length(); i ++ ) { if (isPalindrome(s . substring( 0 , i + 1 ))) { temp . add(s . substring( 0 , i + 1 )); helper(res, temp, s . substring(i + 1 )); temp . remove(temp . size() - 1 ); } } } private boolean isPalindrome ( Stri...

Problem: Given a collection of candidate numbers ( C ) and a target number ( T ), find all unique combinations in  C  where the candidate numbers sums to  T . Each number in  C  may only be used  once  in the combination. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set  [10, 1, 2, 7, 6, 1, 5]  and target  8 , A solution set is:  [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] 3/26/2018 update: 第三遍写还是有问题。忘记了排序，index 忘记了 + 1. 思路： 和combination sum几乎一模一样。不允许重复那么就是startIndex = i+1。在for循环里面需要去除重复，也就是在树的同一层不能出现重复的数，否则答案会重复。其中一个判断条件是i != startIndex 而不是 i != 0。如果用i != 0 , [1,1,2] t =4, 这个例子就没有答案。直接把深度上重复的数给忽略了。 combination sum是数组里面不允许重复，II是在树的同一层不允许重复。 for循环一次其实就是铺开树的一层。

1/22/2018 The provided array has no duplicate, so no need to remove duplicate. The solution set won't have duplicates as the tree expands. Solution: class Solution { public List< List< Integer > > combinationSum ( int [] candidates, int target) { // write your code here List< List< Integer > > res = new ArrayList<> (); if (candidates == null) { return null; } //Arrays.sort(candidates); List< Integer > subset = new ArrayList< Integer > (); Arrays . sort(candidates); search(subset, 0 , res, candidates, target); return res; } private void search ( List< Integer > subset, int startIndex, List< List< Integer > > res, int [] candidates, int remain) { if (remain == 0 ) { res . add( new ArrayList<> (subset)); return ; } fo...