📣 VIP通行证夏日特惠 限时立减$68
查看: 8206| 回复: 70
跳转到指定楼层
上一主题 下一主题
收起左侧

刷题skill+编程cultivation+记录

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
02/06/2019 第一天
Leetcode 59 Spiral Matrix II

这题主要是输入一个n,生成一个旋转上身的矩阵

解题思路:
暴力解决;
通过一个while loop嵌套四个for loop,每个for loop填满一行或一列;
每次一个for loop之后,改变 rowBegin, rowEnd, colBegin, colEnd

技巧:
通过 rowBegin, rowEnd, colBegin, colEnd 来记录未完成赋值到的区域

评分

参与人数 2大米 +11 收起 理由
poc7667 + 1 赞一个
14417335 + 10 给你点个赞!

查看全部评分


上一篇:开贴刷题 顺便找队友一起刷题
下一篇:刷题打卡贴
推荐
 楼主| AChris 2019-2-15 10:57:57 | 只看该作者
全局:

02/14/2019 Day9
LeetCode 60. Permutation Sequence

解题思路: 这题主要是利用等价拆分排序的思想。
1. 首先想到,n个数,总共有n!种情况,第一位有n种情况,每种情况对应一个set,set相互之间有序,每个set有(n-1)!种情况。
2. 那么我们可以根据 k_index / (n-1) !得到我们想要的数在第几个set里面
3. k_index % (n-1)! 可以得到在那个set里面,我们要找第几个数



  1. class Solution {
  2.     // method 1: 96.03% 100%
  3.      public String getPermutation(int n, int k) {
  4.          
  5.          // time: O(n)
  6.          // space: O(n)
  7.          
  8.          //  {1,2,3,4}
  9.          //   1 -> {2,3,4}
  10.          //   2 -> {1,3,4}
  11.          //   3 -> {1,2,4}
  12.          //   4 -> {1,2,3}
  13.          //
  14.          //   k = 18 -> k = 17
  15.          //   index = k / fact[3] = 2;  k = k % fact[3] = 5
  16.          //   res = {1,2,4}
  17.          
  18.          //   k = 5
  19.          //   index = k / fact[2] = 2;  k = k % fact[2] = 1
  20.          //.  res = {1,2}
  21.          
  22.          //   k = 1
  23.          //   index = k / fact[1] = 1;  k = k % fact[1] = 0
  24.          //   res = {1}
  25.          
  26.          //   k = 0
  27.          //   index = k / fact[0] = 0;  k = k % fact[0] = 0
  28.          //   res = {}
  29.          
  30.          List<Integer> res = new ArrayList<Integer> ();
  31.          if (n == 0) new String ();

  32.          for (int i = 1; i <= n; i++) {
  33.              res.add(i);
  34.          }
  35.          
  36.          //fact[i] to store i!
  37.          int[] fact = new int[n];
  38.          fact[0] = 1;
  39.          for (int i = 1; i < n; i++) {
  40.              fact[i] = fact[i-1] * i;
  41.          }
  42.          
  43.          k = k - 1;
  44.          StringBuilder sb = new StringBuilder ();
  45.          for (int i = n - 1; i >= 0; i--) {
  46.              int index = k / fact[i];
  47.              k = k % fact[i];
  48.             
  49.              sb.append(res.get(index));
  50.              res.remove(index);
  51.          }
  52.          
  53.          return sb.toString();
  54.      }
  55.    
  56.    
  57. //     // method 2: 15.53% 100%
  58. //     // time: O(n*k)
  59. //     // space: O(n)
  60.    
  61. //     public String getPermutation(int n, int k) {
  62. //         StringBuilder sb = new StringBuilder ();
  63. //         if (n == 0) return sb.toString();
  64.    
  65. //         for (int i = 1; i <= n; i++) {
  66. //             sb.append((char)('0' + i));
  67. //         }
  68. //         for (int i = 1; i < k; i++) {
  69. //             increasePer(sb);
  70. //         }
  71. //         return sb.toString();
  72. //     }
  73.    
  74. //     private void increasePer(StringBuilder sb) {
  75. //         int firstSmall = -1;
  76. //         for (int i = sb.length() - 2; i >= 0; i--) {
  77. //             if (sb.charAt(i) < sb.charAt(i+1)) {
  78. //                 firstSmall = i;
  79. //                 break;
  80. //             }
  81. //         }
  82. //         // System.out.println("*firstSmall*" + firstSmall);
  83.         
  84. //         if (firstSmall == -1) {
  85. //             reverse(sb, 0, sb.length() - 1);
  86. //         }
  87.    
  88. //         // firstLarge must exists since sb.charAt(firstSmall) < sb.charAt(firstSmall + 1)
  89. //         int firstLarge = -1;
  90. //         for (int i = sb.length() - 1; i >= firstSmall + 1; i--) {
  91. //             if (sb.charAt(i) > sb.charAt(firstSmall)) {
  92. //                 firstLarge = i;
  93. //                 break;
  94. //             }
  95. //         }
  96. //         // System.out.println("*firstLarge*" + firstLarge);
  97. //         swap(sb, firstSmall, firstLarge);
  98. //         reverse(sb, firstSmall + 1, sb.length() - 1);
  99. //     }
  100.    
  101. //     private void reverse(StringBuilder sb, int i, int j) {
  102. //         while( i < j) {
  103. //             swap(sb, i++, j--);
  104. //         }
  105. //     }
  106.    
  107. //     private void swap(StringBuilder sb, int i, int j) {
  108. //         char temp = sb.charAt(i);
  109. //         sb.setCharAt(i, sb.charAt(j));
  110. //         sb.setCharAt(j, temp);
  111. //     }
  112. }
