抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

MarsCode算法题(1-5)

发布于：2025年3月4日

次浏览

1. 找单独的数

问题描述

在一个班级中, 每位同学都拿到了一张卡片, 上面有一个整数. 有趣的是, 除了一个数字之外, 所有的数字都恰好出现了两次. 现在需要你帮助班长小C快速找到那个拿了独特数字卡片的同学手上的数字是什么.

要求：

  1. 设计一个算法, 使其时间复杂度为 O(n), 其中 n 是班级的人数.
  2. 尽量减少额外空间的使用, 以体现你的算法优化能力.

测试样例

输入：cards = [1, 1, 2, 2, 3, 3, 4, 5, 5]
输出：4
解释：拿到数字 4 的同学是唯一一个没有配对的.

解题思路

由于数据范围较小, 可以直接使用数组统计所有数字出现次数, 但不符合优化要求. 这种数字重复出现的情况一般可以通过异或来计算.

异或运算规律:

  • 任何数和 0 做异或运算, 结果仍然是原来的数, 即 a^0=a.
  • 任何数和其自身做异或运算, 结果是 0, 即 a^a=0.
  • 异或运算满足交换律和结合律, 即 a^b^a=(a^a)^b=0^b=b.

因此只需要将所有数字异或运算一次, 重复出现的数就会因异或两次变为 0, 最后剩下的就是单独的数. 如果单独的是 0, 由于其它数字全部出现两次都被抵消了, 因此最后剩下的还是 0.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>

int solution(std::vector<int> cards) {
    int a = 0;
    for(int i=0;i<cards.size();++i){
        a = a ^ cards[i];
    }
    return a;
}

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

2. 徒步旅行中的补给问题

问题描述

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

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

输入

  • n 总路程需要的天数
  • k 小R最多能同时携带食物的份数
  • data[i] 第i天补给站每份食物的价格

输出

返回完成这次徒步旅行的最小花费

约束条件

  • 1 < n,k < 1000
  • 1 < data[i] < 10000

测试样例

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

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

输入：n = 4 ,k = 1 ,data = [3, 2, 4, 1]
输出：10

解题思路

先转换思路, 把小R能够携带 k 个食物转化为小R能够买到前 k 天的食物, 这与携带 k 个食物是等价的. 设定 dp 数组为第 i 天的最小花费 (注意第一天实际是 i==0), 则有

  • 第 0 天必须购买第 0 个食物.
  • 第 i 天可以选择购买第 i 个食物, 也可以选择购买前 k 天的食物, 取两者最小值.
  • 第 i 天的最小花费与第 i-1 天的最小花费有关, 与第 i+1 天无关.

因此只需要在第 i-1 天的最小花费的基础上, 计算吃前 k 天哪一天的食物最优惠即可.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>

int solution(int n, int k, std::vector<int> data) {
  int dp[n];
  dp[0] = data[0];
  for (int i = 1; i < n; i++) {
    int min = data[i];
    for (int j = 1; j < k && i - j >= 0; j++) {
      if (data[i - j] < min) {
        min = data[i - j];
      }
    }
    dp[i] = dp[i - 1] + min;
  }
  return dp[n - 1];
}

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

3. 数字字符串格式化

问题描述

小M在工作时遇到了一个问题, 他需要将用户输入的不带千分位逗号的数字字符串转换为带千分位逗号的格式, 并且保留小数部分. 小M还发现, 有时候输入的数字字符串前面会有无用的 0, 这些也需要精简掉. 请你帮助小M编写程序, 完成这个任务.

测试样例

输入：s = "1294512.12412"
输出：'1,294,512.12412'

输入：s = "0000123456789.99"
输出：'123,456,789.99'

输入：s = "987654321"
输出：'987,654,321'

解题思路

先找第一个非 0 数字, 再找第一个小数点, 最后格式化输出即可.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <string>

using namespace std;

std::string solution(const std::string &s) {
  // 查找第一个非0
  int len = s.size();
  int first_non_zero = 0;
  int first_point = 0;
  while (s[first_non_zero] == '0' && first_point < len) {
    first_non_zero++;
  }
  while (s[first_point] != '.' && first_point < len) {
    first_point++;
  }
  int num_len = (first_point - first_non_zero) % 3;
  string result = "";
  result.push_back(s[first_non_zero]);
  num_len = (num_len + 2) % 3;
  for (int i = first_non_zero + 1; i < first_point && i < len; i++) {
    if (num_len == 0) {
      result.push_back(',');
    }
    result.push_back(s[i]);
    num_len = (num_len + 2) % 3;
  }
  for (int i = first_point; i < len; i++) {
    result.push_back(s[i]);
  }
  return result;
}

int main() {
  std::cout << (solution("1294512.12412") == "1,294,512.12412") << std::endl;
  std::cout << (solution("0000123456789.99") == "123,456,789.99") << std::endl;
  std::cout << (solution("987654321") == "987,654,321") << std::endl;
}

4. 数字分组求偶数和

问题描述

