数据结构技巧记录

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

数据结构分类

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

链表

图书整理

题目：

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

示例 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;
    }
};

反转链表

题目：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

img

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

示例 2：

img

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

示例 3：

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

非常简单，链表的基础使用加栈就可以解决，但需要注意的是，使用过程中，都要使用临时指针，而不是用head这个指针

代码：
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
/**
 * 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* reverseList(ListNode* head) {
        stack<int> resultS;
        ListNode* current = head;
        while(current!=nullptr)
        {   
            resultS.push(current->val);
            current = current->next;
        }
        current = head;
        while(!resultS.empty())
        {
            current->val=resultS.top();
            resultS.pop();
            current = current->next;
        }
        return head;
    }
};

还有一个方法就是只需要遍历一次，原理就是遍历链表节点，暂存每个节点的前节点，将每个节点的next指向前节点。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode* trainningPlan(ListNode* head) {
        ListNode *cur = head, *pre = nullptr;
        while(cur != nullptr) {
            ListNode* tmp = cur->next; // 暂存后继节点 cur.next
            cur->next = pre;           // 修改 next 引用指向
            pre = cur;                 // pre 暂存 cur
            cur = tmp;                 // cur 访问下一节点
        }
        return pre;
    }
};

返回链表倒数的节点

题目：

给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。

示例 1：

1
2
输入：head = [2,4,7,8], cnt = 1
输出：8

这个有两种解法，第一个比较简单，就是遍历完节点后，用数组存储节点，再访问数组中的内容即可，第二个解法就是用到了技巧了，用的双指针，前后指针相差cnt个节点，当后指针达到nullptr后，前指针的位置就是所求的位置

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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* trainingPlan(ListNode* head, int cnt) {
        ListNode* cur = head;
        vector<ListNode*> list;
        while(cur!=nullptr)
        {
            list.push_back(cur);
            cur = cur->next;
        }
        return list[list.size()-cnt];
    }
};

这个是第一个比较简单的版本，缺点就是消耗的空间比较大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    ListNode* trainingPlan(ListNode* head, int cnt) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(cnt)
        {
            cnt--;
            fast = fast->next;
        }
        while(fast!=nullptr)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

这个就是双指针版本，难度也不大。

合并两个有序链表

题目：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

img

1
2
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

1
2
输入：l1 = [], l2 = []
输出：[]

示例 3：

1
2
输入：l1 = [], l2 = [0]
输出：[0]

这个也比较基础，提供两种思路，第一个是修改原list1，就是在list1里面添加list2的数据，有点难理解，还有第二个思路容易理解一下，原理其实差不多，就是吧list2插入list1改成了同时调整。

代码：
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
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1)return list2;
        if(!list2)return list1;
        if(list1->val>list2->val)
            swap(list1,list2);
        ListNode* cur = list1;
        while(cur->next && list2)
        {
            if(cur->next->val>=list2->val)
            {
                ListNode* tmp = list2->next;
                list2->next = cur->next;
                cur->next = list2;
                list2 = tmp;
            }
            cur = cur->next;
        }
        if(list2)
        {
            cur->next = list2;
        }
        return list1;
    }
};

这个是第一个修改list1的版本，可能中间的变换部分有点难看懂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
        ListNode* dum = new ListNode(0);
        ListNode* cur = dum;
        while(l1 != nullptr && l2 != nullptr) {
            if(l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            }
            else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 != nullptr ? l1 : l2;
        return dum->next;
    }
};

这个比较直观一些，先创建一个空的头结点，然后慢慢遍历l1和l2，可以学习这里的创建空的头节点的思想。

相交链表

题目：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

img

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

这个就需要一点技巧了，本质就是A，B一起推进，推进到某个节点某个链表结束后，就是转接到另一个链表的表头继续推进，最终这两个推进都会汇集到一个节点上，就是最终的结果。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* p = headA;
        ListNode* q = headB;
        while (p != q) {
            p = p ? p->next : headB;
            q = q ? q->next : headA;
        }
        return p;
    }
};

随机链表的复制

题目：

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random –> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random –> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

就是一个带有random指针的链表深拷贝。

这个有两种方法，一种是用哈希表来存储新旧节点，旧节点是key，新节点是value，然后再遍历旧节点，把旧节点的数据统一复制到新节点中，还可以通过复制链表然后再通过奇偶链表的做法来实现。

这里就只放了第一种哈希表的方法，比较容易理解，缺点就是占用的内存比较多。

代码：
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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*,Node*> list;
        for(Node* cur = head;cur!=NULL;cur = cur->next)
        {
            list[cur] = new Node(cur->val);
        }
        for(Node* cur = head;cur!=NULL;cur = cur->next)
        {
            list[cur]->next = cur->next?list[cur->next]:NULL;
            list[cur]->random = cur->random?list[cur->random]:NULL;
        }
        return list[head];
    }
};

数组

奇偶数列排序

题目：

教练使用整数数组 actions 记录一系列核心肌群训练项目编号。为增强训练趣味性，需要将所有奇数编号训练项目调整至偶数编号训练项目之前。请将调整后的训练项目编号以 数组 形式返回。

示例 1：

输入：actions = [1,2,3,4,5]
输出：[1,3,5,2,4]
解释：为正确答案之一

这个有两种方法，一种非常简单，就是遍历数组，选出奇数和偶数然后分别存到数组里面，然后再数组拼接即可，思路没问题，就是太占内存了。

第二种方法就比较取巧了，用的双指针，具体操作就是从数组前后遍历，然后找奇数和偶数，前面的指针找偶数，后面的指针找奇数，然后找到后互相对调即可，这里需要注意的是先判断交换，再递增，如果先递增后判断，又可能出现i>j的情况

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> trainingPlan(vector<int>& actions) {
        int i = 0;
        int j = actions.size()-1;
        while(i<j)
        {
            if(actions[i]%2==0 && actions[j]%2==1)
            {
                int tmp = actions[i];
                actions[i] = actions[j];
                actions[j] = tmp;
                i++;
                j--;
            }
            if(actions[i]%2==1)
                i++;
            if(actions[j]%2==0)
                j--;
        }
        return actions;
    }
};

文件组合

题目：

待传输文件被切分成多个部分，按照原排列顺序，每部分文件编号均为一个 正整数（至少含有两个文件）。传输要求为：连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组合列表。

注意，返回时需遵循以下规则：

每种组合按照文件编号 升序 排列；
不同组合按照第一个文件编号 升序 排列。

示例 1：

输入：target = 12
输出：[[3, 4, 5]]
解释：在上述示例中，存在一个连续正整数序列的和为 12，为 [3, 4, 5]。
示例 2：

输入：target = 18
输出：[[3,4,5,6],[5,6,7]]
解释：在上述示例中，存在两个连续正整数序列的和分别为 18，分别为 [3, 4, 5, 6] 和 [5, 6, 7]。

这个有两种方法，一种就是数学法，通过分析数学规律，找到对应的表达式，就是固定 target 和一个边的数字，可以求出另一边的数字，遍历求解即可，这里注意的是一个小技巧，就是判断整数的技巧，通过 a==(int)a 这个表达式来判断是否为整数

第二种方法就比较取巧了，用的双指针加滑窗的思想，就是两个索引的方式来完成，每次将前后两个索引的内容相加，结果和 target 进行比较，如果大的话，就移动前面的指针，如果小的话就移动后面的指针，相等就是找到了一种情况。

代码：
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
class Solution {
public:
    vector<vector<int>> fileCombination(int target) {
        int i = 1;
        int j = 2;
        vector<vector<int>> result;
        while(1)
        {
            int sum = (i+j)*(j-i+1)/2;
            if(j==target&&sum>target)
                break;
            if(sum<target)
            		j++;
            else if(sum>target)
                i++;
            else
            {
                vector<int> ans;
                int tmp = i;
                while(1)
                {
                    ans.push_back(i);
                    if(i==j)
                        break;
                    i++;
                }
                result.push_back(ans);
                i = tmp;
                j++;
            }
        }
        return result;
    }
};

按规则计算统计结果

题目：

为了深入了解这些生物群体的生态特征，你们进行了大量的实地观察和数据采集。数组 arrayA 记录了各个生物群体数量数据，其中 arrayA[i] 表示第 i 个生物群体的数量。请返回一个数组 arrayB，该数组为基于数组 arrayA 中的数据计算得出的结果，其中 arrayB[i] 表示将第 i 个生物群体的数量从总体中排除后的其他数量的乘积。

示例 1：

输入：arrayA = [2, 4, 6, 8, 10]
输出：[1920, 960, 640, 480, 384]

这个有两种方法，一种就是直接写，就是用到了除法，缺点就是需要讨论的东西比较多，需要维护一个记录0的变量，并且还要照顾0的情况。

第二种方法就比较取巧了，用的前缀和后缀的乘法，就是遍历两遍数组，第一遍将每个元素乘以它之前的内容，叠加起来，第二遍则是乘以它之后的内容。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> statisticalResult(vector<int>& arrayA) {
        long long int tmp = 1;
        vector<int> result;
        result.resize(arrayA.size(),1);
        for(int i=1;i<arrayA.size();i++)
        {
            result[i] = result[i-1] * arrayA[i-1];
        }
        for(int i=arrayA.size()-2;i>=0;i--)
        {
            tmp *= arrayA[i+1];
            result[i] = result[i] * tmp;
        }
        return result;
    }
};

螺旋遍历二维数组

题目：

给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。

螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。

示例 1：

输入：array = [[1,2,3],[8,9,4],[7,6,5]]
输出：[1,2,3,4,5,6,7,8,9]
示例 2：

输入：array = [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
输出：[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

这里的思路主要是先用四个变量top，bottom，right，left，分别存储四个边的数据，然后按照上左下右的顺序循环输出数据，每次输出完都需要更新这四个变量的值，同时需要注意条件的判断，只要一边接触就需要退出循环

代码：
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
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> results = {};
        int right = matrix[0].size()-1;
        int top = 0;
        int bottom = matrix.size()-1;
        int left = 0;
        int a  = 0;
        while(1) {
            if (top > bottom || left > right) break;
            if(a==0) {
                for(int i=left;i<=right;i++) {
                    results.push_back(matrix[top][i]);
                }
                top++;
                a=1;
            }
            else if(a==1) {
                for(int j=top;j<=bottom;j++) {
                    results.push_back(matrix[j][right]);
                }
                right--;
                a=2;
            }
            else if(a==2) {
                for(int j=right;j>=left;j--) {
                    results.push_back(matrix[bottom][j]);
                }
                bottom--;
                a=3;
            }
            else if(a==3) {
                for(int j=bottom;j>=top;j--) {
                    results.push_back(matrix[j][left]);
                }
                left++;
                a=0;
            }
        }
        return results;
    }
};

思路分类

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

定长滑窗

原链接

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/

思路

这个说是困难题确实有点太水了，关键的内容就在于两点，第一个是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;
    }
};

设计任务管理器

原链接

https://leetcode.cn/problems/design-task-manager/

思路

这道题我一开始的方法是纯数组储存，没做任何的算法优化的暴力解法，纯用数组维护变量，并且查找最高的任务都是遍历两次数组查找，可以通过前600个测试，到了后面几个测试，就提示了超时了，于是看了题解，提供了新的思路。

题解的思路是：

  1. 使用了类型为unordered_map的mp来维护全部的数据，这个mp的主要作用就是利用哈希表，将taskId和另外两个东西挂上钩，做到快速查找taskId是否存在，和其对应的其他的数据
  2. 使用了类型为priority_queue的pq来维护更新的高优先级的数据，priority_queue<tuple<int,int,int>>这个会始终按照元组里面的内容，始终做到排序好，排序的优先级就是按照元组的数据，元组中按照排列靠前的数字大小进行排序
  3. 至于add函数，就是mp和pq加入新的数据，并且pq会自动按照它的优先级排序好，edit函数也就是利用了add函数，同时更新mp和pq，rmv函数就是将对应的taskId的优先级置为-1，实现懒删除
  4. 最后的是execTop函数，这个就是从pq里面找，直到找到一个数据和mp里的数据完全符合，这就证明了，这个数据是没有问题的，就可以删除并且返回出来了

主要涉及的内容就是堆的使用和懒删除。

代码

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
class TaskManager {
public:
    unordered_map<int,pair<int,int>> mp;
    priority_queue<tuple<int,int,int>> pq;
    TaskManager(vector<vector<int>>& tasks) {
        for(auto& task:tasks)
        {
            add(task[0],task[1],task[2]);
        }
    }
    
    void add(int userId, int taskId, int priority) {
        mp[taskId] = {priority,userId};
        pq.emplace(priority,taskId,userId);
    }
    
    void edit(int taskId, int newPriority) {
        add(mp[taskId].second,taskId,newPriority);
    }
    
    void rmv(int taskId) {
        mp[taskId].first = -1;
    }
    
    int execTop() {
        while(!pq.empty())
        {
            auto [priority,taskId,userId] = pq.top();
            pq.pop();
            if(mp[taskId] == pair(priority,userId))
            {
                rmv(taskId);
                return userId;
            }
        }
        return -1;
    }
};

设计电子表格

原链接

https://leetcode.cn/problems/design-spreadsheet/

思路

这道题比较简单，我的思路是采用哈希表，其中key是26个字母，value是数组vector，其中vector的位置就是行的位置。

我觉得需要注意的点是一定要在每个操控电子表格，都需要事先resize一下，这样子才可以访问对应行数的内容。

题解中还有个更优解，就是免去了字母和数字解析这种东西，就是比如将“A11”这样的直接作为键值进行储存，这样子更加方便和简洁一些。

主要涉及的内容就是哈希表的使用和字符串的切割。

代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Spreadsheet {
public:
    unordered_map<char,vector<int>> sheet;
    int Rows;
    Spreadsheet(int rows) {
        Rows = rows;
    }
    
    void setCell(string cell, int value) {
        sheet[cell[0]].resize(Rows);
        string cells = cell.substr(1,cell.size()-1);
        int num = stoi(cells);
        sheet[cell[0]][num-1] = value;
    }
    
    void resetCell(string cell) {
        string cells = cell.substr(1,cell.size()-1);
        int num = stoi(cells);
        sheet[cell[0]].resize(Rows,0);
        sheet[cell[0]][num-1] = 0;        
    }
    
    int getValue(string formula) {
        string x;
        int xResult=0;
        int yResult=0;
        string y;
        int size = formula.size();
        for(int i=0;i<size;i++)
        {
            if(formula[i]=='+')
            {
                y = formula.substr(i+1,size-1);
                x = formula.substr(1,i-1);  
            }
        }
        if(x[0]>='A' && x[0]<='Z')
        {
            string cells = x.substr(1,x.size()-1);
            int num = stoi(cells);
            sheet[x[0]].resize(Rows,0);
            xResult = sheet[x[0]][num-1];   
        }
        else
        {
            xResult = stoi(x);
        }
        if(y[0]>='A' && y[0]<='Z')
        {
            string cells = y.substr(1,y.size()-1);
            int num = stoi(cells);
            sheet[y[0]].resize(Rows,0);
            yResult = sheet[y[0]][num-1];   
        }
        else
        {
            yResult = stoi(y);
        }
        return xResult+yResult;
    }
};

/**
 * Your Spreadsheet object will be instantiated and called as such:
 * Spreadsheet* obj = new Spreadsheet(rows);
 * obj->setCell(cell,value);
 * obj->resetCell(cell);
 * int param_3 = obj->getValue(formula);
 */

