Datawhale 系列数据结构
本文参考链接：
01背包问题：https://blog.csdn.net/chanmufeng/article/details/82955730
Task7.1 递归
7.1.1爬楼梯
//爬楼梯：
//假设你正在爬楼梯。需要 n 阶你才能到达楼顶
//每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
class Solution {
public int climbStairs(int n) {
int [] ways = new int[n+1];
ways[0] = 0;
for (int i = 1;i<ways.length;i++){
if (i < 3 ){
ways[i] = i;
}else {
ways[i] = ways[i-1] + ways[i-2];
}
}
return ways[n];
}
}
//使用最小花费爬楼梯
//数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。
//每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
//您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
class Solution {
public int minCostClimbingStairs(int[] cost) {
int length = cost.length;
int[] newCost = new int[length+1];
newCost = Arrays.copyOf(cost,length+1);
length = length+1;
cost = newCost;
int[] fn = new int[length];
fn[0] = 0;
fn[1] = 0;
fn[2] = Math.min(cost[0],cost[1]);
for (int i = 3;i<length;i++){
fn[i] = Math.min(fn[i-1] + cost[i-1],fn[i-2]+cost[i-2]);
}
return fn[length-1];
}
}7.1.2 0-1背包问题（递归方法解决）
问题描述：
给定 n 种物品重量$ w_1,w_2,w_3,...,w_n $,价值为$v_1,v_2,v_3,...,v_4$，一个容量为$C$的背包，问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
递归思想：
首先我们用递归的方式来尝试解决这个问题
我们用$F(n,C)$ 表示将前$n$个物品放进容量为$C$的背包里，得到最大的价值。
我们用自顶向下的角度来看，假如我们已经进行到了最后一步（即求解将$n$个物品放到背包了获得最大价值），此时我们便有两种选择：
1.不放第$n$个物品，此时总价值为$F(n-1,C)$
2.放置第$n$个物品，此时总价值为$v_n+F(n-1,C-w_n)$两种选择中总价值最大的方案就是我们的最终方案，递推式如下：
$F(i,C)=max(F(i-1,C),v(i)+F(i-1,C-w(i)))$//递归解法
public static int solveKS(int[] w,int[] v,int index,int capacity ){
if(index<0 || capacity <=0) return 0;
int res = solveKS(w,v,index-1,capacity);
if(w[index]<=capacity){
res=Math.max(res, v[index]+solveKS(w,v,index-1,capacity-w[index]));
}
return res;
}
public static int knapSack(int [] w,int [] v,int C){
int size=w.length;
return solveKS(w,v,size-1,C);
}Task 7.2 回溯
7.2.1八皇后问题
public static int [][] array=new int[8][8];
public static int map=0;
public static void main(String[] args) {
System.out.println("八皇后问题");
findQueen(0);
System.out.println("八皇后问题共有："+map+"种可能");
}
public static void findQueen(int i){
if(i>7){
map++;
print();//
return;
}
for(int m=0;m<8;m++){
if(check(i,m)){
array[i][m]=1;
findQueen(i+1);
array[i][m]=0;
}
}
}
public static boolean check(int k, int j){
for(int i=0;i<8;i++){//检查行列冲突
if(array[i][j]==1){
return false;
}
}
for(int i=k-1,m=j-1;i>=0&& m>=0;i--,m--){
if(array[i][m]==1){//检查左对角线冲突
return false;
}
}
for(int i=k-1,m=j+1;i>=0&&m<=7;i--,m++){
if(array[i][m]==1){
return false;
}
}
return true;
}
public static void print(){
System.out.print("方案"+map+":"+"\n");
for(int i=0;i<8;i++){
for(int m=0;m<8;m++){
if(array[i][m]==1){
//System.out.print("皇后"+(i+1)+"在第"+i+"行，第"+m+"列\t");
System.out.print("o ");
}
else{
System.out.print("+ ");
}
}
System.out.println();
}
System.out.println();
}7.2.2求解0-1背包问题（回溯方法解决）
整体思路：
用回溯法需要构造子集树。对于每一个物品i,对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一颗空间树：基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案算法设计：
利用回溯设计一个算法求出0-1背包问题的解，也就是求出一个解向量xi(即对n个物品放或不妨的一种的方案)
其中，（xi=0或1，xi=0表示物体i不放入背包，xi=1表示把物体i放入背包）。
在递归函数Backtrack中，
当i>n时，算法搜索到叶子节点，得到一个新的物品包装方案。此时算法适时更新当前的最有价值。
当i<n时，当前扩展结点位于排列树的第（i-1）层，此时算法选择下一个要安排的物品，以深度优先方式递归的对相应的子树进行搜索，对不满足上界约束的结点，则剪去相应的子树//回溯
public class KnapSack02 {
private static int n=3;//物品数量编号，从0开始
private static double c=5;//背包容量
private static double [] v={12,10,20,15};//各个物品的价值
private static double [] w={2,1,3,2};//各个物品的重量
private static double cw = 0.0;//当前背包重量 current weight
private static double cp = 0.0;//当前背包中物品总价值 current value
private static double bestp = 0.0;//当前最优价值best price
private static double [] perp = new double [4];//单位物品价值(排序后) per price
private static int [] order = new int [4];//物品编号
private static int [] put = new int [4];//设置是否装入，1装入，0不装
//按单位价值排序
public static void knapsack(){
int i,j;
int temporder = 0;
double temp= 0.0;
for(i=1;i<=n;i++)
perp[i]=v[i]/w[i];
for(i=1;i<=n-1;i++)
{
for(j=i+1;j<=n;j++)
if(perp[i]<perp[j])//冒泡排序perp[],order[],sortv[],sortw[]
{
temp = perp[i]; //冒泡对perp[]排序
perp[i]=perp[i];
perp[j]=temp;
temporder=order[i];//冒泡对order[]排序
order[i]=order[j];
order[j]=temporder;
temp = v[i];//冒泡对v[]排序
v[i]=v[j];
v[j]=temp;
temp=w[i];//冒泡对w[]排序
w[i]=w[j];
w[j]=temp;
}
}
}
public static void backtrack(int i){
//i表示到达的层数（第几步，从0开始），同事也只是当前选择玩了几个物品
bound( i);
if(i>n){
bestp=cp;
return;
}
//如若左子节点可行，则直接搜索左子树;
//对于右子树，先计算上界函数，以判断是否将其减去
if(cw+w[i]<=c)//将物品i放入背包,搜索左子树
{
cw+=w[i];//同步更新当前背包的重量
cp+=v[i];//同步更新当前背包的总价值
put[i]=1;
backtrack(i+1);//深度搜索进入下一层
cw-=w[i];//回溯复原
cp-=v[i];//回溯复原
}
if(bound(i+1)>bestp)//如若符合条件则搜索右子树
backtrack(i+1);
}
//计算上界函数，功能为剪枝
public static double bound(int i)
{ //判断当前背包的总价值cp＋剩余容量可容纳的最大价值<=当前最优价值
double leftw= c-cw;//剩余背包容量
double b = cp;//记录当前背包的总价值cp,最后求上界
//以物品单位重量价值递减次序装入物品
while(i<=n && w[i]<=leftw)
{
leftw-=w[i];
b+=v[i];
i++;
}
//装满背包
if(i<=n)
b+=v[i]/w[i]*leftw;
return b;//返回计算出的上界
}
public static void main(String[] args) {
knapsack();
backtrack(1);
System.out.println(bestp);
}
}Task7.3 分治
7.3.1 利用分治算法求一组数据的逆序对个数
public class ReverseOrder {
private static int sum = 0;
private static int []a ={5,4,2,6,3,1};
private static int []b =new int [6];
public static void worksort(int l,int r){
int mid,tmp,i,j;
if(r>l+1){
mid=(l+r)/2;
worksort(l,mid-1);
worksort(mid,r);
tmp=l;
for(i=l,j=mid;i<=mid-1 && j<=r;){
if(a[i]>a[j])
{
b[tmp++]=a[j++];//快速排序
sum+=mid-i;//统计逆序对个数
}
else
b[tmp++]=a[i++];
}
if(j<=r)
for(;j<=r;j++) b[tmp++]=a[j];
else
for(;i<=mid-1;i++) b[tmp++]=a[i];
for(i=l;i<=r;i++) a[i]=b[i];//将排好序的b数组赋值给a数组
}else{
if(l+1==r)//递归的边界
if(a[l]>a[r])
{ int temp = a[l];
a[l]=a[r];
a[r]=temp;
sum++;
}
}
}
public static void main(String[] args) {
worksort(0,5);
System.out.println(sum);
}
}Task 7.4 动态规划
7.4.1 0-1背包问题
//动态规划
int size = w.length;
if (size == 0) {
return 0;
}
int[] dp = new int[C + 1];
//初始化第一行
//仅考虑容量为C的背包放第0个物品的情况
for (int i = 0; i <= C; i++) {
dp[i] = w[0] <= i ? v[0] : 0;
}
for (int i = 1; i < size; i++) {
for (int j = C; j >= w[i]; j--) {
dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]);
}
}
return dp[C];
}
public static void main(String[] args) {
int[] w = {2, 1, 3, 2};
int[] v = {12, 10, 20, 15};
System.out.println(knapSack(w, v, 5));
}7.4.2 编程实现莱温斯坦最短编辑距离
public static int minEditDistance(String dest,String src){
int [][] f=new int[dest.length()+1][src.length()+1];
f[0][0]=0;
for(int i=1;i<dest.length()+1;i++){
f[i][0]=i;
}
for(int i=1;i<src.length()+1;i++){
f[0][i]=i;
}
for(int i=1;i<dest.length()+1;i++){
for(int j=1;j<src.length()+1;j++){
int cost=0;
if(dest.charAt(i - 1) != src.charAt(j - 1)){
cost=1;
}
int minCost;
if(f[i-1][j]<f[i][j-1]){
minCost=f[i-1][j]+cost;
}else{
minCost=f[i][j-1]+cost;
}
f[i][j]=minCost;
}
}
return f[dest.length()][src.length()];
}
public static void main(String[] args) {
System.out.println(minEditDistance("sot", "stop"));
}7.4.3 编程实现查找两个字符串的最长子序列
//求解str1 和 str2 的最长公共子序列
public static int LCS(String str1, String str2){
int[][] c = new int[str1.length() + 1][str2.length() + 1];
for(int row = 0; row <= str1.length(); row++)
c[row][0] = 0;
for(int column = 0; column <= str2.length(); column++)
c[0][column] = 0;
for(int i = 1; i <= str1.length(); i++)
for(int j = 1; j <= str2.length(); j++)
{
if(str1.charAt(i-1) == str2.charAt(j-1))
c[i][j] = c[i-1][j-1] + 1;
else if(c[i][j-1] > c[i-1][j])
c[i][j] = c[i][j-1];
else
c[i][j] = c[i-1][j];
}
return c[str1.length()][str2.length()];
}
//test
public static void main(String[] args) {
String str1 = "BDCABA";
String str2 = "ABCBDAB";
int result = LCS(str1, str2);
System.out.println(result);
}7.4.4编程实现一个数据序列的最长递增子序列
class Solution {
public int lengthOfLIS(int[] nums) {
/**
dp[i]: 所有长度为i+1的递增子序列中, 最小的那个序列尾数.
由定义知dp数组必然是一个递增数组, 可以用 maxL 来表示最长递增子序列的长度.
对数组进行迭代, 依次判断每个数num将其插入dp数组相应的位置:
1. num > dp[maxL], 表示num比所有已知递增序列的尾数都大, 将num添加入dp
数组尾部, 并将最长递增序列长度maxL加1
2. dp[i-1] < num <= dp[i], 只更新相应的dp[i]
**/
int maxL = 0;
int[] dp = new int[nums.length];
for(int num : nums) {
// 二分法查找, 也可以调用库函数如binary_search
int lo = 0, hi = maxL;
while(lo < hi) {
int mid = lo+(hi-lo)/2;
if(dp[mid] < num)
lo = mid+1;
else
hi = mid;
}
dp[lo] = num;
if(lo == maxL)
maxL++;
}
return maxL;
}
}Task 7.5 练习
7.5.1 实战递归
//Letter Combinations of a Phone Number(17)
String[] button=new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
List<String> list=new ArrayList<>();
public List<String> letterCombinations(String digits) {
if (digits==null||digits.length()==0)
return list;
letterCombinations(digits,0,new String());
return list;
}
public void letterCombinations(String digits,int index,String temp) {
if(index==digits.length()){
list.add(temp);
return;
}
int position=digits.charAt(index)-'0';
String str=button[position];
for (int i=0;i<str.length();i++){
letterCombinations(digits,index+1,temp+str.charAt(i));
}
}
//permutations(46)
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
permutation(nums, 0, nums.length - 1);
return res;
}
private void permutation(int[] nums, int p, int q) {
if (p == q) {
res.add(arrayToList(nums));
}
for (int i = p; i <= q; i++) {
swap(nums, i, p);
permutation(nums, p + 1, q);
swap(nums, i, p); // 这里要交换回来，免得出现重复的情况
}
}
private List<Integer> arrayToList(int[] nums) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
res.add(nums[i]);
}
return res;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}7.5.2 实战dp
//完成0-1背包问题实现(自我实现)及Leetcode
参考7.4.1
//Palindrome Partitioning II(132)
public int minCut(String s) {
if(s == null || s.isEmpty()){
return 0;
}
int len = s.length();
boolean[][] dp = new boolean[s.length()][s.length()];
int[] cut = new int[s.length()];
for(int i = 0; i < len; i++){
//最大划分就是i次
cut[i]= i;
for(int j = 0; j <= i; j++){
if(s.charAt(i) == s.charAt(j) &&(i-j <= 1 || dp[j+1][i-1])){
dp[j][i] = true;
if(j == 0) {
//0-i直接是回文
cut[i] = 0;
} else {
cut[i] = Math.min(cut[j-1]+1, cut[i]);
}
}
}
}
return cut[len-1];
}
7.5.2 可选练习
//Regular Expression Matching（正则表达式匹配）
class Solution {
public boolean isMatch(String text, String pattern) {
if (pattern.isEmpty()) return text.isEmpty();
boolean first_match = (!text.isEmpty() &&
(pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
if (pattern.length() >= 2 && pattern.charAt(1) == '*'){
return (isMatch(text, pattern.substring(2)) ||
(first_match && isMatch(text.substring(1), pattern)));
} else {
return first_match && isMatch(text.substring(1), pattern.substring(1));
}
}
}
//Minimum Path Sum（最小路径和）
public int minPathSum(int[][] grid) {
int rows=grid.length;
int cols=grid[0].length;
int [] dp=new int[cols];
dp[0]=grid[0][0];
for(int col=1;col<cols;col++){
dp[col]=dp[col-1]+grid[0][col];
}
for(int row = 1; row < rows; row++) {
for(int col = 0; col < cols; col++) {
if(col > 0){
dp[col] = Math.min(dp[col-1], dp[col]) + grid[row][col];
}else{
dp[col] += grid[row][col];
}
}
}
return dp[cols - 1];
}
//Coin Change （零钱兑换）[作为可选]
//Best Time to Buy and Sell Stock（买卖股票的最佳时机）[作为可选]
//Maximum Product Subarray（乘积最大子序列）[作为可选]
//Triangle（三角形最小路径和）[作为可选]