11月 8 2014

LeetCode 笔记 1 in Java

1 2分查找时，上界一般是开区间，这样取均值最后总会收敛到up-1。

2 数组问题边界一定要注意，看问题是否考虑完全。

3 开闭区间端点认真对待。

4 Arrays.asList(1,2,3,4) => 变成一个Collection，可以批量初始化。

5 List 避免重复可以先check list.contains(x) 也可以

1 2	ArrayList<ArrayList<Integer>> newList = new ArrayList<ArrayList<Integer>>(new HashSet<ArrayList<Integer>>(oldList);

6 Bit operator: ~是非。 ^是xor。

7 char 是 primitive 类型，木有自己的方法。得Character.isDigit(curr)
Character.isLetter(curr)。

8 kmp 中最后返回的 i-j 其实就是文字串跳出时的长度 - PatternString跳出的长度。 1) 成功匹配，那就是匹配的起始点。2)没找到，那么 i - j > n - m (i = n, j < m)。

9 kmp 中匹配则 i++ , j++, next[i] = j // 反应的是j前匹配情况和i前一致，所以这个i如果匹配失败的话则应该用j匹配。然后根据 A[i] 是否= A[j] 判断是否 next[i] = next[j]。
如果不匹配呢？ i不动，j=-1，那么下一次一定能匹配了(P[-1] = '*')。

10 ArrayDeque offerLast & removeLast 做Stack用比较方便。

11 SearchARange 中可以使用 find upperbound 以及 lowerbound, 结果是[lower, upper)。注意区间开闭。二分法的核心是:

// upperbound
if (target >= *mid)
    first = ++mid; //开区间 )
else
    last = mid;
// lowerbound
if (target > *mid)
    first = ++mid; 
else 
    last = mid; //闭区间 [

12 数组初始化 new int[]{1,2,3,4} 或者 int[] rt = {1,2,3,4}

13 通常Array 或者 LinkedList => BST 都采用二分法，那么很重要的参数即是数列的长度。

14 字符串缓存通常使用StringBuilder, 配套方法有append(), toString()。

15 Subset II,

If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

采用增量法处理，每次在之前的每个set的基础上加一。特殊情况就是如果当前项与前一项相同，那么会重复前一项完成的添加。所以需要从前一项处理对象的后一项开始。其他情况依然从零开始，关键代码如下。

// ...
for (int i = 0; i < num.length; ++i){
    int start = 0;
    if (i > 0 && num[i] == num[i-1])
        start = last; //last last
        last = subsets.size();
    for (int j = start; j < last; ++j){
        List<Integer> subset = new ArrayList<Integer>(subsets.get(j));
        subset.add(num[i]);
        subsets.add(subset);
    }
}
// ...

16 构造二叉树(Pre+In Order || Post + In Order)，递归的来看# 表示root：
Pre-Order: #LL...LLRR...RR
In-Order: LL...LL#RR...RR
Post-Order: LL...LLRR...RR#
可以用HashMap 优化查找InOrder的过程。或者注意区间。

private TreeNode build(Map<Integer, Integer> inMap, 
int[] postorder, int inBegin, int postLast, int len){
    if (len == 0) return null;
    TreeNode root = new TreeNode(postorder[postLast]);
    int iRoot = inMap.get(root.val);
    root.left = build(inMap, postorder, inBegin, 
    	postLast-(len-(iRoot-inBegin)) ,iRoot-inBegin);
    root.right = build(inMap, postorder, iRoot+1, 
    	postLast-1, len -(iRoot-inBegin)-1);
    return root;
}

17 pow(x,n)的递归解法。其实就是把指数分解成2进制。比如$n\ mod\ 2$ 的余数是$2^0$上的数,$n/2\ mod\ 2$的余数是$2^1$上的的数。

private double power(double x, int n){
    double res = 1;
    double times = x;
    while(n!=0){
        if ((n & 1) == 1) res*=times;
        times *=times;
        n>>=1;
    }
    return res;
}

18 Valid BST。不仅要考虑局部有序，整体也得保证根左边所有的点都小于他。

private boolean isValidBST(TreeNode root, int lower, int upper){
    if (root == null) return true;
    return root.val > lower && root.val < upper 
    && isValidBST(root.left, lower, root.val) 
    && isValidBST(root.right, root.val,upper);
}

