wy的leetcode刷题记录_Day79

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间：2024-3-1

前言

@TOC

2369. 检查数组是否存在有效划分

今天的每日一题是：2369. 检查数组是否存在有效划分

题目介绍

给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个 连续 子数组。

如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分：

• 1.子数组 恰 由 2 个相等元素组成，例如，子数组 [2,2] 。
• 2.子数组 恰 由 3 个相等元素组成，例如，子数组 [4,4,4] 。
• 3.子数组 恰 由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。
  如果数组 至少 存在一种有效划分，返回 true ，否则，返回 false 。

示例 1：
输入：nums = [4,4,4,5,6]
输出：true
解释：数组可以划分成子数组 [4,4] 和 [4,5,6] 。这是一种有效划分，所以返回 true 。

示例 2：
输入：nums = [1,1,1,2]
输出：false
解释：该数组不存在有效划分。

思路

动态规划，令数组的长度为n，它至少存在一个有效的划分取决于它的子状态：

• 1.前(n-2)个元素存在有效的划分，并且后俩个元素相等
• 2.前(n-2)3个元素存在有效的划分，并且后三个元素相等或者后三个元素呈递增

于是我们使用一个数组dp[n+1]来记录前n个元素是否存在有效划分。初始化全为false，dp[0]为true。状态转移方程为

 bool euqal=(nums[i-1]==nums[i-2])&(nums[i-1]==nums[i-3]);//判断相等
 bool continuous=(nums[i-1]-nums[i-2]==1)&(nums[i-2]-nums[i-3]==1);//判断递增
 dp[i]=(dp[i-2]&(nums[i-2]==nums[i-1]))||(dp[i-3]&&(euqal||continuous));

代码

class Solution {
public:
    bool validPartition(vector<int>& nums) {
        int n=nums.size();
        vector<bool> dp(n+1,false);
        dp[0]=true;
        for(int i=1;i<=n;i++)
        {
            if(i>=2)
            {
                dp[i]=dp[i-2]&(nums[i-2]==nums[i-1]);
            }
            if(i>=3)
            {
                bool euqal=(nums[i-1]==nums[i-2])&(nums[i-1]==nums[i-3]);
                bool continuous=(nums[i-1]-nums[i-2]==1)&(nums[i-2]-nums[i-3]==1);
                dp[i]=dp[i]||(dp[i-3]&&(euqal||continuous));
            }
        }
        return dp[n];

    }
};

收获

稳固了动态规划的知识。

61. 旋转链表

61. 旋转链表

题目介绍

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

思路

本题其实跟博主以前做过的题有点类似，就是数组循环右移，不过换成了链表，同样也是老套路。首先我们先得到链表长度为n，然后根据k%n得到实际上所需的右移次数k（节省了多余重复的移动），然后从头遍历链表n-k-1次得到新链表的尾节点，而其下一个节点就是新链表的头节点。此时我们将原链表的尾指针指向原链表的头节点，再将新链表的头节点记录下来最后置新链表的尾节点为空即可。

代码

/**
 * 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* rotateRight(ListNode* head, int k) {
        int count=0;
        ListNode* temp=head;
        ListNode* tail=nullptr;
        ListNode* newHead=nullptr;
        while(temp)
        {
            if(temp->next==nullptr)
                tail=temp;
            count++;
            temp=temp->next;

        }
        if(count==0)
            return head;
        k=k%count;
        if(k==0)
            return head;
        k=count-k-1;
        temp=head;
        for(int i=0;i<k;i++)
        {
            temp=temp->next;
        }
        newHead=temp->next;
        temp->next=nullptr;
        tail->next=head;

        return newHead;
    }
};

收获

无

82. 删除排序链表中的重复元素 II

82. 删除排序链表中的重复元素 II

题目介绍

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

思路

本题其实最关键的就是使用一个哑节点类似书上没有用处的头节点一样，这里称呼它为哑节点。一般用这种情况是因为第一个节点可能会被删掉。首先建立一个指向第一个节点的哑节点newHead，然后使用一个指针cur从newHead来遍历整个链表，在遍历的过程中要判断相邻的俩个节点是否相同（只需判断每一组相同数的子链表前俩个），若相同的话则记录此时节点的值，然后将链表中与这个值相同的节点全部删掉，直到出现相邻的节点值不同；若不同的话则可以将cur置于该节点上使用cur->next判断下一组子串。

代码

/**
 * 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* deleteDuplicates(ListNode* head) {
        if(!head)
        {
            return head;
        }
        ListNode* newHead=new ListNode(0,head);
        ListNode* cur=newHead;

        while(cur->next&&cur->next->next)
        {
            if(cur->next->val==cur->next->next->val)
            {
                int x=cur->next->val;
                while(cur->next&&cur->next->val==x)
                {
                    cur->next=cur->next->next;
                }
            }
            else
            {
                cur=cur->next;
    
            }
        }
        return newHead->next;
    }
};

收获

哑节点的使用很巧妙，极大程度上的能符合我的逻辑思维且减少我的代码复杂程度。

86. 分隔链表

86. 分隔链表

题目介绍

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

思路

这题也巧借哑节点的思路，因为头节点不确定是否仍能保持其头节点的地位（如果他大于x那么他就不再是头节点）。这道题我们使用俩个哑节点分别存储按链表顺序分别大于x和小于x的节点，最后再将这两个链表合并即得到所需链表。

代码

/**
 * 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* partition(ListNode* head, int x) {
        ListNode* small=new ListNode(0);
        ListNode* large=new ListNode(0);
        ListNode* smallHead=small;
        ListNode* largeHead=large;
        while(head)
        {
            if(head->val<x)
            {
                small->next=head;
                small=small->next;
            }
            else
            {
                large->next=head;
                large=large->next;
            }
            head=head->next;

        }
        small->next=largeHead->next;
        large->next=nullptr;
        return smallHead->next;

    }
};

收获

巩固了哑节点的使用，对于链表类的题，其中对于首节点的处理往往都用到了哑节点的方法。