facebook

题目地址：https://leetcode.com/problems/word-break/#/description 题目： 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. You may assume the dictionary does not contain duplicate words. For example, given s  =  "leetcode" , dict  =  ["leet", "code"] . Return true because  "leetcode"  can be segmented as  "leet code" . 思路： 这道题看似可以直接用twopointer来解决，但是对于s = aaaaaaa， word是aaa和aaaa是会有问题的。所以这题只能够用dynamic programming来解决。但是中间会用到twopointer的思想。 代码： public boolean wordBreak(String s, List<String> wordDict) { if (s == null || s.length() == 0 ){ return false ; } boolean [] valid = new boolean [s.length() + 1 ]; valid[ 0 ] = true ; for ( int fast = 1 ; fast <= s.length(); fast++){ for ( int slow = 0 ; slow <= fast - ...

原题地址：https://leetcode.com/problems/3sum-closest/#/description 题目： Given an array  S  of  n  integers, find three integers in  S  such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution. For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). 思路： 这道题课3sum类似，只是在判断条件上有所不同。当curr和target的diff比rst和target之间diff小的时候才会更新rst。去重和3sum是一样的。 代码： public int threeSumClosest( int [] nums, int target) { if (nums == null || nums. length <= 2 ){ return 0 ; } int rst = Integer. MAX_VALUE / 2 ; Arrays. sort (nums); for ( int i = 0 ; i <= nums. length - 3 ; i++){ while (i != 0 && nums[i - 1 ] == nums[i] && i <= nums. length - 3 ){ i++; } int j = i + 1 ; int k = nums. length - 1 ; int curr = nums[...

原题地址：https://leetcode.com/problems/3sum/#/description 题目： Given an array  S  of  n  integers, are there elements  a ,  b ,  c  in  S  such that  a  +  b  +  c  = 0? Find all unique triplets in the array which gives the sum of zero. Note:  The solution set must not contain duplicate triplets. For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ] 解法： 这道题难点在于考虑一些边界条件。例如如何去重，i, j, k指针如何变动，arrays是不是sorted等。 代码： public List<List<Integer>> threeSum( int [] nums) { List<List<Integer>> rst = new ArrayList<>(); if (nums == null || nums. length <= 2 ){ return rst; } Arrays. sort (nums); for ( int i = 0 ; i <= nums. length - 3 ; i++){ while (i != 0 && nums[i - 1 ] == nums[i] && i <= nums. length - 3 ){ i++; } int j = i + 1 ; int...