极客时间算法课笔记整理15——理论讲解+面试题实战:动态规划
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了极客时间算法课笔记整理15——理论讲解+面试题实战:动态规划,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4084字,纯文字阅读大概需要6分钟。
内容图文
![极客时间算法课笔记整理15——理论讲解+面试题实战:动态规划](/upload/InfoBanner/zyjiaocheng/611/b19c71bceb9f472e8427a3bc635d4a7b.jpg)
文章目录
- 动态规划(Dynamic Programming)
- 面试题
- [70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)
- [120. Triangle](https://leetcode.com/problems/triangle/)
- [152. Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/)
- [121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)
- [122. Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/)
- [123. Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/)
- [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)
- [322. Coin Change](https://leetcode.com/problems/coin-change/)
- [72. Edit Distance](https://leetcode.com/problems/edit-distance/)
动态规划(Dynamic Programming)
代码简化:
复杂度是2n
加入记忆
反过来:
一个例子
时间复杂度O(m*n)
面试题
70. Climbing Stairs
我的:
class Solution {
public int climbStairs(int n) {
int[] memory= new int[n+1];
memory[0]=1;
memory[1]=1;
for(int i=2;i<=n;i++){
memory[i]=memory[i-1]+memory[i-2];
}
return memory[n];
}
}
老师的:
120. Triangle
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int length= triangle.size();
for(int i=length-2;i>=0;i--){
List<Integer> tmp= triangle.get(i);
List<Integer> under= triangle.get(i+1);
for(int j =0; j< tmp.size(); j++){
int min = (under.get(j)>under.get(j+1)?under.get(j+1):under.get(j));
tmp.set(j,tmp.get(j)+ min);
}
}
return triangle.get(0).get(0);
}
}
152. Maximum Product Subarray
class Solution {
public int maxProduct(int[] nums) {
if(nums==null){return 0;}
int length=nums.length;
if(length==1){return nums[0];}
int[] tmp= new int[length+1];
tmp[length-1]=1;
int res=nums[0];
for(int i=1;i<=length;i++){
tmp[length-i]=1;
for(int j= length;j>=length-i;j--){
tmp[j]=nums[i-1]*tmp[j];
res=(res>tmp[j]?res:tmp[j]);
}
}
return res;
}
}
老师的方法:
待实现!
121. Best Time to Buy and Sell Stock
一次买卖
一个报错
class Solution {
public int maxProfit(int[] prices) {
int res=0;
if(prices.length ==0){return res;}
int min=prices[0];
for(int i=1;i<prices.length;i++){
min=prices[i]<min?prices[i]:min;
res=(prices[i]-min>res?prices[i]-min:res);
}
return res;
}
}
122. Best Time to Buy and Sell Stock II
多次买卖
class Solution {
public int maxProfit(int[] prices) {
int res=0;
if(prices==null || prices.length==1){return 0;}
int last=prices[0];
int tmp=prices[0];
for(int i=1;i<prices.length;i++){
tmp=prices[i];
int profits=tmp-last;
res+= (profits>0?profits:0);
last=tmp;
}
return res;
}
}
123. Best Time to Buy and Sell Stock III
老师的思路
N天,k次,可以持有股票数
多股股票
代码:
300. Longest Increasing Subsequence
报错原因:内层循环写成i++、是死循环
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums==null || nums.length==0 ){return 0;}
int[] LIS = new int[nums.length];
int res=1;
LIS[0]=1;
for(int i=1;i<nums.length;i++){
int max=0;
for(int j=0;j<i;j++){
if(LIS[j]>max && nums[i]>nums[j]){
max=LIS[j];
}
}
LIS[i]=max+1;
res=(LIS[i]>res?LIS[i]:res);
}
return res;
}
}
322. Coin Change
注意初始值的设置;用于判别
我的代码:
class Solution {
public int coinChange(int[] coins, int amount) {
int[] counts=new int[amount+1];
counts[0]=0;
for(int i=1;i<=amount;i++){
int min=0;
for(int j=0;j<coins.length;j++){
int tmp =i-coins[j];
if(tmp>= 0 && counts[tmp]!=-1){
if(min==0){
min=counts[tmp]+1;
}else{
min=(min<counts[tmp]+1?min:counts[tmp]+1);
}
}
}
if(min==0){
counts[i]=-1;
}else{
counts[i]=min;
}
}
return counts[amount];
}
}
老师的方法:
72. Edit Distance
老师的方法:BFS>DFS;没理解
class Solution {
public int minDistance(String word1, String word2) {
char[] w1=word1.toCharArray();
char[] w2=word2.toCharArray();
int[][] mp=new int[w1.length+1][w2.length+1];
for(int i=0;i<=w2.length;i++){
mp[0][i]=i;
}//注意别忘记初始值的设置
for(int i=0;i<=w1.length;i++){
mp[i][0]=i;
}
for(int i=1;i<=w1.length;i++){
for(int j=1;j<=w2.length;j++){
if(w1[i-1]==w2[j-1]){
mp[i][j]=mp[i-1][j-1];
}else{
mp[i][j]=min(mp[i][j-1],mp[i-1][j],mp[i-1][j-1])+1;
}
}
}
return mp[w1.length][w2.length];
}
public static int min(int a, int b, int c){
int res=a;
res=(res<b?res:b);
res=(res<c?res:c);
return res;
}
}
内容总结
以上是互联网集市为您收集整理的极客时间算法课笔记整理15——理论讲解+面试题实战:动态规划全部内容,希望文章能够帮你解决极客时间算法课笔记整理15——理论讲解+面试题实战:动态规划所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。