设计路由器

原链接

https://leetcode.cn/problems/implement-router/description/

思路

设计题的关键还是数据结构的选择和设计，这里选择的数据结构是队列存储所有的包，还有一个目的地和时间对应的哈希表，还有一个集合，为了判断是否有重合的部分，每一个步骤都需要对这三个数据结构同时进行处理。

  1. 添加包。添加包的时候，先在集合里判断是否有重复的，如果有重复的就返回错误，没有重复的就进入下一个步骤，判断是否需要弹包，如果路由器满了就会弹包，弹完包后，就可以更新哈希表和队列了。
  2. 弹包。弹包这里就提现了数据结构的精巧，选择了deque，所以可以弹出指定地址的最开始的包，deque就是使用的pop_front方法，set则是使用的erase直接擦出包
  3. 获取数量，这里也是用到了deque的特点，deque可以O(1)地访问每个位置，所以用的二元查找的方法，找到对应的迭代器，迭代器相减就是最终的结果。

主要就是在deque和set的使用，deque支持先进先出，还跟数组一样可以很方便访问每个位置，所以可以用二元查找迅速定位到位置。

代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
struct TupleHash {
    template<typename T>
    static void hash_combine(size_t& seed, const T& v) {
        // 参考 boost::hash_combine
        seed ^= hash<T>{}(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }

    size_t operator()(const tuple<int, int, int>& t) const {
        auto& [a, b, c] = t;
        size_t seed = 0;
        hash_combine(seed, a);
        hash_combine(seed, b);
        hash_combine(seed, c);
        return seed;
    }
};
class Router {
public:
    int MemoryLimit = 0;
    queue<tuple<int,int,int>> packetQ;
    unordered_map<int,deque<int>> destToTime;
    unordered_set<tuple<int,int,int>,TupleHash> packetSet;

