数据结构算法题目（四）：攀登者杯

贪心算法篇

1. 划分数组为连续数字的集合

给你一个整数数组 nums 和一个正整数 k，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。 如果可以，请返回 true；否则，返回 false。

输入：nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3 输出：true 解释：数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]。

哈希表+贪心算法

假设数据可被划分多个连续数组，就从单个连续数组构造开始。哈希表统计各元素个数，nums[i]到nums[i]+k-1尝试构造k个数（因此num[i]应该有序），并且消耗个数，只有哈希表个数全为0，才可能划分成功。

class Solution {
public:
    bool isPossibleDivide(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        unordered_map<int,int>umap;
        for(int i=0; i<nums.size(); i++){
            umap[nums[i]]++;
        }
        for(int i=0; i<nums.size(); i++){
            if(umap[nums[i]]>0){
                for(int j = nums[i]; j<=nums[i]+k-1; j++){
                    umap[j]--;
                }
            }
        }
        
        for(auto i:umap){
            if(i.second!=0)
                return false;
        }
        return true;
    }
};

• 时间复杂度：哈希表计算O(kn)，排序是O(nlogn)，综合是O(nlogn)

• 空间复杂度：O(n)

递归/回溯篇

1. 求根节点到叶节点数字之和

给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

example：
输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

dfs+回溯

dfs遍历结点，结束条件是遇到空结点或者叶子节点，记得对称回溯。

class Solution {
public:
    string temp;  //存放每个路径数字
    vector<string> result;  //存放所有路径
    void dfs(TreeNode* root){
        if(root==nullptr)  //递归结点空
            return;
        else if(root->left==nullptr&&root->right==nullptr){  //叶子节点
            temp.push_back(root->val+'0');  //叶子入队
            result.push_back(temp);
            temp.pop_back();  //叶子出队回溯
            return;
        }
        temp.push_back(root->val+'0');  //非叶子结点
        dfs(root->left);      //递归左右
        dfs(root->right);    
        temp.pop_back();  //非叶子出队
    }

    int sumNumbers(TreeNode* root) {
        dfs(root);  
        int sum = 0;
        for(int i=0; i<result.size(); i++){  //统计结果
            sum += stoi(result[i]);
        }        
        return sum;
    }
};

动态规划篇

购物单

王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大，满意度是指所购买的每件物品的价格与重要度的乘积的总和。

输入描述： 输入的第 1 行，为两个正整数N，m，用一个空格隔开：

（其中 N （ N<32000 ）表示总钱数， m （m <60 ）为可购买的物品的个数。）

从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q

（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）

输出描述： 输出一个正整数，为张强可以获得的最大的满意度。

输入：
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
输出：2200
解析：从主物品入手，买800满意度只为1600，买400+500满意度为2200，不能单独买重要程度为5的400商品，因为它是编号1（即800）主件的附件，因此最高满意度为2200。

问题分析：每个商品只有输入的m种，如果不考虑附件，那么就是典型的01背包问题，钱就是最大容量，满意度是dp数组。现在有附件问题，就要使用一种数据结构将附件纳入一起主件考虑，这里是有限的附件（最多两个），因此此处选择定义数据结构，统一讨论：

• 当不含附件时，只需要考虑是否放入主件；

• 当含附件时：考虑5种情况（什么都不放、只放主、放主+附1、主+附2、全放）；

开始想比较难，但是数据结构确定了就不难明白。将附件都划归到主件行管理，初始化时，第一列j==0，没钱没满足度，不用初始化；i==0时，第一个主件自由组合，这里要考虑主件、附件的自由组合，完成初始化后续只需要判断与上一个满意度的比较。

其他细节：输入流需要小心处理，要确保主件、附件划分正确，全0行是否滤除没有太大关系；

#include <iostream>
#include <iterator>
#include <sys/types.h>
#include <vector>
#include <algorithm>
using namespace std;
struct price{  //主物品价格、从物品1、2价格（Optional）
    int mprice, s1price, s2price;
};

struct matter{  //主物品重要程度、从物品1、2重要程度（Optional）
    int mmatter, s1matter, s2matter;
};

