facebook

原题链接：https://leetcode.com/problems/decode-ways/#/description 题目： A message containing letters from  A-Z  is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message  "12" , it could be decoded as  "AB"  (1 2) or  "L"  (12). The number of ways decoding  "12"  is 2. 解题思路：这道题主要是要想到用dynamic programming来保存前一位和前两位的decode方法数。另外一些corner case比如以0开头的或者超过26的需要考虑。 代码： public int numDecodings(String s) { if (s == null || s.length() == 0 ){ return 0 ; } int [] dp = new int [s.length() + 1 ]; dp[ 0 ] = 1 ; dp[ 1 ] = valid(s.substring( 0 , 1 )) ? 1 : 0 ; for ( int i = 2 ; i <= s.length() ; i++){ if (valid(s.substring(i - 1 , i))){ dp[i] = dp[i - 1 ]; } if (valid(s.substring(i - 2 , i))){ ...

题目地址：https://leetcode.com/problems/word-break-ii/#/description 题目： 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. You may assume the dictionary does not contain duplicate words. Return all such possible sentences. For example, given s  =  "catsanddog" , dict  =  ["cat", "cats", "and", "sand", "dog"] . A solution is  ["cats and dog", "cat sand dog"] . 思路： 解决此题的关键在于用dfs来返回从某个起点开始的所有可行的解；用map是为了来memorize之前算过的解，可以大幅度减少运行时间；另外还有一些小技巧比如maxLen的使用来节省时间等。红色标记部分是memorization。 代码： Map <Integer, List<String>> map = new HashMap<>(); public List<String> wordBreak(String s, List<String> wordDict) { List<String> rst = new ArrayList<>(); if (s == null || s.length() == 0 ){ return rst; } int maxLen = - ...

题目地址：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...