算法设计与分析[0023] 秋招华为在线笔试

编程珠玑Algorithm

　　昨晚华为在线笔试，三道编程题，结果倒在第二题上，刷了两题半，没能 AK。

第一题

　第一题是括号（“(”、“[”、“{”）匹配，想法也比较简单，就通过栈stack模拟，遇到开括号推入堆栈，每当遇到闭括号（“)”、“]”、“}”），就进行配对，满足配对就将栈顶的开括号弹出。假如最终的栈是空的，说明输入表达式不存在括号或者括号能够完全匹配。
　需要注意的是：①满足配对并不是stack.top()==inputStr[currentIdx]，而需要分上述三种括号进行一一配对；②当存在闭括号，但栈为空或者栈顶元素并不是配对的开括号，已经能够证明输入表达式括号不匹配了，此时可以跳出循环。

第二题

  • 问题背景是打印机任务打印，给一个任务打印队列，不过是每个任务对应的优先级的一个优先级队列int tasksPriority[MAX_TASK_NUM];，每个任务通过其在优先级队列的下标唯一标识0...tasksNum-1；此外还有补充条件：任务的优先级只有 1~9 这九种，优先级数值越高优先级越大。要求：任务打印时，假如等待队列中有优先级更大的，该任务不能被打印，需要重新回到队列中（重新插入队尾），求通过下标标识的一个任务打印队列的最终打印顺序。
  • 一开始的想法是，用一位数组tasksIdx[]维护一个优先级和任务下标标识的对应关系，因为优先级只有 1~9，可以开一个大小为 10 的数组，与tasksIdx[1...9]对应；打印顺序即是优先级的一个由大到小排序，通过sort(vector.begin(), vector.end(), greater<int>())实现，需要先将tasksPriority[]通过vector.assign(tasksPriority, tasksPriority+tasksNum)转为 vector。排序后对应的优先级下标tasksIdx[tasksPriority[0...tasksNum-1]]顺序即为最终的打印顺序。
  • 可惜的是，第一种想法并没有考虑到一个优先级可能有多个重复任务。现在想想，这种应该维护一个vector<vector<int>> tasksIdx(10, vector<int>())的二维向量，按照优先级队列中的先后顺序插入在每个优先级下标对应的那个向量中。不过，就需要跳过降序排列的优先级队列中重复的优先级。
  • 另一种想法，因为优先级和任务下标的这种关系，想到用pair<int, int>保存（first记录优先级，second记录任务下标），又因为排序，所以想到了优先级队列priority_queue，以优先级first作为键值，可怕的是，priority_queue驾驭不了那种存在多个键值相同的情形，不能保证顺序的稳定：相同优先级的多个任务，其打印顺序与其在输入的优先级队列中的顺序一致。
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    struct cmp {
      bool operator() (pair<int, int> a, pair<int, int> b) {
        // fitst: tasksPriority[]
        // second: tasksIdx[]
        return a.first>b.first;
      }
    };
     
    priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> tasksQueue;
  • 最后，现在想想，似乎应该回到问题的本质：其实就是一种稳定排序吧。所以想到了 Bubble Sort；因为交换的存在，干脆将需要进行冒泡排序的打印任务优先级队列与对应的打印任务下标队列（新建这样一个队列）通过二者下标绑定，交换优先级队列位置的时候，也将下标队列对应位置进行交换。最终得到排好序的优先级队列满足打印要求，下标队列也能与之一一对应，下标队列即为最终的打印顺序。
  • 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
    #include <iostream>
    #include <queue>
    #include <algorithm>
    #include <vector>
     
    using namespace std;
     
    static const int MAX_TASK_NUM=100;
     
    void printOrder(const int input[], int len, int output[]) {
      vector<int> input_(len);
      for(int idx=0; idx<len; idx++) {
        output[idx] = idx;
        input_[idx] = input[idx];
      }
     
      bool isSorted;
      for(int i=0; i<len; i++) {
        isSorted = true;
        for(int j=len-1; j>i; j--) {
          if(input_[j] > input_[j-1]) {
            isSorted = false;
            int tmpPriority = input_[j];
            input_[j] = input_[j-1];
            input_[j-1] = tmpPriority;
     
            int tmpIdx = output[j];
            output[j] = output[j-1];
            output[j-1] = tmpIdx;
          }
        }
        if(isSorted) {
          break;
        }
      }
    }
     
    int main() {
      string inputStr;
     
      while(getline(cin, inputStr)) {
        // cout << inputStr << endl;
        int strLen = inputStr.length();
        int taskNum = 0;
        int tasks[MAX_TASK_NUM];
        int printTasks[MAX_TASK_NUM];
        for(int i=0; i<strLen; i++) {
          // cout << inputStr[i] << endl;
          if(inputStr[i]>'0' && inputStr[i]<='9') {
            tasks[taskNum++] = inputStr[i] - '0';
            // cout << inputStr[i] - '0' << endl;
          }
        }
     
        if(taskNum>=1) {
          printOrder(tasks, taskNum, printTasks);
          cout << printTasks[0];
          for(int i=1; i<taskNum; i++) {
            cout << ", " << printTasks[i];
          }
        }
        cout << endl;
      }
     
      return 0;
    }
    • 需要注意的是：①冒泡排序原理的正确实现，只有只比较相邻的元素，才能保证排序的稳定性；②输入输出格式的要求，输入格式“1, 1, 1, 1, 1”，除了上面这种获取方式，也可以通过cin >> int >> char获取，不过还得注意cin的空格自动结束，可能还是比上面的方式麻烦；输出格式的满足还是比较简单的。

