• 佳期投资专场——第321场LeetCode周赛题解


    目录

    前缀数组:6245. 找出中枢整数

    双指针:6246. 追加字符以获得子序列

    数组模拟:6247. 从链表中移除节点

    中心扩散:6248. 统计中位数为 K 的子数组


    前缀数组:6245. 找出中枢整数

    这题不清楚暴力是否能过,要是每一次都计算一遍和肯定很浪费计算资源。

    我们可以把前缀和计算一遍,再把后缀和计算一遍,这个复杂度是O(N+N)

    然后再把遍历一遍,返回前缀数组和后缀数组相等的即可。

    1. class Solution {
    2. public:
    3. int pivotInteger(int n) {
    4. int ans = -1;
    5. int sum = 0;
    6. int presum[n+1];
    7. for (int i = 1; i <= n; i++) {
    8. sum += i;
    9. presum[i] = sum;
    10. }
    11. int temp = 0;
    12. int backsum[n+1];
    13. sum = 0;
    14. for (int i = n; i>=1; i--) {
    15. sum += i;
    16. backsum[i] = sum;
    17. }
    18. for (int i = 1; i <= n; i++) {
    19. if (presum[i] == backsum[i]) {
    20. return i;
    21. }
    22. }
    23. return ans;
    24. }
    25. };

    双指针:6246. 追加字符以获得子序列

    这题乍一看是KMP,但是KMP是要把模板数组全部匹配,这题不用这么麻烦。直接双指针遍历,让指向字符串s的指针走的快,指向字符串t的指针走得慢,tp就是两个字符串相互重复的最大部分。

    1. class Solution {
    2. public:
    3. int appendCharacters(string s, string t) {
    4. int ts = 0;
    5. int tp = 0;
    6. while (ts <= s.size() && tp <= s.size()) {
    7. if (s[ts] == t[tp]) {
    8. ts ++;
    9. tp ++;
    10. } else {
    11. ts ++;
    12. }
    13. }
    14. if (t.size() - tp == -1) {
    15. return 0;
    16. }
    17. return t.size() - tp;
    18. }
    19. };

    数组模拟:6247. 从链表中移除节点

    这题的关键在于我们需要从右向左看,但是单向链表逆序遍历又比较麻烦,所以我们先遍历一遍链表,将所有链表的值保存下来。

    然后从右往左遍历数组,只保留下右侧没有比其更大的节点。

    最后再新建一个链表,当然你也可以在原来的链表上删除,因为第二步得出了需要保存节点的val。

    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. * int val;
    5. * ListNode *next;
    6. * ListNode() : val(0), next(nullptr) {}
    7. * ListNode(int x) : val(x), next(nullptr) {}
    8. * ListNode(int x, ListNode *next) : val(x), next(next) {}
    9. * };
    10. */
    11. class Solution {
    12. public:
    13. ListNode* removeNodes(ListNode* head) {
    14. if (head->next == nullptr) {
    15. return head;
    16. }
    17. vector<int> v;
    18. while (head) {
    19. v.push_back(head->val);
    20. head = head->next;
    21. }
    22. int backmax[v.size()];
    23. int maxnum = v[v.size() - 1];
    24. backmax[v.size() - 1] = maxnum;
    25. for (int i = v.size() - 2; i >= 0; i--) {
    26. if (v[i] < maxnum) {
    27. backmax[i] = maxnum;
    28. } else {
    29. backmax[i] = v[i];
    30. maxnum = v[i];
    31. }
    32. }
    33. vector<int> last;
    34. for (int i = 0; i < v.size(); i++) {
    35. if (v[i] >= backmax[i]) {
    36. last.push_back(v[i]);
    37. }
    38. }
    39. ListNode* dummy = new ListNode(-1);
    40. ListNode* cur = dummy;
    41. for (int i = 0; i < last.size(); i++) {
    42. ListNode* temp = new ListNode(last[i]);
    43. cur->next = temp;
    44. cur = cur->next;
    45. }
    46. return dummy->next;
    47. }
    48. };

    中心扩散:6248. 统计中位数为 K 的子数组

    这题我没来得及写完,我当时的思路很简单:回溯得到所有子数组,然后遍历一遍得到符合条件的数量。

    但是连续子数组用回溯不好写,如果用暴力双循环的话,复杂度O(N*N),这样也过不了。

    后来看到到来用中心扩散过了,笑死:力扣

    1. class Solution {
    2. public:
    3. int countSubarrays(vector<int>& nums, int k) {
    4. int n=nums.size(),idx=-1;
    5. for(int i=0;i<n;i++)
    6. {
    7. if(nums[i]==k)idx=i;
    8. }
    9. if(idx==-1)return 0;
    10. int cnt=0,sum=0;
    11. unordered_map<int,int>left;
    12. left[0]=1;
    13. for(int i=idx-1;i>=0;i--)
    14. {
    15. if(nums[i]<k)sum--;
    16. else sum++;
    17. left[sum]++;
    18. }
    19. cnt+=left[0];
    20. cnt+=left[1];
    21. sum=0;
    22. for(int i=idx+1;i<n;i++)
    23. {
    24. if(nums[i]<k)sum--;
    25. else sum++;
    26. cnt+=left[-1*sum];
    27. cnt+=left[1-sum];
    28. }
    29. return cnt;
    30. }
    31. };

    再加油吧!

  • 相关阅读:
    2.【自动驾驶与机器人中的SLAM技术】左乘模型推导ESKF
    jQuery侧边栏手风琴菜单效果(1+X Web前端开发初级 例题)
    Selenium环境+元素定位大法
    Hive数据操纵语言-DML(Load、insert、事务表)
    2023年中国雷达设备市场规模及市场份额分析[图]
    SpringBoot中Bean的创建过程及扩展操作点 @by_TWJ
    label-preserving transformations
    golang的管道阻塞问题
    手动上传本地jar、aar到maven私有仓库nexus
    Python数据攻略-Pandas常用数据操作与数据清洗
  • 原文地址:https://blog.csdn.net/qq_41895747/article/details/128064154