    Router(int memoryLimit) {
        MemoryLimit = memoryLimit;
    }
    
    bool addPacket(int source, int destination, int timestamp) {
        auto packet = tuple(source,destination,timestamp);
        if(!packetSet.insert(packet).second)
        {
            return false;
        }
        if(packetQ.size()==MemoryLimit)
        {
            forwardPacket();
        }

        packetQ.push(packet);
        destToTime[destination].push_back(timestamp);
        return true;
    }
    
    vector<int> forwardPacket() {
        if(packetQ.empty())
            return {};
        auto packet = packetQ.front();
        packetQ.pop();
        packetSet.erase(packet);
        destToTime[get<1>(packet)].pop_front();
        return {get<0>(packet),get<1>(packet),get<2>(packet)};
    }
    
    int getCount(int destination, int startTime, int endTime) {
        auto& timestamps = destToTime[destination];
        auto left = ranges::lower_bound(timestamps,startTime);
        auto right = ranges::upper_bound(timestamps,endTime);
        return right-left;
    }
};

/**
 * Your Router object will be instantiated and called as such:
 * Router* obj = new Router(memoryLimit);
 * bool param_1 = obj->addPacket(source,destination,timestamp);
 * vector<int> param_2 = obj->forwardPacket();
 * int param_3 = obj->getCount(destination,startTime,endTime);
 */

最大频率元素计数

题目：

给你一个由 正整数 组成的数组 nums 。

返回数组 nums 中所有具有 最大 频率的元素的 总频率 。

元素的 频率 是指该元素在数组中出现的次数。

示例 1：

1
2
3
4
输入：nums = [1,2,2,3,1,4]
输出：4
解释：元素 1 和 2 的频率为 2 ，是数组中的最大频率。
因此具有最大频率的元素在数组中的数量是 4 。

示例 2：

1
2
3
4
输入：nums = [1,2,3,4,5]
输出：5
解释：数组中的所有元素的频率都为 1 ，是最大频率。
因此具有最大频率的元素在数组中的数量是 5 。

这个也基本没什么难度，可以用哈希表加维护一个最大频率，也可以通过单纯的数组，然后排序取前面的的频率解决，我采用的就是第二种方法。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxFrequencyElements(vector<int>& nums) {
        vector<int> result;
        int i=100;
        result.resize(101,0);
        for(int num:nums)
        {
            result[num]++;
        }
        sort(result.begin(),result.end());
        for(i;i>=0;i--)
        {
            if(result[i]<result[100])
                break;
        }
        return (100-i)*result[100];
    }
};

