C++OJ题经验总结（竞赛）4

注意：本篇标红字段均是可纳为己用的经验条。

OJ题知识归属：

   1、第一题：动态规划 -> 区间dp（基于区间上某⼀点，划分成左右区间讨论）（线形）

   2、第二题：顺序表 -> 双指针

   3、第三题：顺序表 -> 双指针

   4、第四题：链表 -> 双指针

   5、第五题：链表 -> 双指针

   6、第六题：链表 -> 双指针

OJ题来源：洛谷

OJ题名：248

OJ题归属：动态规划【区间dp】

        解题算法：动态规划

五板斧：

#include<iostream>

using namespace std;

const int N = 255;

int n;
int a[N];
int f[N][N];

int main()
{
cin >> n;
int ret = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];

f[i][i] = a[i];
ret = max(ret, a[i]);
}

for (int len = 2; len <= n; len++)
{
for (int i = 1; i + len – 1 <= n; i++)
{
int j = i + len – 1;

//枚举分割点
for (int k = i; k < j; k++)
{
if (f[i][k] == f[k + 1][j] && f[i][k] > 0)
f[i][j] = max(f[i][j], f[i][k] + 1);
}
ret = max(ret, f[i][j]);
}
}

//ret的操作：以所有数据没有一次合并作为大保底，有合并，就跟新一下
cout << ret << endl;

return 0;
}

OJ题来源：力扣

OJ题名：移除元素

OJ题归属：顺序表练习题

        解题算法：快慢双指针

class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int d1 = 0, d2 = 0;
while(d1 < nums.size())
{
if (nums[d1] != val)
{
nums[d2] = nums[d1];
d2++;
d1++;
}
else
{
d1++;//找不相等的值
}
}

return d2;
}
};

OJ题来源：力扣

OJ题名：删除有序数组中的重复项

OJ题归属：顺序表练习题

        解题算法：快慢双指针

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int d1 = 1, d2 = 0;
while(d1 < nums.size())
{
if (nums[d1] == nums[d2])
{
d1++;
}
else
{
d2++;
nums[d2] = nums[d1];
d1++;
}
}

return d2 + 1;
}
};

OJ题来源：力扣

OJ题名：链表的中间结点

OJ题归属：链表练习题

经验总结：固定步数大小，同步走。

        解题算法：快慢双指针

/**
* 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* middleNode(ListNode* head) {
ListNode* d1 = head, *d2 = head;
while(d1 != nullptr && d1->next != nullptr)
{
d1 = d1->next->next;
d2 = d2->next;
}

return d2;
}
};

OJ题来源：力扣

OJ题名：返回倒数第k个节点

OJ题归属：链表练习题

经验总结：先拉开距离差，同步数大小、同步走。

        解题算法：快慢双指针

/**
* 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:
int kthToLast(ListNode* head, int k) {
ListNode* d1 = head, * d2 = head;
while(k–)
{
d1 = d1->next;
}

while(d1 != nullptr)
{
d1 = d1->next;
d2 = d2->next;
}

return d2->val;
}
};

OJ题来源：力扣

OJ题名：移除链表元素

OJ题归属：链表练习题

经验总结：一个遍历、一个记录，遍历到下一个、记录当前的。

        解题算法：双指针

/**
* 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* removeElements(ListNode* head, int val) {
ListNode* cur = head, *prev = nullptr;
while(cur != nullptr)
{
if(cur->val != val)
{
prev = cur;
cur = cur->next;
}
else
{
if (prev == nullptr)
{
head = cur->next;
delete cur;
cur = head;
}
else
{
prev->next = cur->next;
delete cur;
cur = prev->next;
}
}
}

return head;
}
};