复制代码
回复

使用道具 举报

推荐
 楼主| AChris 2019-3-9 05:16:15 | 只看该作者
全局:
03/08/2019 Day31

Leetcode 200. Number of Islands
Importance【5】

解题思路:
这题主要是 暴力解决+DFS/BFS。
具体来说。暴力解决是指,遍历矩阵中的每一个点,看是否为1。然后对每一个点用 DFS/BFS 来搜索该点相邻的点,并将它们设置为其他数,表示这个岛屿已经被发现了。

设置成的数,可以是0,这样最快,最省空间,但不可以将grid回复到原来的样子。
如果要将 grid 在 count 完岛屿之后,恢复到原来的样子,可以将设置成的数变成是1、2然后在搜索之后进行恢复。


  1. class Solution {
  2.    
  3.     // method 1: DFS
  4.     public int numIslands(char[][] grid) {
  5.         // time: O(m*n) 99.99%
  6.         // space: O(m*n) 63.72% since the max depth of the dfs tree is m*n
  7.         if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;
  8.         int rowNum = grid.length;
  9.         int colNum = grid[0].length;
  10.         int res = 0;
  11.         for (int i = 0; i < rowNum; i++) {
  12.             for (int j = 0; j < colNum; j++) {
  13.                 if (grid[i][j] == '1') {
  14.                     dfs(grid, i, j, rowNum, colNum);
  15.                     res++;
  16.                 }
  17.             }
  18.         }
  19.         return res;
  20.     }
  21.    
  22.     private void dfs(char[][] grid, int i, int j, int rowNum, int colNum) {
  23.         if (i < 0 || i >= rowNum || j < 0 || j >= colNum || grid[i][j] == '0') return;
  24.         // if we do not want to restore the original graph, we can use 0
  25.         // if we want to restore the original graph, we should use another number except from 0
  26.         grid[i][j] = '0';
  27.         dfs(grid, i+1, j, rowNum, colNum);
  28.         dfs(grid, i-1, j, rowNum, colNum);
  29.         dfs(grid, i, j+1, rowNum, colNum);
  30.         dfs(grid, i, j-1, rowNum, colNum);
  31.         return;
  32.     }
  33.    
  34. //     // method2 : BFS
  35. //     class Coordinate {
  36. //         int x;
  37. //         int y;
  38. //         public Coordinate (int x, int y) {
  39. //             this.x = x;
  40. //             this.y = y;
  41. //         }
  42. //     }
  43.    
  44. //     public int numIslands(char[][] grid) {
  45. //         // time: O(m*n) 9.68%
  46. //         // space: O(m*n) 9.02%
  47. //         if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;
  48. //         int rowNum = grid.length;
  49. //         int colNum = grid[0].length;
  50. //         int res = 0;
  51. //         Queue<Coordinate> queue = new LinkedList<> ();
  52. //         for (int i = 0; i < rowNum; i++) {
  53. //             for (int j = 0; j < colNum; j++) {
  54. //                 if (grid[i][j] == '1') {
  55. //                     // Initialize the BFS
  56. //                     queue.add(new Coordinate(i, j));
  57. //                     // use the BFS to set all num in this island to be 0
  58. //                     while (!queue.isEmpty()) {
  59. //                         Coordinate cur = queue.poll();
  60. //                         int x = cur.x;
  61. //                         int y = cur.y;
  62. //                         if (x < 0 || x >= rowNum || y < 0 || y >= colNum || grid[x][y] == '0') {
  63. //                             continue;
  64. //                         } else {
  65. //                             grid[x][y] = '0';
  66. //                             queue.add(new Coordinate(x+1, y));
  67. //                             queue.add(new Coordinate(x-1, y));
  68. //                             queue.add(new Coordinate(x, y+1));
  69. //                             queue.add(new Coordinate(x, y-1));
  70. //                         }
  71. //                     }
  72. //                     res++;
  73. //                 }
  74. //             }
  75. //         }
  76. //         return res;
  77. //     }
  78.    
  79. }
