建信金科11/4笔试
第一题:链表的合并,如果是偶数,跟之前的合并。
ListNode* mergeNode(ListNode* head) { // write code here if (head == nullptr) return nullptr; if (head->next == nullptr) return head; auto prev = head; // 前置节点 auto curr = prev->next; // 下一个节点 // 如果节点是偶数值,准备从当前节点合并 if ((curr->val) % 2 == 0) { // 这部分可能出错,因为合并的前提是前一个为奇数,当时做题没看到 // 这也是只A了80%的原因,交卷才反应过来 prev->val = (prev->val) + (curr->val); auto temp = curr->next; delete curr; // 删除该节点所占空间 prev->next = temp; // 连接起下一个节点 prev = mergeNode(prev); // 继续判断 } // 如果是奇数值,则能从下一个点开始合并 else { prev->next = mergeNode(curr); } return head; }
第二题:删除链表的次数的期望
数学问题,概率乘次数,动态规划问题;
double get_expect(int n) { // write code here // if (n == 0) return 0; // if (n == 1) return 1; // if (n == 2) return 1; // if (n == 3) { // return (double)5 / 3; // } // double f1 = double(n - 2) / n; // double f2 = 1 - f1; // 递归版本的代码爆栈,超时,改为动态规划 // return f1 * get_expect(n - 3) + f2 * get_expect(n - 2) + 1; vector<double> dp(n + 1); if (n == 0) return 0; if (n == 1) return 1; if (n == 2) return 1; if (n == 3) { return (double)5 / 3; } dp[0] = 0; dp[1] = 1; dp[2] = 1; dp[3] = (double)5 / 3; for (int i = 4; i <= n; ++i) { double f1 = double(i - 2) / i; double f2 = 1 - f1; dp[i] = f1 * dp[i - 3] + f2 * dp[i - 2] + 1; } return dp[n]; }#建信金科校招##建信金科#