秋招机试代码记录

秋招机试

2023-8-6 小红书机试

①统计热点词频
②最大快乐值
③树 质数 染色

2023-8-12 柠檬微趣机试

todo
① 正则匹配 字符串 模式串
② 严格最小 其后第一个严格最小的数
③ 打分 name score rank 查询 logn 插入删除 n
④ 组合数

2023-09-09 美团机试

五道题做出来前4道，第五题一分没得

第一题：签到题，将abc替换成bc ca ab

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

int main() {
  string str;
  int k;
  cin >> str >> k;
  for (int i = 0; i < k; i++) {
    string ans = "";
    for (char c : str) {
      if (c == 'a') {
        ans += "bc";
      } else if (c == 'b') {
        ans += "ca";
      } else {
        ans += "ab";
      }
    }
    str = ans;
  }
  cout << str << endl;
}

第二题 将表达式中的一个加号改成减号，要求不能出现负数，求改变后最小值

比较简单，找到最大的符合条件的数字减去即可，若未找到则输出-1

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>
using namespace std;
using ll = long long;
int main() {
  int n;
  cin >> n;
  vector<int> arr(n);
  vector<ll> sum(n + 1, 0);  // 可以使用一个变量代替数组存储，节省空间
  int max_suit_num = -1;     // 合适的数字
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    sum[i + 1] = sum[i] + arr[i];
    if (arr[i] <= sum[i]) {  // 当前数字小于等于之前所有数字之和，不会出现负数
      max_suit_num = max(max_suit_num, arr[i]);
    }
  }
  if (max_suit_num == -1) {  // 没有合适的数字，输出-1
    cout << -1 << endl;
  } else {  // 总和减去两倍该数字
    cout << sum[n] - 2 * max_suit_num << endl;
  }
}

第三题 给定一个01串，需要进行k次翻转，求翻转字符串后将00 11删除后的最小字符串长度

刚开始使用dfs回溯骗分，枚举所有情况，只过了30%

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
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int CountValue(string& str) {  // 计算01串删除后剩余值
  string ans = "2";
  int i = 0;
  while (i < str.length()) {
    int j = i;
    while (j < str.length() && str[j] == str[i]) {  // 找到连续相同的字符
      j++;
    }
    if ((j - i) % 2 == 1) {        // 若为奇数个
      if (ans.back() == str[i]) {  // 字符相等，抵消
        ans.pop_back();
      } else {  // 不相等，加入最终字符
        ans.push_back(str[i]);
      }
    }
    i = j;
  }
  return ans.length() - 1;
}
int min_val = 1 << 30;
int n, k;
void dfs(string& str, int index, int start) {  // index 翻转次数 start 翻转开始位置
  if (min_val == 0) {                          // 最小为0，无需继续搜索
    return;
  }
  if (index > k) {  // 达到翻转次数
    min_val = min(min_val, CountValue(str));
    return;
  }
  for (int i = start; i < n - k + index; i++) {  // 依次尝试翻转01
    str[i] = str[i] == '0' ? '1' : '0';
    dfs(str, index + 1, i + 1);
    str[i] = str[i] == '0' ? '1' : '0';
  }
}

int main() {
  string str;
  cin >> n >> k >> str;
  if (n == k) {  // 0 1全部翻转，没有任何变化
    cout << CountValue(str) << endl;
  } else {
    dfs(str, 1, 0);  // 暴力枚举，找到最小剩余值
    cout << min_val << endl;
  }
}

而后有时间了，回过头写这题，想到了一些点
1 可以先对原始字符串进行删除操作，这两者是等效的
2 最终剩余的字符串一定是010101这种类型的，且0或1没有太大区别
3 如果字符串长度为奇数，则其删除字符串后最小值为2，若为偶数，则最小值为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
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string EqualString(string& str) {  // 返回与其等效的删除字符串
  string ans = "2";                // 辅助字符，保证与谁都不相等
  int i = 0;
  while (i < str.length()) {
    int j = i;
    while (j < str.length() && str[j] == str[i]) {
      j++;
    }
    if ((j - i) % 2 == 1) {
      if (ans.back() == str[i]) {
        ans.pop_back();
      } else {
        ans.push_back(str[i]);
      }
    }
    i = j;
  }
  ans.erase(ans.begin());  // 删除开头的辅助字符
  return ans;
}

int n, k;

