AI掘金训练营刷题

题1 多米诺骨牌

# 问题描述

多米诺骨牌游戏规则非常简单，将骨牌按一定间距的尺寸排成单行，或分行排成一片。推倒第一张骨牌，其余发生连锁反应依次倒下，或形成一条长龙，或形成一幅图案。

小 A 觉得多米诺骨牌超级没意思，所以他想了点小花招。

小 A 将 n 个多米诺骨牌放在一条线上，每一块都垂直竖立。他同时将一些骨牌向左或向右推倒。注意：不会出现连续向左或者向右推的情况。 每过一秒，被推向左边或右边的骨牌会将左边或右边的相邻骨牌推倒。当一个骨牌，其左边倒向它的骨牌数目与其右边倒向它的骨牌数目相等时，由于力的平衡，该骨牌将依然保持竖立。

给定小 A 最初推骨牌的方向，求出最后依然保持竖立的骨牌数目和位置。

## 输入格式

输入数据第一行包括一个整数 n（1≤n≤3000），表示这一行多米诺骨牌的数目。下一行包括一个长度为 n 的字符串，字符串的第 i 个字符意义如下：

“L”，第 i 个字符将要被向左推。

“R”，第 i 个字符将要被向右推。

“.”，第 i 个字符不会被推。

## 输出格式

首先输出保持竖立的骨牌数目。如果保持竖立的骨牌数目不为 0，下一行输出保持竖立的骨牌的位置，骨牌位置从 1 到 n。

每两个数之间用一个空格隔开，注意最后一个数后面没有空格。

解题思路

考虑 一个骨牌是否会保持竖立，仅需要考虑其最近的L或者R即可。

考虑四种情形：

  • L……R：中间的’’.”会全部保留
  • R……L：如果中间的”.”为奇数个，保留最中间的一个”.”
  • R…….R：无”.”保留
  • L……..L：无”.”保留

使用 双指针 “l”指向左边的L或者R， “r”指向右边的L或者R

代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <string>

using namespace std;


std::string solution(int num, std::string data) {
    // Please write your code here
    
    data = 'L' + data + 'R';
    //cout<<data<<endl;
    int res[data.length()];
    int count =0 ;
    string rr = "";
    int l = 0;
    for(int r=1; r<data.length(); r++){

        
        
        if(data[r] == '.'){
            continue;
        }
        if (data[l] == 'R' && data[r] == 'L') {
            //cout<<"l: "<<l<<"  r: "<<r<<endl;

            if((r -l +1)  % 2 != 0){
                res[count] = (r+l) / 2;
                count++;
                //cout<<"count: "<<count<<" j: "<<res[count-1]<<endl;
            }
        
        }
        else if(data[l] == 'L' && data[r] == 'R'){
            //cout<<"l: "<<l<<"  r: "<<r<<endl;
            for(int j=l+1; j<r;j++){
                res[count] = j;
                count++;
                //cout<<"count: "<<count<<" j: "<<j<<endl;
            }

        }

        
        

        l = r;

        


    }
    rr = to_string(count) ;
    if(count!=0){

        rr += ':';

        for(int i=0; i<count; i++){
        rr += to_string(res[i])  ;
        if(i!= count-1){
            rr += ',';
        }
    }

    }
    




    return rr;
}

int main() {
    //  You can add more test cases here
    std::cout << (solution(14, ".L.R...LR..L..") == "4:3,6,13,14") << std::endl;
    std::cout << (solution(5, "R....") == "0") << std::endl;
    std::cout << (solution(1, ".") == "1:1") << std::endl;

    

    return 0;
}

题2 计算x到y的最少步数

问题描述

小F正在进行一个 AB 实验，需要从整数位置 x 移动到整数位置 y。每一步可以将当前位置增加或减少，且每步的增加或减少的值必须是连续的整数（即每步的移动范围是上一步的 -1，+0 或 +1）。首末两步的步长必须是 1。求从 x 到 y 的最少步数。

输入描述

输入包含两个整数 x 和 y，表示起始位置和目标位置。

输出描述

输出从 x 到 y 所需的最小步数。

测试样例

样例1：

输入：x_position = 12, y_position = 6
输出：4

样例2：

输入：x_position = 34, y_position = 45
输出：6

样例3：

输入：x_position = 50, y_position = 30
输出：8

样例4：

输入：x_position = 0, y_position = 0
输出：0

题3 环形DNA序列整理

题4 DNA序列还原

题5 打点计数器

题6 叠盘子

问题描述

小明是个讲究生活质量的人，家里的一切都井井有条，比如说家中的盘子都是一个系列，每个盘子都标有唯一的一个整数作为标识。在每次吃完饭后，小明都会将这些盘子按照特定的顺序叠放收拾起来，收拾的规则如下：

  • 盘子叠放后会被分为多堆，每一堆都可能是由一个或多个盘子组成

  • 叠放在同一堆的盘子的序号都是不间断递增的（例如 1，2，3 为不间断递增，而 1，3，4 则只是普通的递增），并且这些盘子的数量至少是 3 个

  • 这些盘子的序号在被叠放之前就是递增的

请问你可以编写一个程序，帮助小明算一算盘子该如何叠放么？

输入格式

空格分隔输入所有的数字

输出格式

一个字符串，每个堆被逗号分隔开，如果堆中只有一个盘子，就用序号表达；如果堆中有多个盘子，用『起始编号』+『-』+『终止编号』来表达。

输入样例(1)

-3 -2 -1 2 10 15 16 18 19 20

输出样例(1)

“-3–1,2,10,15,16,18-20”

输入样例(2)

-6 -3 -2 -1 0 1 3 4 5 7 8 9 10 11 14 15 17 18 19 20

输出样例(2)

“-6,-3-1,3-5,7-11,14,15,17-20”

输入样例(3)

1 2 7 8 9 10 11 19

输出样例(3)

“1,2,7-11,19”

解题思路

我的思路是 先把数字组成的字符串 ——> 一个int型数组

双指针法：i指向左边的盘子序号，j指向右边的盘子序号