复制代码
回复

使用道具 举报

推荐
 楼主| AChris 2019-2-11 09:56:24 | 只看该作者
全局:
02/10/2019 Day5

Leetcode 56. Merge Intervals

本题有两种算法,在本质上是一样的,都是通过考虑不同区间的叠加状况,来求解result

解题思路:方法一更优,是扫描线算法的一种。
确定start end,不断考虑下一个区间的情况。当不能合并当前interval和下一个interval时,添加interval。
然后,把下一个interval的起终作为start,end,继续loop

  1. /**
  2. * Definition for an interval.q
  3. * public class Interval {
  4. *     int start;
  5. *     int end;
  6. *     Interval() { start = 0; end = 0; }
  7. *     Interval(int s, int e) { start = s; end = e; }
  8. * }
  9. */
  10. class Solution {
  11.    
  12.         // method 1
  13.         public List<Interval> merge(List<Interval> intervals) {
  14.             
  15.             // time: O(nlogn)    25.92%
  16.             // space: O(n)    41.53%
  17.             
  18.             // |------|      |-------|
  19.             //     |-----|     |---|
  20.             
  21.             if (intervals == null || intervals.size() <= 1) return intervals;
  22.             Collections.sort(intervals, (a, b) -> a.start - b.start);
  23.             
  24.             List<Interval> res = new ArrayList<> ();
  25.             
  26.             int start = intervals.get(0).start;
  27.             int end = intervals.get(0).end;
  28.             
  29.             for (Interval interval: intervals) {
  30.                 if (interval.start <= end) {
  31.                     end = Math.max(end, interval.end);
  32.                 } else {
  33.                     res.add(new Interval(start, end));
  34.                     start = interval.start;
  35.                     end = interval.end;
  36.                 }
  37.             }
  38.             res.add(new Interval(start, end));
  39.             return res;
  40.         
  41.         }
  42.    
  43. //     // method2 : works
  44. //     public List<Interval> merge(List<Interval> intervals) {
  45.    
  46. //         time: O(nlogn) + O(n)    10.83%
  47. //         space: O(n)    2.24%
  48. //
  49.         
  50. //         List<Interval> res = new ArrayList<Interval> ();
  51.         
  52. //         //corner case
  53. //         if (intervals.size() == 0 || intervals == null) return res;
  54.         
  55. //         Collections.sort(intervals, (a,b) -> a.start - b.start);
  56.         
  57. //         List<Integer> starts = new ArrayList<> ();
  58. //         List<Integer> ends = new ArrayList<> ();
  59. //         for (Interval interval: intervals) {
  60. //             starts.add(interval.start);
  61. //             ends.add(interval.end);
  62. //         }
  63.         
  64.         
  65.         
  66. //         while (ends.size() > 0) {
  67. //             int curStart = starts.get(0);
  68. //             starts.remove(0);
  69. //             int curEnd = ends.get(0);
  70. //             ends.remove(0);
  71. //             while ( starts.size() > 0 && ends.size() > 0 &&  curEnd >= starts.get(0)) {
  72. //                 if (ends.get(0) <= curEnd) {
  73. //                     starts.remove(0);
  74. //                     ends.remove(0);
  75. //                 } else if (ends.get(0) > curEnd && starts.get(0) <= curEnd) {
  76. //                     starts.remove(0);
  77. //                     curEnd = ends.get(0);
  78. //                     ends.remove(0);
  79. //                 }
  80. //             }
  81. //             res.add(new Interval(curStart, curEnd));
  82. //         }
  83.         
  84. //         return res;
  85. //     }
  86. }
