MarsCode算法题(6-10)

6. 小E的怪物挑战

问题描述

小E在一个游戏中遇到了 $n$ 个按顺序出现的怪物. 每个怪物都有其特定的血量 $h_i$ 和攻击力 $a_i$ . 小E的初始血量为攻击力为. 游戏规则如下:

1.小E可以击败血量和攻击力都小于她当前属性的怪物
2.对于每只怪物, 小E可以选择与它战斗或者跳过这只怪物
3.为了保持战斗节奏, 要求击败的怪物序列中, 后一个怪物的血量和攻击力都必须严格大于前一个怪物

小E想知道, 她最多能击败多少怪物.

输入

n: 怪物的数量
H: 小E的血量
A: 小E的攻击力
h[i]: 第i个怪物的血量
a[i]: 第i个怪物的攻击力

输出

返回小E最多能击败的怪物数量

约束条件

1 < n < 100
1 < H, A, h[i], a[i] < 1000

测试样例

输入: n = 3, H = 4, A = 5, h = [1, 2, 3], a = [3, 2, 1]
输出: 1

输入: n = 5, H = 10, A = 10, h = [6, 9, 12, 4, 7], a = [8, 9, 10, 2, 5]
输出: 2

输入: n = 4, H = 20, A = 25, h = [10, 15, 18, 22], a = [12, 18, 20, 26]
输出: 3

输入: n = 4, H = 20, A = 25, h = [22, 18, 15, 10], a = [26, 20, 18, 12]
输出: 1

解题思路

经典的单调递增子序列问题. 首先打不过的怪物一定会跳过, 所以直接删除打不过的怪物, 最后再选出一条最长的单调递增序列. 定义 dp[i] 表示在 i 位置结束, 可以达到的最长序列. 首先 dp[i] 至少为 1, 因为可以直接打败当前位置怪物. 然后逐个比较之前位置的怪物 j, 如果怪物 i 比怪物 j 更强, 那么可以在打败怪物 j 之后打败怪物 i, 则 dp[i] = max(dp[i], dp[j] + 1).

代码实现

#include <iostream>
#include <vector>
using namespace std;

int solution(int n, int H, int A, vector<int> h, vector<int> a) {
    // 删除打不过的怪物
    int h_list[100];
    int a_list[100];
    int k=0;
    for(int i=0;i<n;i++){
        if(h[i]<H && a[i]<A){
            h_list[k] = h[i];
            a_list[k] = a[i];
            ++k;
        }
    }
    int dp[k];
    dp[0] = 1;
    int _max = 1;
    for(int i=1; i<k;i++){
        dp[i] = 1;
        for(int j=0; j<i;j++){
            if (h_list[i]>h_list[j] && a_list[i]>a_list[j]){
                dp[i] = max(dp[i], dp[j] + 1);
                _max = max(_max, dp[i]);
            }
        }
    }
    return _max;
}

int main() {
    cout << (solution(3, 4, 5, {1, 2, 3}, {3, 2, 1}) == 1) << endl;
    cout << (solution(5, 10, 10, {6, 9, 12, 4, 7}, {8, 9, 10, 2, 5}) == 2) << endl;
    cout << (solution(4, 20, 25, {10, 15, 18, 22}, {12, 18, 20, 26}) == 3) << endl;
    return 0;
}

7. 创意标题匹配

题目描述

在广告平台中, 为了给广告主一定的自由性和效率, 允许广告主在创造标题的时候以通配符的方式进行创意提交. 线上服务的时候, 会根据用户的搜索词触发的 bidword 对创意中的通配符(通配符是用成对 {} 括起来的字符串, 可以包含 0 个或者多个字符)进行替换, 用来提升广告投放体验. 例如: “{末日血战} 上线送 SSR 英雄, 三天集齐无敌阵容!”, 会被替换成“帝国时代游戏下载上线送 SSR 英雄, 三天集齐无敌阵容!”. 给定一个含有通配符的创意和n个标题, 判断这句标题是否从该创意替换生成的.