while((p2[j+1] ) - (p2[j] ) == 1){

j++;

}

代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <string>
#include <vector>

using namespace std;

std::string solution(std::string plates) {
  // Please write your code here
  vector<int> p2;
  int t =0;
  int p;
  for(p =0; p<plates.length(); p++){
    if(plates[p] == ' '){
      p2.push_back(stoi(plates.substr(t, p-t)));
      t = p+1;
    }
  }
  
  if (t < plates.length()) {
        p2.push_back(stoi(plates.substr(t, plates.length() - t)));
   }
   //cout<<stoi(plates.substr(t, plates.length() - t))<<endl;

  
  string res = "";
  string tmp;
  int i = 0;
  int j = 0;
  int tp;
  while(j<p2.size()){
    tp = j;
    while((p2[j+1] ) - (p2[j] ) == 1){
      j++;
    }
    if(j-i<2){
      j = tp;
    }
    if(j == i ){
      tmp = to_string(p2[i]);
    }
    else{
      tmp = to_string(p2[i]) + "-" + to_string(p2[j]);
    }
    
    res += tmp + ",";
    //cout<<"res: "<<res<<endl;
    j++;
    i = j;


  }
  //cout<<res.substr(0, res.length()-1)<<endl;
  
  return res.substr(0, res.length()-1);
}

int main() {
  //  You can add more test cases here
  std::cout << (solution("-3 -2 -1 2 10 15 16 18 19 20") ==
                "-3--1,2,10,15,16,18-20")
            << std::endl;
  std::cout << (solution(
                    "-6 -3 -2 -1 0 1 3 4 5 7 8 9 10 11 14 15 17 18 19 20") ==
                "-6,-3-1,3-5,7-11,14,15,17-20")
            << std::endl;
  std::cout << (solution("1 2 7 8 9 10 11 19") == "1,2,7-11,19") << std::endl;

  return 0;
}

题7 飞行棋分组

问题描述

现在桌子上有一堆飞行棋棋子，有 N 个，每个棋子上标有数字序号，现在想让你帮忙给这堆飞行棋分成 M 组，需要满足：

  • 每个分组只能包含 5 个棋子
  • 每个棋子只能出现在一个分组里
  • 每个分组里的棋子的数字序号相同

请问可以完成上述分组么？

输入格式

空格分割的飞行棋棋子序号，如：1 3 4 5 6 5 4

输出格式

是否可以完成分组，如果可以输出 true，否则输出 false

输入样例(1)

1
1 2 3 4 5

上述棋子只有 5 个只能分为一组，但组内棋子序号不一致，所以无法完成分组，输出 false

输出样例(2)

1
1 1 1 1 2 1 2 2 2 2

上述棋子可以分为两组，[1, 1, 1, 1, 1] 和 [2, 2, 2, 2, 2] 两组，可以完成分组，输出 true

数据范围

  • 棋子数量：1 <= N <= 10^5
  • 棋子序号：1 <= pieces[i] <= 40

解题思路

先对整个数组排序，如果数组形式为 [a,a,a,a,a] [b,b,b,b,b] [c,c,c,c,c] ——>True

代码

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
44
45
46
47
48
49
#include <iostream>

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

bool compare(int a, int  b){
    return a  < b;
}

std::string solution(std::vector<int> nums) {
    // Please write your code here
    // [a,a,a,a,a] [b,b,b,b,b] [c,c,c,c,c] True

    sort(nums.begin(), nums.end());
    int j =0;
    if(nums.size() % 5 !=0  ){
        //cout<<"False"<<endl;
        return "False";
    }
    while( (j)*5  <nums.size() -5){

        for(int i=5*j; i<5*j+4; i++){
        	
            if(nums[i+1] != nums[i]){
                //cout<<"False"<<endl;
                return "False";
            }
        }
        j++;

    }
    
    //cout<<"True"<<endl;
    return "True";
    
    


    
}

int main() {
    // You can add more test cases here
    std::cout << (solution({1, 3, 4, 5, 6, 5, 4}) == "False") << std::endl;
    std::cout << (solution({1, 1, 1, 1, 2, 1, 2, 2, 2, 2}) == "True") << std::endl;
    std::cout << (solution({11, 45, 49, 37, 45, 38, 3, 47, 35, 49, 26, 16, 24, 4, 45, 39, 28, 26, 14, 22, 4, 49, 18, 4, 4, 26, 47, 14, 1, 21, 9, 26, 17, 12, 44, 28, 24, 24, 10, 31, 33, 32, 23, 41, 41, 19, 17, 24, 28, 46, 28, 4, 18, 23, 48, 45, 7, 21, 12, 40, 2, 19, 19, 28, 32, 6, 27, 43, 6, 18, 8, 27, 9, 6, 6, 31, 37, 15, 26, 20, 43, 3, 14, 40, 20}) == "False") << std::endl;
    return 0;
}

题8 和为偶数的数字组合

# 问题描述

给定 1 到 9 共 9 个数字，随机将九个数字分成多组，按顺序从每组中任意取出一个数字组成一个新的数字，使得新组成的数字每位数字相加之和为偶数，求共有多少种组合方法。具体请配合样例理解。

## 输入格式

多个整型数字，数字之间用一个空格分隔

## 输出格式

一个整数

## 数据范围

数组 1 到 9 共 9 个数，随机分成多组（>=1）

解题思路

一个一个累积的思想：从当前的和 如果当前和为偶数，要保持后面的和仍为偶数 = 前期偶和 * 可以加的偶数的个数 + 前期奇和 * 可以加的奇数的个数

代码

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
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <string>
#include <vector>

using namespace std;




int solution(std::vector<int> numbers) {
    // Please write your code here
    vector<pair<int, int>> pp(numbers.size()); 
    int res_odd = 1;
    int res_even = 0;
    int new_res_even =0;
    int new_res_odd = 0;
    for(int t=0; t<numbers.size(); t++){
        string s = to_string(numbers[t]);
        for(int a =0; a<s.size(); a++){
            if( (s[a] - '0') % 2 ==0 ){
                pp[t].second ++;
            }
            else{
                pp[t].first ++;
            }
            
            
        }
        
        
        new_res_even = res_even*pp[t].second + res_odd*pp[t].first;
        new_res_odd = res_odd*pp[t].second + res_even*pp[t].first;
        
        res_even = new_res_even;
        res_odd = new_res_odd;
       


    }
    


    return res_odd;
}

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;
}