19 Insertion Sort List。注意到与一般的Insertion Sort不同，我们不能从当前点往前寻找需要交换的点。考虑到LinkedList的特殊性，我们只能每次从前往后寻找要交换的点。dummy.next 一开始是null。在过程中，如果dummy这个list都比p.val要小，那么pre会指向最后一个，pre.next = null。而如果中间出现比p.val大的情况，pre指向<=p.val的最后一个，完成交换后整个dummyListy依然有序。

ListNode dummy = new ListNode(-1);
ListNode p = head;
while(p!=null){
     ListNode pre = dummy;
     while(pre.next!=null){
        if (pre.next.val <= p.val)
            pre = pre.next;
        else break;
    }
            
    ListNode tmp = p.next;
    p.next = pre.next;
    pre.next = p;
    p = tmp;
            
}
        
return dummy.next;

20 Edit Distance: 要求求两个String 之间的距离。每一步可以改变一个字符，添加一个字符或者删除一个字符。于是我们可以建立一个表，其中f[i][j]表示A.sub(0,i) 到B.sub(0,j)的最小Edit Distance。

f[i][j] = f[i-1][j-1] //当A[i-1]=B[j-1]
f[i][j] = f[i-1][j-1]+1 //Replace
f[i][j] = f[i][j-1]+1 // add in A
f[i][j] = f[i-1][j]+1 // delete in A, add in B.

21 Permutation II. 采用组合数学中学到的字典序生成法。nextPermutation 算法如下，结束时，i=0，所有对都逆序了。

$$
1)\ i=max{j|p{j-1}<p_j} \
2)\ h=max{k|p{i-1}<pk} \
3)\ swap(num,p{i-1},p_k) \
4)\ reverse(num,i,end)
$$

22 Recover BST, 一个简单的作法是先将InOrder遍历结果存入一个List中，从左到右寻找第一个$a[i]>a[i+1]$,从右到左寻找第一个$a[j-1]>a[j]$。然后交换两个TreeNode的val。

23 关于PostOrderTraversal。一直往左，不断入栈这个没有问题。然后取栈顶，先看能不能往左，然后如果有右得先往右，如果没有右则可以处理当前栈顶节点。(这里可能还有右但是右孩子已经被处理完了，所以需要有一个额外的last指针指向上一个被处理的节点，如果需要处理的节点的右孩子==last，那么该节点也可以被处理了)

24 Distinct SubSequences
Alt text
f[i,j] 表示T[0,j]在S[0,i]中出现的次数。

1 2	f[i,j] = f[i-1][j]// when T[j]!=S[i], 不用S[i] f[i,j] = f[i-1][j] + f[i-1][j-1]// when T[j]==S[i], 可以用或不用S[i]

public int numDistinct(String S, String T) {
    int[] f = new int[T.length()+1];
    f[0] = 1;
    for (int i = 1; i <= S.length(); ++i){
        for( int j = T.length(); j > 0; --j ){
            f[j] += S.charAt(i-1)==T.charAt(j-1)? f[j-1]:0;
        }
    }
    return f[T.length()];
}

24 Jump Game I. 这个比较简单，我们可以一步步更新MaxReach = max(maxReach, i+A[i])。同时保证每次i<=reach即可。

25 Jump Game II. 我们需要借助last记住上一步的maxReach，cur记录的是上一格的maxReach。当i > last 的时候，上一步一个不能cover当前位置，所以需要多一步:++step。但是如果cur <= last 的话，我多一步也无法到达更远的地方，所以只能返回。

public int jump(int[] A) {
    int step = 0;
    int last = 0; 
    int cur = 0;
    for (int i = 0; i < A.length; ++i){
        if (i > last){
            if (cur <= last)
                return 0;
            last = cur;
            step++;
                
        }
        cur = Math.max(cur, i+A[i]);
    }
    return step;
}

26 Anagrams. 利用HashMap即可，把字符串先排序作为key，把字符串本身作为Value中List的一员插入。
需要注意 charArray不能直接toString(), 可以使用 new String(charArray);

27 Clone Graph. 可以利用HashMap建立旧新节点的一一映射关系，如果新节点尚未被创建，那么可以递归地在该处创建一个图。

private UndirectedGraphNode cloneGraph(UndirectedGraphNode node, 
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map){
    UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
    map.put(node, newNode);
    for (UndirectedGraphNode neighbor: node.neighbors){
        UndirectedGraphNode newNeighbor = map.get(neighbor);
        if (newNeighbor == null)
            newNeighbor = cloneGraph(neighbor, map);
            newNode.neighbors.add(newNeighbor);
                
    }
    return newNode;
}