复制代码

补充内容 (2019-2-11 10:04):
new一个list的时候记得用ArrayList
List只是interface,不能被new
回复

使用道具 举报

🔗
 楼主| AChris 2019-2-8 03:54:14 | 只看该作者
全局:
02/07/2019 D2
Leetcode 54. Spiral Matrix

这题主要是输入一个m*n,按照spiral的规则遍历所有元素并返回一个list

解题思路:
暴力解决;
类似于上一题,但是由于输入的矩阵可能是不规则的m*n的矩阵,所以每个for loop 中沿着一行赋值的时候,一定要判断列begin end的条件满不满足
矩阵由于本身的对称性,所以loop 中一个条件就可以满足了

技巧:
注意corner case, 尤其是输入是空集的情况

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        
        // [[1, 2, 3, 4],
        //  [5, 6, 7, 8],
        //  [9, 10, 11, 12]]
        // rowBegin  rowEnd
        //   2        1
        // colBegin  colEnd
        //   1         1
        
        // time complexity: O(n) n elemnts
        // space complexity: O(n)
        
        if (matrix.length == 0) return new ArrayList<Integer>();
        
        List<Integer> res = new ArrayList<Integer> ();
        int rowBegin = 0, rowEnd = matrix.length - 1;
        int colBegin = 0, colEnd = matrix[0].length - 1;
        
        while (rowBegin <= rowEnd && colBegin <= colEnd) {
            for (int i = colBegin; i <= colEnd && rowBegin <= rowEnd; i++) res.add(matrix[rowBegin][i]);
            rowBegin++;
            
            for (int i = rowBegin; i <= rowEnd && colBegin <= colEnd; i++) res.add(matrix[i][colEnd]);
            colEnd--;
            
            for (int i = colEnd; i >= colBegin && rowBegin <= rowEnd; i--) res.add(matrix[rowEnd][i]);
            rowEnd--;
            
            for (int i = rowEnd; i>= rowBegin && colBegin <= colEnd; i--) res.add(matrix[i][colBegin]);
            colBegin++;
        }
        
        return res;
    }
}
回复

使用道具 举报

🔗
 楼主| AChris 2019-2-8 10:07:18 | 只看该作者
全局:
02/07/2017 Day 2

解题思路:首先,考虑两个数相乘,得到的结果最大会是几位数,然后创建相应的int[]用于存放结果。
然后,利用乘法,把两个多位数的乘法转化为 很多个个位数的和。
个位数的加减乘除我们可以通过 ‘?’与 ‘0’ 相减来得到相应的int。

intuition:想到个位数的加乘可以通过char来实现,然后把多位数乘法往个位数乘法转化

class Solution {
    public String multiply(String num1, String num2) {
        
        // time: O(m * n)
        // space: O(m + n)
        
        if (num1 == null || num2 == null) return "0";
        
        int[] digits = new int[num1.length() + num2.length()];
        for (int i = num1.length() - 1; i >= 0; i--) {
            for (int j = num2.length() - 1; j >= 0; j--) {
                int product = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j, p2 = i + j + 1;
                int sum = digits[p2] + product;
                digits[p2] = sum % 10;
                digits[p1] += sum / 10;
                if (digits[p1] == 10) {
                    digits[p1] = 0;
                    digits[p1 - 1] += 1;
                }
            }
        }
        
        // do not forget the case where product is 0
        StringBuilder sb = new StringBuilder();
        for (int digit: digits) {
            if (!(digit == 0 && sb.length() == 0)) {
                sb.append(digit);
            }
        }
        
        return sb.length() == 0? "0" : sb.toString();
        
    }
}

补充内容 (2019-2-8 10:07):
Leetcode 43. Multiply Strings
回复

使用道具 举报

🔗
 楼主| AChris 2019-2-9 11:32:10 | 只看该作者
全局:
02/08/2019 Day 3

LeetCode 17. Letter Combinations of a Phone Number