题9 两个数列

# 问题描述

给定长度分别为 n 和 m 的两个数列a[n]、b[m]，和一个整数k。求|(a[i] - b[j])^2 - k^2|的最小值。

## 输入格式

第一行有 2 个整数 n、m、k，分别表示数列 a、b 的长度，以及公式中的整数 k。

第二行有 n 个整数，表示数列 a 的各个元素。

第三行有 m 个整数，表示数列 b 的各个元素。

## 输出格式

求上述公式的最小值。

*数据范围*

其中 20%的数据：1 <= n,m <= 3000，-10^9 <= a[i], b[j], k <= 10^9，for all i, j

其中 30%的数据：1 <= n,m <= 50000，k = 0，-10^9 <= a[i], b[j] <= 10^9，for all i, j

其中 50%的数据：1 <= n,m <= 50000，-10^9 <= a[i], b[j], k <= 10^9，for all i, j

解题思路

直接穷举了

代码

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>
#include <unordered_set>

using namespace std;

int solution(std::vector<std::vector<int>> cases) {
    // Please write your code here
   
    vector<int> l1 = cases[0];
    vector<int> l2 = cases[1];
    vector<int> l3 = cases[2];
    int n = l1[0];
    int m = l1[1];
    int k = abs(l1[2]);
    int t;
    int res;
    int mini = 100000;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            t = abs(l2[i] - l3[j]);
          
            res = abs(t*t - k*k);
            mini = min(mini, res);

        }
    }



    return mini;
}

int main() {
    // You can add more test cases here
    std::vector<std::vector<int>> case1 = {{5, 5, 1}, {5, 3, 4, 1, 2}, {0, 6, 7, 9, 8}};
    std::vector<std::vector<int>> case2 = {{5, 5, 0}, {5, 3, 4, 1, 2}, {0, 6, 7, 9, 8}};
    std::cout << (solution(case1) == 0) << std::endl;
    std::cout << (solution(case2) == 1) << std::endl;
    return 0;
}

题10 升级

小 W 有 n 个英雄，能力值为 a_i (1 <= i <= n)，初始能力值都为 1，小 W 可以最多完成 k 次升级，每一次升级从 n 个英雄中挑选出某一个（例如 i ），然后任意选择一个正整数 x，对它进行升级，升级后能力值 a_i = a_i + \text{floor}(a_i / x) （floor 代表下取整）。其中每一个英雄能力值刚好升级成 b_i 时小 W 会获得 c_i 的奖励（每个英雄只能获取一次奖励），最后小 W 想知道最多能获得多少的奖励？

解题思路

贪心？

代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <math.h>
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

bool compare(pair<int,int>a,  pair<int,int>b){
    return a.second > b.second;
}

int solution(int n, int k, const std::vector<int>& b, const std::vector<int>& c) {
    // Edit your code here
    // 2 4 8 ..  2^n
    // 4次
    //  3 3 1 0
    //  6 5 2 2
    double t;
    vector<pair<int,int>> bb(n);
    for(int i=0; i<n; i++){
        t = log2(b[i]);
        if(t == std::floor(t)){
            bb[i].first = int(t);
            bb[i].second = c[i];
        }
        else{
            bb[i].first = int(t) + 1;
            bb[i].second = c[i];
        }

    }

    sort(bb.begin(), bb.end(), compare);
    int total_k = 0 ;
    int total_w = 0;

    for(int i=0; i<n; i++){

        if(total_k + bb[i].first <=k  ){
            //cout<<"次数: "<<bb[i].first<<" 获得奖励："<<bb[i].second<<endl;
            total_k += bb[i].first;
            total_w += bb[i].second;
        }

    }




    //cout<<"total_w : "<<total_w<<endl;
    return total_w;
}

