注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
大家这三道题有什么好的解法吗。自己做了和看了网上的答案,感觉都不是很好地能记下来,很容易忘
Permutations:- public class Solution {
- public ArrayList<ArrayList<Integer>> permute(int[] nums) {
- ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
-
- result.add(new ArrayList<Integer>());
-
- for(int i = 0; i < nums.length; i++)
- {
- ArrayList<ArrayList<Integer>> curr = new ArrayList<ArrayList<Integer>>();
- for(ArrayList<Integer> l : result)
- {
- for(int j = 0; j < l.size()+1; j++)
- {
- l.add(j, nums[i]);
- ArrayList<Integer> temp = new ArrayList<Integer>(l);
- curr.add(temp);
- l.remove(j);
- }
- }
- result = new ArrayList<ArrayList<Integer>>(curr);
- }
- return result;
- }
- }
复制代码 Word ladder:- public class Solution {
- public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
- if (wordDict.size() == 0)
- return 0;
-
- wordDict.add(endWord);
-
- LinkedList<String> wordQueue = new LinkedList<String>();
- LinkedList<Integer> distanceQueue = new LinkedList<Integer>();
-
- wordQueue.add(beginWord);
- distanceQueue.add(1);
-
- //track the shortest path
- int result = Integer.MAX_VALUE;
- while (!wordQueue.isEmpty()) {
- String currWord = wordQueue.pop();
- Integer currDistance = distanceQueue.pop();
-
- if (currWord.equals(endWord)) {
- result = Math.min(result, currDistance);
- }
-
- for (int i = 0; i < currWord.length(); i++) {
- char[] currCharArr = currWord.toCharArray();
- for (char c = 'a'; c <= 'z'; c++) {
- currCharArr[i] = c;
-
- String newWord = new String(currCharArr);
- if (wordDict.contains(newWord)) {
- wordQueue.add(newWord);
- distanceQueue.add(currDistance + 1);
- wordDict.remove(newWord);
- }
- }
- }
- }
-
- if (result < Integer.MAX_VALUE)
- return result;
- else
- return 0;
- }
-
-
- }
复制代码 Word break:- public class Solution {
- public boolean wordBreak(String s, Set<String> wordDict) {
- boolean[] t = new boolean[s.length()+1];
- t[0] = true;
-
- for(int i = 0; i<s.length(); i++)
- {
- if(!t[i])
- {
- continue;
- }
- for(String a : wordDict)
- {
- int len = a.length();
- int end = i + len;
-
- if(end > s.length())
- {
- continue;
- }
-
- if(t[end])
- {
- continue;
- }
-
- if(s.substring(i,end).equals(a))
- {
- t[end]=true;
- }
- }
- }
- return t[s.length()];
- }
- }
复制代码 |