解题思路: 利用DFS的递归对所有可能的结果进行遍历,将最底层符合要求的String添加到result中去

技巧:
1.要用递归的时候,把 Recursion Tree 画出来!!然后对着树写
2.递归的时候,首先写base case,然后写 递归的具体内容,然后记住要recover!!!
3.生成一些辅助性的hashmap的时候,可以专门可以写一个method construct他,这样结构清楚

  1. public List<String> letterCombinations(String digits) {
  2.             /*

  3.                                                root

  4.                                      /.          |.     \
  5.             level 0: "2"           'a'          'b'     'c'

  6.                              /.     |.    \     
  7.             level 1: "3"  'ad'     'ae'    'af'
  8.             */
  9.            
  10.            // time: O(4**n)  n is length of digits
  11.            // complexity: O(n) sb is dynamic with length at most n, other is constant

  12.             List<String> res = new ArrayList<String> ();
  13.             // corner case
  14.             if (digits == null || digits.length() == 0) return res;
  15.             
  16.             StringBuilder sb = new StringBuilder ();
  17.             Map<Character, String> numToString = constructNumToString();
  18.             dfsHelper(res, 0, sb, numToString, digits);
  19.             return res;  
  20.         }
  21.    
  22.         private void dfsHelper(List<String> res, int level, StringBuilder sb, Map<Character, String> numToString, String digits) {
  23.             // base case
  24.             if (level == digits.length()) {
  25.                 res.add(sb.toString());
  26.                 return;
  27.             }
  28.             
  29.             // recursion
  30.             for (char ch: numToString.get(digits.charAt(level)).toCharArray()) {
  31.                 sb.append(ch);
  32.                 dfsHelper(res, level+1, sb, numToString, digits);
  33.                 // recover
  34.                 sb.deleteCharAt(sb.length() - 1);
  35.             }
  36.             return;
  37.         }
  38.    
  39.         private Map<Character, String> constructNumToString() {
  40.             Map<Character, String> numToString = new HashMap<> ();
  41.             numToString.put('0', "");
  42.             numToString.put('1', "");
  43.             numToString.put('2', "abc");
  44.             numToString.put('3', "def");
  45.             numToString.put('4', "ghi");
  46.             numToString.put('5', "jkl");
  47.             numToString.put('6', "mno");
  48.             numToString.put('7', "pqrs");
  49.             numToString.put('8', "tuv");
  50.             numToString.put('9', "wxyz");
  51.             return numToString;
  52.         }
复制代码

补充内容 (2019-2-9 11:33):
按照格式添加进去的java代码间距怎么突然这么大,下次还是直接粘贴文本吧

补充内容 (2019-2-9 11:34):
刷新一下格式又好了hhh
回复

使用道具 举报

🔗
 楼主| AChris 2019-2-10 03:13:09 | 只看该作者
全局:
02/09/2019 Day 4

LeetCode 31. Next Permutation

解题思路: 本题利用当前已有的数字,通过交换数字,刚好找到比当前数字大的数字。比如
123 -> 132 -> 213 -> 231 -> 312 -> 321 --|
^                                                           /
  \--------------------------------------------------

具体的思路是,
step1:
找到firstSmall, firstSmall之后的所有书,是一个依次递减的数列,这个数列的数字排列处于最大的状态,没法增加

step2:
找到firstSmall之后的数列中,刚好比firstSmall大的数字,称作firstLarge

step3:
交换firstSmall 和 firstLarge, 然后就得到了一个新的数字,比原来数字大,但此时,firstSmall后的依旧为一个递减数列,处于数列最大状态

step4:
reverse firstSmall之后的数列,使其成为递增数列,处于最小状态

