边工作边刷题：70天一遍leetcode: day 77

Paint House I/II

要点：这题要区分房子编号i和颜色编号k：目标是某个颜色，所以min的list是上一个房子编号中所有其他颜色+当前颜色的cost

https://repl.it/Chwe/1 (I)

善用slicing来eliminate list中一点，还有一点好处是不用考虑超越边界了

II：如何从O(nkk)降到O(n*k)? 每次找到上一个房子编号list的的min这个循环如果在每个k都做一遍，肯定是redundant的。其实loop一遍就能找到对所有颜色k需要的min：min和second_min：second_min用于min对应颜色的上一个房子

错误点：

注意不要搞混min/second_min的对象：因为当前颜色的cost是固定的。要min的是上一个房子编号的选择
list comprehension: if else的优先级低于+，所以+两种可能之一要把if else加括号
second_smallest的更新：如果smallest变了，第一件事是更新second_smallest，没变则比较second_smallest更新：所以是两处，并注意顺序

https://repl.it/Chxo/2 (II)

错误点：

小心k和循环下标混了
1d list就能搞定，因为下一个只依赖于前一个

# There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

# The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

# Note:

# All costs are positive integers.

# Hide Company Tags LinkedIn

# Hide Tags Dynamic Programming

# Hide Similar Problems (E) House Robber (M) House Robber II (H) Paint House II (E) Paint Fence

class Solution(object):

    def minCost(self, costs):

        """

        :type costs: List[List[int]]

        :rtype: int

        """

        prev = [0]*3

        for colors in costs:

        	prev = [colors[i] + min(prev[:i]+prev[i+1:]) for i in xrange(3)]

        return min(prev)

sol = Solution()

assert sol.minCost([[1,2,3],[4,5,6],[7,8,9]])==13

# There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

# The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

# Note:

# All costs are positive integers.

# Follow up:

# Could you solve it in O(nk) runtime?

# Hide Company Tags Facebook

# Hide Tags Dynamic Programming

# Hide Similar Problems (M) Product of Array Except Self (H) Sliding Window Maximum (M) Paint House (E) Paint Fence

class Solution(object):

    def minCostII(self, costs):

        """

        :type costs: List[List[int]]

        :rtype: int

        """

        if not costs: return 0

        n,k = len(costs), len(costs[0])

        prev = [0]*k

        for j in xrange(k):

            prev[j]=costs[0][j]

        for i in xrange(1, n):

            minVal, secondMin = float("inf"), float("inf")

            minIdx= -1

            for j in xrange(k):

                if prev[j]<minVal:

                    secondMin = minVal

                    minVal, minIdx = prev[j], j

                elif prev[j]<secondMin:

                    secondMin = prev[j]

            prev = [costs[i][j] + (minVal if j!=minIdx else secondMin) for j in xrange(k)]

        return min(prev)

sol = Solution()

assert sol.minCostII([[1,5,3],[2,9,4]])==5

assert sol.minCostII([[1,2,3],[4,5,6],[7,8,9]])==13

巴特西

边工作边刷题：70天一遍leetcode: day 77

Paint House I/II

最新文章

热门文章