28 Scramble String. 可以递归的考虑这个问题。把字符串分为k 和 n-k 两段。
设状态 f[n][i][j] 表示长度为n，起点为s1[i]的子串与起点为s2[j]的两个子串是否互为scramble。状态转移方程为：

/*
f[n][i][j] = (f[k][i][j] && f[n-k][i+k][j+k]) ||
            (f[k][i][j+k] && f[n-k][i+k][j]);
*/
for (int i=0; i < N; ++i)
    for(int j=0; j <N; ++j)
        f[1][i][j] = s1.charAt(i) == s2.charAt(j);
        
        
for (int n = 1; n <=N; ++n ){
    for (int i = 0; i+n <=N; ++i){
        for (int j = 0; j+n <=N; ++j){
            for(int k =1; k< n; ++k){
                if ((f[k][i][j] && f[n-k][i+k][j+k]) ||
                    (f[k][i][j+n-k] && f[n-k][i+k][j])){
                        f[n][i][j] = true;
                        break;
                    }
            }
        }
    }
}
return f[N][0][0];

29 First Missing Positive。使用桶排序。桶排序的核心是直接把数换到它应该在的位置。然后再找哪个地方漏了。

30 Merge K Sorted Lists 直接两两合并会超时。其实最直观的想法是每次从k个List的头部选取最小的添加到结果中，所以可以借助优先级队列。

 public ListNode mergeKLists(List<ListNode> lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(10,
        new Comparator<ListNode>(){
        @Override
        public int compare(ListNode a, ListNode b){
            return a.val - b.val;
        }
    });
        
    for (ListNode node: lists){
        if (node != null)
            heap.add(node);
    }
    ListNode dummy = new ListNode(-1);
    ListNode pre = dummy;
    while(!heap.isEmpty()){
        ListNode top = heap.poll();
        pre.next = top;
        if (top.next != null)
            heap.add(top.next);
                
        pre = pre.next;
    }
    return dummy.next;
}

31 Maximum Rectangle。

首先我们把问题缩小到一行来看。用L[n],R[n],H[n]储存当前位置的左右端点和包括本行在内的最高高度。先从左往右扫，确定左端点。’1’: H[j]=1，左界取Max(left, 0/初始L/)。’0’：那么下一个1的左界至少是j+1，用left储存。

下面我们看i+1行。 ‘1’: H[j]++，左界取Max(left, L[j]/上一行的L/)。’0’：那么下一个1的左界至少是j+1，用left储存。同时H[j]=0，L[j] =0, R[j] =n。也就是下一行的此列与之前行此列的结果无关。

接下来我们从右往左扫，确定R[j]。’1’: 右界取Min(right, R[j])。此时L R H 都以确定，可以求得迄今为止包括此行此列能求得的最大的矩形大小。’0’：那么下一个1的右界至多是j。

public int maximalRectangle(char[][] matrix) {
        final int m = matrix.length;
        if (m==0) return 0;
        final int n = matrix[0].length;
        
        int[] L, R, H;
        L = new int[n];
        R = new int[n]; Arrays.fill(R,n);
        H = new int[n];
        int ret = 0;
        for (int i = 0; i < m; ++i){
            int left = 0, right = n;
            //from left to right
            for (int j = 0; j < n; ++j){
                if (matrix[i][j] == '1'){
                    H[j]++;
                    L[j] = Math.max(L[j], left);
                }else{
                    left = j+1;
                    H[j]=0;
                    L[j]=0;
                    R[j]=n;
                }
            }
            //from right to left
            for (int j = n-1; j>=0; --j){
                if (matrix[i][j] == '1'){
                    R[j] = Math.min(R[j], right);
                    ret = Math.max(ret, (R[j]-L[j])*H[j]);
                }else{
                    right = j;
                }
            }
            
        }
        return ret;
    }

32 Sort List. 链表类型题目中，采用快慢两个指针是很常见的手法。可以1)把链表分成两段，2)找环路。

33 Best time to sell and buy stock 系列。
1)只能买一次卖一次。用一个变量存迄今为止的最小值，然后不停的试着去卖。
2)可以买卖无数次。把查分序列大于0的都加起来即可。
3)只能买卖2次。也就是分成两段，前一段买卖一次后一段买卖一次。直接这样算的话是$O(n^2)$。所以考虑先把从左至右得到的当前点最大profit存起来，然后从右往左，根据迄今为止最大的卖出价，不停试着买。看怎么样前后两轮交易获益最大。