over。



  1. class Solution {
  2.     public void nextPermutation(int[] nums) {
  3.         
  4.         // 1  2  3  7  5  8  6  3  2
  5.         //             ^ firstSmall
  6.         // nums after firstSmall are sorted reversely, cannot be increased more
  7.         // 1  2  3  7  5  8  6  3  2
  8.         //                   ^ firstLarge  
  9.         // first Large must exist, in worse case, it will be firstSmall + 1
  10.         // 1  2  3  7  6  8  5  3  2
  11.         //             ^     ^ exchange
  12.         // 1  2  3  7  6  2  3  5  8
  13.         //             ^| reverse nums

  14.         // time: O(n)
  15.         // space: O(1)
  16.         
  17.         //corner case
  18.         if (nums == null || nums.length == 0) return;
  19.         
  20.         // step 1:
  21.         int firstSmall = -1;
  22.         for (int i = nums.length - 2; i >= 0; i--) {
  23.             // use < since we need to find a descending subarrays where the value cannot be increased
  24.             if (nums[i] < nums[i+1]) {
  25.                 firstSmall = i;
  26.                 break;
  27.             }
  28.         }
  29.         if (firstSmall == -1) {
  30.             reverse(nums, 0, nums.length - 1);
  31.             return;
  32.         }
  33.         
  34.         // step 2:
  35.         int firstLarge = -1;
  36.         for (int i = nums.length - 1; i > firstSmall; i--) {
  37.             if (nums[i] > nums[firstSmall]) {
  38.                 firstLarge = i;
  39.                 break;
  40.             }
  41.         }
  42.         
  43.         // step 3:
  44.         swap(nums, firstSmall, firstLarge);
  45.         
  46.         // step 4:
  47.         reverse(nums, firstSmall + 1, nums.length - 1);
  48.         return;
  49.     }
  50.    
  51.     private void swap(int[] nums, int i, int j) {
  52.         int temp = nums[i];
  53.         nums[i] = nums[j];
  54.         nums[j] = temp;
  55.         return;
  56.     }
  57.    
  58.     private void reverse(int[] nums, int start, int end) {
  59.         while (start < end) {
  60.             swap(nums, start++, end--);
  61.         }
  62.         return;
  63.     }
  64. }
复制代码
回复

使用道具 举报

🔗
 楼主| AChris 2019-2-11 08:59:30 | 只看该作者
全局:
02/10/2019 Day5

Leetcode 118. Pascal's Triangle

解题思路:这是一道easy难度的recursion题目。
主要是注意写recursion 的时候有两个base case,最底层和最高层(因为最高层只需要加1次1,中间层需要手动加两次1)
每次进入下一个recursion后,记得return

  1. class Solution {
  2.     public List<List<Integer>> generate(int numRows) {
  3.         
  4.         // create n elements
  5.         // time: O(n)
  6.         // space: O(n)
  7.         
  8.         List<List<Integer>> res = new ArrayList<List<Integer>>  ();
  9.         
  10.         if (numRows == 0) return res;
  11.         
  12.         createLayer(res, 0, numRows);
  13.         
  14.         return res;
  15.     }
  16.    
  17.     private void createLayer(List<List<Integer>> res, int level, int numRows) {
  18.         // base case
  19.         if (level == numRows) return;
  20.         List<Integer> curRow = new ArrayList<Integer> ();
  21.         curRow.add(1);
  22.         if (level == 0) {
  23.             res.add(curRow);
  24.             // System.out.println(curRow);
  25.             createLayer(res, level+1, numRows);
  26.             return;
  27.         }
  28.         
  29.         
  30.         //recursion
  31.         List<Integer> lastRow = res.get(res.size() - 1);
  32.         for (int i = 0; i <= lastRow.size() - 2; i++) {
  33.             // System.out.print(i);
  34.             curRow.add(lastRow.get(i) + lastRow.get(i+1));
  35.         }
  36.         curRow.add(1);
  37.         res.add(curRow);
  38.         // System.out.println(curRow);
  39.         createLayer(res, level+1, numRows);
  40.         
  41.         return;
  42.     }
  43. }
复制代码
回复

使用道具 举报

🔗
 楼主| AChris 2019-2-12 03:25:02 | 只看该作者
全局:

02/11/2019 Day6

Leetcode 62. Unique Paths

