一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2779|回复: 26
收起左侧

[Leetcode] Leetcode个人刷题思路和自我督促贴

[复制链接] |试试Instant~ |关注本帖
jaly50 发表于 2014-11-23 03:15:47 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 jaly50 于 2014-12-29 12:30 编辑

开个贴子自我督促一下哈~
顺便分享一下自己的思路,欢迎讨论~

2楼:Anagrams
3楼:Wildcard Matching
4-5楼:Jump Game II
6楼:Flatten Binary Tree to Linked List

7楼:Insert Interval
8楼:Construct Binary Tree from Preorder and Inorder Traversal

9楼:Construct Binary Tree from Postorder and Inorder Traversal

10楼:Validate Binary Search Tree

11楼: Simplify Path

12楼:Set Matrix Zeroes
13楼:Permutation Sequence
14楼: Restore IP Addresses

15楼: Subsets II

16楼:Partition List


18楼:Recover Binary Search Tree

19楼: Interleaving String

20楼   Minimum Window Substring

21楼 Largest Rectangle in Histogram

22楼 Maximal Rectangle

23楼 Excel Sheet Column Title

24楼 Maximum Gap

25楼 Fraction to Recurring Decimal






















评分

6

查看全部评分

 楼主| jaly50 发表于 2014-11-23 03:18:52 | 显示全部楼层
  1. /*
  2. * Author: Scarlett
  3. * Date: 11/21/2014 Fri 11:12 PM
  4. * LeetCode: 110  Anagrams
  5. * thought: HashMap
  6. * If only using HashMap, it will TLE. Since map[i].equals(map[j]) cost m time. (m is the length of a string)
  7. * Way to improve: To calculate total ASCii in one String, check whether TotalASCII[i]==totalASCII[b], it only cost 1 time.
  8. */



  9. import java.util.ArrayList;
  10. import java.util.Arrays;
  11. import java.util.Comparator;
  12. import java.util.HashMap;
  13. import java.util.List;
  14. import java.util.Map;

  15. // Same length? Duplicated group with different length? First step is to clarify the scope.
  16. //TLE QAQ 是不是str如果按长度排序,就可以再少点time consuming
  17. public class Anagrams {
  18.         public List<String> anagrams_buxiele(String[] strs) {
  19.                  List<String> list = new ArrayList<String>();
  20.                  return list;

  21.         }
  22.         public List<String> anagrams(String[] strs) {
  23.         List<String> list = new ArrayList<String>();
  24.                 Arrays.sort(strs,new Comparator<String>(){

  25.                         @Override
  26.                         public int compare(String o1, String o2) {
  27.                                 if (o1.length()<o2.length())  return -1;
  28.                                 else if (o1.length()>o2.length()) return 1;
  29.                                 return 0;
  30.                         }});
  31.                
  32.         int len = strs.length;
  33.         
  34.         //To reduce time, judging whether they are same total accil QAQ
  35.         //it works!!! GREAT!!!!!
  36.         int[] totalAC = new int[len];
  37.         Arrays.fill(totalAC, 0);
  38.         
  39.         //Make every String a map
  40.         Map<Character,Integer>[] map =new HashMap[len];
  41.         for (int i=0; i<len; i++) {
  42.            map[i] = new HashMap<Character,Integer>();
  43.            char[] s =strs[i].toCharArray();
  44.            for (char ch:s) {
  45.                    totalAC[i] += ch-'0';
  46.                    if (map[i].containsKey(ch) ) {
  47.                    map[i].put(ch,map[i].get(ch)+1);
  48.                }
  49.                else map[i].put(ch,1);
  50.            }
  51.         }
  52.         //Try some methods to reduce consuming time QAQ
  53.         //Mark strings which are already in the groups
  54.         boolean[] mark = new boolean[len];
  55.         Arrays.fill(mark, false);
  56.         
  57.         
  58.         
  59.         // To detect whether they are anagrams by compare map
  60.         for (int i=0; i<len; i++) {
  61.                 if (!mark[i])
  62.             for (int j=i+1; j<len; j++) {
  63.                 if (strs[i].length()!=strs[j].length()) break;
  64.                 if (totalAC[i] !=totalAC[j]) continue;
  65.                 if (map[i].equals(map[j])) {
  66.                          if (!mark[i])  list.add(strs[i]);
  67.                     list.add(strs[j]);
  68.                     mark[i] = true;
  69.                     mark[j] = true;
  70.                 }
  71.             }
  72.         }
  73.         return list;
  74.     }
  75.    

  76.         public static void main(String[] args) {
  77.                 // TODO Auto-generated method stub
  78.                 Anagrams a = new Anagrams();
  79.                 String[] strs = new String[]{"dog","cat","god","tac"};
  80.                 System.out.println(a.anagrams(strs));
  81.         }

  82. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-11-23 03:19:41 | 显示全部楼层
本帖最后由 jaly50 于 2014-12-14 11:19 编辑
  1. /*
  2. * LeetCode 141 Wild Card
  3. * Author: Scarlett Chen
  4. * Time: 12/13/2014 Sat 10:17 PM
  5. * 二十天以前不会写,参考了别人的答案。
  6. * 今天用那个dp的思路。发现还有很多细节需要注意
  7. */
  8. import java.util.HashMap;
  9. import java.util.Map;
  10. //https://oj.leetcode.com/discuss/10133/linear-runtime-and-constant-space-solution
  11. public class Wildcard {
  12.          public boolean isMatch(String s, String p) {
  13.                int len1 = s.length();
  14.                int len2 = p.length();
  15.                int j=0;
  16.                int i=0;
  17.                int prej=-1, prei=0;
  18.                // p串是零的情况
  19.                if (len1!=0 && len2==0) return false;
  20.                while (i<len1) {
  21.                    char cs = s.charAt(i);
  22.                    char cp;
  23.                    //直接不匹配 没有*号的情况
  24.                    if (j==-1) return false;
  25.                    if (j<len2) cp = p.charAt(j);
  26.                    else  cp = ' ';
  27.                    if (cs==cp || cp=='?') {
  28.                        i++;
  29.                        j++;
  30.                    }
  31.                    else if (cp=='*') {
  32.                        prej = j;
  33.                        prei = i;
  34.                        j++;
  35.                       
  36.                    }
  37.                    else {
  38.                      j = prej;
  39.                      i = ++prei;
  40.                    }
  41.                }
  42.                //注意这里不只一个值要注意,要看看是不是后面都是*号,才能放过它。
  43.                while (j<len2) {
  44.                       if (p.charAt(j)=='*') j++; else return false;
  45.                       
  46.                }
  47.              
  48.               return true;  
  49.             }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-11-26 11:35:00 | 显示全部楼层
/*
* LeetCode Jump Game II
*
* 需要思考,但是实现很容易。一次过~
* Date:11/25/2014 Tue 10:25 PM
* 思路:dp
*    在i的位置上,每次可以跳子距离(0,A[i]) , 就可以算f[i到i+A[i]]的次数了
*    f[i+j] = min (f[i+j], f[i]+1)  (j is in [1,A[i]])
*    再加点优化, if i<j, A[i]>A[j]+distance(i,j), 那么f[j]就不用算
*
*/
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-11-26 11:35:21 | 显示全部楼层
  1. public int jump(int[] A) {
  2.         int[] f = new int[A.length];
  3.         Arrays.fill(f,Integer.MAX_VALUE);
  4.         f[0]=0;
  5.         int max=0;
  6.       for (int i=0; i<A.length; i++) {
  7.           max = Math.max(A[i],max);
  8.           if (A[i]<max) {
  9.               max = max-1;
  10.               continue;
  11.           }
  12.           for (int j=1; j<=A[i] && i+j<A.length; j++) {
  13.               f[i+j] = Math.min(f[i+j], f[i]+1);
  14.               if (i+j==A.length-1)
  15.                       return f[i+j];
  16.           }
  17.       }
  18.       return f[A.length-1];
  19.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-11-26 23:35:08 | 显示全部楼层
  1. /*
  2. * LeetCode 124  Flatten Binary Tree to Linked List
  3. * Author: Scarlett Chen
  4. * Date:11/26/2014 Wed 10:32 AM
  5. * in place的意思大概是不要clone tree吧
  6. *  如果我new TreeNode(root.val),就会过不了(1,2)...虽然不知道为什么
  7. *  所以我就先把root的左右孩子先放栈里,然后脱离它与孩子们的关系,再让它放到我的树里。就不复制了。
  8. *  思路:栈,深搜
  9. */


  10. import java.util.Stack;


  11. public class Flatten {
  12.     public void flatten(TreeNode root) {
  13.         TreeNode result;
  14.         TreeNode head = new TreeNode(-1);
  15.         result = head;
  16.         Stack<TreeNode> tree = new Stack<TreeNode>();
  17.         if (root!=null) tree.push(root);
  18.         while (!tree.isEmpty()) {
  19.          root = tree.pop();
  20.         if (root.right!=null) tree.push(root.right);
  21.         root.right = null;
  22.         if (root.left!=null) tree.push(root.left);
  23.         root.left = null;
  24.         result.right = root;
  25.         result.left = null;
  26.         result = result.right;
  27.         }
  28.         root = head.right;
  29.         
  30.     }
  31. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-11-29 15:37:56 | 显示全部楼层
  1. /*
  2. * Author: Scarlett
  3. * LeetCode:Insert Interval
  4. * date:11/29/2014 Sat 2:33 AM
  5. * 设(x,y)为newInterval, (a,b)为当前比较的interval
  6. * 要考虑的情况包括: (x<a,y<a);(x<a,a<y<b);(x<a,y>b);(a<x<b,a<y<b);(a<x<b,y>b);(x>b)
  7. * 一开始先把newinterval加进list里
  8. * 注意list不能边改边删,所以要复制list再进行遍历
  9. */
复制代码
  1. /*
  2. * Be careful for the null list~~~!!
  3. * 要想清楚,要分情况!!
  4. */
复制代码
  1.         public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
  2.                 intervals.add(0,newInterval);
  3.                 List<Interval> copy = new LinkedList<Interval>(intervals);
  4.                 Interval pre=newInterval;
  5.                 for (int i=1; i<copy.size(); i++) {
  6.                     Interval list = copy.get(i);
  7.                     if (pre.start < list.start) {
  8.                             if (pre.end < list.start) {
  9.                                     return intervals;
  10.                             }
  11.                             else if (list.start<=pre.end && list.end >=pre.end ) {
  12.                                     list.start = pre.start;
  13.                                     intervals.remove(pre);
  14.                                     return intervals;
  15.                             }
  16.                             else if (pre.end > list.end) {
  17.                                     intervals.remove(list);
  18.                                     continue;
  19.                             }
  20.                     }
  21.                     else if (list.start<=pre.start && list.end>=pre.start) {
  22.                             if (list.start <=pre.end && list.end >=pre.end) {
  23.                                     intervals.remove(pre);
  24.                                     return intervals;
  25.                             }
  26.                             else if (pre.end >list.end) {
  27.                                     pre.start = list.start;
  28.                                     intervals.remove(list);
  29.                                     continue;
  30.                             }
  31.                     }
  32.                     else if (pre.start > list.end) {
  33.                             int a = intervals.indexOf(pre);
  34.                             int b =intervals.indexOf(list);
  35.                             intervals.set(a, list);
  36.                             intervals.set(b, pre);
  37.                             continue;       
  38.                     }
  39.                    
  40.                 }
  41.                 return intervals;
  42.         }
  43.                    
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-11-29 16:18:52 | 显示全部楼层

  1. /*
  2. * 一次过。但是难免边写边改。。如果在白板上写,还需要注意多一些。
  3. * 不喜欢用长名字命名,但是短名字常常含义不清。唉。
  4. * LeetCode 127:Construct Binary Tree from Preorder and Inorder Traversal
  5. * 思路:递归,二分
  6. * Date:11/29/2014 Sat 3:15 AM
  7. *
  8. */
复制代码
  1.    public TreeNode buildTree(int[] preorder, int[] inorder) {
  2.             if (preorder.length==0) return null;
  3.         TreeNode root = new TreeNode(preorder[0]);
  4.         if (preorder.length==1) return root;
  5.         int i=0;
  6.         int[] inorderLeft, inorderRight,preorderLeft,preorderRight;
  7.         //To find the root at int[] inorder, to divide it to two part
  8.         for (int in=0; in<inorder.length; in++) {
  9.             if (inorder[in] == preorder[0])
  10.             { i = in; break;}
  11.         }   
  12.                   inorderLeft = Arrays.copyOfRange(inorder,0,i);
  13.               int leftLen = inorderLeft.length;
  14.               inorderRight = Arrays.copyOfRange(inorder, i+1, inorder.length);
  15.              preorderLeft = Arrays.copyOfRange(preorder, 1,1+leftLen);
  16.              preorderRight = Arrays.copyOfRange(preorder, i+1, preorder.length);
  17.               root.left = buildTree(preorderLeft,inorderLeft);
  18.               root.right = buildTree(preorderRight, inorderRight);
  19.               return root;
  20.          
  21.         }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-11-29 16:37:35 | 显示全部楼层
  1.         /*
  2.          * 在leetcode上直接写一次过的~
  3.          * 代码也比前一题漂亮多了!
  4.          * 题目是通过后序和中序遍历建树,和前一题基本一样。。
  5.          * LeetCode:Construct Binary Tree from Inorder and Postorder Traversal
  6.          * Date:11/29/2014 Sat 3:37 AM
  7.          * Author:Scarlett
  8.          */
  9.     public TreeNode buildTree(int[] inorder, int[] postorder) {
  10.         int len = inorder.length;
  11.         if (len ==0) return null;
  12.         TreeNode root = new TreeNode(postorder[len-1]);
  13.         if (len==1) return root;
  14.         int indexOfRoot = 0;
  15.         for (int i=0; i<len; i++) {
  16.             if (inorder[i] ==postorder[len-1]) {
  17.                 indexOfRoot = i;
  18.             }
  19.         }
  20.         int[] inorderLeft, inorderRight, postorderLeft, postorderRight;
  21.         inorderLeft = Arrays.copyOfRange(inorder,0,indexOfRoot);
  22.         inorderRight = Arrays.copyOfRange(inorder,indexOfRoot+1,len);
  23.         postorderLeft = Arrays.copyOfRange(postorder,0,indexOfRoot);
  24.         postorderRight = Arrays.copyOfRange(postorder,indexOfRoot,len-1);
  25.         root.left = buildTree(inorderLeft, postorderLeft);
  26.         root.right = buildTree(inorderRight, postorderRight);
  27.         return root;
  28.         
  29.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-12-13 06:38:43 | 显示全部楼层
  1. /*
  2. * LeetCode 136 Validate Binary Search Tree
  3. * Author: Scarlett
  4. * 这道题很容易陷入一个小陷阱,就是只测试是否root.left <root<root.right,但其实BST的要求是必须root.left的最右儿子也要小于root的值。
  5. * 所以一开始写了fail的版本。
  6. *
  7. *  后来想着用DFS来做,每次记录前一个访问过的结点的值,必须小于当前结点。就可以满足BST的条件了。
  8. *  但是前一个访问过的点的值pre,在每个访问点上 从call左子树到call右子树之间是会变化的。
  9. *  因此又想了很久要怎么储存,进入了一些误区,还考虑过了应该是primitive or reference...要不要static...
  10. */


  11. public class IsValidBST {
  12.         Long pre;
  13.         public boolean isValidBST(TreeNode root) {
  14.                 if (root ==null) return true;
  15.                 boolean ans = true;
  16.                 pre = new Long((long)(Integer.MIN_VALUE) -1);
  17.                 return isValidNode(root, ans);

  18.         }
  19.         private boolean isValidNode(TreeNode root, boolean ans) {
  20.                 if (!ans) return ans;
  21.                 //System.out.println("At first, root= "+root.val+" pre= "+pre);
  22.                 if (root.left!=null) ans &= isValidNode(root.left,ans);
  23.                 if (pre < root.val) {
  24.                         pre =new Long(root.val);
  25.                 }
  26.                 else return false;
  27.                 //System.out.println("root= "+root.val+" pre= "+pre);
  28.                 if (root.right!=null) ans &= isValidNode(root.right,ans);
  29.                 //System.out.println("root= "+root.val+" pre= "+pre);
  30.                 return ans;
  31.         }

  32.         public boolean isValidBST_fail(TreeNode root) {
  33.                 if (root == null) return true;
  34.                 boolean ans = true;
  35.                 if (root.left !=null) {
  36.                     ans &= isValidBST(root.left);
  37.                     ans &= root.val > root.left.val;
  38.                 }
  39.                 if (root.right !=null) {
  40.                     ans &= isValidBST(root.right);
  41.                     ans &= root.val < root.right.val;
  42.                 }
  43.                 return ans;
  44.             }
  45.         public static void main(String[] args) {
  46.                 // TODO Auto-generated method stub
  47.                 IsValidBST is = new IsValidBST();
  48.         TreeNode root = new TreeNode(3);
  49.         TreeNode a = new TreeNode(1);
  50.         TreeNode b = new TreeNode(2);
  51.         TreeNode c = new TreeNode(4);
  52.         root.left = a;
  53.         root.right = c;
  54.         a.right = b;
  55.         System.out.println(is.isValidBST(root));
  56.         }

  57. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-12-13 07:40:04 | 显示全部楼层
  1. import java.util.Arrays;
  2. import java.util.Stack;
  3. /*
  4. * LeetCode: 137  Simplify Path
  5. * Author: Scarlett
  6. * 字符串处理题,要用到string.split
  7. * 主要是处理 . 和..的情况
  8. * 用stack增加和删除路径
  9. *
  10. * 第一遍没过是因为没有考虑 //的情况下,split会分配给它一个 length=0的string  ---要注理掉
  11. */

  12. public class SimplifyPath {
  13.          public String simplifyPath(String path) {
  14.                 if (path==null || path.length()==0) return path;
  15.                 Stack<String> s = new Stack<String>();
  16.                 String[] pos = path.split("/");
  17.              //   System.out.println(Arrays.toString(pos));
  18.                 for (int i =0 ; i< pos.length; i++) {
  19.                     if (pos[i].equals(".") || pos[i].length()==0) {
  20.                         continue;
  21.                     }
  22.                     else if (pos[i].equals("..")) {
  23.                         if (!s.isEmpty()) s.pop();
  24.                     }
  25.                     else {
  26.                         s.push(pos[i]);
  27.                     }
  28.                 }
  29.                 StringBuffer ans = new StringBuffer();
  30.                 while (!s.isEmpty()) {
  31.                         ans.insert(0, '/'+s.pop());
  32.                 }
  33.                 if (ans.length()==0) ans.append('/');
  34.                 return ans.toString();
  35.             }
  36.         public static void main(String[] args) {
  37.                 // TODO Auto-generated method stub
  38.                 SimplifyPath s = new SimplifyPath();
  39.                 System.out.println(s.simplifyPath("/..."));
  40.         }

  41. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-12-13 09:02:54 | 显示全部楼层
  1. import java.util.Arrays;
  2. /*
  3. * Leetcode 137 Set Matrix Zeroes
  4. * Author: Scarlett
  5. * 要求:Did you use extra space?
  6. A straight forward solution using O(mn) space is probably a bad idea.
  7. A simple improvement uses O(m + n) space, but still not the best solution.
  8. Could you devise a constant space solution?

  9.   这道题常见的误区可能是 会在matrix里直接改值,这样会导致错误。比如我因为matrix[1][2]==0,
  10.   就把row[1] col[2]全设零,那么当数组遍历到 matrix[other number][2]时,也会把相应行全设为零。这就不是我们要的。
  11.   
  12.   O(mn)的方法很直接,就是再设一个boolean或int二维数组,用original的数组去判断是否修改,用新数组存改后的值
  13.   o(m+n)的方法就是下面第一个, 用两个boolean数组(长度分别为m和n)判断该行或该列是否已被设为零
  14.   
  15.   O(1)的方法,这个不错:https://oj.leetcode.com/discuss/16190/is-there-any-constant-space-solution-with-just-one-pass

  16. */

  17. public class SetMatrixZeroes {
  18.         /*
  19.          *  extra space: o(m+n)
  20.          *  用两个boolean数组(长度分别为m和n)判断该行或该列是否已被设为零
  21.          *  Date: 12/12/2014 Fri 7:15 PM
  22.          */
  23.     public void setZeroes_OmPlusN(int[][] matrix) {
  24.         int n = matrix.length;
  25.         if (n==0) return;
  26.         int m = matrix[0].length;
  27.         boolean[] rowIsZero = new boolean[n];  
  28.         boolean[] colIsZero = new boolean[m];
  29.         Arrays.fill(rowIsZero, false);
  30.         Arrays.fill(colIsZero, false);
  31.         for (int i=0; i<n; i++) {
  32.             for (int j=0; j<m; j++) {
  33.                 if (matrix[i][j]==0) {
  34.                     rowIsZero[i] = true;
  35.                     colIsZero[j] = true;
  36.                 }
  37.             }
  38.         }
  39.         for (int i=0; i<n; i++) {
  40.             for (int j=0; j<m; j++) {
  41.                 if (rowIsZero[i] || colIsZero[j]) {
  42.                     matrix[i][j] = 0;
  43.                 }
  44.             }
  45.         }
  46.         return;
  47.       }
  48.    
  49.     /*   本来以为constant space solution可以用位运算,放两个字符串,分别代表row和col,每个数的每一位都代表具体的某一行或某一列,值可能有0或1
  50.    其实就是利用了发现o(m+n)的方法里多的数组的值其实只有0和1  才能再进一步升级为位运算
  51.      * 于是试图用bit operation写...
  52.       发现n和m的长度超出20位...要用string的话。。我觉得就和上面那个O(m+n)没有什么本质区别了
  53.       宣告失败= =
  54.    */
  55.     public void setZeroes_bitOperation_fail(int[][] matrix) {
  56.         int n = matrix.length;
  57.         if (n==0) return;
  58.         int m = matrix[0].length;
  59.         long rowIsZero = 0;  
  60.         long colIsZero = 0;
  61.         for (int i=0; i<n; i++) {
  62.             for (int j=0; j<m; j++) {
  63.                 if (matrix[i][j]==0) {
  64.                     rowIsZero |= 1<<i;
  65.                     colIsZero |= 1<<j;
  66.                 }
  67.             }
  68.         }
  69.         for (int i=0; i<n; i++) {
  70.             for (int j=0; j<m; j++) {
  71.                 if ((rowIsZero & 1<<i) !=0 || (colIsZero &1<<j) !=0) {
  72.                     matrix[i][j] = 0;
  73.                 }
  74.             }
  75.         }
  76.         return;
  77.       }
  78.         public static void main(String[] args) {
  79.                 // TODO Auto-generated method stub

  80.         }

  81. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-12-13 11:03:13 | 显示全部楼层
本帖最后由 jaly50 于 2014-12-13 11:13 编辑
  1. /*
  2. * LeetCode 139 Permutation Sequence
  3. * Author: Scarlett
  4. * Date: 12/12/2014 Fri 9:55 PM
  5. * 得到长度为n的第k个排列。
  6. * 我的方法是研究k个排列的规律,比如 1-6之间,就只有最后3位变化。
  7. * 所以我先把 k=k-max(x!<k)  (1<x<n), 同时得到x位的新值,把x后面的值往后挪。重复这样做,就可以得到第K个值。
  8. * 有点儿算是十进制换成二进制的思路呢。如65>64,就先把第6位的值改为1。
  9. * 更复杂一点点,因为这里不只有1和0两种变化。
  10. * 2!=2 ,3!=6  如果k是5的话,就要减去2次的2,于是第三位的值就会加两次,变成3.  
  11. *
  12. * 和别人的思路差不多,但是人家用recursive的方法,清楚简单多了:https://oj.leetcode.com/discuss/5568/does-anyone-have-better-idea-share-accepted-python-code-here
  13. */
  14. public class PermutationSequence {
  15. public String getPermutation(int n, int k) {
  16.         StringBuffer ans = new StringBuffer();
  17.         for (int i=1; i<=n; i++)
  18.                 ans.append(i);
  19.         k= k-1; //The current one is the first one. So we make it begin from 0
  20.         while (k>0) {
  21.         int pos =1;
  22.         int maxValue = 1;
  23.         //求最大阶乘
  24.         while (maxValue * pos <= k) {
  25.                 maxValue = maxValue * pos++;
  26.         }
  27.         char posValue, newPosValue;
  28.         posValue = ans.charAt(n-pos);
  29.         newPosValue= posValue;
  30.         int posOld, posNew;
  31.         posOld = n-pos;
  32.         posNew = posOld;
  33.         //算算有多少 (x-1)!的变化,当前位的值就要从后面几个拿。
  34.         //其实是取商和取余的过程= =
  35.         while (k>=maxValue) {
  36.         k = k - maxValue;
  37.         posNew++;
  38.         }
  39.         newPosValue = ans.charAt(posNew);
  40.         
  41.         ans.deleteCharAt(posNew);
  42.         ans.insert(posOld,newPosValue);
  43.         
  44.       //  System.out.println("maxValue= "+maxValue+" k="+k+" pos= "+ pos+" s1= "+newPosValue+" s2= "+posValue+"  --> "+ans.toString());
  45.         }
  46.      return ans.toString();        
  47.     }

  48.         public static void main(String[] args) {
  49.                 // TODO Auto-generated method stub
  50.                 char v ='1';
  51.                 //System.out.println(++v);
  52.                 PermutationSequence p = new PermutationSequence();
  53.                 System.out.println(p.getPermutation(3, 1));
  54.                 System.out.println(p.getPermutation(3, 4));
  55.         }

  56. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-12-13 12:50:52 | 显示全部楼层
  1. import java.util.ArrayList;
  2. import java.util.List;
  3. /*
  4. * LeetCode 140 Restore IP Addresses
  5. * Author: Scarlett chen
  6. * Date: 12/12/2014 Fri 11:48 PM
  7. * 完成今天5题刷题任务:D
  8. * 这题用搜索...比较经典简单直接~
  9. * 第一次没有过:是少考虑了 不能“00”的情况
  10. * 其他情况要考虑的是: 每个field不能多于3位数,也不能少于1位数; 数字必须在0到255之间。
  11. */



  12. public class RestoreIP {
  13.         List<String> ans;
  14.     public List<String> restoreIpAddresses(String s) {
  15.         ans = new ArrayList<String>();
  16.         int len = s.length();
  17.         if (len >12 || len<4) {
  18.             return ans;
  19.         }
  20.         search(1,len,s,"");
  21.         return ans;
  22.     }
  23.     private void search(int curField, int digitsLeft, String s, String path) {  
  24.             int fieldsLeft = 4 - curField;
  25.             if (fieldsLeft <0 ) {
  26.                     ans.add(path.substring(0, path.length()-1));
  27.             }
  28.         for (int i=1; i<=3; i++) {
  29.             //Make the leftDigits is enough for leftFields,but not too much
  30.           if (digitsLeft-i < fieldsLeft) {
  31.               break;
  32.           }
  33.           else
  34.           if (3 * fieldsLeft + i < digitsLeft) {
  35.               continue;
  36.           }
  37.           else {
  38.               String fieldValue = s.substring(0, i);
  39.               if (fieldValue.length()>1) {
  40.                       if (fieldValue.charAt(0)=='0') continue;
  41.               }
  42.               int value = Integer.parseInt(fieldValue);
  43.               if (value >=0 && value <=255)
  44.               search(curField+1,digitsLeft-i, s.substring(i), path+fieldValue+".");
  45.           }
  46.         }
  47.          
  48.       }
  49.         public static void main(String[] args) {
  50.                 // TODO Auto-generated method stub
  51.                 RestoreIP ri = new RestoreIP();
  52.                 System.out.println(ri.restoreIpAddresses("2502510035"));
  53.         }

  54. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-12-15 02:39:01 | 显示全部楼层
  1. /*
  2. * Time:12/14/2014 Sun 1:34 PM
  3. * Author: Scarlett Chen
  4. * LeetCode 145 Subsets II
  5. * 题本身不难,比非duplicate就是多两行判重的代码~
  6. * 要注意的就是path加了以后,要记得删掉~因为它是object,在method里call的时候不会自己变值
  7. *
  8. */

  9. import java.util.ArrayList;
  10. import java.util.Arrays;
  11. import java.util.List;


  12. public class SubSet2 {
  13.          List<List<Integer>> ans;
  14.          int[] num;
  15.          int len;
  16.         public List<List<Integer>> subsetsWithDup(int[] num) {
  17.                 Arrays.sort(num);
  18.         ans = new ArrayList<List<Integer>>();
  19.         this.num = num;
  20.         this.len = num.length;
  21.         ans.add(new ArrayList<Integer>());
  22.         List<Integer> path= new ArrayList<Integer>();
  23.       
  24.             for (int i=0; i < len; i++) {
  25.                      for (int count=1; count<=len-i; count++) {
  26.                     
  27.                     if (i>0 && num[i]==num[i-1]) continue;
  28.                 path = new ArrayList<Integer>();
  29.                 search(i,count,path);
  30.             }
  31.         }
  32.         return ans;
  33.         
  34.     }
  35.     private void search (int index, int countLeft,  List<Integer> path) {
  36.         if (countLeft==1) {
  37.             path.add(num[index]);
  38.           // System.out.println("Ans "+path);
  39.             ans.add(new ArrayList<Integer>(path));
  40.             path.remove(path.size()-1);
  41.             return;
  42.         }
  43.         else {
  44.              path.add(num[index]);
  45.               for (int i=index+1; i<len; i++) {
  46.                       if (i>index+1 && num[i]==num[i-1]) continue;
  47.                      // System.out.println(path+ " countLeft="+countLeft);
  48.                   search(i, countLeft-1, path);
  49.               }
  50.               path.remove(path.size()-1);
  51.             }
  52.         }
  53.    
  54.         public static void main(String[] args) {
  55.                 // TODO Auto-generated method stub
  56.                 SubSet2 s= new SubSet2();
  57.                 //System.out.println(s.subsetsWithDup(new int[]{}));
  58.                 //System.out.println(s.subsetsWithDup(new int[]{1}));
  59.                 //System.out.println(s.subsetsWithDup(new int[]{1,2}));
  60.                 //System.out.println(s.subsetsWithDup(new int[]{2,1,1}));
  61.                 System.out.println(s.subsetsWithDup(new int[]{1,2,3}));

  62.         }

  63. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-12-15 05:27:26 | 显示全部楼层
  1. /*
  2. * LeetCode  Partition List
  3. * Author: Scarlett Chen
  4. * Time:12/14/2014 Sun 4:25 PM
  5. * 解法就是再建一个list放较大值,最后再拼接
  6. * 需要注意的就是把一个数挪给较大的list时,要让turn.next=null
  7. */
  8. public class Partition {
  9.     public ListNode partition(ListNode head, int x) {
  10.         if (head==null || head.next==null) return head;
  11.         ListNode second = new ListNode(-1);
  12.         ListNode first= new ListNode(-1);
  13.         ListNode secondHead = second;
  14.         ListNode firstHead = first;
  15.         first.next = head;
  16.         while (first.next!=null) {
  17.            if (first.next.val < x) {
  18.               first = first.next;
  19.            }
  20.            else {
  21.                    ListNode turn = first.next;
  22.                first.next = turn.next;
  23.                turn.next = null;
  24.                second.next = turn;
  25.                second = second.next;
  26.                
  27.            }
  28.            
  29.         }
  30.         first.next = secondHead.next;
  31.         return firstHead.next;  
  32.     }
  33.         public static void main(String[] args) {
  34.                 // TODO Auto-generated method stub
  35.                 Partition p = new Partition();
  36.                 ListNode head =new ListNode(1);
  37.                 head.next = new ListNode(1);
  38.                 p.print(p.partition(head, 0));

  39.         }
  40.         private void print(ListNode head) {
  41.                 // TODO Auto-generated method stub
  42.                 while (head!=null) {
  43.                         System.out.print(head.val+" ");
  44.                         head = head.next;
  45.                 }
  46.         }

  47. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-12-22 10:01:48 | 显示全部楼层
  1. import java.util.Arrays;
  2. /*
  3. * Date:12/21/2014 Sun 5:59 PM
  4. * @author: Scarlett Chen
  5. */

  6. public class SurroundedRegion {
  7.             boolean [] hasEdge;
  8.             int[] union;
  9.             /*
  10.              * 一开始用了recursive dfs, 还发生了stackoverflow.QAQ .
  11.              * 最后用了algorithm1的unionfind写的~!感觉自己代码实现能力有提高呢!.
  12.              */
  13.             public void solve(char[][] board) {
  14.              int n = board.length;
  15.              if (n<1) return;
  16.              int m = board[0].length;
  17.              hasEdge = new boolean[n*m];
  18.              union = new int[n*m];
  19.              int pos;
  20.              for (int i=0; i<n; i++) {
  21.                      for (int j=0; j<m; j++) {
  22.                             pos = i*m +j;
  23.                             hasEdge[pos] = (i==0 ||j==0||i==n-1||j==m-1) ? true : false;
  24.                             union[pos] = pos;
  25.                             if (i>0 && board[i][j]== board[i-1][j]) {
  26.                                     union(pos, pos-m);
  27.                             }
  28.                             if (j>0 && board[i][j] == board[i][j-1]) {
  29.                                     union(pos, pos-1);
  30.                             }
  31.                       
  32.                      }
  33.              }
  34.              for (int i=0; i<n; i++) {
  35.                      for (int j=0; j<m; j++) {
  36.                              pos = i*m+j;
  37.                              if (board[i][j]=='O' &&  !hasEdge[findRoot(pos)]) {
  38.                                      board[i][j] = 'X';
  39.                              }
  40.                      }
  41.              }
  42.              for (int i=0; i<board.length; i++)
  43.                                 System.out.println(Arrays.toString(board[i]));
  44.              
  45.             }
  46.             
  47.             private void union(int x, int y) {
  48.                         int rootX = findRoot(x);
  49.                         int rootY = findRoot(y);
  50.                         union[rootX] = rootY;
  51.                         boolean hasedge = hasEdge[rootX] || hasEdge[rootY];
  52.                         hasEdge[rootY] = hasedge;
  53.        
  54.                 }

  55.                 private int findRoot(int x) {
  56.                         if (union[x]==x) return x;
  57.                         else return findRoot(union[x]);
  58.                 }


  59.         public static void main(String[] args) {
  60.                 // TODO Auto-generated method stub
  61.                 SurroundedRegion sr = new SurroundedRegion();
  62.                 char[][] board = new char[][] {{'X', 'X', 'X', 'X'},
  63.                                                                                 {'X', 'O', 'O', 'X'},
  64.                                                                                 {'X', 'X', 'O', 'X'},
  65.                                                                                 {'X', 'O' ,'X' ,'X'}};
  66.                 sr.solve(board);
  67.         }
  68.        
  69.        
  70.         //Failed
  71.         //Limitation in recursion depth
  72.         //sometimes we need to use stack to do bfs or dfs.
  73.          boolean[][] withEdge;
  74.             char[][] board;
  75.             int n;
  76.             int m;
  77.         public void solve_fail(char[][] board) {
  78.                n= board.length;
  79.                this. board = board;
  80.                if (n<1) return;
  81.                m = board[0].length;
  82.                withEdge = new boolean[n][m];
  83.                for (int i=0; i<n; i++) {
  84.                    Arrays.fill(withEdge[i], false);
  85.                }
  86.                 for (int i=0; i<n; i++) {
  87.                  if (board[i][0]=='O') {
  88.                      if (!withEdge[i][0]) {
  89.                          dfs(i,0);
  90.                      }
  91.                  }
  92.                 if (board[i][m-1]=='O') {
  93.                      if (!withEdge[i][m-1]) {
  94.                          dfs(i,m-1);
  95.                      }
  96.                  }
  97.                 }
  98.                for (int j=0; j<m; j++) {
  99.                    if (board[0][j]=='O') {
  100.                        if (!withEdge[0][j]) {
  101.                          dfs(0,j);
  102.                        }
  103.                    }
  104.                   if (board[n-1][j]=='O') {
  105.                        if (!withEdge[n-1][j]) {
  106.                          dfs(n-1,j);
  107.                        }
  108.                    }
  109.                }
  110.               for (int i=0; i<n; i++) {
  111.                   for (int j=0; j<board[0].length; j++) {
  112.                       if (board[i][j]=='O' && !withEdge[i][j]) {
  113.                           board[i][j] = 'X';
  114.                       }
  115.                   }
  116.               }
  117.                 
  118.             }
  119.             public void dfs(int row, int col) {
  120.                     withEdge[row][col] = true;
  121.                 if (row>0 && board[row-1][col]=='O' && !withEdge[row-1][col]) {
  122.                     dfs(row-1, col);
  123.                 }
  124.                 if (row<n-1 && board[row+1][col]=='O' && !withEdge[row+1][col]) {
  125.                     dfs(row+1, col);
  126.                 }
  127.                 if (col>0 && board[row][col-1]=='O' && !withEdge[row][col-1]) {
  128.                     dfs(row, col-1);
  129.                 }
  130.                 if (col<board[0].length-1 && board[row][col+1]=='O' && !withEdge[row][col+1]) {
  131.                     dfs(row, col+1);
  132.                 }
  133.             }
  134.        
  135. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-12-22 11:08:28 | 显示全部楼层
  1. import java.util.HashMap;
  2. import java.util.Map;
  3. import java.util.Stack;
  4. /*
  5. * LeetCode: 148 Clone Graph
  6. * @author:Scarlett Chen
  7. * @date: 12/21/2014 Sun 7:04 PM
  8. * clone一个无向图,用栈一个一个访问结点,用hashmap记录clone的结点
  9. * 最近写代码都是一次过,真是不好意思嘿嘿嘿~~ 不过还是用了ide,如果没有提示的话,常常记不得如stack or map 的method的name
  10. */

  11. public class CloneGraph {
  12.          public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
  13.                 //To traverse the original nodes
  14.                 Stack<UndirectedGraphNode> stack = new Stack<UndirectedGraphNode>();
  15.                 //To record lable and its cloned Graph
  16.                 Map<Integer,UndirectedGraphNode> clone = new HashMap<Integer,UndirectedGraphNode>();
  17.                 if (node==null) return node;
  18.                 stack.push(node);
  19.                 clone.put(node.label, new UndirectedGraphNode(node.label));
  20.                 while (!stack.isEmpty()) {
  21.                    UndirectedGraphNode root = stack.pop();
  22.                    UndirectedGraphNode cloneRoot = clone.get(root.label);
  23.                    for (UndirectedGraphNode nei:root.neighbors) {
  24.                            UndirectedGraphNode cloneNei;
  25.                           
  26.                            //说明该结点已加入栈中
  27.                            if (clone.containsKey(nei.label)) {
  28.                                    cloneNei = clone.get(nei.label);
  29.                                   
  30.                            }
  31.                            else {
  32.                                    cloneNei = new UndirectedGraphNode(nei.label);
  33.                                    clone.put(nei.label, cloneNei);
  34.                                    stack.push(nei);
  35.                            }
  36.                            cloneRoot.neighbors.add(cloneNei);
  37.                       
  38.                    }
  39.                    
  40.                 
  41.                 }
  42.                 return clone.get(node.label);
  43.                  
  44.          }
  45.         public static void main(String[] args) {
  46.                 // TODO Auto-generated method stub

  47.         }

  48. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-12-24 16:46:19 | 显示全部楼层
  1. /*
  2. * LeetCode 149  Recover Binary Search Tree
  3. * @author: Scarlett Chen
  4. * @date: 12/24/2014 Wed 12:43 AM
  5. * 这道题告诉我们 要巧用全局变量!
  6. * 以及理解一下~两个互相交换的node,在dfs中,第一个一定是和它下一个对比才被发现错的!第二个和它上一个对比发现错的!---利用这个规律就很好写了!
  7. */
  8. public class RecoverBST {
  9.             TreeNode prev;
  10.             TreeNode first;
  11.             TreeNode second;
  12.             public void recoverTree(TreeNode root) {
  13.                first = null;
  14.                second = null;
  15.                 prev = new TreeNode(Integer.MIN_VALUE);
  16.                 if (root==null) return;
  17.                 dfs(root);
  18.                 if (first!=null && second!=null)
  19.                         swap(first,second);
  20.             }
  21.             private void dfs(TreeNode root) {
  22.                 if (root.left!=null)  dfs(root.left);
  23.                 if (prev.val > root.val) {
  24.                     if (first == null)
  25.                             first = prev;
  26.                     second = root;
  27.                 }

  28.                 prev = root;
  29.                if (root.right!=null) dfs(root.right);
  30.             }
  31.             public void swap(TreeNode first, TreeNode second) {
  32.                int temp = first.val;
  33.                first.val = second.val;
  34.                second.val = temp;
  35.             }
  36.         public static void main(String[] args) {
  37.                 // TODO Auto-generated method stub
  38.        TreeNode head = new TreeNode(0);
  39.        TreeNode b = new TreeNode(1);
  40.        head.left = b;
  41.        RecoverBST rb = new RecoverBST();
  42.        rb.recoverTree(head);
  43.         }

  44. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2014-12-25 04:52:37 | 显示全部楼层
  1. import java.util.Arrays;
  2. /*
  3. * LeetCode 152 Interleaving String
  4. * DP o(n^2)
  5. * @author: Scarlett.chen
  6. * @date:12/24/2014 Wed 12:50 PM
  7. * 注意边界值,len1==0等情况
  8. * 以及f[i][j]表示s1的前i个和s2的前j个,是不是能构成s3的前i+j个
  9. */

  10. public class InterLeaving {
  11.          public boolean isInterleave(String s1, String s2, String s3) {
  12.                  int len1 = s1.length();
  13.                  int len2 = s2.length();
  14.                  int len3 = s3.length();
  15.                  if (len3!=len2+len1) return false;
  16.                  if (len1==0) return s2.equals(s3);
  17.                  if (len2 == 0) return s1.equals(s3);
  18.                  boolean[][] f = new boolean[len1+1][len2+1];
  19.                  
  20.                  for (int i=0; i<=len1; i++) Arrays.fill(f[i], false);
  21.                  f[0][0] = true;
  22.                  for (int i=0; i<=len1; i++) {
  23.                          for (int j=0; j<=len2; j++) {
  24.                                  if (i>0 && s1.charAt(i-1) == s3.charAt(i-1+j)) {
  25.                                          f[i][j] = f[i-1][j] ||f[i][j];
  26.                                  }
  27.                                  if (j>0 && s2.charAt(j-1) == s3.charAt(i+j-1)) {
  28.                                          f[i][j] = f[i][j-1] ||f[i][j];
  29.                                  }
  30.                                  
  31.                          }
  32.                  }
  33.                  
  34.          return f[len1][len2];
  35.          }
  36.         public static void main(String[] args) {
  37.                 // TODO Auto-generated method stub
  38.                 InterLeaving il = new InterLeaving();
  39.                 System.out.println(il.isInterleave("ab", "aa", "abaa"));
  40.         }

  41. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 10:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表