比较版本号

题目：

给你两个 版本号字符串 version1 和 version2 ，请你比较它们。版本号由被点 '.' 分开的修订号组成。修订号的值 是它 转换为整数 并忽略前导零。

比较版本号时，请按 从左到右的顺序 依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0。

返回规则如下：

  • 如果 *version1* < *version2* 返回 -1，
  • 如果 *version1* > *version2* 返回 1，
  • 除此之外返回 0。

这个的主要内容是字符串分割，找到一个’.’就进行一次字符串分割，并且在一开始的字符串的末尾部分加上一个’.’来保证分割不会出错，分割完字符串并且转成数组以后，就可以开始比较了，少0的补0，知道双双达到他们的最大长度就返回，比较常规的判断逻辑。

这道题实则不难，主要在c++的字符串分割部分。

代码：

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
50
51
class Solution {
public:
    int compareVersion(string version1, string version2) {
        vector<int> v1;
        vector<int> v2;
        int pos = 0;
        version1.push_back('.');
        version2.push_back('.');
        for(int i=0;i<version1.size();i++)
        {
            if(version1[i]=='.')
            {
                string tmp = version1.substr(pos,i-pos);
                v1.push_back(stoi(tmp));
                pos = i+1;
            }
        }
        pos=0;
        for(int i=0;i<version2.size();i++)
        {
            if(version2[i]=='.')
            {
                string tmp = version2.substr(pos,i-pos);
                v2.push_back(stoi(tmp));
                pos = i+1;
            }
        }
        int i=0;
        while(1)
        {
            if(i==v1.size()&&i<v2.size())
            {
                v1.push_back(0);
            }
            if(i==v2.size()&&i<v1.size())
            {
                v2.push_back(0);
            }
            if(v1[i]<v2[i])
                return -1;
            if(v1[i]>v2[i])
                return 1;
            if(i==v2.size()-1&&i==v1.size()-1)
            {
                break;
            }
            i++;
        }
        return 0;
    }
};

