2020-5-6

617076674 · 617076674 · commit 2ff20bbb718f · 2020-05-06T15:06:57.000+08:00
diff --git a/question0300_longest_increasing_subsequence/Solution1.java b/question0300_longest_increasing_subsequence/Solution1.java
@@ -4,15 +4,17 @@
  * 动态规划。
  *
  * 状态定义：
- * dp[i]，以索引i处数字结尾的最长上升子序列的长度。
+ * dp[i]表示以索引i处数字结尾的最长上升子序列的长度。
  *
- * 状态转移：
- * dp[0] = 1
- * 当i > 0时，dp[i] = Math.max(dp[j] + 1, dp[i])，其中j∈[0, i)且nums[i] > nums[j]
+ * 初始化条件：
+ * dp[0] = 1。
+ *
+ * 状态转移方程：
+ * dp[i] = Math.max(dp[j] + 1, dp[i])，其中j∈[0, i)且nums[i] > nums[j]。
  *
  * 时间复杂度是O(n ^ 2)，其中n为nums数组的长度。空间复杂度是O(n)。
  *
- * 执行用时：22ms，击败65.26%。消耗内存：36.6MB，击败31.51%。
+ * 执行用时：36ms，击败5.39%。消耗内存：37.6MB，击败7.14%。
  */
 public class Solution1 {
     public int lengthOfLIS(int[] nums) {
diff --git a/question0300_longest_increasing_subsequence/Solution2.java b/question0300_longest_increasing_subsequence/Solution2.java
@@ -3,34 +3,10 @@
 /**
  * 二分查找法。
  *
- * 首先，我们需要一个n行的二维数组，其中第0行记录长度为1的一个"上升子序列"，第1行记录长度为2的一个"上升子序列"，...，
- * 第n - 1行记录长度为n的一个"上升子序列"。所有的这些子序列满足一个条件：它们的"结尾"是所有相同长度的"上升子序列"里面最小的。
- *
- * 以数组[10, 9, 2, 5, 3, 7, 101, 18]为例进行说明：
- *
- * 首先我们需要一个8行的数组，初始均为空：
- * [[], [], [], [], [], [], [], []]
- *
- * （1）遍历第0个元素——10，此时我们填充第0行：
- * [[10], [], [], [], [], [], [], []]
- * （2）遍历第1个元素——9，此时我们的数组如下：
- * [[9], [], [], [], [], [], [], []]
- * （3）遍历第2个元素——2，此时我们的数组如下：
- * [[2], [], [], [], [], [], [], []]
- * （4）遍历第3个元素——5，5比2大，此时我们填充第1行：
- * [[2], [2, 5], [], [], [], [], [], []]
- * （5）遍历第4个元素——3，3比2大比5小，此时我们的数组如下：
- * [[2], [2, 3], [], [], [], [], [], []]
- * （6）遍历第5个元素——7，7比3大，此时我们填充第2行：
- * [[2], [2, 3], [2, 3, 7], [], [], [], [], []]
- * （7）遍历第6个元素——101，101比7大，此时我们填充第3行：
- * [[2], [2, 3], [2, 3, 7], [2, 3, 7, 101], [], [], [], []]
- * （8）遍历第7个元素——18，18比7大，比101小，此时我们的数组如下：
- * [[2], [2, 3], [2, 3, 7], [2, 3, 7, 18], [], [], [], []]
- *
- * 遍历完成后，我们发现总共填充了3行，因此最长子序列长度就是4。
- *
- * 在整个过程中，我们只用到了第i行的最后一个元素，因此我们只需要用一个一维数组tail来保存某行的最后一个元素即可。
+ * 扑克牌分堆放置，放置规则如下：
+ * （1）只能把点数小的牌压到点数比它大的牌上。
+ * （2）如果当前牌点数较大没有可以放置的堆，则新建一个堆，把这张牌放进去。
+ * （3）如果当前牌有多个堆可供选择， 则选择最左边的堆放置。
  *
  * 时间复杂度是O(nlogn)，其中n为nums数组的长度。空间复杂度是O(n)。
  *
@@ -42,28 +18,30 @@ public int lengthOfLIS(int[] nums) {
         if (nums == null || (n = nums.length) == 0) {
             return 0;
         }
-        int[] tail = new int[n];
-        tail[0] = nums[0];
-        int end = 0; //end表示有序数组tail的最后一个已经赋值元素的索引
+        int[] tops = new int[n];    // 每堆扑克牌堆顶的牌
+        tops[0] = nums[0];  // 第一张牌显然只能新建一堆
+        int piles = 1;  // 现在一共有piles堆扑克牌
         for (int i = 1; i < n; i++) {
-            if (nums[i] > tail[end]) {  //得到一个长度+1的新的上升子序列
-                tail[++end] = nums[i];
-            } else {
-                //ceil()函数二分查找，在tail数组[0, end]范围内找到大于nums[i]的元素，更新其值
-                int left = 0, right = end + 1;
-                while (left < right) {
-                    int mid = left + ((right - left) >> 1);
-                    if (tail[mid] <= nums[i]) {
-                        left = mid + 1;
-                    } else {
-                        right = mid;
-                    }
-                }
-                if (left - 1 < 0 || tail[left - 1] != nums[i]) {  //如果nums[i]在tail数组的[0, end]范围内已经存在，什么都不做
-                    tail[left] = nums[i];   //更新tail[left]值为nums[i]
+            // 在[0, piles - 1]范围内寻找第一处比nums[i]大的位置，即ceil函数
+            int left = 0, right = piles - 1;
+            while (left <= right) {
+                int mid = left + ((right - left) >> 1);
+                if (tops[mid] == nums[i]) {
+                    left = mid + 1;
+                } else if (tops[mid] < nums[i]) {
+                    left = mid + 1;
+                } else if (tops[mid] > nums[i]) {
+                    right = mid - 1;
                 }
             }
+            if (left - 1 >= 0 && tops[left - 1] == nums[i]) {
+                continue;
+            }
+            if (left == piles) {
+                piles++;
+            }
+            tops[left] = nums[i];
         }
-        return end + 1;
+        return piles;
     }
 }
diff --git a/question0983_minimum_cost_for_tickets/Solution.java b/question0983_minimum_cost_for_tickets/Solution.java
@@ -0,0 +1,37 @@
+package question0983_minimum_cost_for_tickets;
+
+/**
+ * 动态规划。
+ *
+ * 时间复杂度是O(n ^ 2)，其中n为days数组的长度。空间复杂度是O(n)。
+ *
+ * 执行用时：2ms，击败48.29%。消耗内存：37.6MB，击败100.00%。
+ */
+public class Solution {
+    public int mincostTickets(int[] days, int[] costs) {
+        int[] dp = new int[days.length];
+        dp[days.length - 1] = Math.min(costs[0], Math.min(costs[1], costs[2]));
+        for (int i = days.length - 2; i >= 0; i--) {
+            dp[i] = dp[i + 1] + costs[0];
+            int tmp = i;
+            while (tmp < days.length && days[tmp] - days[i] < 7) {
+                tmp++;
+            }
+            if (tmp != i && tmp < days.length) {
+                dp[i] = Math.min(dp[i], dp[tmp] + costs[1]);
+            } else {
+                dp[i] = Math.min(dp[i], costs[1]);
+            }
+            tmp = i;
+            while (tmp < days.length && days[tmp] - days[i] < 30) {
+                tmp++;
+            }
+            if (tmp != i && tmp < days.length) {
+                dp[i] = Math.min(dp[i], dp[tmp] + costs[2]);
+            } else {
+                dp[i] = Math.min(dp[i], costs[2]);
+            }
+        }
+        return dp[0];
+    }
+}
diff --git a/question1012_numbers_with_repeated_digits/Solution.java b/question1012_numbers_with_repeated_digits/Solution.java
@@ -0,0 +1,12 @@
+package question1012_numbers_with_repeated_digits;
+
+public class Solution {
+    public int numDupDigitsAtMostN(int N) {
+        if (N <= 10) {
+            return 0;
+        } else if (N < 100) {
+            return 1 + (N - 11) / 10;
+        }
+        return -1;
+    }
+}

Original file line number	Diff line number	Diff line change
`@@ -4,15 +4,17 @@`
`4`	`4`	`* 动态规划。`
`5`	`5`	`*`
`6`	`6`	`* 状态定义：`
`7`		`- * dp[i]，以索引i处数字结尾的最长上升子序列的长度。`
	`7`	`+ * dp[i]表示以索引i处数字结尾的最长上升子序列的长度。`
`8`	`8`	`*`
`9`		`- * 状态转移：`
`10`		`- * dp[0] = 1`
`11`		`- * 当i > 0时，dp[i] = Math.max(dp[j] + 1, dp[i])，其中j∈[0, i)且nums[i] > nums[j]`
	`9`	`+ * 初始化条件：`
	`10`	`+ * dp[0] = 1。`
	`11`	`+ *`
	`12`	`+ * 状态转移方程：`
	`13`	`+ * dp[i] = Math.max(dp[j] + 1, dp[i])，其中j∈[0, i)且nums[i] > nums[j]。`
`12`	`14`	`*`
`13`	`15`	`* 时间复杂度是O(n ^ 2)，其中n为nums数组的长度。空间复杂度是O(n)。`
`14`	`16`	`*`
`15`		`- * 执行用时：22ms，击败65.26%。消耗内存：36.6MB，击败31.51%。`
	`17`	`+ * 执行用时：36ms，击败5.39%。消耗内存：37.6MB，击败7.14%。`
`16`	`18`	`*/`
`17`	`19`	`public class Solution1 {`
`18`	`20`	`public int lengthOfLIS(int[] nums) {`