电影订票网站开发,网站备案现状,做音乐网站没有版权,工信部icp备案号查询一、动态规划
动态规划 是一种用于解决优化问题的算法设计技术#xff0c;尤其适用于具有重叠子问题和最优子结构性质的问题。它通过将复杂问题分解为更简单的子问题#xff0c;并保存这些子问题的解以避免重复计算#xff0c;从而提高效率。
动态规划的核心思想 最优子结…一、动态规划
动态规划 是一种用于解决优化问题的算法设计技术尤其适用于具有重叠子问题和最优子结构性质的问题。它通过将复杂问题分解为更简单的子问题并保存这些子问题的解以避免重复计算从而提高效率。
动态规划的核心思想 最优子结构Optimal Substructure 一个问题的最优解可以通过其子问题的最优解来构造。比如在最短路径问题中从起点到终点的最短路径可以由起点到某个中间点的最短路径和该中间点到终点的最短路径组合而成。 重叠子问题Overlapping Subproblems 在递归求解过程中相同的子问题会被多次求解。动态规划通过存储子问题的解来避免重复计算通常使用数组或哈希表等数据结构来存储这些解。
1.算法原理
1)状态表示
dp表(一维数组 填满该表其中某一个值就是结果 数组中某个数据值的意义就是状态表示)
通过题目要求 经验 分析问题发现重复子问题 来创建dp表
2)状态转移方程
dp[i]等于什么?
3)初始化
根据状态转移方程填表,保证填表的时候不越界
4)填表顺序
为了填写当前状态的时候,所需要的状态已经计算过了
5)返回值
题目要求状态表示
2.例题
泰波那契序列 Tn 定义如下
T0 0, T1 1, T2 1, 且在 n 0 的条件下 Tn3 Tn Tn1 Tn2
给你整数 n请返回第 n 个泰波那契数 Tn 的值。
示例 1输入n 4 输出4 解释 T_3 0 1 1 2 T_4 1 1 2 4
状态表示:dp[i]第i个泰波那契数的值
状态转移方程:dp[i]dp[i-1]dp[i-2]dp[i-3];
初始化:dp[0]0;dp[1]1;dp[2]1
填表顺序:从左向右
返回值:dp[n]
JAVA代码
class Solution {public int tribonacci(int n) {
if(n0) return 0;
if(n1||n2) return 1;
int[] dpnew int[n1];
dp[0]0;dp[1]1;dp[2]1;
for(int i3;in;i){dp[i]dp[i-1]dp[i-2]dp[i-3];
}
return dp[n];}
}
3.空间优化
求解某个状态时仅需要其的前几个状态
一定要确定好赋序
int tribonacci(int n){
//空间优化 滚动数组
if(n0) return 0;
if(n1||n2) return 1;
int a0;int b1,c1;int d0;
for(int i3;in;i){dabc;ab;bc;cd;}
return d;
}二、贪心算法
1.算法原理:
局部最优-全局最优
把解决问题的过程分为若干步,解决每一步的时候都选择当前看起来最优的解法
希望得到全局最优解
但贪心算法并不总是保证全局最优解
2.例题
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
示例 1
[7,1,5,3,6,4]
输出5
解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。示例 2
输入prices [7,6,4,3,1]
输出0
解释在这种情况下, 没有交易完成, 所以最大利润为 0。
在数组中挑出两个数,使其差值最大
1)暴力解法(两层for循环) 超出时间限制时间复杂度O(n^2)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;class Solution {public int maxProfit(int[] prices) {int ret 0;if (prices null || prices.length 2) {return 0;}for (int i 0; i prices.length - 1; i) {for (int j i1; j prices.length; j) {ret Math.max(ret, prices[j] - prices[i]);}}return ret;}public static void main(String[] args) {Scanner scnew Scanner(System.in);Solution solutionnew Solution();ListInteger pricesList new ArrayList();while (sc.hasNextInt()) {pricesList.add(sc.nextInt());}int[] prices new int[pricesList.size()];for (int i 0; i pricesList.size(); i) {prices[i] pricesList.get(i);}int retsolution.maxProfit(prices);System.out.println(ret);sc.close();}
}//在输入结束后输入一个非数字字符如字母 q这样 hasNextInt() 会返回 false从而结束循环,或 Ctrl ZWindows来发送 EOF 信号。
2)贪心
分为两段,prevmin表示前一段中最小值(买入),prices[i]卖出去的价钱
class Solution {public int maxProfit(int[] prices) {int ret0;for(int i0,prevminInteger.MAX_VALUE;iprices.length;i){retMath.max(ret,prices[i]-prevmin);prevminMath.min(prevmin,prices[i]);}return ret;}
} 三、 (双指针算法)
给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。
请注意 必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums [0,1,0,3,12]
输出: [1,3,12,0,0]
数组划分
利用数组下标充当指针
两个指针的作用:
cur:从左往右扫描,遍历数组
dest:已处理的区间内,非0元素的最后一个位置
三个区间:
[0,dest] [dest1,cur-1] [cur,n-1]
非0 0元素 待处理的区间
解法:
初始dest-1 cur0
遇到0元素,cur;
遇到非0元素 swap(dest1,cur)交换位置 dest cur class Solution {public void moveZeroes(int[] nums) {
int dest-1;
int cur0;
int k0;
int nnums.length;
while(curn){
if(nums[cur]0)
cur;
else
{dest;
knums[dest];
nums[dest]nums[cur];
nums[cur]k;
cur;
}}}
} 给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。
在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。
返回 你能获得的 最大 利润 。
输入prices [7,1,5,3,6,4]
输出7
解释在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4。
随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3。
最大总利润为 4 3 7 。
利用数组下标充当指针(i,j)
class Solution {public int maxProfit(int[] prices) {//双指针算法int ret0;int i0,j0;for(i0;iprices.length;i){ji;while(j1prices.length prices[j1]-prices[j]0){j;}retprices[j]-prices[i];ij;}return ret;}
}
四、递归
1.什么是递归
函数自己调用自己(主问题-相同的子问题)
出口(一个问题不能在分割了)
1.算法思想
函数头 函数体 递归出口
把递归的函数当成一个黑盒,不在意递归的细节
深度优先遍历(后序遍历)
2.例题
计算布尔二叉树的值
给你一棵 完整二叉树 的根这棵树有以下特征
叶子节点 要么值为 0 要么值为 1 其中 0 表示 False 1 表示 True 。非叶子节点 要么值为 2 要么值为 3 其中 2 表示逻辑或 OR 3 表示逻辑与 AND 。
计算 一个节点的值方式如下
如果节点是个叶子节点那么节点的 值 为它本身即 True 或者 False 。否则计算 两个孩子的节点值然后将该节点的运算符对两个孩子值进行 运算 。
返回根节点 root 的布尔运算值。
完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。
叶子节点 是没有孩子的节点。
class Solution {public boolean evaluateTree(TreeNode root) {if(root.leftnull) return root.val0 ? false: true;boolean leftevaluateTree(root.left);boolean rightevaluateTree(root.right);return root.val2 ?left | right : left right;}
}