分数到小数

原链接

https://leetcode.cn/problems/fraction-to-recurring-decimal/description/

思路

这个其实都可以算作一个数学问题了，跟算法相关程度不高，本质是对长除法的理解，首先需要明确的就是当在做长除的时候，如果余数出现了一样的情况，那么一定是开始了循环，所以可以想到用哈希表来存储余数，key是余数，value是位置。然后这里的还有一个技巧就是通过两个数字相乘来判断他们相除的正负关系，其他的就比较常规了，主要是对长除法的理解。

代码

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
class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        long long a = numerator;
        long long b = denominator;
        string ans;
        string sign = a * b < 0 ? "-" : "";
        a = abs(a);
        b = abs(b);
        long long p,r,pos;
        p = a/b;
        r = a%b;
        if(r==0)
            ans += sign + to_string(p);
        else
            ans += sign + to_string(p) + '.';

        pos = ans.size();
        unordered_map<long long,int> map;
        while(r)
        {
            r *= 10;
            p = r/b;
            r = r%b;
            ans += '0'+p;
            if(map.contains(r))
            {
                pos = map[r];
                ans = ans.substr(0,pos) + '(' + ans.substr(pos) + ')';
                break;
            }
            pos = ans.size();
            map[r] = pos;
        }
        return ans;
    }
};