class Solution{
public:
    int get_result(vector<price>& vp,vector<matter>& vm,int money){
        int m = vp.size();  //主物品的数量（含全0行没关系）
        int n = (money/10);//（价钱是10的倍数，减少开辟数组空间）
        
        vector<vector<int>>dp(m,vector<int>(n+1)); 

        //初始化：只放第一个主物品
        for(int j=1; j<=n; j++){

            int m_pandm = vp[0].mprice*vm[0].mmatter;  //主物品满意度 = 价钱*重要程度
            int s1_pandm = vp[0].s1price*vm[0].s1matter; //从1物品满意度
            int s2_pandm = vp[0].s2price*vm[0].s2matter; //从2物品满意度

            if(vp[0].mprice<=j)   //放得下主物品
                dp[0][j] = m_pandm;

            if(vp[0].mprice+vp[0].s1price<=j)  //放得下主+从1
                dp[0][j] = max(dp[0][j],m_pandm+s1_pandm);  //肯定大于，max不max没关系

            if(vp[0].mprice+vp[0].s2price<=j)  //放得下主+从2
                dp[0][j] = max(dp[0][j],m_pandm+s2_pandm); //一定要max，比较放从1还是从2

            if(vp[0].mprice+vp[0].s1price+vp[0].s2price<=j) //主+从1+从2均可
                dp[0][j] = m_pandm+s1_pandm+s2_pandm;
    
        }

        for(int i=1; i<m; i++){
            for(int j=1; j<=n; j++){
                if(vp[i].mprice>j)   //放不下主物品
                    dp[i][j] = dp[i-1][j];
                else{
                    int m_pandm = vp[i].mprice*vm[i].mmatter;
                    int s1_pandm = vp[i].s1price*vm[i].s1matter;
                    int s2_pandm = vp[i].s2price*vm[i].s2matter;

                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-vp[i].mprice]+m_pandm); //放得下主

                    if(vp[i].mprice+vp[i].s1price<=j)  //放得下主+从1
                        dp[i][j] = max(dp[i][j],dp[i-1][j-vp[i].mprice-vp[i].s1price]+m_pandm+s1_pandm);

                    if(vp[i].mprice+vp[i].s2price<=j)  //放得下主+从2
                        dp[i][j] = max(dp[i][j],dp[i-1][j-vp[i].mprice-vp[i].s2price]+m_pandm+s2_pandm);

                    if(vp[i].mprice+vp[i].s1price+vp[i].s2price<=j) //主+从1+从2均可
                        dp[i][j] = max(dp[i][j],dp[i-1][j-vp[i].mprice-vp[i].s1price-vp[i].s2price]+m_pandm+s1_pandm+s2_pandm);
            
                }
            }
        }
        return dp[m-1][n];  //m-1主物品自由组合，不超过n价格

    }



};


int main() {
    int money,n;  //钱、n个物品
    cin>>money>>n;

    int a,b,c; //物价、重要程度、主编号0/从属的主编号
    vector<price>vp(n+1);  //最多n个主物品,+1对齐编号
    vector<matter>vm(n+1);
    int i=0; 
    while(n--){
        cin>>a>>b>>c;
        a/=10;  //钱定义了列数，降数据复杂度
        i++; //放主物品的序号，从1放起
        if(c==0){  //放主物品
            vp[i].mprice = a;
            vm[i].mmatter = b;
        }
        else{
            if(vp[c].s1price==0){    //放从1
                vp[c].s1price = a;
                vm[c].s1matter = b;
            }
            else{
                vp[c].s2price = a; //放从2
                vm[c].s2matter = b;
            }
        }
    }

    Solution mySolution;
    cout<<10*mySolution.get_result(vp, vm, money)<<endl; //输出要乘回去10
    
    return 0;
}

徒步旅行中的补给问题

小R正在计划一次从地点A到地点B的徒步旅行，总路程需要 N 天。为了在旅途中保持充足的能量，小R每天必须消耗1份食物。幸运的是，小R在路途中每天都会经过一个补给站，可以购买食物进行补充。然而，每个补给站的食物每份的价格可能不同，并且小R最多只能同时携带 K 份食物。

现在，小R希望在保证每天都有食物的前提下，以最小的花费完成这次徒步旅行。你能帮助小R计算出最低的花费是多少吗？