解题思路:本题自己用了3种方法来解。最后的一个方法由于时间复杂度k太大,没有过,因为递归过程中造成了重复计算
第一种方法就是简单的DP思路,用res[][]来存起点到各个点的路线数
第二种是对第一种的空间复杂度简化,因为每次每一行的值用一次就行了,所以用一个一位数组就好
第三种是利用排列组合的方法,写的时候res用double型,防止溢出,也要防止 1/i 时 i 太大得到0

  1. class Solution {
  2.    
  3. //     // method 1:
  4. //     // time: O(m*n)
  5. //     // space: O(n)
  6. //     public int uniquePaths(int m, int n) {
  7.         
  8. //         int[][] res = new int[m][n];
  9.         
  10. //         for (int j = 0; j < n; j++) res[0][j] = 1;
  11. //         for (int i = 1; i < m; i++) res[i][0] = 1;
  12.         
  13. //         for (int i = 1; i < m; i++) {
  14. //             for (int j = 1; j < n; j++) {
  15. //                 res[i][j] = res[i-1][j] + res[i][j-1];
  16. //             }
  17. //         }
  18. //         return res[m-1][n-1];
  19. //     }
  20.    
  21. //     // method 2:
  22. //     // simplify space complexity since a lot of info are temporarily useful
  23. //     // time: O(m*n)
  24. //     // space: O(n)
  25. //     public int uniquePaths(int m, int n) {
  26.         
  27. //         int[] res = new int[n];
  28.         
  29. //         for (int j = 0; j < n; j++) res[j] = 1;
  30.         
  31. //         for (int i = 1; i < m; i++) {
  32. //             for (int j = 1; j < n; j++) {
  33. //                 res[j] = res[j] + res[j - 1];
  34. //             }
  35. //         }
  36. //         return res[n-1];
  37. //     }
  38.    
  39.     // method 3:
  40.     // Use combination
  41.     // time: O(m), space: O(1)
  42.     // in total, we have m+n-2 step including m-1 down steps
  43.     // result is combination(m+n-2, m-1)
  44.     // for combination (count, k)
  45.     // count! / k!(count-k)! = (count - k + 1) * (count - k + 2) ......* count / k!
  46.    
  47.     public int uniquePaths(int m, int n) {
  48.         int count = m + n - 2;
  49.         int k = m - 1;
  50.         // use double res to avoid overflow
  51.         double res = 1;
  52.         
  53.         for (int i = 1; i <= k; i++) {
  54.             // put i at last instead of res  / i * (count - k + i)
  55.             // since res / i may be 0 when i is too large
  56.             res = res  * (count - k + i) / i;
  57.         }
  58.         return (int)res;
  59.     }
  60.    
  61. //     // method 4   
  62. //     // time limit exceed
  63. //     // time:O(2 * m * n)   
  64. //     public int uniquePaths(int m, int n) {

  65. //         int numPath = 0;
  66.         
  67. //         numPath = dpHelper(0, 0, m, n);
  68.         
  69. //         return numPath;
  70. //     }
  71.    
  72. //     private int dpHelper(int i, int j, int m, int n) {
  73. //         // base case
  74. //         int numPath = 0;
  75. //         if (i == m - 1 && j == n - 1) {
  76. //             return 1;
  77. //         }
  78.         
  79. //         // recursion
  80. //         if (i < m - 1 && j < n - 1){
  81. //             numPath = numPath + dpHelper(i+1, j, m, n) + dpHelper(i, j+1, m, n);
  82. //         } else if (i >= m - 1 && j < n - 1) {
  83. //             numPath = numPath + dpHelper(i, j+1, m, n);
  84. //         } else if (i < m - 1 && j >= n - 1) {
  85. //             numPath = numPath + dpHelper(i+1, j, m, n);
  86. //         }
  87.         
  88.         
  89. //         return numPath;
  90. //     }
  91. }
复制代码
回复

使用道具 举报

🔗
 楼主| AChris 2019-2-13 00:44:53 | 只看该作者
全局:
02/12/2019 Day7

Leetcode 22. Generate Parentheses

