My code:
public class Solution {
public int minCostII(int[][] costs) {
if (costs == null || costs.length == 0 || costs[0].length == 0) {
return 0;
}
int min1 = -1;
int min2 = -1;
int k = costs[0].length;
int n = costs.length;
for (int i = 0; i < n; i++) {
int lastMin1 = min1;
int lastMin2 = min2;
min1 = -1;
min2 = -1;
for (int j = 0; j < k; j++) {
if (j != lastMin1) {
costs[i][j] += (lastMin1 < 0 ? 0 : costs[i - 1][lastMin1]);
}
else {
costs[i][j] += (lastMin2 < 0 ? 0 : costs[i - 1][lastMin2]);
}
if (min1 == -1 || costs[i][j] < costs[i][min1]) {
min2 = min1;
min1 = j;
}
else if (min2 == -1 || costs[i][j] < costs[i][min2]) {
min2 = j;
}
}
}
return costs[n - 1][min1];
}
}
reference:
https://discuss.leetcode.com/topic/22580/ac-java-solution-without-extra-space/2
继续是贪心的思想。
我一开始并不是这么做的，用了自己的做法，并且AC
在 I 中，是三个房子，我用了三个变量来存上一层。
所以这一题，我首先想到的就是，用 k 个变量，形成一个list，来存上一层。
于是写了下面代码：
My code:
public class Solution {
public int minCostII(int[][] costs) {
if (costs == null || costs.length == 0 || costs[0].length == 0) {
return 0;
}
List<Integer> last = new ArrayList<Integer>();
for (int i = 0; i < costs[0].length; i++) {
last.add(costs[0][i]);
}
for (int i = 1; i < costs.length; i++) {
List<Integer> curr = new ArrayList<Integer>();
for (int j = 0; j < last.size(); j++) {
curr.add(getMin(j, last) + costs[i][j]);
}
last = curr;
}
return getMin(-1, last);
}
private int getMin(int excludeIndex, List<Integer> list) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < list.size(); i++) {
if (i == excludeIndex) {
continue;
}
else {
min = Math.min(min, list.get(i));
}
}
return min;
}
}
AC
但是空间复杂度是 O(k)
而且，从链表中读写，也都需要消耗时间。
于是看了答案。发现自己对这道题目的认识还是不够深刻。
为什么要存 k 个变量呢？
我们要求最小值。那么， k 个变量都会对最终结果产生影响吗？
当然不会。
只有最小的两个，他们会对下一层结果产生结果。
或者说，下一层结果的最小值，一定是由这两个最小值决定的。
于是每一层只用两个变量来存下当前这一层，最小的两个cost的index
为什么是两个？
当我们遍历 [0, k - 1] 时，可能某个index = min1
所以这个时候我们不能用这个颜色。为了达到最小的结果。我们得存一个 min2
思路差不多就这样了。
然后一个小细节。
如何保存最小的两个变量呢？
int min1 = -1;
int min2 = -1
for (int j = 0; j < k; j++) {
if (min1 < 0 || costs[i][j] < costs[i][min1]) {
min2 = min1;
min1 = j;
}
else {
min2 = j;
}
}
注意第一个if里面加的 min2 = min1;
缺了他不可。
Anyway, Good luck, Richardo! -- 09/20/2016