测试样例

输入: n = 4, template = "ad{xyz}cdc{y}f{x}e", titles = ["adcdcefdfeffe", "adcdcefdfeff", "dcdcefdfeffe", "adcdcfe"]
输出: "True,False,False,True"

解题思路

本题实际上是通配符匹配, {}中的内容可以任意替换, 所以可以将其看作一个通配符. 例如 ad{xyz}cdc{y}f{x}e 可以看作 ad*cdc*f*e. 我们只需要将通配符替换为 * 然后进行通配符匹配即可.

定义 dp[i][j] 表示字符串 str 的第 i 个字符和模板 p 的第 j 个字符是否匹配. 如果匹配, 则 dp[i][j] = 1, 否则为 -1. 因此会出现以下 3 种情况.

p[j] == '*', 则可以匹配 0 个字符, 模板指针后移, dp[i][j] = dp[i][j+1], 也可以匹配 1 个字符, 字符串指针后移, dp[i][j] = dp[i+1][j].
p[j] == str[i], 则可以匹配, 检查下一个字符是否匹配, dp[i][j] = dp[i+1][j+1].
p[j] != str[i], 则不匹配, dp[i][j] = -1.

另外还有一种情况, 如果模板被匹配完了, 那么字符串必须同时结束, 否则说明模板不够长, 不匹配.

代码实现

#include <iostream>
#include <string>
#include <vector>
#define MAX_SIZE 1000
using namespace std;

string p, s;
int dp[MAX_SIZE][MAX_SIZE];

int isMatch(int i, int j) {
  if (j == p.size()) {
    return i == s.size() ? 1 : -1;
  }
  if (dp[i][j] != 0) {
    return dp[i][j];
  }
  if (p[j] == '*') {
    // 匹配 0 个字符
    int s1 = isMatch(i, j + 1);
    // 匹配 1 个字符
    int s2;
    if (i < s.size()) {
      s2 = isMatch(i + 1, j);
    } else {
      s2 = -1;
    }
    dp[i][j] = max(s1, s2);
  } else if (s[i] == p[j]) {
    dp[i][j] = isMatch(i + 1, j + 1);
  } else {
    dp[i][j] = -1;
  }
  return dp[i][j];
}

std::string solution(int n, std::string template_,
                     std::vector<std::string> titles) {
  p = "";
  string results = "";
  for (int i = 0; i < template_.size(); i++) {
    if (template_[i] == '{') {
      while (template_[i] != '}') {
        ++i;
      }
      p.push_back('*');
    } else {
      p.push_back(template_[i]);
    }
  }
  for (string _s : titles) {
    s = _s;
    for (int i = 0; i <= _s.size(); i++) {
      for (int j = 0; j <= p.size(); j++) {
        dp[i][j] = 0;
      }
    }
    if (isMatch(0, 0) == 1) {
      results += "True,";
    } else {
      results += "False,";
    }
  }
  return results.substr(0, results.size() - 1);
}

int main() {
  //  You can add more test cases here
  std::vector<std::string> testTitles1 = {"adcdcefdfeffe", "adcdcefdfeff",
                                          "dcdcefdfeffe", "adcdcfe"};
  std::vector<std::string> testTitles2 = {
      "CLSomGhcQNvFuzENTAMLCqxBdj", "CLSomNvFuXTASzENTAMLCqxBdj",
      "CLSomFuXTASzExBdj",          "CLSoQNvFuMLCqxBdj",
      "SovFuXTASzENTAMLCq",         "mGhcQNvFuXTASzENTAMLCqx"};
  std::vector<std::string> testTitles3 = {"abcdefg", "abefg", "efg"};

  std::cout << (solution(4, "ad{xyz}cdc{y}f{x}e", testTitles1) ==
                "True,False,False,True")
            << std::endl;
  std::cout << (solution(6, "{xxx}h{cQ}N{vF}u{XTA}S{NTA}MLCq{yyy}",
                         testTitles2) == "False,False,False,False,False,True")
            << std::endl;
  std::cout << (solution(3, "a{bdc}efg", testTitles3) == "True,True,False")
            << std::endl;

  return 0;
}