解题思路:利用dfs解决的backtracking问题
time complexity不太确定
了解一下卡特兰数catalan number
https://en.wikipedia.org/wiki/Catalan_number

  1. class Solution {
  2.     public List<String> generateParenthesis(int n) {
  3.         //              root
  4.         //             /    \
  5.         //            (       )
  6.         //           /  \      |
  7.         //          (    )     terminates
  8.         
  9.         // time: O(2^n)
  10.         // space: O(n)
  11.         
  12.         List<String> res = new ArrayList<String> ();
  13.         if (n == 0) return res;
  14.         
  15.         
  16.         dfsHelper(res, "", n, n);
  17.         
  18.         return res;
  19.     }
  20.    
  21.     private void dfsHelper(List<String> res, String s, int left, int right) {
  22.         if (left > right) return;
  23.         if (left == 0 && right == 0) res.add(s);
  24.         if (left > 0) {
  25.             dfsHelper(res, s + "(", left - 1, right);
  26.         }
  27.         if (right > 0) {
  28.             dfsHelper(res, s+")", left, right - 1);
  29.         }
  30.     }
  31.    
  32.     // private void dfsHelper(List<String> res, StringBuilder sb, int left, int right) {
  33.     //     if (left > right) return;
  34.     //     if (left == 0 && right == 0) res.add(sb.toString());
  35.     //     if (left > 0) {
  36.     //         sb.append("(");
  37.     //         dfsHelper(res, sb, left - 1, right);
  38.     //         // recover
  39.     //         sb.deleteCharAt(sb.length() - 1);
  40.     //     }
  41.     //     if (right > 0) {
  42.     //         sb.append(")");
  43.     //         dfsHelper(res, sb, left, right - 1);
  44.     //         // recover
  45.     //         sb.deleteCharAt(sb.length() - 1);
  46.     //     }
  47.     // }
  48. }
复制代码
回复

使用道具 举报

🔗
 楼主| AChris 2019-2-13 11:18:28 | 只看该作者
全局:
02/12/2019 Day7
LeetCode 39. Combination Sum

解题思路:用dfs进行深度优先搜索。
有一个技巧是,在传参数的时候加入start,之后每次递归下一层都从start开始,这样就保证了遍历所有情况的同时,得到的result cur不经过sort也是有序的。

本题的时间空间复杂度也有一点点tricky,具体分析在代码备注中。

用另外一种方法还写了一遍,但test case总是过不了,正在想原因中。


  1. class Solution {
  2.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  3.         // p = target / min(candidates[]) + 1
  4.         // n = size of candidates
  5.         // C(n,r) = n! / (r! * (n-r)!)
  6.         // time: O(C(n,1) + C(n,2) + ... + C(n, p))
  7.         // space: O(path + recursion stack) = O(p)
  8.         
  9.         List<List<Integer>> res = new ArrayList<> ();
  10.         
  11.         // corner case
  12.         if (candidates == null || candidates.length == 0 || target == 0) return res;
  13.         
  14.         dfsHelper(res, candidates, target, new ArrayList<> (), 0);
  15.         
  16.         return res;
  17.     }
  18.    
  19.     private void dfsHelper(List<List<Integer>> res, int[] candidates, int target, List<Integer> cur, int start) {
  20.         // base case
  21.         if (target < 0) return;
  22.         if (target == 0) res.add(new ArrayList<>(cur));
  23.         
  24.         // recursion
  25.         for (int i = start; i < candidates.length; i++) {
  26.             cur.add(candidates[i]);
  27.             dfsHelper(res, candidates, target - candidates[i], cur, i);
  28.             
  29.             //recover
  30.             cur.remove(cur.size() - 1);
  31.         }
  32.         return;
  33.     }
  34.    
  35.     // method2: why wrong?
  36.    
  37. //     public List<List<Integer>> combinationSum(int[] candidates, int target) {

  38. //         List<List<Integer>> res = new ArrayList<> ();

  39. //         // corner case
  40. //         if (candidates == null || candidates.length == 0 || target == 0) return res;

  41. //         dfsHelper(res, candidates, target, new ArrayList<> (), 0);

  42. //         return res;
  43. //     }

  44. //     private void dfsHelper(List<List<Integer>> res, int[] candidates, int target, List<Integer> cur, int sum) {
  45. //         // base case
  46. //         if (sum == target) {
  47. //             Collections.sort(cur);
  48. //             System.out.println(target);

  49. //             if (!res.contains(cur)) {
  50. //                 res.add(new ArrayList<> (cur));
  51. //             }
  52. //             return;
  53. //         } else if (sum > target) {
  54. //             return;
  55. //         }


  56. //         // recursion
  57. //         for (int i = 0; i < candidates.length; i++) {
  58. //             cur.add(candidates[i]);
  59. //             sum += candidates[i];
  60. //             System.out.println("****");
  61. //             System.out.println(cur);
  62. //             System.out.println(sum);
  63. //             dfsHelper(res, candidates, target, cur, sum);

  64. //             //recover
  65. //             sum = sum - candidates[i];
  66. //             cur.remove(cur.size() - 1);
  67. //         }
  68. //         return;
  69. //     }
  70. }

复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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