第三题

　第三题是输入平安果矩阵，即一个 row×col 的二维矩阵appleGrids，只不过矩阵的每个元素appleGrids[rowIdx][colIdx]表示当前格子中平安果数目；要求只能在二维网格中向下或者向右移动，求从网格左上角移动到网格右下角能收获的平安果的最大数目。
　显然通过 DP 可以很快速求解，dp[rowIdx][colIdx]表示从网格左上角移动到格子[rowIdx][colIdx]能收获的平安果最大数目，显然dp[row-1][col-1]便是最终的答案；又由于只能向下或者向右移动，动态转移方程，直观说就是dp二维表格从左到右（[rowIdx-1][colIdx]→[rowIdx][colIdx]）、从上到下（[rowIdx][colIdx-1]→[rowIdx][colIdx]）的填表过程，易知这个转移方程：$$ dp[rowIdx][colIdx] = max(dp[rowIdx-1][colIdx], dp[rowIdx][colIdx-1]) + appleGrids[rowIdx][colIdx] $$
　需要注意的是：①dp[0][0]、dp[0][1...col-1]、dp[1...row-1][0]需要单独初始化；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static inline int max(int a, int b) { return (a>b?a:b); }
 
// dp[i][j]: the largest collected apple number reach appleGrids[i][j]
vector<vector<int> > dp(row, vector<int>(col, 0));
dp[0][0] = appleGrids[0][0];
for(int colIdx=1; colIdx<col; colIdx++) {
  dp[0][colIdx] = dp[0][colIdx-1] + appleGrids[0][colIdx];
}
for(int rowIdx=1; rowIdx<row; rowIdx++) {
  dp[rowIdx][0] = dp[rowIdx-1][0] + appleGrids[rowIdx][0];
}
for(int rowIdx=1; rowIdx<row; rowIdx++) {
  for(int colIdx=1; colIdx<col; colIdx++) {
    // max(up->down, left->right)
    dp[rowIdx][colIdx] = max(dp[rowIdx-1][colIdx], dp[rowIdx][colIdx-1]) + appleGrids[rowIdx][colIdx];
  }
}

　②二维平安果矩阵如何初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
int row, col;
while(cin >> row >> col) {
  if(row>1 && col>1) {
    vector<vector<int> > appleGrids(row, vector<int>(col, -1));
    for(int rowIdx=0; rowIdx<row; rowIdx++) {
      for(int colIdx=0; colIdx<col; colIdx++) {
        cin >> appleGrids[rowIdx][colIdx];
      }
    }
    //...
  }
  //...
}

本文标题:算法设计与分析[0023] 秋招华为在线笔试

文章作者:Gary

发布时间:2017-07-13, 08:55:22

最后更新:2020-03-28, 12:37:22

原始链接:http://durant35.github.io/2017/07/13/Algorithms_OnlineJudge4Huawei2017/

文章目录
  1. 1. 第一题
  2. 2. 第二题
  3. 3. 第三题