example:输入：n = 5 ,k = 2 ,data = [1, 2, 3, 3, 2]
输出：9

记忆化搜索

问题分析:这是背包问题吗？不是，因为存在底线：必须保证每日食物不为空；因此只能回归递归问题了，起始枚举每天的选择，递归子问题即可，每天选择是：

• 食物不为0，明天再考虑买不买的子问题；

• 买1份——k-ret份的最划算计划，其中ret代表当前最多食物量。

因此可以知道，这次的递归不是二叉树了，而是一个多叉树，因此记忆化剪枝非常高效，以下：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int dfs(vector<int>&data,int n,int k,int i,int ret,vector<vector<int>>&db_Array){  //总天数、规定的最多携带食物量、剩余天数、剩余食物量
    if(ret>=i)  //剩余食物足够天数，不用考虑再买了
        return 0;
    //if(ret<0)  //非必须：食物量小于0，该方法不可取，给个大值
    //    return INT_MAX/2;
    if(db_Array[i][ret]!=0)   //记忆化搜索：只有剩余天数、剩余食物量一致才可记忆
        return db_Array[i][ret];
    int cost = INT_MAX;  //找当前买和不买的最小值
    if(ret!=0)  //还有食物，可以下一天买
        cost = dfs(data,n,k,i-1,ret-1,db_Array);  //下一天再考虑买不买
    for(int j=1; j<=k-ret; j++){  //买的数量讨论
        cost = min(cost,dfs(data,n,k,i-1,ret+j-1,db_Array)+data[n-i]*j);
    }  //data[n-i]代表当天价格，j代表买几份
    return db_Array[i][ret]=cost;
}


int solution(int n, int k, std::vector<int> data) {
    vector<vector<int>>db_Array(n+1,vector<int> (k+1)); //记忆化数组
    int result = 0;
    result += dfs(data,n,k,n,0,db_Array); 
    return result;
}

int main() {
    // Add your test cases here

    std::cout << (solution(5, 2, {1, 2, 3, 3, 2}) == 9) << std::endl;
    return 0;
}

小美打怪

小E在一个游戏中遇到了n个怪物。每个怪物都有其特定的血量hi和攻击力ai。小E的初始血量为H，攻击力为A。她可以击败那些血量和攻击力都小于她自身的怪物。每击败一个怪物后，小E的血量和攻击力会变为该怪物的血量和攻击力。小E想知道，她最多能击败多少怪物。

example:输入：
3 4 5
1 2 3
3 2 1

输出：1 解析：最多只能打败一个怪物。

BUG：该题应该是比较新的题，豆包内测测试用例是错误的，按攻击力排序能够通过牛客的测试，按血量排序却仅通过91%，应该是测试用例本身问题。

动态规划

问题分析：本题需要《最长递增子序列基础》：只有血量和攻击力低于的时候才能打败，且小美会继承怪物的攻击力。因此首先将怪物的攻击力进行排序，此时其血量分布可能是乱序的，例如当怪物攻击力分别为1，2，3，4，5时，其血量分布是5，2，3，6，1；假设小美初始攻击力和血量均为5，那么只能打败下标为1和2两只，而血量下标3的最长子序列也恰好是2，因此只需要确保怪物的血量、攻击力均小于初始攻击力，其最长子序列长度就是能够打败的怪物数。（最长子序列内部是严格递增的，代表能力继承后一定能够打败前面的）。

以下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct master{
    int h,a;  //怪物血量、攻击力
};

//最长递增子序列
//怪物攻击力已经从小到大排序，只需要从小到大找到血量序列即可
vector<int> get_subArray(int n,vector<master>&vp){
    vector<int>dp(n);  //各位置的最长子序列长度
    for(int i=0; i<n; i++){   //此处看不懂应该参考《最长上升子序列》
        for(int j=i-1; j>=0; j--){
            if(vp[j].h<vp[i].h)  //血量小的，递归到此处计算其子序列长度
                dp[i] = max(dp[i],dp[j]); //len = max(len,dfs(nums,j));
        }
        dp[i]++;   //return len++;
    }
    return dp;
}