//3)
 public int maxProfit(int[] prices) {
        if (prices.length < 1) return 0;
        int[] profit = new int[prices.length];
        int minPrice = prices[0];
        for (int i=1; i< prices.length; ++i){
            profit[i] = Math.max(profit[i-1], prices[i]-minPrice);
            minPrice = Math.min(minPrice, prices[i]);
        }
        int maxPrice = prices[prices.length-1];
        int maxProfit = profit[prices.length-1];
        for (int i=prices.length-2; i>0;--i){
            maxProfit = Math.max(maxProfit, profit[i-1]+maxPrice-prices[i]);
            maxPrice = Math.max(maxPrice, prices[i]);
        }
        return maxProfit;
    }

34 Largest Rectangle in Histogram. 这个神奇的题目需要借助一个栈。让我们来考虑从左至右加入bar。当bar的高度不是递增时，出现情况1，就是加入一个更矮的bar显然会使得矩形面积减小，所以先pop对前面的bar进行处理。而pop到情况2是，也就是a比b(当前位置)更矮，那我们就停止pop，转而将b push进去。

Alt text

public int largestRectangleArea(int[] height) {
        int maxArea = 0;
        Deque<Integer> q = new ArrayDeque<Integer>();
        int i = 0;
        while (i < height.length){
            if (q.isEmpty() || height[q.peekLast()] <= height[i])
                q.offerLast(i++);
            else{
                int pos = q.removeLast();
                maxArea = Math.max(maxArea, 
                    (q.isEmpty()? i : i-q.peekLast()-1)*height[pos]);
            }
        }
        while(!q.isEmpty()){
            int pos = q.removeLast();
            maxArea = Math.max(maxArea, 
                    (q.isEmpty()? i : i-q.peekLast()-1)*height[pos]);
        }
        return maxArea;
    }

35 Word Break。首先我们递归的思考，假设f[i] 表示字符串s[0,i]可分。那么$f[j] = \exists j,s.t. f[j]\ and\ s[j,i] \in dict == true$。那么其实我们也可以用动态规划来做。

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        int n = s.length();
        boolean[] f = new boolean[n+1];
        f[0] = true;
        for (int i = 1; i <= n; ++i )
            for (int j = i-1; j >=0; --j){
                if (f[j] && dict.contains(s.substring(j,i)))
                    f[i] = true;
            }
        return f[n];
    }
}

36 Word Break II. 这题需要返回结果，so我们先记录s[0,i]中可以cut之后，[j,i)也是一个词是j是哪些。然后深度优先进行搜索。

public List<String> wordBreak(String s, Set<String> dict) {
    final int n = s.length();
    boolean[] f = new boolean[n+1];
    boolean[][] cut = new boolean[n][n+1];
    f[0] = true;
    for (int i = 1; i<=n; ++i)
        for(int j=i-1; j>=0; --j)
            if (f[j] && dict.contains(s.substring(j,i))){
                f[i] = true;
                cut[j][i] = true;// [j,i) is a feasible word.
            }
    List<String> res = new ArrayList<String>();
    Deque<String> path = new ArrayDeque<String>();
    dfs(s, cut, s.length(), path, res);
    return res;
    
}
private void dfs(String s, boolean[][] cut, 
	int cur, Deque<String> path, List<String> res){
    if(cur == 0){
        String tmp="";
        for(String str:path){
            tmp += str + " ";
        }
        tmp = tmp.substring(0, tmp.length()-1);
        res.add(tmp);
    }
    
    for (int i=cur-1; i >=0; --i){
        if (cut[i][cur]){
            path.offerFirst(s.substring(i,cur));
            dfs(s, cut, i, path, res);
            path.removeFirst();
        }
    }
}

37 Merge Interval. 先排序，然后逐个比对并更新Interval，直到确定这个Interval.end < 下个interval.start，于是加入result，别忘了最后一个。

Collections.sort(list, new Comparator(){
    @Override
    public int compare(Interval a, Interval b){
        if (a.start == b.start)
            return a.end-b.end;
        else
            return a.start-b.start;
    }
});

38 Insert Interval. Maybe you can use binarySearch.

// in a for loop
if (new.start > cur.end) ++i;
else if (new.end < cur.start) {
    intervals.add(i,new);
    return intervals;
    }