int main() {
  string str;
  cin >> n >> k >> str;
  str = EqualString(str);
  n = str.length();
  if (n == 0) {  // 原始字符串为空，如果翻转次数为奇数，则为2，为偶数则为0  （例如1111111为输入字符串）
    cout << (k % 2) * 2 << endl;
    return 0;
  }
  k = k % n;     // k对n取余，可以将这些字符串来回翻转，但值不变
  if (k == 0) {  // 不修改原始字符串
    cout << n << endl;
    return 0;
  }
  if (n % 2 == 0 && k <= n / 2) {  // 字符串为偶数且k小于等于半数，将中间的0或1翻转，合并
    cout << n - 2 * k << endl;
    return 0;
  }
  if (n % 2 == 1 && k <= n / 2 + 1) {  // 字符串为奇数且k小于等于半数，将中间的0或1翻转，合并
    k = (k == n / 2 + 1) ? k - 1 : k;
    cout << n - 2 * k << endl;
    return 0;
  }
  // 超过半数的情况，找规律或者直觉，可举出一些例子辅助理解
  if (n % 2 == 0 && k > n / 2) {
    cout << 2 << endl;
    return 0;
  }
  if (n % 2 == 1 && k > n / 2 + 1) {
    cout << 1 << endl;
    return 0;
  }
}

第四题 给定一个n与m，在1-m中选择n个数，使得各个数之间的差异值不同个数最多的序列

刚开始使用第三题类似的dfs骗分，枚举所有可能找到最大差异值个数的序列

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 <vector>
#include <string>
#include <set>
using namespace std;
int CountValue(vector<int>& arr) {  // 计算序列的差异值个数
  set<int> tmp;
  for (int i = 1; i < arr.size(); i++) {
    tmp.emplace(arr[i] - arr[i - 1]);
  }
  return tmp.size();
}

int max_val = 0;
vector<int> ans;
int n, m;
void dfs(vector<int>& arr, int index, int start) {  // index 选择的元素个数 start 遍历的开始位置
  if (max_val == n - 1) {                           // 差异值个数最大，无需搜索
    return;
  }

  if (index > n) {  // 选完所有元素
    int new_val = CountValue(arr);
    if (new_val > max_val) {
      max_val = new_val;
      ans = arr;
    }
    return;
  }
  for (int i = start; i <= m - n + index; i++) {
    arr.push_back(i);  // 尝试当前元素
    dfs(arr, index + 1, i + 1);
    arr.pop_back();  // 回退
  }
}

int main() {
  cin >> n >> m;
  if (n == m) {
    for (int i = 1; i <= n; i++) {
      cout << i << " ";
    }
  } else {
    vector<int> arr;
    dfs(arr, 1, 1);
    for (int num : ans) {
      cout << num << " ";
    }
  }
  return 0;
}

而后回过头使用正常的方法
1 可能的序列有可能有许多，但一定存在一个以1起始的序列（平移）
2 可以采用贪心的方法，间距从1依次增加，直到大于m

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
#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  if (n == m) {  // 不用选择，只能选择所有数字
    for (int i = 1; i <= n; i++) {
      cout << i << " ";
    }
  } else {
    vector<int> arr;
    arr.emplace_back(1);
    int delta = 1;  // 间距
    for (int i = 2; i <= n; i++) {
      int next_val = arr.back() + delta;             // 下一个预期数字
      if (next_val <= m && m - next_val >= n - i) {  // 该数字小于m且与m之间有以后数字的空间
        arr.emplace_back(next_val);                  // 加入序列并增加间距
        delta++;
      } else {
        break;
      }
    }
    while (arr.size() < n) {  // 补全后续序列
      arr.emplace_back(arr.back() + 1);
    }
    for (int num : arr) {
      cout << num << " ";
    }
  }
  return 0;
}

第五题 连续子数组的异或和，完全没做

2023-09-10 腾讯机试

题目链接：腾讯0910秋招笔试真题解析
牛客网提交系统出现问题，无法看到过了多少，故简单记录解题思路

在这里插入图片描述
dfs回溯，签到题

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
#include <bits/stdc++.h>
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
 public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * 返回节点权值1个数比0的个数多一的路径数
   * @param root TreeNode类 权值为0和1的二叉树根节点
   * @return int整型
   */
  void dfs(TreeNode *node, int zero_num, int one_num, int &path_num) {  // zero_num 权值0节点个数 one_num 权值1节点个数 path_num 符合条件的路径个数
    if (node == nullptr) {
      return;
    }

    if (node->val == 0) {
      zero_num++;
    }

    if (node->val == 1) {
      one_num++;
    }

    if (node->left == nullptr && node->right == nullptr) {  // 叶子节点
      if (one_num - zero_num == 1) {                        // 权值1比权值0个数多1，路径数加一
        path_num++;
      }
      return;
    }

    if (node->left != nullptr) {
      dfs(node->left, zero_num, one_num, path_num);
    }

    if (node->right != nullptr) {
      dfs(node->right, zero_num, one_num, path_num);
    }
  }
  int pathNumber(TreeNode *root) {
    if (root == nullptr) {
      return 0;
    }
    int ans = 0;
    dfs(root, 0, 0, ans);
    return ans;
  }
};