三角形最小路径和

原链接

https://leetcode.cn/problems/triangle/description/

思路

这道题的本质是dp加记忆化搜索，也就是递推加记忆化搜索，保存之前递推出的结果，这道题把所有结果列出来，本质上可以发现是一个二叉树，每个节点都有两个节点可选，所以当遍历到相同的节点是，可以直接计算出结果。

动态规划通用思路：

  1. 寻找子问题，我们要从（0,0）出发，走到最后一排，其实也就是求出每种路径的所有结果，然后返回最小值，我们从（0,0）出发，下一步能去的地方是（1,0）和（1,1），那么我们现在面临的问题就是，从 (1,0) 出发，移动到 triangle 最后一排，路径上的元素之和的最小值，或者，从 (1,1) 出发，移动到 triangle 最后一排，路径上的元素之和的最小值。可以明显看出可以用递推的思想。

  2. 状态定义和状态转移方程，定义dfs（i，j）位从三角形的（i，j）出发，到底底部的最小结果。

    那么可以得到一个方程，dfs(i,j) = min(dfs(i+1,j),dfs(i+1,j+1))+triangle[i][j];

    然后就是中断的条件，这里的条件就是当i==n-1时，也就是三角形到底部的时候，退出这一条路径的递推

    这个就是我们的核心内容了。

  3. 保存递推返回值，我们这里采用的是vector memo(n,vector(n,INT_MIN));这个数据结构来保存，定义了一个memo数组，里面全部被初始为INT_MIN，要是要存储就在对应的位置写进已经算出的结果即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector memo(n,vector(n,INT_MIN));
        auto dfs = [&](this auto && dfs,int i,int j) -> int {
            if(i==n-1)
                return triangle[i][j];
            int& res = memo[i][j];
            if(res!=INT_MIN)
            {
                return res;
            }
            return res = min(dfs(i+1,j),dfs(i+1,j+1))+triangle[i][j];
        };
        return dfs(0,0);
    }
};

  1. 是中断的条件，这里的条件就是当i==n-1时，也就是三角形到底部的时候，退出这一条路径的递推

    这个就是我们的核心内容了。

  2. 保存递推返回值，我们这里采用的是vector memo(n,vector(n,INT_MIN));这个数据结构来保存，定义了一个memo数组，里面全部被初始为INT_MIN，要是要存储就在对应的位置写进已经算出的结果即可

