Weekly Contest 95

1. 876. 链表的中间结点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int get_nodes(ListNode* head){
        ListNode* p = head;
        int node_num = 0;
        while(p){
            node_num ++;
            p = p->next; //not p ++(用于数组指针)
        }
        return node_num;
    }

    ListNode* middleNode(ListNode* head) {
        ListNode* mid_node = head;
        int step = get_nodes(head)/2;
        for(int i=1;i<=step;i++) mid_node = mid_node->next;
        return mid_node;
    }
};
------

2 . 877. 石子游戏

class Solution {
public:
    //dp[i][j]: 区间长度为i且下标从j开始时先手多出的石子数
    bool stoneGame(vector<int>& piles) {
        int len = piles.size();
        vector<vector <int>> dp = vector<vector <int>> (len + 5, vector<int>(len + 5)); //创建二维数组
        for(int i=0;i<len;i++) dp[1][i] = piles[i];
        for(int i=2;i<=len;i++){
            for(int j=0;j+i<=len;j++){
                dp[i][j] = max(piles[j] - dp[i-1][j+1], piles[j+i-1] - dp[i-1][j]);
            }
        }
        return dp[len][0] > 0;
    }
};

3 . 878. 第 N 个神奇数字

const int P = 1e9 + 7;
typedef long long ll;
class Solution {
public:

    int gcd(int A, int B){
        int rem = A % B; 
        while(rem) {
            A = B;
            B = rem;
            rem = A % B;
        }
        return B;
    }

    int nthMagicalNumber(int N, int A, int B) {
        ll low = 1, high = min(A, B)*(ll)N; //
        int lcm = A * B / gcd(A, B);
        while(low < high){
            ll mid = (low + high) >> 1;
            //'>''='放一起是因为可能在mid不整除A或B的情况下计算结果为N，譬如A = 2, B = 3, N = 4， 此时mid = 6 或 7
            if(mid/A + mid/B - mid/lcm >= N) high = mid; 
            else low = mid + 1;
        }
        return low % P;
    }
};

4 . 879. 盈利计划

const int PR = 1e9 + 7;
class Solution {
public:
    //dp[i][j]:i名成员的犯罪计划至少产生利润j的方案数
    int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
        vector<vector <int >> dp(G + 5, vector<int>(P + 5)); //默认为0
        dp[0][0] = 1;
        //背包
        for(int k = 0; k < group.size(); k++) {
            //这两个循环都是从大到小（两者顺序不受限制）
            for(int j = P; j >= 0; j--) {
            for(int i = G-group[k]; i >= 0; i--) {
                 //for(int j = P; j >= 0; j--) {
                    if(dp[i][j]) (dp[i+group[k]][min(P, j+profit[k])] += dp[i][j]) %= PR; //
                }
            }
        }
        int ret = 0;
        for(int i = 0; i <= G; i++) (ret += dp[i][P]) %= PR; //%=
        return ret;
    }
};

参照：
【1】: [email protected]阳谷县
【2】: wangyisong-CN