- 浏览: 130616 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
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?
[分析]
使用color[j]刷house[i]时我们希望知道刷house[0,i-1]且house[i-1]刷的不是color[j]时的最小cost,于是求解过程中我们需要保留的就是dp[i][j],表示刷完house[0, i]的最小cost且house[i]使用color[j],递推式就是dp[i][j] = min(dp[i - 1][0]...dp[i-1][k-1]) + costs[i][j]
思路1:直接实现上面的递推式,复杂度是O(n*k*k),非最优。
思路2:受Product of Array Except Self启发,使用两个额外数组:
minPrior[i][j]表示使用color[0,j]刷house[i]时刷house[0,i]需要的最小cost,
minAfter[i][j]表示使用color[0,j]刷house[i]时刷house[i,n-1]需要的最小cost.
则递推式变为dp[i][j] = min(minPrior[i-1][j-1], minAfter[i-1][j+1]) + costs[i][j]
复杂度是O(n*k)。因为变量较多且需要处理边界元素,很快bug free难度较高。
思路3:每次迭代house i前先计算出dp[i-1][]的最小值和次小值,
则递推式简化为dp[i][j]=(dp[i-1][j] == preMin ? preSecondMin : preMin) + costs[i][j]
如果dp[i-1][j]正好是刷前面所有house的最小值,由于相邻house不能同色,那这次我们就要用次小值(运气好,可能和最小值相等~) 这个思路很清晰容易实现,且空间复杂度还低,
谢谢yb君分享的巧妙方案~
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?
[分析]
使用color[j]刷house[i]时我们希望知道刷house[0,i-1]且house[i-1]刷的不是color[j]时的最小cost,于是求解过程中我们需要保留的就是dp[i][j],表示刷完house[0, i]的最小cost且house[i]使用color[j],递推式就是dp[i][j] = min(dp[i - 1][0]...dp[i-1][k-1]) + costs[i][j]
思路1:直接实现上面的递推式,复杂度是O(n*k*k),非最优。
思路2:受Product of Array Except Self启发,使用两个额外数组:
minPrior[i][j]表示使用color[0,j]刷house[i]时刷house[0,i]需要的最小cost,
minAfter[i][j]表示使用color[0,j]刷house[i]时刷house[i,n-1]需要的最小cost.
则递推式变为dp[i][j] = min(minPrior[i-1][j-1], minAfter[i-1][j+1]) + costs[i][j]
复杂度是O(n*k)。因为变量较多且需要处理边界元素,很快bug free难度较高。
思路3:每次迭代house i前先计算出dp[i-1][]的最小值和次小值,
则递推式简化为dp[i][j]=(dp[i-1][j] == preMin ? preSecondMin : preMin) + costs[i][j]
如果dp[i-1][j]正好是刷前面所有house的最小值,由于相邻house不能同色,那这次我们就要用次小值(运气好,可能和最小值相等~) 这个思路很清晰容易实现,且空间复杂度还低,
谢谢yb君分享的巧妙方案~
public class Solution { public int minCostII(int[][] costs) { if (costs == null || costs.length == 0) return 0; int n = costs.length, k = costs[0].length; if (n > 1 && k == 1) { return 0; // ask interviewer whether return 0 or Integer.MAX } //dp[i][j]: minmum cost painting house 0-i with house i painted with color j int[][] dp = new int[n][k]; for (int j = 0; j < k; j++) dp[0][j] = costs[0][j]; for (int i = 1; i < n; i++) { int preMin = Integer.MAX_VALUE; int preSecondMin = Integer.MAX_VALUE; for (int j = 0; j < k; j++) { if (dp[i - 1][j] <= preMin) { preSecondMin = preMin; preMin = dp[i - 1][j]; } else if (dp[i - 1][j] < preSecondMin) { preSecondMin = dp[i - 1][j]; } } for (int j = 0; j < k; j++) { if (dp[i - 1][j] == preMin) { dp[i][j] = preSecondMin + costs[i][j]; } else { dp[i][j] = preMin + costs[i][j]; } } } int min = Integer.MAX_VALUE; for (int j = 0; j < k; j++) { min = Math.min(min, dp[n - 1][j]); } return min; } public int minCostII_Method1(int[][] costs) { if (costs == null || costs.length == 0) return 0; int n = costs.length, k = costs[0].length; if (n > 1 && k == 1) { return 0; } if (n == 1) { int min = costs[0][0]; for (int j = 1; j < k; j++) { min = Math.min(min, costs[0][j]); } return min; } int[][] dp = new int[n][k]; int[][] minPrior = new int[n][k]; int[][] minAfter = new int[n][k]; dp[0][0] = costs[0][0]; minPrior[0][0] = dp[0][0]; for (int j = 1; j < k; j++) { dp[0][j] = costs[0][j]; minPrior[0][j] = Math.min(minPrior[0][j - 1], dp[0][j]); } minAfter[0][k - 1] = dp[0][k - 1]; for (int j = k - 2; j >= 0; j--) { minAfter[0][j] = Math.min(minAfter[0][j + 1], dp[0][j]); } for (int i = 1; i < n; i++) { dp[i][0] = minAfter[i - 1][1] + costs[i][0]; minPrior[i][0] = dp[i][0]; for (int j = 1; j < k - 1; j++) { dp[i][j] = Math.min(minPrior[i - 1][j - 1], minAfter[i - 1][j + 1]) + costs[i][j]; minPrior[i][j] = Math.min(minPrior[i][j - 1], dp[i][j]); } dp[i][k - 1] = minPrior[i- 1][k - 2] + costs[i][k - 1];// at first minPrior[i][k - 2], make me crazy, cyb kill the bug minPrior[i][k - 1] = Math.min(minPrior[i][k - 2], dp[i][k - 1]); minAfter[i][k - 1] = dp[i][k - 1]; for (int j = k - 2; j >= 0; j--) { minAfter[i][j] = Math.min(minAfter[i][j + 1], dp[i][j]); } } return minPrior[n - 1][k - 1]; } }
发表评论
-
Leetcode - Ugly Number II
2015-08-24 22:54 1119[分析] 暴力的办法就是从1开始检查每个数是否是丑数,发现丑数 ... -
Leetcode - Maximum Square
2015-08-16 13:33 465Given a 2D binary matrix filled ... -
Leetcode - Paint House
2015-08-16 10:48 1114There are a row of n houses, ea ... -
Leetcode - Different Ways to Add Parentheses
2015-07-29 20:21 1154Given a string of numbers and o ... -
Jump Game II
2015-07-05 16:49 502Given an array of non-negative ... -
Leetcode - Jump Game
2015-07-05 15:52 489Given an array of non-negative ... -
Leetcode - Interleaving String
2015-06-07 11:41 566Given s1, s2, s3, find whe ... -
Leetcode - Wildcard Matching
2015-06-06 20:01 951Implement wildcard pattern ma ... -
Leetcode - Maximal Square
2015-06-04 08:25 588Given a 2D binary matrix fille ... -
Leetcode - Palindrome Partition II
2015-05-21 21:15 639Given a string s, partition ... -
Leetcode - Palindrome Partition
2015-05-21 09:56 748Given a string s, partition s s ... -
Leetcode - House Robber II
2015-05-20 22:34 731Note: This is an extension of ... -
Leetcode - Maximum Rectangle
2015-05-20 08:58 464Given a 2D binary matrix fill ... -
Leetcode - Scramble String
2015-05-17 14:22 542Given a string s1, we may repre ... -
Leetcode - Regular Expression Matching
2015-05-16 16:31 386Implement regular expression ma ... -
Leetcode - Distinct Subsequences
2015-05-01 16:56 464Given a string S and a string T ... -
Leetcode - Best Time to Buy and Sell Stock IV
2015-05-01 16:11 579Say you have an array for which ... -
Leetcode - Best Time to Buy and Sell Stock IV
2015-04-23 09:59 0public class Solution ... -
Leetcode - Best Time to Buy and Sell Stock III
2015-04-23 09:04 445Say you have an array for whi ... -
Leetcode - Dungeon Game
2015-04-21 09:50 414The demons had captured the pr ...
相关推荐
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode 答案解析 golang解答
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
leetcode-helper-1.7.1
leetcode-tag-dynamic programming
970. 强整数对数运算function powerfulIntegers(x: number, y: number, bound: number): numb
leetcode-tag-Tree
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
然后进入到LeetCode-Spider目录中修改config.json,其中outputDir需要填写该工程的/docs/views文件夹路径 { "username": "aaa", "password": "bbb", "outputDir": "/Users/liuyao/Downloads/LeetCode-Blog-Test/docs...
leetcode-tag-Stack
leetcode-tag-array