sitJac's Blog
0%

华为OD机试 C卷 三道题目思路汇总

Posted on In
  • 第一题吃货馋嘴分披萨，考察深度优先遍历和动态规划处理环形数组问题，在一个环形数组（比萨）中，每次可以选择左边或右边的元素，并且每次选择的元素必须是当前可选元素中的最大值，求能够选择的元素的最大和。
  • 第二题字符串变换最小字符串，考察对字符串的处理，从后面向前面查找，把倒数第一个字典序最小字符的与第一个字符替换，保证最小。
  • 第三题满足要求的最长子串，考察滑动窗口+字符串的处理，使用滑动窗口来找出只包含一个字母和任意数量数字的最长子串。

第一题 吃货馋嘴分披萨（100）

“吃货”和”馋嘴”两人到披萨店点了一份铁盘圆形披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。但是粗心的服务员将披萨切成了每块大小都完全不同奇数块，且肉眼能分辨出大小。

由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法：从”吃货”开始，轮流取被萨。除了第一块破产可以任意选取外，其他都必须从缺口开始选。

他俩选披萨的思路不同。”馋嘴”每次都会选最大块的披萨，而且”吃货”知道”馋嘴”的想法。

已知披萨小块的数量以及每块的大小，求”吃货”能分得的最大的披萨大小的总和。

输入描述：

1.第1行为一个正整数奇数 N，表示披萨小块数量。
2.接下来的第 2 行到第 N + 1行(共 N 行)，每行为一个正整数，表示第 i 块披萨的大小。

说明：
3 <= N <= 500
1 <= i <= N
每块披萨的大小范围为[1, 2147483647]

输出描述：

“吃货”能分到的最大的披萨大小的总和。

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
/*
Input:
5
8
2
10
5
7

Output:
19

Description:
此例子中，有5块披萨，每块大小分别为8、2、10、5、7
按照如下顺序拿披萨，可以使"吃货"拿到最多的披萨:
"吃货"拿大小为10的披萨
"馋嘴"拿大小为5的披萨
"吃货"拿大小为7的披萨
"馋嘴"拿大小为8的披萨
"吃货"拿大小为2的披萨
至披萨瓜分完毕，"吃货"拿到的披萨总大小为10 + 7 + 2 = 19

注：可能存在多种拿法，以上只身其中一种拿法。
*/

#include <bits/stdc++.h>
using namespace std;

vector<vector<long>> memory; // 用于存储已经计算过的子问题的结果

// 使用DFS和DP的方法来解决问题
long backtrace(vector<long> nums, int n, int left, int right) {
    // 调整left和right的值，使其始终在数组的范围内
    if(nums[left] > nums[right]) {
        left = left < 0 ? left : (left + n + 1) % n;
    } else if(nums[left] < nums[right]) {
        right = right < 0 ? right : (right + n - 1) % n;
    }

    // 如果当前子问题的结果已经计算过，直接返回结果
    if(memory[left][right] <= 0) {
        // 如果left和right相等，说明只有一个元素可以选择，直接返回这个元素的值
        if(left == right) {
            memory[left][right] = nums[left];
        } else {
            // 否则，计算选择左边元素和选择右边元素两种情况的最大值
            int newLeft = (left + 1) % n;
            int newRight = (right + n - 1) % n;
            memory[left][right] = nums[left] + backtrace(nums, n, newLeft, right);
            if(nums[right] + backtrace(nums, n, left, newRight) > memory[left][right]) {
                memory[left][right] = nums[right] + backtrace(nums, n, left, newRight);
            }
        }
        return memory[left][right];
    } else {
        return memory[left][right];
    }
}

int main() {
    int n;
    while(cin >> n) {
        vector<long> nums(n);    // 披萨大小
        for(int i = 0; i < n; i++) {
            cin >> nums[i];
        }

        // 初始化memory数组
        for(int i = 0; i < n; i++) {
            vector<long> tmp;
            memory.push_back(tmp);
            for(int j = 0; j < n; j++) {
                memory[i].push_back(0);
            }
        }

        long res = 0;
        int i = 0;  // 遍历数组
        while(1) {
            if (i > n - 1) {
                break;
            } else {
                int left = (i + n + 1) % n;
                int right = (i + n - 1) % n;
                long target = backtrace(nums, n, left, right);
                if(target + nums[i] > res) {
                    res = target + nums[i];
                }
            }
            i++;
        }
        cout << res << endl;
    }

    return 0;
}

第二题 字符串变换最小字符串（100）

给定一个字符串s，最多只能进行一次变换，返回变换后能得到的最小字符串（按照字典序进行比较）。
变换规则：交换字符串中任意两个不同位置的字符。

输入描述：

一串小写字母组成的字符串s。

说明:
s是都是小写字符组成
1 <= s.length <= 1000

输出描述：

按照要求进行变换得到的最小字符串。

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
/*
Input:
abcdef

Output:
abcdef

Description:
abcdef已经是最小字符串，不需要交换


Input:
bcdefa

Output:
acdefb

Description:
a和b进行位置交换，可以等到最小字符串
*/

#include <bits/stdc++.h>
using namespace std;

int main() {
    string str;
    while(cin >> str) {
        char minChar = 'z';
        int minCharIndex = 0;

        for(int i = str.size() - 1; i >= 0; i--) { // 注意遍历顺序！！！
            if(str[i] <= minChar) { // 确保如果有多个最小字符，总是选择最后一个
                minChar = str[i];
                minCharIndex = i;
            }
        }

        char tmp = str[0];
        str[0] = minChar;
        str[minCharIndex] = tmp;

        cout << str << endl;
    }

    return 0;
}

第三道 满足要求的最长子串（200）

给定一个字符串，只包含字母和数字，按要求找出字符串中的最长（连续）子串的长度，字符串本身是其最长的子串，子串要求：

  1. 只包含1个字母(a ~ z, A ~ Z)，其余必须是数字。
  2. 字母可以在子串中的任意位置。

如果找不到满足要求的子串，如全是字母或全是数字，则返回-1。

输入描述：

字符串(只包含字母和数字)

输出描述：

子串的长度，没有满足要求的子串，返回-1

解题思路：

什么时候右边界滑动：每次滑动一个
什么时候形成滑动窗口：当charCount = 1 && numCount >=1
什么时候左边界滑动：当charCount > 1时，当charCount == 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
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
/*
Input:
abC124ACb

Output:
4

Description:
满足条件的最长子串是C124或者124A，长度都是4


Input:
a5

Output:
2

Description:
字符串自身就是满足条件的子串，长度为2


Input:
aBB9

Output:
2

Description:
满足条件的子串为B9，长度为2


Input:
abcdef

Output:
-1

Description:
找不到满足要求的子串，返回-1
*/

#include <bits/stdc++.h>
using namespace std;

// 只包含一个字母 + 字母可在任意位置
int maxLength(string str) {
     int left = 0, right = 0; // 滑动窗口
     int charCount = 0, digitCount = 0, maxCount = -1;
     while(right < str.size()) {
         if(isdigit(str[right])) {
             digitCount++;
         } else {
             charCount++;
         }
         if(charCount == 1 && digitCount > 0) {
             maxCount = max(maxCount, right + 1 - left);
         }
         while(charCount > 1) {
             if(isdigit((str[left]))) {
                 digitCount--;
             } else {
                 charCount--;
             }
             left++;
         }
        right++;
     }
     return maxCount;
}

int main() {
    string str;
    while(cin >> str) {
        cout << maxLength(str) << endl;
    }
    return 0;
}