数据结构技巧记录

算法刚刚入门，打算将一些需要死记硬背的算法模板和一些灵活的算法思路记录下来，以后可以复习或者思路整理。

数据结构分类

这是按照算法中所使用的数据结构进行分类整理的题目

链表

图书整理

题目：

书店店员有一张链表形式的书单，每个节点代表一本书，节点中的值表示书的编号。为更方便整理书架，店员需要将书单倒过来排列，就可以从最后一本书开始整理，逐一将书放回到书架上。请倒序返回这个书单链表。

示例 1：

输入：head = [3,6,4,1]

输出：[1,4,6,3]

提示：

0 <= 链表长度 <= 10000

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> reverseBookList(ListNode* head) {
    stack<int> resultS;
    vector<int> result;
    ListNode* current = head;
    while (current != nullptr) {
        resultS.push(current->val);
        current = current->next;
    }
    while (!resultS.empty()) {
        result.push_back(resultS.top());
        resultS.pop();
    }
    return result;
}

就是通过栈来实现链表转数组反转，先拿出链表的数据，存储到栈中间，再把栈转成数组

删除链表节点

题目：

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

示例 1：

输入：head = [4,5,1,9], val = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2：

输入：head = [4,5,1,9], val = 1
输出：[4,5,9]
解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

这个也基本没什么难度，考的是链表的基础使用，就是需要单独注意头结点的问题

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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* deleteNode(ListNode* head, int val) {
        ListNode* nextHead;
        ListNode* curruntHead = head;		//保留出事节点位置
        while(1)
        {
            if(head->next==nullptr)
            	break;
            nextHead = head->next;
            if(head->val==val)
            {
                return head->next;			//对头结点单独讨论
            }
            if(nextHead->val==val)
            {
                head->next = nextHead->next;
            }
            else
            {
                head = head->next;			//常规移动当前节点
            }
        }
        return curruntHead;
    }
};

思路分类

这是根据思路技巧的不同进行分类

定长滑窗

原链接

https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/

思路

碰到这样的给定长度的窗口，然后窗口可以自由移动，让你求出不同窗口中的一些东西，比如这道题，就是在定长窗口中找到元音字母最多的数量，比较典型的定长滑窗的题目，通用的思路是三步：进入-更新-出来，窗口右端点在 i 时，由于窗口长度为 k，所以窗口左端点为 i−k+1。

  1. 进入：下标为 i 的元素进入循环后，更新统计量，就是数据处理，更新完后还需要判断窗口是否形成，如果左端点 i - k + 1 小于0，则continue跳过后面的循环

  2. 更新：然后更新答案，就是再次处理进入中的数据

  3. 出来：就是在窗口滑动，窗口的左边出来的时候，判断左边的情况，就是判断原左端点i-k+1的数据对整个的结果会不会有影响，这里再次更新统计量，数据处理

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxVowels(string s, int k) {
        int ans=0;
        int maxans=0;
        int length = s.length();
        for(int i=0;i<length;i++)
        {
            if(s[i]=='a'||s[i]=='e'||s[i]=='i'||s[i]=='o'||s[i]=='u')//进入
                ans++;
            if(i-k+1<0)
            {
                continue;
            }
            if(ans>maxans)//更新
                maxans = ans;
            if(s[i-k+1]=='a'||s[i-k+1]=='e'||s[i-k+1]=='i'||s[i-k+1]=='o'||s[i-k+1]=='u')//出来
                ans = ans-1;                 
        }
        return maxans;
    }
};

替换数组中的非互质数

原链接

https://leetcode.cn/problems/replace-non-coprime-numbers-in-array/description/?envType=daily-question&envId=2025-09-16

思路

这个说是困难题确实有点太水了，关键的内容就在于两点，第一个是GCD和LCM函数的编写，这个是可以直接记背源代码的。

第二个就是栈的使用，通过维护一个栈来实现高效快捷管理数据结构，首先先遍历整个数组中的数据，然后将栈顶的数字和当前的数字进行处理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    int GCD(int a,int b)
    {   
        if(b==0)
            return a;
        return GCD(b,a%b);
    }
    int LCM(int a,int b)
    {
        return (a/GCD(a,b))*b;
    }
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        stack<int> resultS;
        for(int i=0;i<nums.size();i++)
        {
            int current = nums[i];

            while(!resultS.empty())
            {            
                int top = resultS.top();
                int g = GCD(top,current);
                if(g>1)
                {
                    current = LCM(top,current);
                    resultS.pop();
                }
                else
                {
                    break;
                } 
            }
            resultS.push(current);

        }
        int j=0;
        int n = resultS.size();
        vector<int> result(n);
        while(1)
        {
            result[n-1-j] = resultS.top();
            j++;
            resultS.pop();
            if(resultS.empty()==1)
                break;
        }
        return result;
    }
};