建信金科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];
}