8. 找出整数里超过一般的数

题目描述

小R从班级中抽取了一些同学, 每位同学都会给出一个数字. 已知在这些数字中, 某个数字的出现次数超过了数字总数的一半. 现在需要你帮助小R找到这个数字.

测试样例

输入: array = [1, 3, 8, 2, 3, 1, 3, 3, 3]
输出: 3

解题思路

直接排序, 取中位数. 或者一个一个统计, 找到出现次数超过一半的数.

代码实现

#include <iostream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

int solution1(vector<int> array) {
    map<int, int> m;
    for(int num: array){
        m[num]++;
    }
    for(auto s = m.begin(); s != m.end(); s++){
        if(s->second > array.size() / 2){
            return s->first;
        }
    }
    return 0;
}

int solution2(vector<int> array) {
    sort(array.begin(), array.end());
    return array[array.size() / 2];
}

int solution(vector<int> array) {
    return solution1(array);
}

int main() {
    // Add your test cases here
    
    cout << (solution({1, 3, 8, 2, 3, 1, 3, 3, 3}) == 3) << endl;
    return 0;
}

9. 超市里的货物架调整

题目描述

在一个超市里, 有一个包含 n 个格子的货物架, 每个格子中放有一种商品, 商品用小写字母 a 到 z 表示. 当顾客进入超市时, 他们会依次从第一个格子查找到第 n 个格子, 寻找自己想要购买的商品. 如果在某个格子中找到该商品, 顾客就会购买它并离开；如果中途遇到一个空格子, 或查找完所有格子还没有找到想要的商品, 顾客也会离开.

作为超市管理员, 你可以在顾客到来之前重新调整商品的顺序, 以便尽可能多地出售商品. 当第一个顾客进入后, 商品位置不能再调整. 你需要计算在最优调整下, 最多可以卖出多少件商品. 输入变量说明:

n: 货物架的格子数
m: 顾客想要购买的商品种类数
s: 货物架上商品的初始顺序
c: 顾客想要购买的商品种类

测试样例

输入: n = 3 ,m = 4 ,s = "abc" ,c = "abcd"
输出: 3

解题思路

看似很复杂, 实际上看完题目非常简单. 只需要把客户想要购买的商品倒序排列就可以让每个顾客都能买到. 因此只需要统计货架上的商品够不够就行.

代码实现

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int solution(int n, int m, string s, string c) {
    int list[26] = {0};
    for(char ch: s){
        list[ch - 'a']++;
    }
    int t = 0;
    for(char ch: c){
        if(list[ch - 'a'] != 0){
            t++;
            list[ch - 'a']--;
        }
    }
    return t;
}

int main() {
    cout << (solution(3, 4, "abc", "abcd") == 3) << endl;
    cout << (solution(4, 2, "abbc", "bb") == 2) << endl;
    cout << (solution(5, 4, "bcdea", "abcd") == 4) << endl;
    return 0;
}

10. 小F的永久代币回本计划

问题描述

小F最近迷上了玩一款游戏, 她面前有一个永久代币卡的购买机会. 该卡片的价格为 a 勾玉, 每天登录游戏可以返还 b 勾玉. 小F想知道她至少需要登录多少天, 才能让购买的永久代币卡回本.

测试样例

输入: a = 10, b = 1
输出: 10

解题思路

无

代码实现

#include <iostream>
using namespace std;

int solution(int a, int b) {
    return a / b + (a % b != 0);
}

int main() {
    cout << (solution(10, 1) == 10) << endl;
    cout << (solution(10, 2) == 5) << endl;
    cout << (solution(10, 3) == 4) << endl;
    return 0;
}