跳转至

weekly-contest-321

A

Statement

Metadata

给你一个正整数 n ,找出满足下述条件的 中枢整数 x

  • 1x 之间的所有元素之和等于 xn 之间所有元素之和。

返回中枢整数 x 。如果不存在中枢整数,则返回 -1 。题目保证对于给定的输入,至多存在一个中枢整数。

 

示例 1:

输入:n = 8
输出:6
解释:6 是中枢整数,因为 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21 。

示例 2:

输入:n = 1
输出:1
解释:1 是中枢整数,因为 1 = 1 。

示例 3:

输入:n = 4
输出:-1
解释:可以证明不存在满足题目要求的整数。

 

提示:

  • 1 <= n <= 1000

Metadata

Given a positive integer n, find the pivot integer x such that:

  • The sum of all elements between 1 and x inclusively equals the sum of all elements between x and n inclusively.

Return the pivot integer x. If no such integer exists, return -1. It is guaranteed that there will be at most one pivot index for the given input.

 

Example 1:

Input: n = 8
Output: 6
Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.

Example 2:

Input: n = 1
Output: 1
Explanation: 1 is the pivot integer since: 1 = 1.

Example 3:

Input: n = 4
Output: -1
Explanation: It can be proved that no such integer exist.

 

Constraints:

  • 1 <= n <= 1000

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
    int pivotInteger(int n) {
        int res = -1;
        int sum = 0;
        int remind = ((n * (n + 1))) / 2;
        for (int i = 1; i <= n; i++) {
            sum += i;
            if (sum == remind) {
                res = i;
            }
            remind -= i;
        }

        return res;
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

B

Statement

Metadata

给你两个仅由小写英文字母组成的字符串 st

现在需要通过向 s 末尾追加字符的方式使 t 变成 s 的一个 子序列 ,返回需要追加的最少字符数。

子序列是一个可以由其他字符串删除部分(或不删除)字符但不改变剩下字符顺序得到的字符串。

 

示例 1:

输入:s = "coaching", t = "coding"
输出:4
解释:向 s 末尾追加字符串 "ding" ,s = "coachingding" 。
现在,t 是 s ("coachingding") 的一个子序列。
可以证明向 s 末尾追加任何 3 个字符都无法使 t 成为 s 的一个子序列。

示例 2:

输入:s = "abcde", t = "a"
输出:0
解释:t 已经是 s ("abcde") 的一个子序列。

示例 3:

输入:s = "z", t = "abcde"
输出:5
解释:向 s 末尾追加字符串 "abcde" ,s = "zabcde" 。
现在,t 是 s ("zabcde") 的一个子序列。 
可以证明向 s 末尾追加任何 4 个字符都无法使 t 成为 s 的一个子序列。

 

提示:

  • 1 <= s.length, t.length <= 105
  • st 仅由小写英文字母组成

Metadata

You are given two strings s and t consisting of only lowercase English letters.

Return the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

 

Example 1:

Input: s = "coaching", t = "coding"
Output: 4
Explanation: Append the characters "ding" to the end of s so that s = "coachingding".
Now, t is a subsequence of s ("coachingding").
It can be shown that appending any 3 characters to the end of s will never make t a subsequence.

Example 2:

Input: s = "abcde", t = "a"
Output: 0
Explanation: t is already a subsequence of s ("abcde").

Example 3:

Input: s = "z", t = "abcde"
Output: 5
Explanation: Append the characters "abcde" to the end of s so that s = "zabcde".
Now, t is a subsequence of s ("zabcde").
It can be shown that appending any 4 characters to the end of s will never make t a subsequence.

 

Constraints:

  • 1 <= s.length, t.length <= 105
  • s and t consist only of lowercase English letters.

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

const int ALP = 26;
const int N = 1e5 + 10;

struct SQAM {
    struct node {
        int nx[ALP];
        void init() {
            memset(nx, 0, sizeof nx);
        }
    } t[N];
    int lst[ALP], pre[N], tot;

    void init() {
        tot = 1;
        t[1].init();
        for (int i = 0; i < ALP; ++i) lst[i] = 1;
    }

    void extend(int c) {
        int cur = ++tot;
        t[cur].init();
        pre[cur] = lst[c];
        for (int i = tot - 1; i >= pre[cur]; --i) t[i].nx[c] = cur;
        lst[c] = cur;
    }
} sqam;

class Solution {
public:
    int appendCharacters(string s, string t) {
        sqam.init();
        for (const char &c : s) {
            sqam.extend(c - 'a');
        }

        int cur = 1;
        int n = int(t.size());

        for (int i = 0; i < n; i++) {
            int c = t[i] - 'a';
            if (sqam.t[cur].nx[c]) {
                cur = sqam.t[cur].nx[c];
            } else {
                return n - i;
            }
        }

        return 0;
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

C

Statement

Metadata

给你一个链表的头节点 head

对于列表中的每个节点 node ,如果其右侧存在一个具有 严格更大 值的节点,则移除 node

返回修改后链表的头节点 head

 

示例 1:

输入:head = [5,2,13,3,8]
输出:[13,8]
解释:需要移除的节点是 5 ,2 和 3 。
- 节点 13 在节点 5 右侧。
- 节点 13 在节点 2 右侧。
- 节点 8 在节点 3 右侧。

示例 2:

输入:head = [1,1,1,1]
输出:[1,1,1,1]
解释:每个节点的值都是 1 ,所以没有需要移除的节点。

 

提示:

  • 给定列表中的节点数目在范围 [1, 105]
  • 1 <= Node.val <= 105

Metadata

You are given the head of a linked list.

Remove every node which has a node with a strictly greater value anywhere to the right side of it.

Return the head of the modified linked list.

 

Example 1:

Input: head = [5,2,13,3,8]
Output: [13,8]
Explanation: The nodes that should be removed are 5, 2 and 3.
- Node 13 is to the right of node 5.
- Node 13 is to the right of node 2.
- Node 8 is to the right of node 3.

Example 2:

Input: head = [1,1,1,1]
Output: [1,1,1,1]
Explanation: Every node has value 1, so no nodes are removed.

 

Constraints:

  • The number of the nodes in the given list is in the range [1, 105].
  • 1 <= Node.val <= 105

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

/**
 * 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) {}
 * };
 */

#ifdef LOCAL

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) {}
};

#endif

class Solution {
public:
    ListNode *removeNodes(ListNode *head) {
        vector<ListNode *> st;

        while (head) {
            auto *cur = head;
            while (!st.empty() && st.back()->val < cur->val) {
                st.pop_back();
            }
            st.push_back(cur);

            head = cur->next;
        }

        int n = int(st.size());
        for (int i = 0; i < n - 1; i++) {
            st[i]->next = st[i + 1];
        }

        return st[0];
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

D

Statement

Metadata

给你一个长度为 n 的数组 nums ,该数组由从 1n不同 整数组成。另给你一个正整数 k

统计并返回 num 中的 中位数 等于 k 的非空子数组的数目。

注意:

  • 数组的中位数是按 递增 顺序排列后位于 中间 的那个元素,如果数组长度为偶数,则中位数是位于中间靠 的那个元素。
    • 例如,[2,3,1,4] 的中位数是 2[8,4,3,5,1] 的中位数是 4
  • 子数组是数组中的一个连续部分。

 

示例 1:

输入:nums = [3,2,1,4,5], k = 4
输出:3
解释:中位数等于 4 的子数组有:[4]、[4,5] 和 [1,4,5] 。

示例 2:

输入:nums = [2,3,1], k = 3
输出:1
解释:[3] 是唯一一个中位数等于 3 的子数组。

 

提示:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i], k <= n
  • nums 中的整数互不相同

Metadata

You are given an array nums of size n consisting of distinct integers from 1 to n and a positive integer k.

Return the number of non-empty subarrays in nums that have a median equal to k.

Note:

  • The median of an array is the middle element after sorting the array in ascending order. If the array is of even length, the median is the left middle element.
    • For example, the median of [2,3,1,4] is 2, and the median of [8,4,3,5,1] is 4.
  • A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [3,2,1,4,5], k = 4
Output: 3
Explanation: The subarrays that have a median equal to 4 are: [4], [4,5] and [1,4,5].

Example 2:

Input: nums = [2,3,1], k = 3
Output: 1
Explanation: [3] is the only subarray that has a median equal to 3.

 

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i], k <= n
  • The integers in nums are distinct.

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
    int countSubarrays(vector<int> &nums, int k) {
        int n = int(nums.size());
        int target = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] < k) {
                nums[i] = -1;
            } else if (nums[i] > k) {
                nums[i] = 1;
            } else {
                target = i;
            }
        }

        auto mp = map<int, int>();
        int cur = 0;
        ++mp[cur];
        for (int i = target + 1; i < n; i++) {
            cur += nums[i];
            ++mp[cur];
        }

        int res = 0;
        cur = 0;
        for (int i = target; i >= 0; i--) {
            if (i < target) {
                cur += nums[i];
            }

            res += mp[-cur];
            res += mp[-cur + 1];
        }

        return res;
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

最后更新: October 11, 2023
回到页面顶部