笔试面试相关记录（13）

（1）一个链表，当一个结点为偶数，且它前面的结点为奇数时，将这个节点合并到前面的结点中，一直执行这个操作，知道没有满足条件的结点时。

输入如下：{2,3,4,1,2,2,3}

输出：{2,7,5,3}

解释：4合并到3上，变为{2,7,1,2,2,3}，2合并到1上，变成{2,7,3,2,3}，2合并到3上，变成{2,7,5,3}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* mergeNode(ListNode* head) {
        // write code here
        if (head == nullptr) return head;
        ListNode* cur = head->next;
        ListNode* pre = head;
        while(cur) { 
            if (cur->val % 2 == 0 && pre->val % 2 == 1) {
                pre->val = pre->val + cur->val;
                pre->next = cur->next;
                delete cur;
                cur = pre->next;
            } else {
                pre = pre->next;
                cur = cur->next;
            }
        }
        return head;
    }
};

（2）一个链表，每次选择一个节点，删除掉，，三个结点，如果有结点不存在，则不删除，一直对链表执行此操作，问要使得链表为空，需要的操作次数的期望值？

解释：如果链表只有一个结点，则只执行一次删除就变为空，操作次数期望为1

如果链表有两个节点，则选中任意一个，都会变为空，操作期望为1

如果链表为三个结点，则选中第一个，还剩最右边一个，还需一次操作，选中中间，只需一次，选中最右边的，还剩最左边的一个，期望值为1/3 * 2 + 1/3 * 1 + 1/3 * 2 = 1.66666667

如果链表为四个，则期望为1/4*2 + 1/4*2 + 1/4*2 +1/4*2 = 2

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return double浮点型
     */
    double get_expect(int n) {
        // write code here
        vector<double> dp(5, 0);
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1.66666667;
        dp[4] = 2;
        if(n<=4) return dp[n];
        for (int i = 5; i <= n; i++) {
            // 选择了两遍的情况有2种，每种的概率为1/i，操作次数为剩下的操作次数dp[3]+1
            double num1 = 2.0/i * (dp[3] + 1);
            // 选择了非两边的情况，double(i-2)/i
            double num2 = double(i-2)/i * (dp[2] + 1);
            double total = num1 + num2; 
            // dp[2], dp[3], dp[4] 分别用来记录之前已经计算过的值，然后依次迭代
            dp[2] = dp[3];
            dp[3] = dp[4];
            dp[4] = total;
        }
        return dp[4];
    }
};