在这里插入图片描述
思路：将数组排序，维护中间位置的左右指针，当删除特定数字后，更改左右指针指向。对于b数组，构造一个数字大小-排序数组下标的map

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 <vector>
#include <map>
#include <algorithm>
using namespace std;

int find_pos(vector<int>& arr, int start, int dir) {  // 跳过-1的位置，向前或向后遍历
  while (arr[start] == -1) {
    start += dir;
  }
  return start;
}
int main() {
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    // 接收输入
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n - 1);
    for (int j = 0; j < n; j++) {
      cin >> a[j];
    }
    for (int j = 0; j < n - 1; j++) {
      cin >> b[j];
    }
    vector<double> ans(n);
    map<int, vector<int>> value_loc;  // 数字大小与其对应的下标集合
    vector<int> arr = a;
    sort(arr.begin(), arr.end());  // 对数组进行排序，便于计算中位数
    for (int j = 0; j < n; j++) {
      value_loc[arr[j]].emplace_back(j);
    }

    int left = (n + 1) / 2 - 1;  // 左指针
    int right = n / 2;           // 右指针
    ans[0] = (arr[left] + arr[right]) / 2.0;
    for (int j = 1; j < n; j++) {
      int loc = value_loc[a[b[j - 1] - 1]].back();  // 排序数组的位置
      value_loc[a[b[j - 1]]].pop_back();
      arr[loc] = -1;                     // 标记为删除
      bool is_odd = ((n - j) % 2 == 0);  // 当前数组元素个数是否为偶数
      if (is_odd) {                      // 之前左右指针在一起，现在需要分开
        if (loc > right) {
          left = find_pos(arr, left - 1, -1);  // 左指针向左移一位
        } else if (loc < left) {
          right = find_pos(arr, right + 1, +1);  // 右指针向右移一位
        } else {                                 // 恰好删除中位数，左右指针各向两边移一位
          left = find_pos(arr, left - 1, -1);
          right = find_pos(arr, right + 1, +1);
        }
      } else {  // 之前左右指针不在一起，现在需要合并
        if (loc >= right) {
          right = left;
        } else if (loc <= left) {
          left = right;
        }
      }

      ans[j] = (arr[left] + arr[right]) / 2.0;  // 计算新的中位数
    }

    for (int j = 0; j < n; j++) {
      cout << ans[j] << " ";
    }
  }
  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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  long long sum = 0;
  int x = 0;
  // 左右指针
  int left = 0;
  int right = n - 1;
  while (left < right) {
    sum += max(0, a[right] - x);  // 如果a[i]大于x则将a[i]-x勇气值加上
    x = a[right];
    sum += max(0, a[left] - x);
    x = a[left];
    left++;
    right--;
  }
  if (left == right) {  // 数组元素个数为奇数，计算中间元素勇气值
    sum += max(0, a[right] - x);
  }
  cout << sum << endl;
}

第四题 完全没写，题目应该是长度为2的子串异或和什么的，一看就不会

第五题 n个数，执行k次操作，每次操作选择将某个数的最低位1变成0，求最小总和

思路：想不到正确的解决办法，只能用贪心得点分，估计正确思路应该是动态规划之类的
贪心：每次选择最低位1最大的数字删除

反例：1001 0110 操作两次应该选择1001的两个1而不是0110的两个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
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> arr(n);
  long long sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    sum += arr[i];
  }
  vector<queue<int>> low_bit(n);               // 各个数的二进制组成 9:8 1  10:8 2
  priority_queue<pair<int, int>> max_low_bit;  // pair:最低位1大小-所属数字下标
  for (int i = 0; i < n; i++) {
    int x = arr[i];
    int k = 1;
    while (x != 0) {
      if (x % 2 == 1) {
        low_bit[i].emplace(k);  // 将1填入对应队列
      }
      x /= 2;
      k *= 2;
    }
    max_low_bit.emplace(low_bit[i].front(), i);  // 将每个数的最低位1加入优先队列
  }
  for (int i = 0; i < k; i++) {  // 贪心算法，每次选择最低位1最大的删掉
    auto [delta, pos] = max_low_bit.top();
    max_low_bit.pop();
    sum -= delta;
    low_bit[pos].pop();
    if (!low_bit[pos].empty()) {  // 当前数字非空，加入下一位
      max_low_bit.emplace(low_bit[pos].front(), pos);
    }
  }
  cout << sum << endl;
}

2023-09-13 华为机试

2023-09-16 深信服机试

2023-09-16 淘天机试