力扣第321场周赛+acwing第79场周赛补题

T1：找出中枢整数
题目很简单，可以用到前缀和的思想 假设pre[]为前缀和数组，那么中枢整数x满足的条件应该是：pre[n] - pre[x] + x == pre[x];
得到这个关系，代码就很容易写了。

class Solution {
public:
    int pivotInteger(int n) {
        int pre[n+1];
        pre[1] = 1;
        int res = -1;
        for(int i = 2 ;i <= n ; i++){
            pre[i] = pre[i - 1] + i;
        }
        for(int i = 1;i <= n ;i++){
            if(pre[n] - pre[i] + i == pre[i])
                res = i;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

T2：追加字符以获得子序列
这个题目思路很简单，就是用双指针找出s和t的最长公共子序列的长度，然后用t的长度减去公共子序列的长度就是需要追加的长度。

class Solution {
public:
    int appendCharacters(string s, string t) {
        int l = 0 , r = 0;
        while(l < s.size() && r < t.size()){
            if(s[l] == t[r] ){
                r++;
            }
            l++;
        }
        return t.size() - r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

acwing :
T1:数列元素

直接累加判断就好了

#include
#include
using namespace std;
int n;


int main(){
    cin >> n;
    int sum = 0;
    for(int i = 1 ; i <= n ; i++){
        sum += i;
        if(sum == n){
            cout <<"YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

T2：队列
这个题目最开始的思路可能就是暴力解法。进行进队和出队操作。但是题目给的n的范围是10^9。暴力求解的话会超时。
我们假设所有元素不出队列，我们来看看元素入队后的情况：
abcde abcdea abcdeaa abcdeaab abcdeaabb
abcdeaabbcc abcdeaabbccdd abcdeaabbccddee
依次推导下去可以发现，下一次的结果是
abcdeaabbccddeeaaaabbbbccccddddeeee
我们把每一次abcde循环结束当成一段，则后面的一段的长度就是在前一段的基础上乘以2.
所以我们判断第n个被弹出的元素，就需要确定第n个元素在哪一段中，然后再判断n是这一段中的第几个数，由此判定对应位置的元素是多少。

#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 a = (n + len - 1) / len;//向上取整
    cout << char(a - 1 +'a') << endl;
    return 0;
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20