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

 1 public class Solution {
 2     public int findMissedNumber(int[] nums) {
 3         for (int i = 0; i < nums.length; i++) {
 4             if (nums[i] > 0 && nums[i] - 1 != i && nums[i] != nums[nums[i] - 1]) {
 5                 int tmp = nums[nums[i] - 1];
 6                 nums[nums[i] - 1] = nums[i];
 7                 nums[i] = tmp;
 8                 i--;
 9             }
10         }
11         for (int j = 0; j < nums.length; j++) {
12             if (nums[j] - 1 != j) return j + 1;
13         }
14         return nums.length + 1;
15     }
16 }

 1 public class Solution {
 2     public int minPalindromePartition(String s) {
 3         int length = s.length();
 4         boolean[][] map = new boolean[length][length];
 5         int[] record = new int[length];
 6         for (int k = 0; k < length; k++) {
 7             record[k] = k;
 8         }
 9         for (int offset = 0; offset < length; offset++) {
10             for (int i = 0, j = i + offset; i < length - offset; i++, j++) {
11                 if (i == j || (s.charAt(i) == s.charAt(j) && (j - i == 1 || map[i + 1][j - 1]))) {
12                     map[i][j] = true;
13                 }
14             }
15         }
16         for (int i = 1; i < length; i++) {
17             for (int j = 0; j < i; j++) {
18                 if (map[j][i]) {
19                     if (j > 0) {
20                         record[i] = Math.min(record[i], record[j - 1] + 1);
21                     } else {
22                         record[i] = 0;
23                     }
24                 }
25             }
26         }
27         return record[length - 1];
28     }
29 }

 1 public class Solution {
 2     public TreeNode inOrderSuccessor(TreeNode root, TreeNode target) {
 3         if (target == null) return null;
 4         if (target.right != null) return minValue(target.right);
 5         TreeNode succ = null;
 6         while (root != null) {
 7             if (target.val < root.val) {
 8                 succ = root;
 9                 root = root.left;
10             } else if (target.val > root.val) {
11                 root = root.right;
12             } else {
13                 break;
14             }
15         }
16         return succ;
17     }
18 
19     private TreeNode minValue(TreeNode root) {
20         while (root.left != null) {
21             root = root.left;
22         }
23         return root;
24     }
25 }

分析

    这个题目的分析思路，和前面两期是非常相似的：给出递归的解法，发现重复的子问题，改进为动态规划的解法，这是一个分析的过程，待同学们比较熟悉时候，可以直接给出动态规划的解决方案，就很好了。

    这个题目，递归该如何解呢？给定一个字符串str，长度为n，怎么插入最少的字符，是的字符串变为回文呢？插入最少的字符，就是要尽量利用原来的字符，在原字符串str中，尽量利用更多能够匹配的字符。怎么对这个问题进行分解呢？考虑str字符串整体：

    1. 如果str[0]==str[n-1]，则问题转变为求str[1,n-2]，插入最少字符，得到回文

    2. 如果str[0]!=str[n-1]，则需要插入一个字符要么和str[0]相同，要么和str[n-1]相同，

    3. 如果和str[0]，则转变为str[1,n-1]，插入最少字符，得到回文

    4. 如果和str[n-1]，则转变为str[0,n-2]，插入最少字符，得到回文

    上面的第2种情况中，需要取两个值最小值。则完成了问题的分解，并且，基本情况也分析完全，则有递归式为：

    fmi(str, l, h) = (str[l] == str[h]) ? fmi(str, l+1, h-1) : (min(fmi(str, i+1, h), fmi(str,l, h-1))+1)

    通过上面的式子，有经验的、熟练的同学，很直接的就能看出来，存在重复的子问题，这就意味着，我们可以讲子问题的解缓存使用。如果，没有直接能够看出来的同学们，还是可以按照我们之前的方法，把递归树画出来吧，那样更加一目了然。

    那么，这个题目该如何用动态规划的解决呢？如何重复利用子问题的解呢？似乎有些不那么直接。但其实也是于规律可循的。上面的递归式，是从字符串的两 边，想中间移动递归，根据动态规划解决问题的思想，我们先解决子问题，再重复利用子问题，就是要从内向外解决，大家还记得回文子串判断的那个题目么，动态 规划解法的外层循环是子串的长度，这个题目也是类似的。示例代码如下：

 1 public class MergeIntervals {
 2     public class IntervalCmp implements Comparator<Interval> {
 3         @Override
 4         public int compare(Interval i1, Interval i2) {
 5             if (i1.start < i2.start) return -1;
 6             if (i1.start == i2.start && i1.end <= i2.end) return -1;
 7             return 1;
 8         }
 9     }
10     
11     public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
12         ArrayList<Interval> ret = new ArrayList<Interval>();
13         if (intervals.size() == 0) return ret;
14         Interval[] arr = new Interval[intervals.size()];
15         intervals.toArray(arr);
16         Arrays.sort(arr, new IntervalCmp());
17         int start = arr[0].start;
18         int end = arr[0].end;
19         for (int i = 0; i < arr.length; i++) {
20             if (arr[i].start <= end) {
21                 end = Math.max(end, arr[i].end);
22             } else {
23                 ret.add(new Interval(start, end));
24                 start = arr[i].start;
25                 end = arr[i].end;
26             }
27         }
28         ret.add(new Interval(start, end));
29         return ret;
30     }
31 }

 1 public class Solution {
 2     public class IntervalCmp implements Comparator<Interval> {
 3         @Override
 4         public int compare(Interval i1, Interval i2) {
 5             if (i1.start < i2.start) return -1;
 6             if (i1.start == i2.start && i1.end >= i2.end) return -1;
 7             return 1;
 8         }
 9     }
10     
11     public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
12         ArrayList<Interval> ret = new ArrayList<Interval>();
13         if (intervals.size() == 0) return ret;
14         Interval[] arr = new Interval[intervals.size()];
15         intervals.toArray(arr);
16         Arrays.sort(arr, new IntervalCmp());
17         int start = arr[arr.length - 1].start;
18         int end = arr[arr.length - 1].end;
19         for (int i = arr.length - 2; i >= 0; i--) {
20             if (arr[i].end < end) {
21                 ret.add(new Interval(start, end));
22                 start = arr[i].start;
23                 end = arr[i].end;
24             }
25         }
26         ret.add(new Interval(start, end));
27         return ret;
28     }
29 }

 1 public class Solution {
 2     public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
 3         int row = triangle.size();
 4         return findMinPath(triangle, 0, 0, row);
 5     }
 6 
 7     private int findMinPath(ArrayList<ArrayList<Integer>> triangle, int row,
 8             int col, int totalRow) {
 9         if (row == totalRow - 1) {
10             return triangle.get(row).get(col);
11         } else {
12             return triangle.get(row).get(col) + Math.min(findMinPath(triangle, row + 1, col, totalRow), findMinPath(triangle, row + 1, col + 1, totalRow));
13         }
14     }
15 }

 1 public class Triangle {
 2     public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
 3         int n = triangle.size() - 1;
 4         int[] path = new int[triangle.size()];
 5         for (int o = 0; o < triangle.get(n).size(); o++) {
 6             path[o] = triangle.get(n).get(o);
 7         }
 8         for (int i = triangle.size() - 2; i >= 0; i--) {
 9             for (int j = 0, t = 0; j < triangle.get(i + 1).size() - 1; j++, t++) {
10                 path[t] = triangle.get(i).get(t)
11                         + Math.min(path[j], path[j + 1]);
12             }
13         }
14         return path[0];
15     }
16 }