小M面对一组从 1 到 9 的数字, 这些数字被分成多个小组, 并从每个小组中选择一个数字组成一个新的数. 目标是使得这个新数的各位数字之和为偶数. 任务是计算出有多少种不同的分组和选择方法可以达到这一目标.

  • numbers: 一个由多个整数字符串组成的列表, 每个字符串可以视为一个数字组. 小M需要从每个数字组中选择一个数字.
    例如对于 [123, 456, 789] , 14个符合条件的数为：147 149 158 167 169 248 257 259 268 347 349 358 367 369.

测试样例

输入：numbers = [123, 456, 789]
输出：14

输入：numbers = [123456789]
输出：4

输入：numbers = [14329, 7568]
输出：10

解题思路

首先, 本题与具体数字无关, 只需要统计每个类别里的奇偶数个数即可. 对于第 i 组, 想要得到偶数, 只有两种情况:

  1. 前 i-1 组之和为奇数, 第 i 组选择奇数.
  2. 前 i-1 组之和为偶数, 第 i 组选择偶数.

因此在每次遍历时, 只需要根据上一次遍历结果, 直接计算当前组合的奇偶数个数即可.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <vector>

int solution(std::vector<int> numbers) {
  int len = numbers.size();
  int total_odd = 0;
  int total_even = 1;

  for (int i = 0; i < len; i++) {
    int odd_num = 0;
    int even_num = 0;
    // 统计奇偶数个数
    int t = numbers[i];
    while (t != 0) {
      int k = t % 10;
      t /= 10;
      if (k % 2) {
        odd_num++;
      } else {
        even_num++;
      }
    }

    // 前 i-1 组为奇数
    int _total_odd = total_odd * even_num + total_even * odd_num;
    // 前 i-1 组为偶数
    int _total_even = total_odd * odd_num + total_even * even_num;

    total_odd = _total_odd;
    total_even = _total_even;
  }
  return total_even;
}

int main() {
  // You can add more test cases here
  std::cout << (solution({123, 456, 789}) == 14) << std::endl;
  std::cout << (solution({123456789}) == 4) << std::endl;
  std::cout << (solution({14329, 7568}) == 10) << std::endl;
  return 0;
}

5. 寻找最大葫芦

题目描述

在一场经典的德州扑克游戏中, 有一种牌型叫做“葫芦”. “葫芦”由五张牌组成, 其中包括三张相同牌面值的牌 a 和另外两张相同牌面值的牌 b. 如果两个人同时拥有“葫芦”, 我们会优先比较牌 a 的大小, 若牌 a 相同则再比较牌 b 的大小, 牌面值的大小规则为：1 (A) > K > Q > J > 10 > 9 > … > 2, 其中 1 (A) 的牌面值为1, K 为13, 依此类推.

在这个问题中, 我们对“葫芦”增加了一个限制：组成“葫芦”的五张牌牌面值之和不能超过给定的最大值 max.

给定一组牌, 你需要找到符合规则的最大的“葫芦”组合, 并输出其中三张相同的牌面和两张相同的牌面. 如果找不到符合条件的“葫芦”, 则输出 “0, 0”.

测试样例

输入：n = 9, max = 34, array = [6, 6, 6, 8, 8, 8, 5, 5, 1]
输出：[8, 5]
说明：array数组中可组成4个葫芦, 分别为[6,6,6,8,8],[6,6,6,5,5],[8,8,8,6,6],[8,8,8,5,5]. 其中[8,8,8,6,6]的牌面值为36, 大于34不符合要求. 剩下的3个葫芦的大小关系为[8,8,8,5,5]>[6,6,6,8,8]>[6,6,6,5,5],故返回[8,5]

解题思路

本体没啥难度, 测试样例懒得复制粘贴了. 首先遍历卡牌, 统计卡牌数量. 由于总共就 13 张牌, 直接暴力循环, 尝试所有组合. 因为这里的比大小规则比较杂, 所以直接把卡牌按顺序从小到大存为数组 order, 然后按照数组顺序来一个一个尝试, 遇到第一个符合条件的直接输出.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <vector>

std::vector<int> solution(int n, int max, const std::vector<int>& array) {
    int card[14] = {0};
    int order[] = {1, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    for(int num: array){
        card[num]++;
    }
    for(int i: order){
        for(int j: order){
            // 牌面相同
            if (i == j){
                continue;
            // 无法组成葫芦
            } else if (card[i] < 3 || card[j] < 2) {
                continue;
            // 超过最大值
            } else if (i * 3 + j * 2 > max) {
                continue;
            } else {
                return {i, j};
            }
        }
    }

    return {0, 0};
}

int main() {
    // Add your test cases here
    
    std::vector<int> result1 = solution(9, 34, {6, 6, 6, 8, 8, 8, 5, 5, 1});
    std::cout << (result1 == std::vector<int>{8, 5}) << std::endl;

    std::vector<int> result2 = solution(9, 37, {9, 9, 9, 9, 6, 6, 6, 6, 13});
    std::cout << (result2 == std::vector<int>{6, 9}) << std::endl;

    std::vector<int> result3 = solution(9, 40, {1, 11, 13, 12, 7, 8, 11, 5, 6});
    std::cout << (result3 == std::vector<int>{0, 0}) << std::endl;

    return 0;
}

更新于：2025年3月4日

评论



😒再看，再看，再看就把你吃掉!