int main() {
    // Add your test cases here
    std::cout << (solution(4, 4, {1, 7, 5, 2}, {2, 6, 5, 2}) == 10) << std::endl;
    std::cout << (solution(3, 0, {3, 5, 2}, {5, 4, 7}) == 0) << std::endl;
    return 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;

public class Main {
    public static int solution(int n, int k, int[] b, int[] c) {
        // Edit your code here
        int[] cnta = new int[100000];
        Arrays.fill(cnta, 0x3f3f);
        cnta[0]=0;
        cnta[1]=0;
        // 2 3 1
        for (int num = 1; num <= 10000; num++) {
            for (int x = 1; x <= num; x++) {
                int tmp = num + (int)(num / x);
                
                cnta[tmp] =Math.min(cnta[num] + 1, cnta[tmp]);
                
            }
            
        }

        //System.out.println("cnt[5]: "+ cnta[5]);
        

        
        int totalW = 0;

        //dp[j][k] 对前j个英雄升级k次获得的最大奖励
        // dp[j][k] = max(dp[j-1][k-1] + c[i], dp[j-1][k])
        int [][] dp = new int[n+1][k+1];
        dp[0][0] = 0;
        int cnt =0;
        for(int i=1; i<=n; i++){
            if(b[i-1] == 1){
                cnt += c[i-1];
                
                //System.out.println("cnt: "+cnt);

            }
            dp[i][0] = cnt;
        }

        // dp[2][2] = dp[2][0] + 5
       // System.out.println("dp[2][0]: "+ dp[2][0]);


       
        



        for (int i = 1; i <= n; i++) {
           for(int j =1; j<=k; j++){
                if(j-cnta[b[i-1]]>=0){
                    dp[i][j] = Math.max(dp[i-1][j-cnta[b[i-1]]]+c[i-1], dp[i-1][j]);
                    // System.out.println("前i-1个 + 这个： "+ dp[i-1][j-cnta[b[i-1]]]+c[i-1] + " 前i-1个k次： "+ dp[i-1][j]);
                    // System.out.println("dp[" +i +"][" + j + "]: "+ dp[i][j]);

                }
                else{
                    dp[i][j] =  dp[i-1][j];
                }
                

           }
        }

        totalW = dp[n][k];

        //System.out.println("total: "+ totalW);
        

        return totalW;
    }

    public static void main(String[] args) {
        // Add your test cases here
        System.out.println(solution(3, 3, new int[]{3,5,2}, new int[]{5,4,7}) == 12);
        System.out.println(solution(3, 0, new int[]{3, 5, 2}, new int[]{5, 4, 7}) == 0);
    }
}

题11 青海湖租车之旅

# 问题描述

油价飞升的今天，我们尽量减少花费。我们出门旅游，有时候租车去旅游也是一种不错的方式。这次我们这次旅游是从「青海湖」到「景点 X」，景点 X 可以是「敦煌」、「月牙泉」等，线路的路径是唯一的，假设我们每走 1 km 消耗 1 L 的油，车油箱容量 400L。比如：如果「景点 X」是敦煌，我们在青海湖租车前油箱是 200L 的，在「景点 X」（敦煌）还车的时候也是 200L 的，路上有很多加油站，加油站在青海湖和「景点 X」的连线上。

## 输入格式

第 1 行表示「青海湖」到「景点 X」的距离，距离最远不超过 10000 km。

第 2 行表示接下来 N 行表示 N 个加油站（N 为正整数）。

接下来 N（1 <= N <= 100）行表示，每一个加油站情况。每一个加油站包括距离「景点 X」的距离 a km（0 <= a <= 10000），以及每升汽油的价格 b 元（0 <= b <= 2000），a 和 b 均为正整数。

## 输出格式

如果不能到达目的地「景点 X」，输出 Impossible。

如果能到达目的地「景点 X」，输出最小花费多少元。

****输入样例****：

500

4

100 1

200 30

400 40

300 20

****输出样例****：

4300

解题思路

500

100 200 300 400 500

0 100 100 100 100

代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

bool compare(vector<int> &a, vector<int>&b){
    return a[0] < b[0];
}

std::string solution(int distance, int n, std::vector<std::vector<int>> gasStations) {
    // Please write your code here
    int dp[110][410];
    gasStations.push_back({distance});
    sort(gasStations.begin(), gasStations.end(),
        [&](vector<int> &a, vector<int> &b) { return a[0] < b[0]; });

    vector<int> dis(n + 1);
    dis[0] = gasStations[0][0];
    for (int i = 1; i <= n; i++)
        dis[i] = gasStations[i][0] - gasStations[i - 1][0];

    memset(dp, 0x3f, sizeof dp);
    dp[0][200] = 0;

    for (int i = 1; i <= n; i++) {
        if (gasStations[i - 1][0] == distance) {
        n = i - 1;
        break;
        }
        for (int j = 0; j <= 400; j++)
        for (int k = 0; k <= 400; k++)
            if (j + dis[i - 1] - k >= 0 && gasStations[i - 1].size() > 1)
            dp[i][j] = min(dp[i][j], dp[i - 1][k] + (j + dis[i - 1] - k) *
                                                        gasStations[i - 1][1]);
    }

    // cout << "the answer is"  <<  dp[n - 1][200 + dis[n - 1]] << '\n';

    if (n < 1 || 200 + dis[n - 1] < 0 || dp[n][200 + dis[n - 1]] == 0x3f3f3f3f)
        return "Impossible";
    return to_string(dp[n][200 + dis[n - 1]]);


}

int main() {
    std::vector<std::vector<int>> gasStations1 = {{100, 1}, {200, 30}, {400, 40}, {300, 20}};
    std::vector<std::vector<int>> gasStations2 = {{100, 999}, {150, 888}, {200, 777}, {300, 999}, {400, 1009}, {450, 1019}, {500, 1399}};
    std::vector<std::vector<int>> gasStations3 = {{101}, {100, 100}, {102, 1}};
    std::vector<std::vector<int>> gasStations4 = {{34, 1}, {105, 9}, {9, 10}, {134, 66}, {215, 90}, {999, 1999}, {49, 0}, {10, 1999}, {200, 2}, {300, 500}, {12, 34}, {1, 23}, {46, 20}, {80, 12}, {1, 1999}, {90, 33}, {101, 23}, {34, 88}, {103, 0}, {1, 1}};

    std::cout << (solution(500, 4, gasStations1) == "4300") << std::endl;
    std::cout << (solution(500, 7, gasStations2) == "410700") << std::endl;
    std::cout << (solution(500, 3, gasStations3) == "Impossible") << std::endl;
    std::cout << (solution(100, 20, gasStations4) == "0") << std::endl;
    std::cout << (solution(100, 0, std::vector<std::vector<int>>{}) == "Impossible") << std::endl;

    return 0;
}

题12 和的逆运算

问题描述

n 个整数两两相加可以得到 n(n - 1) / 2 个和。我们的目标是：根据这些和找出原来的 n 个整数。

输入格式

输入每行一个整数 n（2 < n < 10）开头，接下来是 n(n - 1) / 2 个整数，代表两两相加的和，相邻整数以空格隔开。

输出格式

对于输入的每一行，输出一行，包含 n 个整数，按非降序排序，如果有多组解，任意输出一组即可。如果无解，输出 “Impossible”。

输入样例：

  • 3 1269 1160 1663
  • 3 1 1 1
  • 5 226 223 225 224 227 229 228 226 225 227
  • 5 -1 0 -1 -2 1 0 -1 1 0 -1
  • 5 79950 79936 79942 79962 79954 79972 79960 79968 79924 79932

输出样例：

  • 383 777 886
  • Impossible
  • 111 112 113 114 115
  • -1 -1 0 0 1
  • 39953 39971 39979 39983 39989

解题思路

x1+x2 x1+x3 x1+x4 x1+xn
x2+x3 x2+x4 x2 + xn
x3 + x4 x3 + xn
xn-1 + xn

s = x1 + x2 +… +xn = (sum1 +… sumk) / (n-1)

对上述上三角矩阵 从左到右增大 从下到上增大。

假设，已知x1

当前 sums中最小的是 x1+ x2 ——> 推出x2 = sums.min - x1 ——> 从sums里面提出 x1+ x2

当前 sums中最小的是 x1+x3 ——> 推出x3 = sums.min - x1 ——>从sums里面剔除 x1+ x3 、 剔除 x2 + x3 (如果他们存在，不存在x1初始化错误)

当前 sums中最小的是 x1+x4 ——> 推出x4 = sums.min - x1 ——>从sums里面剔除 x1+ x4 、 剔除 x2 + x4 、 剔除 x3 +x4 (如果他们存在，不存在x1初始化错误)

代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <vector>
#include <string>
# include <algorithm>
#include <set>

using namespace std;


std::string solution(int n, std::vector<int> sums) {
    // Please write your code here
    vector<int> ans(n+1);
    multiset<int> s;
    int sum = 0;
   for (auto s : sums)
    sum += s;
    
    int findr = 0;

    sort(sums.begin(), sums.end());
    int s1;
    
    if (sum % (n - 1) != 0)
    {return "Impossible";}

    for(s1 = -abs(sums[0]); s1 <= abs(sums[0]); s1++){
        s.clear();
        for(int i=0; i<sums.size(); i++){
            s.insert(sums[i]);
            
    }
        int flag = 1;
        ans[1] = s1;
        //a2 a3 a4...
        for(int i=2; i<=n ;i++){
            ans[i] =  *s.begin() - ans[1];
            for(int j=1; j<i ; j++){
                if(s.find(ans[i] + ans[j]) != s.end()){
                    s.erase(s.find(ans[i] + ans[j]));
                }
                else{
                    flag = 0;
                    break;
                }

            }
            if(flag == 0){
                break;
            }
        }

        if(flag == 1){
            
            break;
           

        }
        
        
            
        


    }
    string res = "";
    for(int i=1; i<= n; i++){
        
        if(i == n  ){
            res += to_string(ans[i]);
        }
        else{
            res += to_string(ans[i]) + ' ';
        }

    }
    //cout<<"res : "<<res<<endl;

    
    return res;
}

int main() {
    // You can add more test cases here
    std::vector<int> sums1 = {1269, 1160, 1663};
    std::vector<int> sums2 = {1, 1, 1};
    std::vector<int> sums3 = {226, 223, 225, 224, 227, 229, 228, 226, 225, 227};
    std::vector<int> sums4 = {-1, 0, -1, -2, 1, 0, -1, 1, 0, -1};
    std::vector<int> sums5 = {79950, 79936, 79942, 79962, 79954, 79972, 79960, 79968, 79924, 79932};

    std::cout << (solution(3, sums1) == "383 777 886") << std::endl;
    std::cout << (solution(3, sums2) == "Impossible") << std::endl;
    std::cout << (solution(5, sums3) == "111 112 113 114 115") << std::endl;
    std::cout << (solution(5, sums4) == "-1 -1 0 0 1") << std::endl;
    std::cout << (solution(5, sums5) == "39953 39971 39979 39983 39989") << std::endl;

    return 0;
}

题13 简单四则计算

问题描述

实现一个基本的计算器来计算一个简单的字符串表达式的值。注意事项如下：

  • 输入是一个字符串表达式（可以假设所给定的表达式都是有效的）

  • 字符串表达式可以包含的运算符号为：左括号 (, 右括号 ), 加号 +, 减号 -

  • 可以包含的数字为：非负整数（< 10）

  • 字符串中不包含空格

  • 处理除法 case 的时候，可以直接省略小数部分结果，只保留整数部分参与后续运算

  • 请不要使用内置的库函数 eval

输入格式

如：3+4*5/(3+2)

数据约束

见题目描述

输出格式

计算之后的数字

输入样例：

  • 1+1
  • 3+4*5/(3+2)
  • 4+2*5-2/1
  • (1+(4+5+2)-3)+(6+8)

输出样例：

  • 2
  • 7
  • 12
  • 23

解题思路

栈！

如： (1+(4+5+2)-3)+(6+8)

数字栈 + 符号栈

数字：压入 数字栈

左括号：压入 符号栈

右括号：进行括号内的运算，直至遇到左括号

操作符：若当前操作符优先级 <= 栈顶操作符优先级 && 栈不为空，则先对栈顶操作符进行运算。 把该操作符压栈

代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <cctype>
#include <iostream>
#include <string>
#include <stack>
#include <map>

using namespace std;


int apply(char opt1, int v1, int v2){
    int res;
    if(opt1 == '+'){
            res =  v1 + v2;
        }
    else if(opt1 == '-'){
            res = v2 -v1;
        }
    else if(opt1 == '/'){
            res =  v2 / v1;
        }
    else if(opt1 == '*') {
            res = v1 * v2;
        }
        //cout<<"v1: "<<v1<<" v2: "<<v2<<endl;
        //cout<<"res: "<<res<<endl;
    return res;
}

int solution(std::string expression) {
    // Please write your code here
    stack<char> opt;
    stack<int> number;
    map<char, int> mp;
    mp['+'] = 1;
    mp['-'] = 1;
    mp['*'] = 2;
    mp['/'] = 2;




    for(int i=0; i<expression.size(); i++){
        if(std::isdigit(expression[i])){

            number.push(expression[i] - '0');

        }
        else if(expression[i] == '('){
            opt.push(expression[i]);
        }
        else if(expression[i] == ')'){
            //对()里面进行运算
            while(!opt.empty() && opt.top()!= '('){

                int v1 = number.top();
                number.pop();
                int v2 = number.top();
                number.pop();
                char opt1 = opt.top();
                opt.pop();
                int res  = apply(opt1, v1, v2);
                //cout<<"res: "<<res<<endl;
                number.push(res);




            }
            if(!opt.empty()){
                opt.pop();
            }
        }
        else{
            // 读入 + - * /
            while(!opt.empty() && mp[expression[i]] <= mp[opt.top()] ){

                int v1 = number.top();
                number.pop();
                int v2 = number.top();
                number.pop();
                char opt1 = opt.top();
                opt.pop();
                int res  = apply(opt1, v1, v2);
                
                
                //cout<<"res: "<<res<<endl;
                number.push(res);

            }

            
            opt.push(expression[i]);
            



        }
    }

    while(!opt.empty()){

        int v1 = number.top();
        number.pop();
        int v2 = number.top();
        number.pop();
        char opt1 = opt.top();
        opt.pop();
        int res  = apply(opt1, v1, v2);
        
        //cout<<"v1: "<<v1<<" v2: "<<v2<<endl;
        //cout<<"res: "<<res<<endl;
        number.push(res);
        
    }
    //cout<<"top: "<< number.top()<<endl;
    return number.top();
}

int main() {
    // You can add more test cases here
    std::cout << (solution("1+1") == 2) << std::endl;
    std::cout << (solution("3+4*5/(3+2)") == 7) << std::endl;
    std::cout << (solution("4+2*5-2/1") == 12) << std::endl;
    std::cout << (solution("(1+(4+5+2)-3)+(6+8)") == 23) << std::endl;
    return 0;
}

题14 二进制之和

# 问题描述

给定两个二进制字符串，返回他们的和（用十进制字符串表示）。输入为非空字符串且只包含数字 1 和 0 ，请考虑大数问题。时间复杂度不要超过 O(n^2)，其中 n 是二进制的最大长度。

## 输入格式

每个样例只有一行，两个二进制字符串以英文逗号“,”分割

## 输出格式

输出十进制格式的两个二进制的和

****输入样例****：

101,110

****输出样例****：

11

****数据范围****：

每个二进制不超过 100 个字符，JavaScript 语言下请考虑大数的情况。

解题思路

先把 两个二进制数 按照 二进制加法 相加

如： 101 + 110 ——> 1011

对这个新的二进制数，每一位(2^j)相加

代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <iostream>
#include <string>
# include <math.h>

using namespace std;

string add(string a1 , string a2){
    //  8918 + 19019
    string res = "";
    int in = 0;
    int now ;
    int minl = min(a1.size(), a2.size());
    //cout<<"minl: "<<minl<<endl;
    int i;
    for(i=0; i<minl;i++){
        int tmp = a1[a1.size() - i - 1] - '0' + a2[a2.size() - i -1]  - '0'+ in;
        //cout<<"tmp: "<<tmp<<" a1: "<<a1[a1.size() - i - 1]<<" a2: "<<a2[a2.size() - i - 1]<<" in: "<<in<<" i: "<<i<<endl;
        
        in = tmp / 10 ;
        now = tmp % 10 ;
        res += to_string(now);
    }
    if(a1.size() > a2.size()){
        while(i<a1.size()){

            int tmp = a1[a1.size() - i - 1] - '0' + in;
            in = tmp /10 ;
            now = tmp % 10;
            res += to_string(now);
            i++;
        }
    }
    else if(a1.size() < a2.size()){

        while(i<a2.size()){

            int tmp = a2[a2.size() - i - 1] - '0' + in;
            in = tmp / 10;
            now = tmp % 10;
            res += to_string(now);
            i++;
        }

    }
    //cout<<"in: "<<in<<endl;
    if(in !=0){
        res += to_string(in);
    }
    string res1 = "";

    for(int i=0; i<res.size(); i++){

        //cout<<"res: "<< res[res.size() - i -1]<<endl;
		res1 += res[res.size() - i -1];

    }
    return res1;
    
    

}

std::string solution(std::string binary1, std::string binary2) {
    // Please write your code here
    int in = 0;
    string out = "";
    int i ;
    int maxl = max(binary1.size(), binary2.size());
    int minl = min(binary1.size(), binary2.size());
    int detal = maxl - minl;
    // 1111 111
    for(i = 0; i + minl -1 >=0 ; i--){
        int b1 = binary1[i + binary1.size() -1 ] - '0' ;
        int b2 = binary2[i + binary2.size() - 1] - '0';
        int c = b1 + b2 + in;
        
        in = c / 2;
        out += to_string(c%2);
       
        
        
    }
    if(binary1.size() > binary2.size()){

        while(i + binary1.size()   >=1){
            int c = binary1[i + binary1.size() - 1] - '0' + in;
            //cout<<"c: "<<c<<endl;
        
            in = (c) / 2;
            out += to_string(c%2);
        
            
            
            i--;
        }

    }
    else if(binary1.size() < binary2.size()){

        while(i + binary2.size() >= 1){
        int c = binary2[i + binary2.size() - 1] - '0' + in;
        
        in = (c) / 2;
        out += to_string(c%2);
        
        i--;
       }

    }
    
    
    if(in!=0){
        out += to_string(in);
    }
    //1110111010101101
    // 89+101 = 
    string pow2j = "1";
    string pow2;

    string ress = "0";

    for(int j=0; j<out.size(); j++){
        //
        if(out[j] == '1'){
            pow2 = pow2j;
        }
        else{
            pow2 = "0";
        }
        
        
       
        ress = add(ress, pow2);
        //cout<<"ress: "<<ress<<" pow2: "<<pow2<<" pow2j: "<<pow2j<<endl;
        pow2j = add(pow2j, pow2j);

        

    }
//    cout<<"out: "<<out<<endl;
//    cout<<"out1: "<<ress<<endl;




    return ress;
}

int main() {
    // You can add more test cases here
    std::cout << (solution("101", "110") == "11") << std::endl;
    std::cout << (solution("111111", "10100") == "83") << std::endl;
    std::cout << (solution("111010101001001011", "100010101001") == "242420") << std::endl;
    std::cout << (solution("111010101001011", "10010101001") == "31220") << std::endl;

    return 0;
}

题15 不再贪心的小包

# 问题描述

众所周知，小包是一名非常喜欢吃甜点的小朋友，他在工作时特别爱吃下午茶里的甜食。

这天，下午茶小哥像往常一样送来了今天的 N 个甜点。小包对每个甜点有自己的喜爱值。但是今天的他不再贪心，并不想要喜爱值越高越好。他今天吃的甜点的喜爱值的和，一定要等于他的预期值 S。

但是他的预期值很高，小哥的甜点似乎不一定满足得了他，所以他准备了 M 个魔法棒，每个魔法棒可以对一个他要吃的甜点使用 1 次，使用后这个甜点的喜爱值会变成原来的喜爱值的阶乘。无法对一个甜点使用多次魔法棒，也不需要使用完所有魔法棒，也无法对不吃的甜点使用魔法棒。

小包很好奇，他有多少种方案，可以吃到喜爱值刚好为他的预期值的甜点。如果 2 种方案，食用了不同的甜点，或者对不同的甜点使用了魔法棒，都算作不同的方案。

## 输入格式

输入第一行，包含 3 个整数 N，M，S

分别代表甜点的数量，魔法棒的数量，以及小包的预期值

接下来一行，包含 N 个整数，代表每个甜点的喜爱值

## 输出格式

输出为一个整数，代表小包的方案数

*输入样例 1*

3 2 6

1 2 3

*输出样例 1*

5

*输入样例 2*

3 1 1

1 1 1

*输出样例 2*

6

*注解*

样例 1 中

小包有以下几种方案

选 1 2 3 不用魔法棒

选 1 2 3 对 1 用魔法棒

选 1 2 3 对 2 用魔法棒

选 1 2 3 对 1 2 用魔法棒

选 3 对 3 用魔法棒

样例 2 中 小包选任意 1 个甜点都是 1 种方案，每种方案都可以使用魔法棒不影响结果。所以一共 6 种方案

*数据范围*

10%的数据保证 M = 0, 1 <= N <= 10

30%的数据保证 1 <= N <= 12

100%的数据保证 1 <= N <= 25, 0 <= M <= N, 1 <= S <= 10^16

解题思路

对每个甜点，可以选择 不使用魔法棒 或者 使用魔法棒（在魔法棒总数允许的情况下）

构造如下数据结构：pair<使用的魔法棒个数， 累积喜爱值>, 可用方法数

考虑 map[{1, 10}] = 2

如果选择 新甜点like[i]， mp[{1 , 10+value}] += 2

代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <utility>
#include <vector>
#include <map>

typedef long long ll;

using namespace std;

ll returnjc(ll v){
    if(v==1 || v==0){return 1;}
    return returnjc(v-1)*v;
}


int solution(int n, int m, int s, std::vector<int> like) {
    // Please write your code here
    map<pair<int, ll>, int> mp;
    // pair<使用的魔法棒个数， 累积喜爱值>, 可用方法数
    mp[{0, 0ll}] = 1;
    for(int i=1; i<=n; i++){
        auto pp = mp;

        for(auto [k,v] : pp){
            int number = k.first;
            ll love_value = k.second;
            int method = v;
            if(love_value + like[i-1] <= s){
                // 取like[i]，不使用魔法棒
                mp[{number, love_value + like[i-1]}] += v;
            }
            if(number +1 <= m && love_value + returnjc(like[i-1]) <=s){
                mp[{number+1, love_value + returnjc(like[i-1])}] += v;
            }

        }
        
    }
    int count = 0;
    for(int i=0; i<=m; i++){

        count += mp[{i, s}];

    }

    // 1 2 3
    // 1 2 6
    // 

    return count;
}

int main() {
    //  You can add more test cases here
    std::vector<int> like1 = {1, 2, 3};
    std::vector<int> like2 = {1, 1, 1};

    std::cout << (solution(3, 2, 6, like1) == 5) << std::endl;
    std::cout << (solution(3, 1, 1, like2) == 6) << std::endl;

    return 0;
}

题16 二分数字组合

问题描述

小F面临一个有趣的挑战：给定一个数组，她需要将数组中的数字分为两组。分组的目标是使得一组数字的和的个位数等于给定的 A，另一组数字的和的个位数等于给定的 B。除此之外，还有一种特殊情况允许其中一组为空，但剩余数字和的个位数必须等于 A 或 B。小F需要计算所有可能的划分方式。

例如，对于数组 [1, 1, 1] 和目标 A = 1，B = 2，可行的划分包括三种：每个 1 单独作为一组，其余两个 1 形成另一组。如果 A = 3，B = 5，当所有数字加和的个位数为 3 或 5 时，可以有一组为非空，另一组为空。

测试样例

样例1：

输入：n = 3,A = 1,B = 2,array_a = [1, 1, 1]
输出：3

样例2：

输入：n = 3,A = 3,B = 5,array_a = [1, 1, 1]
输出：1

样例3：

输入：n = 2,A = 1,B = 1,array_a = [1, 1]
输出：2

样例4：

输入：n = 5,A = 3,B = 7,array_a = [2, 3, 5, 7, 9]
输出：0

解题思路

a1 a2 a3 a4 a5 a6

dp(i,j, k)长i的数组 A=j, B=k

if i分给了A

dp(i+1, j+a[i], k ) += dp(i,j,k)

dp(i+1, j, k+a[i]) += dp(i,j,k)

dp[n,A,B]

代码

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
44
45
46
47
48
public class Main {
    public static int solution(int n, int A, int B, int[] array_a) {
        // Please write your code here
        int sum_all = 0;
        int dp[][][] = new int[n+1][10][10];
        // dp[i][j][k] 长i的数组划分 满足A=j  B=k 的最多划分方案
        dp[0][0][0] = 1;
        for(int i=0; i<n ;i++){
            sum_all += array_a[i];
            for(int j=0; j<=9; j++)
            {
                for(int k=0; k<=9; k++){
                    //i位置上的元素 要么分给A这边 要么分给B这边
                    dp[i+1][(j+array_a[i])%10][k] += dp[i][j][k];
                    dp[i+1][j][(k+array_a[i])%10] += dp[i][j][k];
                    
                }
            }
        }

        if(sum_all%10 == A ||  sum_all%10 == B){
            dp[n][A][B]++;
        }
        



        




        //System.out.println("count: "+dp[n][A][B]);
        return dp[n][A][B];
    }

    public static void main(String[] args) {
        //  You can add more test cases here
        int[] array1 = {1, 1, 1};
        int[] array2 = {1, 1, 1};
        int[] array3 = {1, 1};
        

        System.out.println(solution(3, 1, 2, array1) == 3);
        System.out.println(solution(3, 3, 5, array2) == 1);
        System.out.println(solution(2, 1, 1, array3) == 2);
    }
}

题17 创意标题匹配问题

问题描述

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

测试样例

样例1：

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

样例2：

输入：n = 3, template = "a{bdc}efg", titles = ["abcdefg", "abefg", "efg"]
输出："True,True,False"

样例3：

输入：n = 5, template = "{abc}xyz{def}", titles = ["xyzdef", "abcdef", "abxyzdef", "xyz", "abxyz"]
输出："True,False,True,True,True"

结题思路

递归

顺序匹配，且删掉 从开始-匹配位 的所有内容，持续匹配。

全部匹配后可为True。

代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
public class Main {

    public static boolean match(String template, String title){

        if(template.isEmpty() && title.isEmpty()){

            return true;
        }
        if(title.isEmpty()){
            if(template.charAt(0)=='{' && template.charAt(template.length()-1)=='}'){
                return true;
            }
            else{
                return false;
            }
        }
        if(template.isEmpty()){
            return false;
        }
        int i=1;
        if(template.charAt(0) == '{'){
            while(template.charAt(i)!= '}'){
                i++;
            }
            for(int k=0; k <= title.length() ; k++){
                if(match(template.substring(i+1), title.substring(k))){
                    return true;
                }
            }
            return false;
        }
        
        if(template.charAt(0) != title.charAt(0)){
            return false;
        }

        return match(template.substring(1), title.substring(1));

    }

    public static String solution(int n, String template_, String[] titles) {
        // Please write your code here
        // ad{xyz}cdc{y}f{x}e 与 adcdcefdfeff
        String res ="";
        
        for(int i=0; i<n; i++){
            if(i!=n-1){
                if(match(template_, titles[i])){
                    res += "True,";
    
                }
                else res += "False,";

            }
            else{
                if(match(template_, titles[i])){
                    res += "True";
    
                }
                else res += "False";
            }
            
        }
        
        System.out.println("res: "+res);

        return res;

        
    }

    public static void main(String[] args) {
        //  You can add more test cases here
        String[] testTitles1 = {"adcdcefdfeffe", "adcdcefdfeff", "dcdcefdfeffe", "adcdcfe"};
        String[] testTitles2 = {"CLSomGhcQNvFuzENTAMLCqxBdj", "CLSomNvFuXTASzENTAMLCqxBdj", "CLSomFuXTASzExBdj", "CLSoQNvFuMLCqxBdj", "SovFuXTASzENTAMLCq", "mGhcQNvFuXTASzENTAMLCqx"};
        String[] testTitles3 = {"abcdefg", "abefg", "efg"};
       
        System.out.println(solution(4, "ad{xyz}cdc{y}f{x}e", testTitles1).equals("True,False,False,True"));
        System.out.println(solution(6, "{xxx}h{cQ}N{vF}u{XTA}S{NTA}MLCq{yyy}", testTitles2).equals("False,False,False,False,False,True"));
        System.out.println(solution(3, "a{bdc}efg", testTitles3).equals("True,True,False"));
    }
}

题18 数字翻译成字符串的可能性

小M获得了一个任务，需要将数字翻译成字符串。翻译规则是：0对应”a”，1对应”b”，依此类推直到25对应”z”。一个数字可能有多种翻译方法。小M需要一个程序来计算一个数字有多少种不同的翻译方法。

例如：数字12258可以翻译成 “bccfi”, “bwfi”, “bczi”, “mcfi” 和 “mzi”，共5种方式。

解题思路

dp

代码

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
44
45
46
47
48
49
public class Main {
    public static int solution(int num) {
        // Please write your code here
        // 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 
        // a b c d e f g h i j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
        // 1* (*可以是0到9) 
        // 2*（*可以是0到5）
        //dp[i]前i个字符最多有dp[i]种翻译方式
        // dp[3] = dp[2] + dp[1]
        // dp[i] = dp[i-1] + dp[i-2] //num[i:i+2]是一个小于25的数字
        int []dp = new int[100];
        dp[0] = 1;
        dp[1] = 1;
        int []nums = new int[100];
        int []nums2 = new int[100];
        int i=0;
        while(num!=0){
            
            nums[i] = num % 10;
            num /= 10;
            i++;

        }

        for(int j=0; j<i; j++){
            nums2[j] = nums[i-j-1];

        }
        // i为nums的长度
        for(int j=2; j<=i; j++){
            if(nums2[j-2] * 10 + nums2[j-1] <= 25  &&  nums2[j-2] * 10 + nums2[j-1] >= 10  ){
                dp[j] =  dp[j-1] + dp[j-2];

            }
            else{
                dp[j] = dp[j-1];
            }
        }
        //System.out.println("res: "+dp[i]);
        return dp[i];
    }

    public static void main(String[] args) {
        // You can add more test cases here
        System.out.println(solution(12258) == 5);
        System.out.println(solution(1400112) == 6);
        System.out.println(solution(2110101) == 10);
    }
}

题19 五子棋获胜策略

假设存在一个五子棋棋盘，大小未知。棋盘上已经摆放了一些白色棋子，现在你的手中还有一个白色棋子。你的任务是找出在棋盘的哪些位置摆放这个棋子，能够使棋盘上出现五颗棋子连成一线（不限于横向、纵向或斜向）。

备注：棋盘上当前不存在连成一条线的五个棋子，但至少存在一个点可以通过摆放使得形成五子连线。

（0，0） （0，1） （0，2） （0，3） （0，4）

（1，0） （1，1） （1，2） （1，3） （1，4）

（2，1） （2，2） （2，3） （2，4） （2，5）

AI掘金训练营刷题
https://wendyflv.github.io/2024/10/14/AI掘金训练营刷题/
作者
Wendyflv
发布于
2024年10月14日
许可协议