else {
    new.start = min(new.start, cur.start);
    new.end = min(new.end, cur.end);
    intervals.remove(i);
    --i;
}

39 Binary Tree Maximum Path Sum. Use dfs, return max(left, right). when calculate the sum, add left + right(when > 0) + root.val.

40 Multiply String. 记住乘法的乘数每位有个offset。最后toString的时候注意细节。

41 Spiral Matrix. !Not always square!

42 InterLeaving String.
f[i][j] stands for that s1[0,i) s2[0,j) has interleaving matched s3[0,i+j).

1 2	f[i][j] = f[i-1][j] && s3[i+j-1]==s1[i-1] \|\|f[i][j-1] && s3[i+j-1]==s2[j-1]

也可用滚动数组做，注意边界条件f[0]

boolean[] f = new boolean[s2.length()+1];
f[0]= true;
for (int i = 1; i <=s2.length(); ++i)
    f[i] = f[i-1] && s2.charAt(i-1) == s3.charAt(i-1);
for (int i = 1; i <=s1.length(); ++i){
    f[0] = f[0] && s1.charAt(i-1) == s3.charAt(i-1);
    for(int j = 1; j<=s2.length();++j)
        f[j] = (s1.charAt(i-1)==s3.charAt(i+j-1) && f[j]) 
            || (s2.charAt(j-1)==s3.charAt(i+j-1) && f[j-1]);
}
return f[s2.length()];

43 Palindrome Partitioning II. 得借助备忘录isPalindrome[i][j]表示s[i,j]是否是palindrome。用cuts[i]记录i位置前最少有多少个cut。每次更新cuts=min(回文串前一个cuts+1和当前cuts)，注意当回文串前没字符时cuts始终为0.

public int minCut(String s) {
        if (s.isEmpty()) {
            return 0;
        }
        boolean[][] isPalindrome = new boolean[s.length()][s.length()];
        int[] cuts = new int[s.length()];
        for (int i = 0; i < s.length(); i++) 
            cuts[i] = i;
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i) == s.charAt(j)
                        && (i - j < 2 || isPalindrome[j + 1][i - 1])) {
                    isPalindrome[j][i] = true;
                    cuts[i] = j-1>=0?Math.min(cuts[i], cuts[j-1]+1):0;
                }
            }
        }
        return cuts[s.length()-1];
    }

44 Minimum Window Substring. 用双指针维护一个区间。先尾指针往后扫，直到有一个窗口包含所有T的字符后，考虑收缩头指针。这样所有的情况都不会遗漏。

public String minWindow(String S, String T) {
        if (S.isEmpty() || S.length() < T.length()) return "";
        final int ASCII_MAX=256;
        int[] appeared_count = new int[ASCII_MAX];
        int[] expected_count = new int[ASCII_MAX];
        for (char c: T.toCharArray()) expected_count[c]++;
        int min_end = Integer.MAX_VALUE-1, min_start = 0;
        int start = 0;
        int appeared_c = 0;
        for (int end = 0; end<S.length(); ++end){
            if (expected_count[S.charAt(end)]>0){
                appeared_count[S.charAt(end)]++;
                if (appeared_count[S.charAt(end)] <= expected_count[S.charAt(end)]) 
                	appeared_c++;
            }
            if (appeared_c == T.length()){
                while(expected_count[S.charAt(start)]==0 ||
                      appeared_count[S.charAt(start)] > expected_count[S.charAt(start)]){
                      appeared_count[S.charAt(start)]--;
                      start++;
                }
                if (end-start+1 < min_end-min_start+1){
                    min_start = start;
                    min_end = end;
                }    
            }
        }
        
        return min_end>S.length()? "":S.substring(min_start, min_end+1);
        
    }

45 Decode Ways. 类似斐波拉契数列。

46 Maximum Product Subarray. 关键是一个很小的负数可能*一个负数会变成很大的正数哦！所有可以用max[i] 和 min[i]两个数组记录迄今为止的最大和最小值。

47 Divide Two Integer. 边界情况有除0，Integer.MIN_VALUE 的overflow。先判断正负，后面所有运算均用正值。将除数翻倍加速运算。

首先一直double除数到<=被除数的最大值。
if dividend>= divisor, dividend -=divisor, ans++
in the next run, ans <<=1

48 Surrounded Regions. bfs。可以借助队列or栈把情况放入。从四面墙往中间走，遇到O则继续，遇到X则停止。

