• 笔试面试相关记录（5）

    （1）给定一个字符串，含有大写、小写字母，空格，数字，需要将其变为满足如下条件：

    所有的数字需要换成空格，并且字符串的头尾不包含空格，且整个字符串不包含连续的两个空格。

    （2）给定n,k,L,R，接下拉n个数字，要从中选出某个序列，这个序列满足如下条件：

    对于整个数组中的任意的k个连续的子数组，所选出的子序列必须包含子数组中的x个数字，其中x>=1 && x <= R；求所有满足条件的子序列的序列和（序列和就是序列中所有元素的数字相加）

    示例

    3 2 1 2

    8 3 4 

    输出48

    （3）排雷：每次只能排去正方形的四个角的雷，如果雷的数目不够四个或者不在正方形的四个角，则不能排雷，输入数据为n行a b，其中a b表示雷的位置，求可以排雷的最大数目。

    例如输入

    8
    0 0
    0 1
    1 0
    1 1
    2 0
    2 1
    10 0
    10 1
    输出4,最多可以拍雷四个。

    （4）给定一个字符串如下3(a2(c))3(a)2(bc)，其中n(str)表示str出现n次，其中n > 0 && n < 10，将其还原为原始字符串。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. int main() {
    8.     string str;
    9.     while (cin >> str) { // 注意 while 处理多个 case
    10.         int len = str.size();
    11.         stack stk;
    12.         int i = 0;
    13.         while(i < len) {
    14.             if (str[i] == ')') {
    15.                 string t;
    16.                 while (stk.top() != "(") {
    17.                     t += stk.top();
    18.                     stk.pop();
    19.                 }
    20.                 // 取出(
    21.                 stk.pop();
    22.                 // 取出数字
    23.                 // 3(a2(c)) 3(a) 2(bc)
    24.                 string n = stk.top();
    25.                 stk.pop();
    26.                 if (n.find_first_of("123456789") != string::npos) {
    27.                     // 是数字
    28.                     int times = n[0] - '0';
    29.                     string orign = t;
    30.                     for (int k = 0; k < times-1; k++) {
    31.                         t += orign;
    32.                     }
    33.                 } 
    34.                 if (stk.size()) {   
    35.                     string c = stk.top();
    36.                     if (c != "(") {
    37.                         t = c + t;
    38.                         stk.pop();
    39.                     }   
    40.                 }
    41.                 stk.push(t);
    42.                 i++;
    43.             } else {
    44.                 if (str[i] == '(') {
    45.                     stk.push("(");
    46.                     i++;
    47.                 } else if(isdigit(str[i])) {
    48.                     stk.push(to_string(str[i]-'0'));
    49.                     i++;
    50.                 } else {
    51.                     string l = "";
    52.                     while (isalpha(str[i])) {
    53.                         l += str[i];
    54.                         i++;
    55.                     }
    56.                     stk.push(l);
    57.                 }
    58.             }
    59.         }
    60.         cout << stk.top() << endl;
    61.     }
    62. }

    （5）给一串数字，例如 9 8 5 6 3 2 4 1 7 0，第一个数字表示后面数字的个数，后面的数字都不重复，求出最小的峰值数，如果没有就输出-1（峰值数表示其值比左右两边都大的数字）；

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. int main() {
    7.     string str;
    8.     while (std::getline(std::cin, str)) { // 注意 while 处理多个 case
    9.         int len = str.size();
    10.         vector<int> nums;
    11.         int left = 0, t = 0;
    12.         while (left < len) {
    13.             if (isdigit(str[left])) {
    14.                 t = t*10 + (str[left]-'0');
    15.             } else {
    16.                 nums.push_back(t);
    17.                 t = 0;
    18.             }
    19.             left++;
    20.         }
    21.         nums.push_back(t);
    22.         // for (int i = 0; i < nums.size(); i++) {
    23.         //     cout << nums[i] << "-";
    24.         // }
    25.         int min_head = 1e8;
    26.         for (int i = 2; i < nums.size()-1; i++) {
    27.             if (nums[i] > nums[i-1] && nums[i] > nums[i+1] && nums[i] < min_head) {
    28.                 min_head = nums[i];
    29.             }
    30.         }
    31.         if (min_head == 1e8) {
    32.             cout << -1 << endl;
    33.         } else {
    34.             cout << min_head << endl;
    35.         }
    36.     }
    37. }

    （6） 

    1.     int a = 1;
    2.     int &ra = a;
    3.     int* pa = &a;
    4.     int* pb = new int(a);
    5.     a = 2;
    6.     cout << *pa <<" " << *pb << endl;
    7.     输出2 1

    （7）

    1. void func(char*) {
    2.     cout << "char *" << endl;
    3. }
    4.  
    5. void func(int) {
    6.     cout << "int" << endl;
    7. }
    8. int main()
    9. {
    10.     func(nullptr);
    11.  
    12.     return 0;
    13. }
    14. 输出char *

    （8）

    已知一个按照递增顺序排列的整数数组nums和一个目标值target，找出给定目标值在数组中的开始位置和结束位置。

    要求：

    1.时间复杂度O(log n)

    2.空间复杂度O(1)

    示例：

    输入：nums=[3,5,5,8,8,8,10]，target=8

    输出：[3,5]

    输入：nums=[3,5,5,8,8,8,10]，target=9

    输出：[-1,-1]

    答题模板

    class Solution {

    public:

       vector searchRange(vector& nums, int target) {

       }

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. int searchleft(vector<int>& nums, int target) {
    7.     int left = 0, right = nums.size()-1;
    8.     while (left < right) {
    9.         int mid = (left+right)>>1;
    10.         if (nums[mid] >= target) {
    11.             right = mid;
    12.         } else {
    13.             left = mid+1;
    14.         }
    15.     }
    16.     if (nums[left] == target) return left;
    17.     return -1;
    18. }
    19.  
    20. int searchright(vector<int>& nums, int target) {
    21.     int left = 0, right = nums.size()-1;
    22.     while(left < right) {
    23.         int mid = (left+right)>>1;
    24.         if (nums[mid] <= target) {
    25.             left = mid+1;
    26.         } else {
    27.             right = mid-1;
    28.         }
    29.     }
    30.     return left;
    31. }
    32.  
    33. vector<int> searchRange(vector<int>& nums, int target) {
    34.     int left = searchleft(nums, target);
    35.     vector<int> ans(2, 0);
    36.     if (left == -1) {
    37.         ans[0] = -1;
    38.         ans[1] = -1;
    39.         return ans;
    40.     }
    41.     int right = searchright(nums, target);
    42.     ans[0] = left;
    43.     ans[1] = nums[right] == target ? right:right-1;
    44.     return ans;
    45. }
    46.  
    47. int main() {
    48.     vector<int> nums{3, 5, 5, 8, 8, 8, 8, 10};
    49.     int target = 3;
    50.     vector<int> ans = searchRange(nums, target);
    51.     cout << ans[0] << " " << ans[1];
    52.     system("pause");
    53.     return 0;
    54. }

    （9）给你一个整数数组coins, 表示不同面额的硬币，以及一个整数amount，表示总金额。
    计算并返回可以凑成总金额所需的 最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。
    你可以认为每种硬币的数量是无限的。
    要求：时间复杂度O(Sn), S是金额，n是面额数

    数值范围：
    1 <= coins.length <= 12
    0 <= amount <= 10^4

    【测试用例】
    输入：coins = [1, 2, 5], amount = 11
    输出：3
    输入：coins = [2], amount = 3
    输出：-1
    输入：coins = [1], amount = 0
    输出：0

    【参考函数】
    int coinChange(vector& coins, int amount) {}

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. int coinChange(vector<int>& coins, int amount) {
    7.     vector<int> dp(amount+1, 1e9);
    8.     // 总价为0时，需要0张
    9.     dp[0] = 0;
    10.     int len = coins.size();
    11.     for (int i = 0; i < len; i++) {
    12.         for (int j = coins[i]; j <= amount; j++) {
    13.             dp[j] = min(dp[j], dp[j-coins[i]] + 1);
    14.         }
    15.     }
    16.     if (dp[amount] == 1e9) {
    17.         return -1;
    18.     }
    19.     return dp[amount];
    20. }
    21.  
    22. int main() {
    23.     vector<int> coins{1,2,5};
    24.     int amount = 11;
    25.     cout << coinChange(coins, amount);
    26.     system("pause");
    27.     return 0;
    28. }

    （10）

    你参与了一个微信小游戏的研发，策划同学计划给你发布n项任务，每项任务会有一个 发布时间点r 和 预估处理时长p ，你需要等待任务发布后才能开始编码实现，同时每项任务都会有一位测试同学跟进测试工作，你需要合理安排工作，让所有测试同学等待的时间之和最少，此外你作为一个资深的程序员，多项任务可以交替进行。
    输入：n r1 p1 ... rn pn
    输出：各项任务的任务id和完成时间，任务id从下标1开始，按完成时间升序排列
    比如
    输入：2 1 4 3 1
    即发布2项任务，任务1的发布时间点r=1，处理时长p=4；任务2的发布时间点r=3，处理时长p=1，合理的工作安排如下图所示:

    输出：
    2 4
    1 6
    测试同学等待的总时长为10
                                                            

    image.png

    【测试用例】
    输入：2 1 4 3 1
    输出：
    2 4
    1 6
    输入：3 3 3 4 1 1 7
    输出：
    2 5
    1 7
    3 12
    输入：2 5 2 3 1
    输出：
    2 4
    1 7
    【题目1】请简要阐述解题思路（12分）
    【题目2】编写相应的程序实现（24分）
    【参考函数】
    struct Task {
       int i;          // 任务id
       int r, p;       // 发布时间，处理时长
    };
    vector> processTasks(vector& tasks) {}

    思路：按照结束时间最早进行排序，这个时候的顺序就是最终的任务执行的顺序，因为多项任务交替进行，每一个任务都有一个测试人员，要让所有测试人员等待最小的时间，需要让 能够最先完成的任务最先完成，如果最先完成的没有在最开始完成，那么它带来的延迟会加到其他所有的测试人员上。（个人思路，不确定是不是正确的）

     

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. struct Task {
    7.     int i;
    8.     int r, p;
    9. };
    10.  
    11. static bool cmp(Task& t1, Task& t2) {
    12.     return t1.r + t1.p < t2.r + t2.p;
    13. }
    14.  
    15. vectorint>> processTasks(vector& tasks) {
    16.     int last_start = tasks[0].r;
    17.     vectorint>> ans;
    18.     int len = tasks.size();
    19.     // 此时第一个任务就是最先完成的任务，直接放入ans中
    20.     ans.push_back({tasks[0].i, tasks[0].r + tasks[0].p});
    21.     // 遍历剩下的任务
    22.     for (int i = 1; i < len; i++) {
    23.         // 分三种情况
    24.         if (tasks[i].r < last_start) {
    25.             int diff = last_start - tasks[i].r;
    26.             last_start = tasks[i].r;
    27.             ans.push_back({tasks[i].i, ans.back()[1] + tasks[i].p - diff});
    28.         } else if (tasks[i].r > tasks[i-1].r + tasks[i].p) {
    29.             ans.push_back({tasks[i].i, ans.back()[1] + tasks[i].p});
    30.         } else {
    31.             int diff = tasks[i].r - (tasks[i-1].r + tasks[i-1].p);
    32.             last_start += diff;
    33.             ans.push_back({tasks[i].i, ans.back()[1] + diff + tasks[i].p});
    34.         }
    35.     }
    36.     return ans;
    37. }
    38.  
    39. int main() {
    40.     int n;
    41.     cin >> n;
    42.     vector tasks(n);
    43.     for (int i = 0; i < n; i++) {
    44.         cin >> tasks[i].r;
    45.         cin >> tasks[i].p;
    46.         tasks[i].i = i+1;
    47.     }
    48.     sort(tasks.begin(), tasks.end(), cmp);
    49.  
    50.     // for (int i = 0; i < n; i++) {
    51.     //     cout << tasks[i].r << " " << tasks[i].p << endl;
    52.     // }
    53.     
    54.     vectorint>> ans = processTasks(tasks);
    55.     for (int i = 0; i < ans.size(); i++) {
    56.         cout << ans[i][0] << " " << ans[i][1] << endl;
    57.     }
    58.     
    59.     system("pause");
    60.     return 0;
    61. }

     

  • 相关阅读:
    Redis - 底层数据结构
    【广州华锐互动】VR可视化政务服务为公众提供更直观、形象的政策解读
    纯Python实现遗传算法
    Docker 安装
    SQL连接查询优化[姊妹篇.第五弹]
    Centos7快速安装跳板机jumpserver
    container/heap使用指南
    三十六、java版 SpringCloud分布式微服务云架构之Java 泛型
    数据分析-numpy2
    leetcode 48. 旋转图像(对矩阵的对角、左右旋转)
  • 原文地址：https://blog.csdn.net/wj617906617/article/details/132922057