IT技术小屋

 1 public class TrappingRainWater {
 2     public int trap(int A[], int n) {
 3         if (n <= 2)
 4             return 0;
 5 
 6         int[] lmh = new int[n];
 7         lmh[0] = 0;
 8         int maxh = A[0];
 9         for (int i = 1; i < n; ++i) {
10             lmh[i] = maxh;
11             if (maxh < A[i])
12                 maxh = A[i];
13         }
14         int trapped = 0;
15         maxh = A[n - 1];
16         for (int i = n - 2; i > 0; --i) {
17             int left = lmh[i];
18             int right = maxh;
19             int container = Math.min(left, right);
20             if (container > A[i]) {
21                 trapped += container - A[i];
22             }
23             if (maxh < A[i])
24                 maxh = A[i];
25         }
26         return trapped;
27     }
28 }

这道题其实有很强的规律可循。首先，n个元素的排列总数是n!。在下面的分析中，让k的范围是0 <= k < n!。（题目代码实际上是1<=k<=n!)
可以看到一个规律，就是这n！个排列中，第一位的元素总是(n-1)!一组出现的，也就说如果p = k / (n-1)!，那么排列的最开始一个元素一定是arr[p]。

这个规律可以类推下去，在剩余的n-1个元素中逐渐挑选出第二个，第三个，...，到第n个元素。程序就结束。

 1 /**
 2  * The set [1,2,3,…,n] contains a total of n! unique permutations.
 3  * 
 4  * By listing and labeling all of the permutations in order, We get the
 5  * following sequence (ie, for n = 3):
 6  * 
 7  * "123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation
 8  * sequence.
 9  * 
10  * Note: Given n will be between 1 and 9 inclusive.
11  * 
12  */
13 
14 public class PermutationSequence {
15     public String getPermutation(int n, int k) {
16         char[] arr = new char[n];
17         int pro = 1;
18         for (int i = 0; i < n; ++i) {
19             arr[i] = (char) ('1' + i);
20             pro *= (i + 1);
21         }
22         k = k - 1;
23         k %= pro;
24         pro /= n;
25         for (int i = 0; i < n - 1; ++i) {
26             int selectI = k / pro;
27             k = k % pro;
28             pro /= (n - i - 1);
29             int temp = arr[selectI + i];
30             for (int j = selectI; j > 0; --j) {
31                 arr[i + j] = arr[i + j - 1];
32             }
33             arr[i] = (char) temp;
34         }
35         return String.valueOf(arr);
36     }
37 }
38 

Lowest Common Ancestor of a Binary Search Tree (BST)

Given a binary search tree (BST), find the lowest common ancestor of two given nodes in the BST.

       _______6______

      /              \

   ___2__          ___8__

  /      \        /      \

  0      _4       7       9

        /  \

        3   5

Using the above tree as an example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. 

But how about LCA of nodes 2 and 4? Should it be 6 or 2?

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between 

two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a 

node to be a descendant of itself).” Since a node can be a descendant of itself, the LCA of 2 and 

4 should be 2, according to this definition.

Hint:

A top-down walk from the root of the tree is enough.

 1 public class LowestCommonAncestorOfaBinarySearchTree {
 2     public TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
 3         if (root == null || p == null || q == null)
 4             return null;
 5         if (Math.max(p.val, q.val) < root.val)
 6             return LCA(root.left, p, q);
 7         if (Math.min(p.val, q.val) > root.val)
 8             return LCA(root.right, p, q);
 9         return root;
10     }
11 }

 1 public class LowestCommonAncestorOfBinaryTree {
 2     public TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
 3         if (root == null)
 4             return null;
 5         if (root == p || root == q)
 6             return root;
 7         TreeNode left = LCA(root.left, p, q);
 8         TreeNode right = LCA(root.right, p, q);
 9         if (left != null && right != null)
10             return root;
11         return left != null ? left : right;
12     }
13 }

 1 public class ScrambleString {
 2     public boolean isScramble(String s1, String s2) {
 3         if (s1.length() != s2.length())
 4             return false;
 5         if (s1.equals(s2))
 6             return true;
 7 
 8         int[] A = new int[26];
 9         for (int i = 0; i < s1.length(); i++) {
10             ++A[s1.charAt(i) - 'a'];
11         }
12 
13         for (int j = 0; j < s2.length(); j++) {
14             --A[s2.charAt(j) - 'a'];
15         }
16 
17         for (int k = 0; k < 26; k++) {
18             if (A[k] != 0)
19                 return false;
20         }
21 
22         for (int i = 1; i < s1.length(); i++) {
23             boolean result = isScramble(s1.substring(0, i), s2.substring(0, i))
24                     && isScramble(s1.substring(i), s2.substring(i));
25             result = result
26                     || (isScramble(s1.substring(0, i),
27                             s2.substring(s2.length() - i, s2.length())) && isScramble(
28                             s1.substring(i), s2.substring(0, s2.length() - i)));
29             if (result)
30                 return true;
31         }
32         return false;
33     }
34 }

 1 public class LargestRectangleinHistogram {
 2     public int largestRectangleArea(int[] height) {
 3         Stack<Integer> stack = new Stack<Integer>();
 4         int i = 0;
 5         int maxArea = 0;
 6         int[] h = new int[height.length + 1];
 7         h = Arrays.copyOf(height, height.length + 1);
 8         while (i < h.length) {
 9             if (stack.isEmpty() || h[stack.peek()] <= h[i]) {
10                 stack.push(i++);
11             } else {
12                 int t = stack.pop();
13                 maxArea = Math.max(maxArea, h[t] * (stack.isEmpty() ? i : i - stack.peek() - 1));
14             }
15         }
16         return maxArea;
17     }
18 }

 1 public class BinaryTreeInorderTraversal {
 2     public ArrayList<Integer> inorderTraversal(TreeNode root) {
 3         ArrayList<Integer> inOrder = new ArrayList<Integer>();
 4         if (root == null)
 5             return inOrder;
 6         Stack<TreeNode> s = new Stack<TreeNode>();
 7         s.add(root);
 8         TreeNode p = root.left;
 9         while (!s.empty()) {
10             while (p != null) {
11                 s.add(p);
12                 p = p.left;
13             }
14             TreeNode n = s.pop();
15             inOrder.add(n.val);
16             p = n.right;
17             if (p != null) {
18                 s.add(p);
19                 p = p.left;
20             }
21         }
22         return inOrder;
23     }
24 }

 1 public class SubsetsII {
 2     public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
 3         ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
 4         ArrayList<ArrayList<Integer>> lastLevel = null;
 5         ret.add(new ArrayList<Integer>());
 6         Arrays.sort(num);
 7         for (int i = 0; i < num.length; i++) {
 8             ArrayList<ArrayList<Integer>> tmp = new ArrayList<ArrayList<Integer>>();
 9             ArrayList<ArrayList<Integer>> prev = i == 0 || num[i] != num[i - 1] ? ret : lastLevel;
10             for (ArrayList<Integer> s : prev) {
11                 ArrayList<Integer> newSet = new ArrayList<Integer>(s);
12                 newSet.add(num[i]);
13                 tmp.add(newSet);
14             }
15             ret.addAll(tmp);
16             lastLevel = tmp;
17         }
18         return ret;
19     }
20 }

 1 public class WordLadderII {
 2     private void GeneratePath(Map<String, ArrayList<String>> prevMap,
 3             ArrayList<String> path, String word,
 4             ArrayList<ArrayList<String>> ret) {
 5         if (prevMap.get(word).size() == 0) {
 6             path.add(0, word);
 7             ArrayList<String> curPath = new ArrayList<String>(path);
 8             ret.add(curPath);
 9             path.remove(0);
10             return;
11         }
12 
13         path.add(0, word);
14         for (String pt : prevMap.get(word)) {
15             GeneratePath(prevMap, path, pt, ret);
16         }
17         path.remove(0);
18     }
19 
20     public ArrayList<ArrayList<String>> findLadders(String start, String end,
21             HashSet<String> dict) {
22         ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();
23         Map<String, ArrayList<String>> prevMap = new HashMap<String, ArrayList<String>>();
24         dict.add(start);
25         dict.add(end);
26         for (String d : dict) {
27             prevMap.put(d, new ArrayList<String>());
28         }
29         ArrayList<HashSet<String>> candidates = new ArrayList<HashSet<String>>();
30         candidates.add(new HashSet<String>());
31         candidates.add(new HashSet<String>());
32         int current = 0;
33         int previous = 1;
34         candidates.get(current).add(start);
35         while (true) {
36             current = current == 0 ? 1 : 0;
37             previous = previous == 0 ? 1 : 0;
38             for (String d : candidates.get(previous)) {
39                 dict.remove(d);
40             }
41             candidates.get(current).clear();
42             for (String wd : candidates.get(previous)) {
43                 for (int pos = 0; pos < wd.length(); ++pos) {
44                     StringBuffer word = new StringBuffer(wd);
45                     for (int i = 'a'; i <= 'z'; ++i) {
46                         if (wd.charAt(pos) == i) {
47                             continue;
48                         }
49 
50                         word.setCharAt(pos, (char) i);
51 
52                         if (dict.contains(word.toString())) {
53                             prevMap.get(word.toString()).add(wd);
54                             candidates.get(current).add(word.toString());
55                         }
56                     }
57                 }
58             }
59 
60             if (candidates.get(current).size() == 0) {
61                 return ret;
62             }
63             if (candidates.get(current).contains(end)) {
64                 break;
65             }
66         }
67 
68         ArrayList<String> path = new ArrayList<String>();
69         GeneratePath(prevMap, path, end, ret);
70 
71         return ret;
72     }
73 }

 1 public class DistinctSubsequences {
 2     public int numDistinct(String S, String T) {
 3         int[][] f = new int[S.length() + 1][T.length() + 1];
 4         for (int k = 0; k < S.length(); k++)
 5             f[k][0] = 1;
 6         for (int i = 1; i <= S.length(); i++) {
 7             for (int j = 1; j <= T.length(); j++) {
 8                 if (S.charAt(i - 1) == T.charAt(j - 1)) {
 9                     f[i][j] += f[i - 1][j] + f[i - 1][j - 1];
10                 } else {
11                     f[i][j] += f[i - 1][j];
12                 }
13             }
14         }
15         return f[S.length()][T.length()];
16     }
17 }

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character

b) Delete a character

c) Replace a character