1. LeetCode单周赛321场

1.1 找出中枢整数

1.1.1 原题链接：力扣https://leetcode.cn/problems/find-the-pivot-integer/

1.1.2 解题思路：

        1、先保存 1-n 的和sum；

        2、从 1 开始枚举，判断前 i 项和 cmp 与 sum - cmp + i 是否相等即可。

1.1.3 代码：

class Solution {
public:int pivotInteger(int n) {int sum = 0;for(int i = 1; i <= n; i ++ ) sum += i;int cmp = 0;for(int i = 1; i <= n ;i ++ ) {cmp += i;if(cmp == (sum - cmp + i)) return i;}return -1;}
};

1.2 追加字符以获得子序列

1.2.1 原题链接：力扣https://leetcode.cn/problems/append-characters-to-string-to-make-subsequence/

1.2.2 解题思路：

        用双指针来判断是否存在一个 s 中的子序列等于 t，若不存在则当前枚举到 t 中剩下的字母都是需要追加到字母。

1.2.3 代码：

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

1.3 从链表中移除节点

1.3.1 原题链接：力扣https://leetcode.cn/problems/remove-nodes-from-linked-list/

1.3.2 解题思路：

        具体思路见代码。

1.3.3 代码：

/*** 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) {if(head == nullptr) return head;//如果head为空直接return就好了ListNode* res = removeNodes(head->next);//递归处理返回的链表头一定是最大值if(res == nullptr) return head;if(res->val > head->val) return res; //删除头节点head->next = res;   //不删除头节点 return head;}
};

1.4 统计中位数为K的子数组

1.4.1 原题链接：力扣https://leetcode.cn/problems/count-subarrays-with-median-k/

1.4.2 解题思路：

        1、转换为数学式子；

        2、在奇数长度下的情况：

                （1）统计K左侧的数的个数sum1，K右侧的数的个数sum2，必然有sum1 == sum2；

                （2）由（1）知：左侧小于K的数的个数 + 右侧小于K的数的个数 == 左侧大于K的数的  个数 + 右侧大于K的数的个数；

                （3）由（2）知：左侧小于K的数的个数 - 左侧大于K的数的个数 ==  右侧大于K的数的个数 - 右侧小于K的数的个数；将 “ - ”看作是 -1， “+”看作是 +1，例如：

         3、找左右匹配的数对，如上图；

        4、对于偶数个的情况：左侧小于K的数的个数 - 左侧大于K的数的个数  + 1 ==  右侧大于K的数的个数 - 右侧小于K的数的个数。

1.4.3 代码：

class Solution {
public:int countSubarrays(vector& nums, int k) {//存k的下标int pos = find(nums.begin(), nums.end(), k) - nums.begin(), n = nums.size();unordered_map cnt;cnt[0] = 1;for(int i =pos + 1, c = 0; i < n; i ++ ) {c += nums[i] > k ? 1 : -1;++ cnt[c];}int ans = cnt[0] + cnt[1];for(int i = pos - 1, c = 0; i >= 0; i --) {c += nums[i] < k ? 1 : -1;ans += cnt[c] + cnt[c + 1];}return ans;}
};

2.AcWing周赛79场

2.1 数列元素

2.1.1 原题链接：4722. 数列元素 - AcWing题库

2.1.2 解题思路：

        预处理前缀和，再从前往后遍历找到相等情况并输出YES，找不到则输出NO。

2.1.3 代码：

#include 
#include 
#include using namespace std;const int N = 510;int s[N];int main()
{int n;cin >> n;for(int i = 1; i <= N; i ++ ) s[i] = s[i - 1] + i;bool flag = false;for(int i = 1; i <= N; i ++ ) {if(s[i] == n) flag = true;}if(flag) puts("YES");else puts("NO");return 0;
}

2.2 队列

2.2.1 原题链接：4723. 队列 - AcWing题库

2.2.2 解题思路：

        1、先判断 n 属于哪个区间；

        2、再判断 n 属于第几个元素。

2.2.3 代码：

#include 
#include 
#include using namespace std;int main()
{int n;cin >> n;int s = 0, k = 5;while(s + k < n) {s += k;k *= 2;}n -= s;int len = k / 5;int t = (n + len - 1) / len;cout << (char) (t - 1 + 'a') << endl;return 0;
}