//n个怪物、起始血量、攻击力、n个怪物血量信息、攻击力信息
int solution(int n, int H, int A, vector<int> &h, vector<int>& a) {
    vector<master>vp;
    for(int i=0; i<n; i++){
        vp.push_back({h[i],a[i]});
    }
    sort(vp.begin(),vp.end(),[](const master&m1,const master&m2){
        return m1.a<m2.a;  //攻击力由小到大排序
    });

    vector<int>dp = get_subArray(n,vp);
    //i怪物血量、攻击力均小于的，找出其最长的子序列
    int result = 0;
    for(int i=0; i<n; i++){
        if(H>vp[i].h && A>vp[i].a)  
            result = max(result,dp[i]);
    }
    return result;
}

int main(){
    int n,H,A;  //怪物数量、小美初始血量、攻击力
    cin>>n>>H>>A;
    vector<int>h(n); //怪物血量
    vector<int>a(n); //怪物攻击力
    for(int i=0; i<n; i++){
       cin>>h[i];
    }
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    int result = solution(n,H,A,h,a);
    cout<<result<<endl;
    return 0;
}

图论

小U的最大连续移动次数问题

小U决定在一个 m×n的地图上行走。地图中的每个位置都有一个高度表示地形的高低。小U只能在满足以下条件的情况下移动：

1. 只能上坡或者下坡，不能走到高度相同的点。
   
2. 移动时必须交替进行：上坡后必须下坡，下坡后必须上坡，不能连续上坡或下坡。
   
3. 每个位置只能经过一次，不能重复行走。

任务是帮助小U找到他在地图上可以移动的最大次数，即在符合所有条件的前提下，小U能走过的最大连续位置数量。

example:输入
1 2
4 3 输出：3
中庸行者可以选择移动顺序 3 -> 4 -> 1 -> 2，最大移动次数为3。

DFS深搜

和岛屿类问题差不多，控制深搜逻辑即可，加入isUp字段判断下次是上坡还是下坡；另一个影响因素是起点位置和起点的爬行逻辑，对于位置只能逐一遍历（可以加入记忆化剪枝），对于先上坡还是下坡就直接两个dfs比较结果好了，以下：

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2]={  //方向数组
    -1,0,
    1,0,
    0,1,
    0,-1
};
int dfs(vector<vector<int>>&a,int x,int y,bool isUp,vector<vector<bool>>visited){
    int m = a.size();
    int n = a[0].size();
    int maxlen = 0;
    visited[x][y] = true;  //标记
    for(int i=0; i<4; i++){
        int nextx = x+dir[i][0];
        int nexty = y+dir[i][1];
        if(nextx<0||nexty<0||nextx>=m||nexty>=n)  //下一站越界
            continue;
        if(visited[nextx][nexty]==true)  //以访问
            continue;
        if(isUp==true&&a[nextx][nexty]>a[x][y]){   
            maxlen = max(maxlen,1+dfs(a,nextx,nexty,false,visited));  //下一站向下
        }   
        else if(isUp==false&&a[nextx][nexty]<a[x][y]){
            maxlen = max(maxlen,1+dfs(a,nextx,nexty,true,visited)); //下一站向上
        }
    }
    return maxlen;
}

int solution(int m, int n, vector<vector<int>>& a) {
    vector<vector<bool>>visited(m,vector<bool>(n,false));  //起始向上走
    vector<vector<bool>>visited_Down(m,vector<bool>(n,false)); //起始向下走
    int temp1 = 0;
    int temp2 = 0;
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(visited[i][j]==false)
                temp1 = max(temp1,dfs(a,i,j,true,visited)); //起点向上走，最大移动数
            if(visited_Down[i][j]==false)
                temp2= max(temp2,dfs(a,i,j,false,visited_Down)); //向下走最大移动数
        }
    }
    return max(temp1,temp2); //取大值
}

int main() {
    vector<vector<int>> a1 = {{1, 2}, {4, 3}};
    cout << (solution(2, 2, a1) == 3) << endl;

    vector<vector<int>> a2 = {{10, 1, 6}, {5, 9, 3}, {7, 2, 4}};
    cout << (solution(3, 3, a2) == 8) << endl;

    vector<vector<int>> a3 = {{8, 3, 2, 1}, {4, 7, 6, 5}, {12, 11, 10, 9}, {16, 15, 14, 13}};
    cout << (solution(4, 4, a3) == 11) << endl;
}