有效三角形的个数

原链接

https://leetcode.cn/problems/valid-triangle-number/description/

思路

主要的思路是排序加双指针。我一开始的想法就是三次遍历，后面看了题解才明白，因为已经排好序了，所以直接双指针移动就好了，三次遍历浪费了太多时间

第一个是先对原数列进行排序，然后令最大的数字做最大边，然后双指针的起始地址一个是0，一个就是最大边-1，然后找到符合条件的组合即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n = nums.size();
        int result = 0;
        for(int k=nums.size()-1;k>=2;k--)
        {
            int j = k-1;
            int i=0;
            while(i<j)
            {
                if(nums[i]+nums[j]>nums[k])				//双指针移动代码，优先移动左边指针，找到后就移动右边指针，优化时间
                {
                    result += j-i;
                    j--;
                }
                else
                    i++;
            }
        }
        return result;
    }
};

数组的三角和

原链接

https://leetcode.cn/problems/find-triangular-sum-of-an-array/description/

思路

我的方法比较容易理解，兼顾模拟和组合数字，先通过组合数字，得到三个化简为一个的方法，就是最外面的两个系数是1，中间的数字系数是2，然后就是遍历和模拟的过程了，遍历数组，一遍一遍地找三的数组，并且化简数组，通过数组的大小来判断是否继续化简。

代码

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
class Solution {
public:
    int triangularSum(vector<int>& nums) {
        while(1)
        {
            if(nums.size()==1)
                break;
            else if(nums.size()==2)
            {
                nums[0] = (nums[0]+nums[1])%10;
                nums.pop_back();
                break;
            }
            else
            {
                for(int i=0;i<nums.size()-2;i++)
                {
                    nums[i] = (nums[i]+nums[i+1]+nums[i+1]+nums[i+2])%10;
                }        
                nums.pop_back();
                nums.pop_back(); 
            }
        }
        return nums[0];
    }
};