ok

NoteXYX · NoteXYX · commit 7d6f63cac549 · 2020-07-19T15:41:43.000+08:00
diff --git a/src/com/leetcode/ListNode.java b/src/com/leetcode/ListNode.java
@@ -1,8 +1,8 @@
 package com.leetcode;
 
 public class ListNode {
-    private int val;
-    private ListNode next = null;
+    public int val;
+    public ListNode next = null;
     ListNode(int val) {
         this.val = val;
     }
diff --git a/src/com/leetcode/Main300.java b/src/com/leetcode/Main300.java
@@ -1,5 +1,7 @@
 package com.leetcode;
 
+import java.util.Arrays;
+
 /**
  * 300. 最长上升子序列
  * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
@@ -8,20 +10,38 @@
  * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
  */
 public class Main300 {
+//    public int lengthOfLIS(int[] nums) {
+//        if (nums==null || nums.length==0)
+//            return 0;
+//        int[] dp = new int[nums.length];
+//        dp[0] = 1;
+//        int maxAns = 1;
+//        for (int i = 1; i < dp.length; i++) {
+//            int curMax = 0;
+//            for (int j = 0; j < i; j++) {
+//                if (nums[i] > nums[j])
+//                    curMax = Math.max(curMax, dp[j]);
+//            }
+//            dp[i] = curMax + 1;
+//            maxAns = Math.max(dp[i], maxAns);
+//        }
+//        return maxAns;
+//    }
     public int lengthOfLIS(int[] nums) {
-        if (nums==null || nums.length==0)
-            return 0;
-        int[] dp = new int[nums.length];
-        dp[0] = 1;
+        int len = nums.length;
+        if (len < 2) {
+            return len;
+        }
+        int[] dp = new int[len];
+        Arrays.fill(dp, 1);
         int maxAns = 1;
-        for (int i = 1; i < dp.length; i++) {
-            int curMax = 0;
+        for (int i = 1; i < len; i++) {
             for (int j = 0; j < i; j++) {
-                if (nums[i] > nums[j])
-                    curMax = Math.max(curMax, dp[j]);
+                if (nums[j] < nums[i]) {
+                    dp[i] = Math.max(dp[i], dp[j] + 1);
+                }
             }
-            dp[i] = curMax + 1;
-            maxAns = Math.max(dp[i], maxAns);
+            maxAns = Math.max(maxAns, dp[i]);
         }
         return maxAns;
     }
diff --git a/src/com/leetcode/Main452.java b/src/com/leetcode/Main452.java
@@ -0,0 +1,46 @@
+package com.leetcode;
+
+import java.util.Arrays;
+
+/**
+ * 452. 用最少数量的箭引爆气球
+ * 在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。
+ *
+ * 一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
+ *
+ * Example:
+ *
+ * 输入:
+ * [[10,16], [2,8], [1,6], [7,12]]
+ *
+ * 输出:
+ * 2
+ *
+ * 解释:
+ * 对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）
+ */
+public class Main452 {
+    public int findMinArrowShots(int[][] points) {
+        if (points.length < 1)
+            return 0;
+        Arrays.sort(points, (p1, p2) -> p1[1]-p2[1]);
+        int[] dp = new int[points.length];
+        Arrays.fill(dp,1);
+        int res = 1;
+        for (int i = 1; i < points.length; i++) {
+            for (int j = 0; j < i; j++) {
+                if (points[j][1] < points[i][0]) {
+                    dp[i] = Math.max(dp[i], dp[j] + 1);
+                }
+            }
+            res = Math.max(res, dp[i]);
+        }
+        return res;
+    }
+
+    public static void main(String[] args) {
+        Main452 m = new Main452();
+        int[][] point = new int[][]{{1,2}, {2,3}, {3,4}, {4,5}};
+        System.out.println(m.findMinArrowShots(point));
+    }
+}
diff --git a/src/com/leetcode/Main46.java b/src/com/leetcode/Main46.java
@@ -0,0 +1,55 @@
+package com.leetcode;
+
+import java.util.ArrayList;
+import java.util.List;
+/**
+ * 46. 全排列
+ * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
+ *
+ * 示例:
+ *
+ * 输入: [1,2,3]
+ * 输出:
+ * [
+ *   [1,2,3],
+ *   [1,3,2],
+ *   [2,1,3],
+ *   [2,3,1],
+ *   [3,1,2],
+ *   [3,2,1]
+ * ]
+ */
+
+public class Main46 {
+    public List<List<Integer>> permute(int[] nums) {
+        int len = nums.length;
+        List<List<Integer>> res = new ArrayList<>();
+        if (len < 1)
+            return res;
+        boolean[] used = new boolean[len];
+        List<Integer> path = new ArrayList<>();
+        dfs(nums, len, 0, used, path, res);
+        return res;
+    }
+    public void dfs(int[] nums, int len, int depth, boolean[] used, List<Integer> path, List<List<Integer>> res) {
+        if (depth == len) {
+            res.add(new ArrayList<>(path));
+            return;
+        }
+        for (int i = 0; i < len; i++) {
+            if (!used[i]) {
+                path.add(nums[i]);
+                used[i] = true;
+                dfs(nums, len, depth+1, used, path, res);
+                used[i] = false;
+                path.remove(path.size()-1);
+            }
+        }
+    }
+    public static void main(String[] args) {
+        int[] nums = {1, 2, 3};
+        Main46 m = new Main46();
+        List<List<Integer>> lists = m.permute(nums);
+        System.out.println(lists);
+    }
+}