49 Wildcard Matching. remember the location of * 。
50 Valid Number. 这道题可以用有限状态机解。用到了enum. PA(How to):Input.SPACE.ordinal() = 1 and the enum type cannot be local. >_> .

enum Input{
            INVALID,    //0
            SPACE,      //1
            SIGN,       //2
            DIGIT,      //3
            DOT,        //4
            EXPONENT,   //5
            NUM_INPUTS  //6
        }
    public boolean isNumber(String s) {
        
        int[][] next = {
            {-1, 0, 1, 3, 2, -1},     //0 Nothing
            {-1, -1, -1, 3, 2, -1},   //1 -()
            {-1, -1, -1, 6, -1, -1},  //2 -.()
            {-1, -1, -1, 3, 8, 4},    //3 -9()
            {-1, -1, 5, 7, -1, -1},   //4 -9.5E()
            {-1, -1, -1, 7,-1, -1},   //5 -9.5E-() 
            {-1, -1, -1, 6, -1, 4},   //6 -.9()
            {-1, -1, -1, 7, -1, -1},  //7 -9.5e-9
            {-1, -1, -1, 6, -1, 4}    //8 -9.
        };
        s = s.trim();
        int state = 0;
        for (int i = 0;i < s.length(); ++i){
            Input input = Input.INVALID;
            char ch = s.charAt(i);
            if (Character.isSpace(ch))
                input = Input.SPACE;
            else if (Character.isDigit(ch))
                input = Input.DIGIT;
            else if (ch=='.')
                input = Input.DOT;
            else if (ch=='E' || ch =='e')
                input = Input.EXPONENT;
            else if (ch =='+' || ch == '-')
                input = Input.SIGN;
            
            state = next[state][input.ordinal()];
            if (state == -1) return false;
        }
        return state == 3 || state == 6 || state == 7 || state ==8;
    }

51 WordLadder II. 这题有点难，需要输出所有可能。 BFS, we need record the states layer by layer.

public class Solution {
    public List<List<String>> findLadders(String start, String end, 
    Set<String> dict) {
        List<List<String>> ans = new ArrayList<List<String>>();
        
        if (start.equals(end)){
            List<String> l = new ArrayList<String>();
            l.add(start);
            ans.add(l);
            return ans;
        }
        
        Set<String> current = new HashSet<String>();
        Set<String> next = new HashSet<String>();
        Set<String> visited = new HashSet<String>();
        Map<String, List<String>> father = new HashMap<String, List<String>>();
        boolean found = false;
        
        current.add(start);
        while(!current.isEmpty() && !found){
            for (String word: current)
                visited.add(word);
            for (String word: current){
                Set<String> new_states = extend(word, visited, dict, end);
                for (String state: new_states){
                    if (state.equals(end)) found = true;
                    next.add(state);
                    if (!father.containsKey(state))
                        father.put(state, new ArrayList());
                    father.get(state).add(word);
                }
            }
            current.clear();
            Set<String> tmpSet = current;
            current = next;
            next = tmpSet;
        }
        
        if (found){
            Deque<String> path = new ArrayDeque<String>();
            generatePath(father, path, start, end, ans);
        }
        
        return ans;
    }
    
    private void generatePath(Map<String, List<String>> father,
        Deque<String> path, final String start, final String word,
        List<List<String>> ans){
        path.offerLast(word);
        if (word.equals(start)){
            ArrayList<String> toAdd = new ArrayList<String>(path);
            Collections.reverse(toAdd);
            ans.add(toAdd);
        } else {
            for (String f: father.get(word))
                generatePath(father, path, start, f, ans);
        }
        path.removeLast();
    }
    
    private Set<String> extend(String s, Set<String> visited, 
    	Set<String> dict, String end){
        Set<String> result = new HashSet<String>();
        for (int i = 0; i < s.length(); ++i){
            char old_char =' ';
            char[] new_word = s.toCharArray();
            for (char c = 'a'; c<='z'; ++c){
                if (c == new_word[i]) continue;
                old_char = new_word[i];
                new_word[i] =c;
                String new_str = new String(new_word);
                if ((dict.contains(new_str) || new_str.equals(end))
                    && !visited.contains(new_str))
                    result.add(new_str);
                new_word[i] = old_char;
            }
            
        }
        
        return result;
    }
}

52 利用Map 记录以每个点为原点，斜率相同的点的个数。注意Double的边界情况，比如0, Double.MAX_VALUE。

神经咩的生活哲学

LeetCode 笔记 1 in Java

评论