周赛补题

leetcode 单 ：

第一题https://leetcode.cn/problems/find-the-pivot-integer/遍历一遍检查是否为中枢数

class Solution {
public:
    int pivotInteger(int n) {
        for (int i = 1; i <= n; i++) {
            int L = (1 + i) * i / 2;
            int R = (i + n) * (n - i + 1) / 2;
            if (L == R) return i;
        }
 
        return -1;
    }
};

第二题https://leetcode.cn/problems/append-characters-to-string-to-make-subsequence/ 双指针遍历，找到最长子序列，最后用 t.size 减去得到答案

class Solution {
public:
    int appendCharacters(string s, string t) {
        int i = 0, j = 0;
        int n = s.size(), m = t.size();
        
        int res = 0;
        while(i < n && j < m){
            if(s[i] == t[j])  res ++, j ++;
            i ++;
        }
        
        return t.size() - res;
    }
};

第三题https://leetcode.cn/problems/remove-nodes-from-linked-list/ 对于链表的操作不太熟悉了，导致耗时多

思路很简单，在链表上直接操作比较繁琐，用数组来处理数据，从后往前遍历，删除非递增的数即可。最后创建新链表，将数组的数放入得到答案

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        ListNode* q = head;
        vector<int> res;
        
        while(q != nullptr){
            res.push_back(q -> val);
            q = q -> next;
        }
        
        int zhon = res[res.size() - 1];
        vector<int> ans;
        ans.push_back(zhon);
        
        for(int i = res.size() - 2; i >= 0; i --){
            if(res[i] >= zhon){
                zhon = res[i];
                ans.push_back(res[i]);
            }
            
        }
        
        reverse(ans.begin(), ans.end());
        
        ListNode* h = new ListNode;
        h -> val = ans[0];
        h -> next = nullptr;
        ListNode* p = h;
        
        for(int i = 1; i < ans.size(); i ++){
            ListNode* zhon = new ListNode;
            zhon -> val = ans[i];
            
            p -> next = zhon;
            p = zhon;
            zhon -> next = nullptr;
        }
        
        return h;
    }
};

leetcode 双 ：

第一题https://leetcode.cn/problems/minimum-cuts-to-divide-a-circle/找规律即可

class Solution {
public:
    int numberOfCuts(int n) {
        if(n == 1)  return 0;
        if(n & 1)  return n;
        else  return n / 2;
    }
};

第二题https://leetcode.cn/problems/difference-between-ones-and-zeros-in-row-and-column/description/模拟，数组存行列 1 的个数

class Solution {
public:
    vectorint>> onesMinusZeros(vectorint>>& grid) {
        int n = grid.size(), m = grid[0].size();
 
        vector<int> row(n), col(m);
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < m; j ++){
                row[i] += grid[i][j];
                col[j] += grid[i][j];
            }
        }
 
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < m; j ++){
                grid[i][j] = row[i] + col[j] - (n - row[i]) - (m - col[j]);
            }
        }
 
        return grid;
    }
};

第三题https://leetcode.cn/problems/minimum-penalty-for-a-shop/description/前缀和，枚举任意一个时间点的代价作比较

顾客在 i 关门，那么代价即为 (i 之前的 N) + (i 之后的 Y 的数量)

为了方便计算前（后）缀和，我们认为 customers 的下标是从 1 开始的，最后答案减 1 即可。

class Solution {
public:
    int bestClosingTime(string customers) {
        int n = customers.size();
 
        int f[n + 2], g[n + 2];
        f[0] = 0;
        for(int i = 1; i <= n; i ++){
            f[i] = f[i - 1] + (customers[i - 1] == 'N' ? 1 : 0);
        }
 
        g[n + 1] = 0;
        for(int i = n; i > 0; i --){
            g[i] = g[i + 1] + (customers[i - 1] == 'Y' ? 1 : 0);
        }
 
        int ans = 0, w = INT_MAX;
        for(int i = 1; i <= n + 1; i ++){
            int t = f[i - 1] + g[i];
            if(t < w){
                ans = i;
                w = t;
            }
        }
 
        return ans - 1;
    }
};