目录
数组
数组理论基础
- 数组下标从0开始；
- 数组内存空间地址连续；
二分查找
- 题目链接：704. 二分查找 - 力扣（LeetCode）
- 思路：二分思想，关键确定好左右定义的区间意义：左闭右开or左闭右闭？然后确定循环终止条件、边界更新实现；左右双指针
- 代码实现：
int search(int* nums, int numsSize, int target) {
// 1、定义二分区间，左闭右开
int left = 0, right = numsSize;
// 2、二分搜索，左闭右开 -- 相等没有意义
while(left < right) {
int middle = (left + right) / 2;
int midValue = *(nums + middle);
// 2.1 在左边
if(midValue > target) {
right = middle;
}
// 2.2 在右边
else if(midValue < target) {
left = middle + 1;
}
// 2.3 找到了
else {
return middle;
}
}
// 3、没找到
return -1;
}
移除元素
- 题目链接：27. 移除元素 - 力扣（LeetCode）
- 思路： 快慢双指针：快指针在前面走，如果遇到与目标值相同——快指针跳过，慢指针不动；慢指针按次序指向数组中当前需要存放不为val的值的位置。快慢双指针。
- 代码实现：
// 快慢双指针
// 快指针在前面走，如果遇到与目标值相同——快指针跳过，慢指针不动；
// 慢指针按次序指向数组中当前需要存放不为val的值的位置
int removeElement(int* nums, int numsSize, int val) {
// 1.定义快慢双指针
int fastP = 0, slowP = 0;
// 2.循环所有元素
while(fastP < numsSize) {
// 2.1 如果fastP不指向val，赋值同时两个指针自增
if(*(nums + fastP) != val) {
*(nums + slowP++) = *(nums + fastP);
}
// 2.2 如果是val，只对fastP自增
fastP++;
}
// 3.此时慢指针的位置就能得到与val不同的元素的数量
return slowP;
}
有序数组的平方
- 题目链接：977. 有序数组的平方 - 力扣（LeetCode）
- 思路：
- 左右双指针，非递减序列中平方的最大值一定在两边；
- 注意其中 returnSize要更新为结果元素的数量，这也是返回数组（int *）时告知数组长度的方式；
- 动态为数组分配内存：
int *ans = (int *)malloc(numsSize * sizeof(int));;
- 代码实现：
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
// 左右双指针：平方最大值一定是从两边到中间
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
*returnSize = numsSize;
// 1.定义左右双指针、结果数组
int left = 0, right = numsSize - 1;
int *ans = (int *)malloc(numsSize * sizeof(int));
int index = numsSize - 1;
// 2.开始循环：循环终止条件--相等为止
while(left <= right) {
// 循环中比较左右双指针哪个指向元素的平方最大
int leftValue = nums[left] * nums[left], rightValue = nums[right] * nums[right];
// printf("leftValue:%d, rightValue:%d\n", leftValue, rightValue);
if(leftValue < rightValue) {
ans[index] = rightValue;
--right;
} else {
ans[index] = leftValue;
++left;
}
// printf("ans[index] = %d\n", ans[index]);
index--;
}
// 3.返回
// printf("return ans:%d", ans[numsSize - 1]);
return ans;
}
长度最小的子数组
- 题目链接：209. 长度最小的子数组 - 力扣（LeetCode）
- 思路：滑动窗口——窗口：左闭右闭，如果小于target，一直移动右指针；否则记录长度，然后移动左指针；
- 代码实现：
// 思路：滑动窗口
// 窗口：左闭右闭，如果小与target，一直移动右指针；否则记录长度，然后移动左指针
int minSubArrayLen(int target, int* nums, int numsSize) {
// 1.滑动窗口左右指针，左闭右闭
int left = 0, right = 0;
int sum = 0;
int count = numsSize + 1;
// 2.遍历
for(;right < numsSize; ++right){
// 2.1 滑动窗口右移了，计入
// printf("right = %d\n", right);
sum += nums[right];
// printf("sum = %d\n", sum);
while(sum >= target) {
// 2.2 只要子序列满足要求，收缩滑动窗口左边界
count = count < (right - left + 1) ? count : (right - left + 1);
// printf("==>count = %d\n", count);
sum -= nums[left++];
// printf("left = %d\n", left);
}
}
// 3.返回
return count == numsSize + 1 ? 0 : count;
}
螺旋矩阵Ⅱ
- 题目链接：59. 螺旋矩阵 II - 力扣（LeetCode）
- 思路：按照题目要求遍历，注意螺旋遍历过程中保持变量不变——每一行、列填充时统一为左闭右开；
- 注意
returnColumnSizes、ans的创建：*returnColumnSizes = (int *)malloc(sizeof(int) * n);、int **ans = (int**)malloc(sizeof(int*) * n);。 returnColumnSizes本质上也是一个二维数组，第一个维度是有多少列，第二个维度是每一列包含多少个元素（也就是多少行）；
- 注意
- 代码实现：
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
// 思路：模拟，注意控制循环时保持变量不变，每一行、列的填充统一为左闭右开
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes) {
// 1.初始化返回数组的大小
*returnSize = n;
*returnColumnSizes = (int *)malloc(sizeof(int) * n);
// 2.初始化结果：二维数组
int **ans = (int**)malloc(sizeof(int*) * n);
// 初始化每一行
for(int i = 0; i < n; ++i) {
ans[i] = (int*)malloc(sizeof(int) * n);
(*returnColumnSizes)[i] = n;
}
// 3.初始化循环变量
// 计数变量(用于赋值)
int count = 1;
// 按照n计算螺旋的圈数
int loop = n / 2;
// 记录中间位置，如果n为奇数，这里需要单独赋值
int mid = n / 2;
// 螺旋的起点
int startX = 0;
int startY = 0;
// 偏移量，用于计算螺旋中每一行、列的终点
int offset = 1;
// 4.开始螺旋循环--按照循环圈数
while(loop != 0) {
// 4.1 设置起点
int i = startX;
int j = startY;
// 4.2 顶部一行，注意左闭右开
for(; j < startY + n - offset; j++) {
ans[i][j] = count++;
}
// 4.3 右侧一列
for(; i < startX + n - offset; i++) {
ans[i][j] = count++;
}
// 4.4 底部一行
for(; j > startY; j--) {
ans[i][j] = count++;
}
// 4.5 左侧一列
for(; i > startX; i--) {
ans[i][j] = count++;
}
// 4.6 一轮螺旋结束，更新变量
// 减少螺旋圈数
--loop;
// 更新下一轮螺旋起点
++startX;
++startY;
// 更新偏移量offset，一轮螺旋少两个
offset += 2;
}
// 5.判断n是否为奇数，从而进行中间点补充
if(n % 2 == 1) {
ans[mid][mid] = count;
}
// 6.返回结果
return ans;
}
总结篇
本章出现的知识点小结：
- 二分算法；
- 快慢双指针；
- 左右双指针；
- 滑动窗口
- 按照题目模拟，注意保持变量意义不变。
链表
1.链表理论基础
-
链表的类型：
- 单链表；
- 双链表；
-
性能分析：
2.移除链表元素
-
思路：设置虚拟头节点，删除的时候注意先记录要删除的节点、然后在链表中删除、在内存中删除；
- 注意：通过指针方式访问其成员变量用
->。
- 注意：通过指针方式访问其成员变量用
-
代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
// 虚拟头节点
struct ListNode* removeElements(struct ListNode* head, int val) {
// 1.设置虚拟头节点
typedef struct ListNode ListNode;
ListNode *dummyHead = (ListNode *)malloc(sizeof(ListNode));
dummyHead->next = head;
ListNode *cur = dummyHead;
// 2.遍历
while(cur->next != NULL) {
// 2.1 如果下一个节点需要被删除
if(cur->next->val == val) {
// 执行删除--记录下要删除的节点、在链表中删除、在内存中释放
ListNode *temp = cur->next;
cur->next = cur->next->next;
free(temp);
}
else {
// 2.2 不需要删除--更新cur
cur = cur->next;
}
}
// 3.返回真实头节点
// 注意：释放虚拟头节点
head = dummyHead->next;
free(dummyHead);
return head;
}
3.设计链表
-
思路：
- 用c语言创建链表的时候要使用虚拟头节点，不然就没办法在头节点位置做更改；
- 注意在 index 位置执行插入删除的时候，使用单链表的话找到 index 位置就晚了，因此要找的是 index - 1，可以使用一个小技巧，让 i 从 1 开始遍历，这样判断的时候判断 i == index 就可以了。
AddAtTai可以优化，不管有没有头节点，只要当前节点的下一节点为 NULL 停止进行添加就可以了。myLinkedListAddAtIndex中在索引0插入可以优化为直接调用AddAtHead；
-
代码实现：
typedef struct MyLinkedList{
int val;
struct MyLinkedList *next;
} MyLinkedList;
MyLinkedList* myLinkedListCreate() {
// 1.创建虚拟头节点
MyLinkedList *dummyHead = (MyLinkedList *)malloc(sizeof(MyLinkedList));
// 2.设置值和下一节点
dummyHead->val = 0;
dummyHead->next = NULL;
return dummyHead;
}
int myLinkedListGet(MyLinkedList* obj, int index) {
// 调试输出
// printf("debug:\n");
// MyLinkedList *debugNode = obj->next;
// int debugIndex = 0;
// while(debugNode != NULL) {
// printf("debuIndex = %d, val = %d\n", debugIndex++, debugNode->val);
// debugNode = debugNode->next;
// }
// 先取出真实头节点
MyLinkedList *cur = obj->next;
// 遍历各个节点
for(int i = 0; cur != NULL; ++i) {
// 找到目标节点
if(i == index) {
// 返回节点val
return cur->val;
}
else {
// 没找到
cur = cur->next;
}
}
// 遍历完不够这么多索引——下标无效
return -1;
}
void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
// 先创建出该节点
MyLinkedList *newHead = (MyLinkedList *)malloc(sizeof(MyLinkedList));
newHead->val = val;
// 将 newHead 设置为新的头节点
newHead->next = obj->next;
obj->next = newHead;
}
void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
// 先创建该节点
MyLinkedList *node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
node->val = val;
node->next = NULL;
// 特殊情况：没有头节点
if(obj->next == NULL) {
// 直接添加为头节点
obj->next = node;
}
else {
// 正常情况：存在头节点——遍历找到末尾
MyLinkedList *cur = obj->next;
// 遍历到链表的末尾节点
while(cur->next != NULL) {
cur = cur->next;
}
// 添加
cur->next = node;
}
}
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
// 特殊情况：在头节点（索引0）插入
if(index == 0) {
// 创建节点
MyLinkedList *node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
node->val = val;
// 添加到头节点位置
node->next = obj->next;
obj->next = node;
return;
}
// 不在头节点插入
MyLinkedList *cur = obj->next;
// 遍历找到目标位置，注意要插入的是index位置，所以要找到 index - 1就停
// 让遍历参数 i 从 1 开始
for(int i = 1; cur != NULL; ++i) {
if(i == index) {
// 创建节点，插入
MyLinkedList *node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
node->val = val;
node->next = cur->next;
cur->next = node;
}
else {
// 移动到下一节点
cur = cur->next;
}
}
// 没找到，不插入，不做任何处理
}
void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
// 特殊情况：头节点的删除(前提：头节点存在)
if(obj->next != NULL && index == 0) {
MyLinkedList *tmp = obj->next;
// 逻辑删除
obj->next = tmp->next;
// 物理删除
free(tmp);
return;
}
// 非头节点删除情况——注意
// 注意：要删除的是索引为index的节点，因此当找到 index - 1 时就要着手删除
// 小技巧：让i从1开始遍历
MyLinkedList *cur = obj->next;
// 遍历
// int targetIndex = index - 1;
for(int i = 1; cur != NULL; ++i) {
if(i == index) {
// 找到了——执行删除
MyLinkedList *tmp = cur->next;
// 逻辑删除 -- 需要保证 tmp 不为 NULL，如果tmp为NULL——索引本身是无效的
if(tmp != NULL) {
cur->next = tmp->next;
}
// 物理删除 -- 即使 tmp 为NULL，free也没影响
free(tmp);
}
else {
// 移动到下一节点
cur = cur->next;
}
}
}
void myLinkedListFree(MyLinkedList* obj) {
// 遍历链表释放每个节点
while(obj != NULL){
MyLinkedList *tmp = obj;
obj = obj->next;
free(tmp);
}
}
/**
* Your MyLinkedList struct will be instantiated and called as such:
* MyLinkedList* obj = myLinkedListCreate();
* int param_1 = myLinkedListGet(obj, index);
* myLinkedListAddAtHead(obj, val);
* myLinkedListAddAtTail(obj, val);
* myLinkedListAddAtIndex(obj, index, val);
* myLinkedListDeleteAtIndex(obj, index);
* myLinkedListFree(obj);
*/
4.反转链表
-
思路：记录当前节点的前一节点和下一节点，然后反转：
- 更改下一节点：cur -> next = prev；
- 移动 prev 和 cur；
-
代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
// 思路：从头节点开始，每次记录前一个节点、当前节点和下一个节点
typedef struct ListNode ListNode;
// 1.当前节点和前一个节点变量，前一节点初始化为NULL
ListNode *prev = NULL;
ListNode *cur = head;
// 2.遍历
while(cur != NULL) {
// 2.1 记录下一节点
ListNode *tmp = cur->next;
// 2.2 让当前节点的下一节点成为前一节点
cur->next = prev;
// 2.3 更新前一节点为当前节点
prev = cur;
// 2.4 更新当前一节点到正序的下一节点
cur = tmp;
}
// 3.返回--最后cur走到了NULL，因此返回prev
return prev;
}
5.两两交换链表中的节点
-
思路：按题目要求对每一对节点进行处理即可；
- 交换时分三步：cur和next为要交换的节点，则先让prev指向next，再让cur指向next的next，再连接起来next到cur，最后记得更新prev和cur。
-
代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head) {
// 思路：遍历，每次递增两个节点，边界条件为判断到当前节点以及其下一个节点为NULL停止
// 1.虚拟头节点
typedef struct ListNode ListNode;
ListNode *dummyHead = (ListNode*)malloc(sizeof(ListNode));
dummyHead->next = head;
ListNode *prev = dummyHead;
ListNode *cur = head;
// 2.遍历 -- 确保进入新的循环时至少还有两个节点
while(cur != NULL && cur->next != NULL) {
// 对cur和其next执行交换
// 2.1 将next接到prev后面
prev->next = cur->next;
// 2.2 将next的next接到cur后面
cur->next = cur->next->next;
// 2.3 将cur接到next后面
prev->next->next = cur;
// 更新prev、cur
prev = cur;
cur = cur->next;
}
// 3.返回
return dummyHead->next;
}
6.删除链表的倒数第N个节点
- 题目链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
- 思路：快慢双指针，链表最少有一个节点，让快慢指针间隔n，然后同步移动，当快指针指向NULL时，慢指针就是倒数第n个；然后注意物理free该节点和虚拟头节点。
- 代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
// 思路：快慢双指针，链表最少有一个节点，让快慢指针间隔n
// 因为可能会删除头结点，所以需要虚拟头结点
typedef struct ListNode ListNode;
// 1.定义虚拟头结点
ListNode *dummyHead = (ListNode*)malloc(sizeof(ListNode));
dummyHead->next = head;
// 2.定义快慢双指针
// 2.1 快指针
ListNode *fast = head;
// 2.2 快指针多走 n
for(int i = 0; i < n; ++i) {
fast = fast->next;
}
// 2.3 定义慢指针此时指向head
ListNode *slow = head;
// 3.让fast移动到为NULL，slow同步移动，则此时slow就在倒数第n个节点——要删除就要记录slow的前一个节点
ListNode *prev = dummyHead;
while(fast != NULL) {
fast = fast->next;
slow = slow->next;
prev = prev->next;
}
// 4.执行删除
// 4.1 逻辑删除
prev->next = slow->next;
// 4.2 物理删除
free(slow);
// 5 返回--释放虚拟头结点
ListNode *newHead = dummyHead->next;
free(dummyHead);
return newHead;
}
7.链表相交
-
思路：如果二者相交，应该是尾端对齐，按照对齐的位置一个一个对比节点地址是否相同（注意不是节点值）；
- 先计算出来两个链表的长度m、n，计算得到长度差lenDiff；
- 然后将尾端对齐——即让长的先走lenDiff步；
- 比较节点地址是否相同。
-
代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
// 思路：如果二者相交，应该是尾端对齐，按照对齐的位置一个一个对比
// 先计算出来m、n，计算得到长度差lenDiff；
// 然后将尾端对齐——即让长的先走lenDiff；
// 按对齐节点一一比较
typedef struct ListNode ListNode;
// 1.计算长度
int lenA = 0, lenB = 0;
ListNode *curA = headA;
while(curA != NULL) {
++lenA;
curA = curA->next;
}
ListNode *curB = headB;
while(curB != NULL) {
++lenB;
curB = curB->next;
}
// 2.计算长度差
int lenDiff = lenA > lenB ? (lenA - lenB) : (lenB - lenA);
// 3.长的先走 lenDiff 步
curA = headA;
curB = headB;
if(lenA > lenB) {
for(int i = 0; i < lenDiff; ++i) {
curA = curA->next;
}
}
else {
for(int i = 0; i < lenDiff; ++i) {
curB = curB->next;
}
}
// 4.比较 curA 和 curB 是否指向相同的节点
while(curA != NULL) {
if(curA == curB) {
return curA;
}
curA = curA->next;
curB = curB->next;
}
// 5.返回NULL
return NULL;
}
8.环形链表Ⅱ
-
思路：
- 快慢双指针，如果存在环，快指针每次走两步，慢指针每次走一步，必能相遇；
- 按照数学推导，当快慢指针相遇时，两个指针分别同步从开头和相遇点移动，再次相遇就是入环节点。
-
代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
// 思路：快慢双指针，如果存在环，快指针每次走两步，慢指针每次走一步，必能相遇
// 按照数学推导，当快慢指针相遇时，两个指针分别同步从开头和相遇点移动，再次相遇就是入环节点
typedef struct ListNode ListNode;
// 1.快慢双指针
ListNode *fast = head;
ListNode *slow = head;
// 2.移动，找快慢指针相遇
// 快指针每次移动两步，要保证节点不为NULL——主要是排除没有环
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
// 3.如果相遇——必定有环，寻找环入口
if(slow == fast) {
ListNode *node1 = head;
ListNode *node2 = fast;
// 4.同步移动到再次相遇
while(node1 != node2) {
node1 = node1->next;
node2 = node2->next;
}
return node1;
}
}
return NULL;
}
9.总结篇
- 链表分类：单链表、双链表、循环链表；
- 虚拟头结点；
- 链表中的双指针：快慢双指针。
哈希表
1.哈希表理论基础
-
哈希表：根据关键码的值直接进行访问；
-
哈希碰撞的解决：拉链法、线性探测法；
-
哈希法的三种数据结构：
- 数组
- set（集合）
- map（映射）
2.有效的字母异位词
-
思路：哈希，因为只包含小写字母，用数组就可以，遍历s统计字符数量、t减去，最后看所有位置是不是都是0；
- 注意数组测试后元素应该可以默认为0；
- 也可以调用函数
strlen获得字符串的长度，然后进行for循环；
-
代码实现：
bool isAnagram(char* s, char* t) {
// 思路：哈希，因为只包含小写字母，用数组就可以
// 1.定义哈希
int hash[26] = {0};
// 2.遍历字符串s，统计字符出现次数
while(*s != '\0') {
// 2.1 统计字符
// 2.2 移动s
// printf("%c\n", *s);
hash[*(s++) - 'a']++;
}
// 3.遍历t，减去字符
while(*t != '\0') {
--hash[*(t++) - 'a'];
}
// 4.判断是否所有位都为0
for(int i = 0; i < 26; ++i) {
if(hash[i] != 0) {
return false;
}
}
return true;
}
3.两个数组的交集
-
思路：哈希，题目规定了两个数组的长度范围，因此可以使用哈希数组；
- 注意，返回的结果数组要传出去，因此不能是局部变量，要动态分配内存：
int* ret = (int*)malloc(lessSize * sizeof(int));
- 注意，返回的结果数组要传出去，因此不能是局部变量，要动态分配内存：
-
代码实现：
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
// 思路：哈希，题目规定了两个数组的长度范围，因此可以使用哈希数组
// 1.创建哈希数组
int hash[1001];
// 结果数组——需要返回，动态创建出来
int lessSize = nums1Size < nums2Size ? nums1Size : nums2Size;
int* ret = (int*)malloc(lessSize * sizeof(int));
// 2.遍历nums1，将出现的数字存入哈希
for(int i = 0; i < nums1Size; ++i) {
hash[*(nums1 + i)]++;
}
// 3.遍历nums2，如果数字在hash中出现过，存放到结果中
// 结果数组索引
int index = 0;
for(int i = 0; i < nums2Size; ++i) {
if(hash[*(nums2 + i)] != 0) {
// 当前元素在hash中存在，放入结果
ret[index++] = nums2[i];
// 记得将hash当前位置清掉，避免重复添加
hash[*(nums2 + i)] = 0;
}
}
// 4.返回结果，记得为结果数组添加长度
*returnSize = index;
return ret;
}
4.快乐数
-
思路：关键点——可能无限循环就到不了1——通过判断算出来的结果是否出现过——哈希
- 用哪种哈希？c语言没有set，数组要求可能出现的索引有限？
- n <= 2^31-1，也就是10位数，每一位最大是9，那么每次计算最大可能是9910 = 810，哈希数组可行
-
代码实现：
int getSum(int n);
bool isHappy(int n) {
// 思路：关键点——可能无限循环就到不了1——通过判断算出来的结果是否出现过——哈希
// 用哪种哈希？c语言没有set，数组要求可能出现的索引有限？
// n <= 2^31-1，也就是10位数，每一位最大是9，那么每次计算最大可能是9*9*10 = 810，哈希数组可行
#define HASH_LENGTH = 811;
// 1.定义哈希数组
int hash[811] ={};
// 2.遍历计算，判断是否出现了无限循环
while(n != 1) {
// 2.1 计算
int sum = getSum(n);
// 2.2 判断
if(hash[sum] != 0) {
// 无限循环，返回false
return false;
}
else {
// 加入hash、替换n
hash[sum]++;
n = sum;
}
}
// 3.成功出来了，返回true
return true;
}
// 根据n求取每一位上的平方和
int getSum(int n) {
int sum = 0;
while(n != 0) {
int temp = n % 10;
sum += temp * temp;
n = n / 10;
}
return sum;
}
5.两数之和
-
思路：哈希：每遍历一个数，将他和target的差值存放到哈希中，后面遍历到的数如果存在于哈希中，就找到了；
- 需要根据值返回索引，因此用hashmap；
-
代码实现：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 哈希：每遍历一个数，将他和target的差值存放到哈希中，后面遍历到的数如果存在于哈希中，就找到了，需要返回索引，因此用hashmap
// 1.定义哈希
std::unordered_map<int, int> map;
// 2.遍历元素并执行寻找
for(int i = 0; i < nums.size(); ++i) {
// 2.1 判断和nums[i]组成target的值在不在map
auto iter = map.find(target - nums[i]);
if(iter != map.end()) {
// 2.2 找到了，返回索引结果
return {iter->second, i};
}
// 2.3 没找到，存入map——值是key，索引是value
map.insert(pair<int, int>(nums[i], i));
}
return {};
}
};
6.四数相加Ⅱ
-
思路：
- 只要满足题目要求的数量——不用考虑向量之间元素的重复；
- 因此只要先统计两组元素可能的和，然后在另两组元素和中找相反数——哈希；
- 每次找到，需要知道该和的个数——用map；
-
代码实现：
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
// 思路：只要满足题目要求的数量——不用考虑向量之间元素的重复
// 因此只要先统计两组元素可能的和，然后在另两组元素和中找相反数——哈希
// 每次找到，需要知道该和的个数——用map
int count = 0;
// 1.定义哈希
std::unordered_map<int, int> map;
// 2.嵌套遍历前两组向量，统计和
for(int a : nums1) {
for(int b : nums2) {
// 插入哈希
map[a + b]++;
}
}
// 3.嵌套遍历后两组向量，计算和，在哈希中找相反数
for(int c : nums3) {
for(int d : nums4) {
if(map.find(0 - (c + d)) != map.end()) {
count += map[0 - (c + d)];
}
}
}
return count;
}
};
7.赎金信
-
思路：
- 哈希，先遍历magazine，字符为key，出现次数为value；
- 然后遍历
ransomNote，每个字符取哈希中找，找到对应值<=0返回false； - 优化：字母全是小写字母，因此可以用哈希数组代替哈希map节省空间、时间消耗。
-
代码实现：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
// 1.哈希
std::unordered_map<char, int> map;
// 2.遍历magazine
for(char ch : magazine) {
map[ch]++;
}
// 3.遍历randomNote
std::unordered_map<char, int>::iterator it;
for(char ch : ransomNote) {
it = map.find(ch);
// 3.1 找不到或者已经被前面匹配完了
if(it == map.end() || it -> second <= 0) {
return false;
}
// 3.2 map中还有可以匹配的字符——减一
it -> second--;
}
return true;
}
};
8.三数之和
-
思路：排序+双指针
- 结果需要的是元素的组合而不是元素的索引，因此可以进行排序，从而方便在后续排除某些答案选项；
- 排序后先遍历第一个元素，对第一个元素可以注意剪枝和去重；
- 对另外两个元素，分别设为剩余元素的前后双指针，遍历，如果整体和偏大，减小右指针，整体和偏小，增大左指针；
- 当找到一种可能的结果时，要去重左右指针出现的元素；
- 最后应当注意，找到可能结果后，要显式地对双指针进行移动，否则程序会死循环在这种结果上。
-
代码实现：
// 思路：排序+双指针
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
// 1.结果向量
vector<vector<int>> ret;
// 2.排序
sort(nums.begin(), nums.end());
// 3.遍历第一个元素
for(int i = 0; i < nums.size(); ++i) {
// 3.1 第一个元素剪枝
if(nums[i] > 0) {
break;
}
// 3.2 第一个元素去重
if(i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 4.双指针遍历后两个元素，此时需要后双指针元素的和为-nums[i]，且上面已经保证nums[i] <= 0
int left = i + 1, right = nums.size() - 1;
while(left < right) {
// 4.1 两元素之和 + nums[i] > 0，移动后面的那个元素
while(left < right && nums[left] + nums[right] + nums[i] > 0) {
--right;
}
// 4.2 两元素之和 + nums[i] < 0，移动前面的指针
while(left < right && nums[left] + nums[right] + nums[i] < 0) {
++left;
}
// 4.3 两元素之和 + nums[i] = 0，此时应保证 left < right
if(left < right && nums[left] + nums[right] + nums[i] == 0) {
// 将结果加入向量
ret.push_back(vector<int> {nums[i], nums[left], nums[right]});
// 出现了一种结果，此时要进行去重——不能再出现与left、right指向值相同的元素
while(left < right && nums[right] == nums[right - 1]) {
--right;
}
while(left < right && nums[left] == nums[left + 1]) {
++left;
}
// 找到了答案，注意对双指针进行移动，否则会死循环在这一个答案上
++left;
--right;
}
}
}
// 5.返回结果
return ret;
}
};
9.四数之和
-
思路：
- 同三数之和，外面两层for循环+双指针；
- 前两个元素剪枝的时候注意，这里和的目标值不是零，排序之后不能单独判断是否大于target，因为后面的两个数还有可能是负数；
- 题目中对于向量中的元素范围定义是 <= 109，当计算四个数之和时如果都顶着上极限会超过int的上限231，所以最后判断四个数之和的时候要注意增加一个long的强转。
-
代码实现：
// 思路：同三数之和，外面两层for循环+双指针
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
// 1.结果向量
vector<vector<int>> ret;
// 2.排序
sort(nums.begin(), nums.end());
// 3.第一层遍历
for(int i = 0; i < nums.size(); ++i) {
// 3.1 第一个元素剪枝--注意与三数之和不同的是，此时目标值可能是负的，因此不能单独判断nums[i] > target
if(nums[i] > 0 && nums[i] > target) {
break;
}
// 3.2 第一个元素的去重
if(i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 4.第二层遍历
for(int j = i + 1; j < nums.size(); ++j) {
// 4.1 第二个元素剪枝
if(nums[i] + nums[j] > 0 && nums[i] + nums[j] > target) {
break;
}
// 4.2 第二个元素的去重
if(j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
// 5.双指针实现O(n)遍历后两个元素
int left = j + 1, right = nums.size() - 1;
while(left < right) {
// 5.1 如果总和 > target，右指针左移
while(left < right && (long)nums[i] + nums[j] + nums[left] + nums[right] > target) {
--right;
}
// 5.2 如果总和 < target，左指针右移
while(left < right && (long)nums[i] + nums[j] + nums[left] + nums[right] < target) {
++left;
}
// 5.3 找到满足要求的组合
if(left < right && (long)nums[i] + nums[j] + nums[left] + nums[right] == target) {
// 5.3.1 放入结果集合
ret.push_back(vector<int> {nums[i], nums[j], nums[left], nums[right]});
// 5.3.2 注意去重：调节左右指针，避免左右指针所指元素出现重复
while(left < right && nums[right] == nums[right - 1]) --right;
while(left < right && nums[left] == nums[left + 1]) ++left;
// 5.3.3 注意移动左右指针，如果上述没有去重，下次还会进入这种组合
--right;
++left;
}
}
}
}
// 6.返回结果
return ret;
}
};
10.总结篇
-
三种哈希结构：数组、set（集合）、map（映射）；
-
C++：
std::set和std::multiset、std::map和std::multimap底层实现都是红黑树，key是有序的；std::unordered_set、std::unordered_map底层实现为哈希;
字符串
1.反转字符串
- 题目链接：344. 反转字符串 - 力扣（LeetCode）
- 思路：双指针
- 代码实现：
// 思路：双指针
class Solution {
public:
void reverseString(vector<char>& s) {
// 1.定义双指针
int left = 0, right = s.size() - 1;
char temp;
// 2.遍历，相等的时候是同一个，因此只用在left < right的时候判断
while(left < right) {
// 2.1 反转
temp = s[left];
s[left] = s[right];
s[right] = temp;
// 2.2 更新指针
++left;
--right;
}
}
};
2.反转字符串Ⅱ
- 题目链接：541. 反转字符串 II - 力扣（LeetCode）
- 思路：
- 双指针+每次反转后让索引i移动2k；
- 开始的错误思路：用索引来控制每次的2k区间，再去取其中的前k个，逻辑不够简洁；
- 代码实现：
// 思路：双指针+每次反转后让索引i移动2k
class Solution {
public:
string reverseStr(string s, int k) {
for(int i = 0; i < s.size(); i += 2*k) {
// 反转区间 i ~ i + k - 1，左闭右闭
// 特殊情况就是新的2k区间不够k个，要调整终点为 s.size() - 1
reverse(s, i, i + k <= s.size() ? i + k - 1 : s.size() - 1);
}
return s;
}
void reverse(string& s, int begin, int end) {
char temp;
while(begin < end) {
temp = s[begin];
s[begin] = s[end];
s[end] = temp;
++begin;
--end;
}
}
};
3.替换数字
- 题目链接：
- 思路：
- 代码实现：
4.翻转字符串里的单词
-
思路：
- 先去除多余的空格，然后双指针将s整体倒序，最后从头开始对每个单词双指针颠倒会单词的正序；
- 重点：移除多余的空格，需要结合数组中移除指定的元素操作
-
代码实现：
// 思路：先去除多余的空格，然后双指针将s整体倒序，最后从头开始对每个单词双指针颠倒会单词的正序
class Solution {
public:
string reverseWords(string s) {
// 1.移除多余空格
eraseExtraSpace(s);
// 2.双指针倒序s整体
inverseString(s, 0, s.size() - 1);
// 3.遍历倒序后的s，每次找到空格停止，左闭右开为一个单词，双指针倒序单词回正序
int wordStartIndex = 0;
for(int i = 0; i <= s.size(); ++i) {
// 3.1 如果遇到空格或走到字符串末尾，辨识出一个单词
if(i == s.size() || s[i] == ' ') {
inverseString(s, wordStartIndex, i - 1);
wordStartIndex = i + 1;
}
}
return s;
}
// 快慢双指针移除多余元素--空格
void eraseExtraSpace(string& s) {
// 思路：快慢双指针，快指针遇到要移除的元素就跳过，而慢指针按需要的字符次序放置快指针对应的字符
int slowIndex = 0, fastIndex = 0;
// 1.移除前导空格
while(fastIndex < s.size() && s[fastIndex] == ' ') {
++fastIndex;
}
// 2.移除单词之间多余的空格
for(; fastIndex < s.size(); ++fastIndex) {
// 2.1 判别单词之间多余的空格——是空格，并且前面还是空格
if(fastIndex - 1 > 0 && s[fastIndex] == s[fastIndex - 1] && s[fastIndex] == ' ') {
// 按照快慢双指针在数组中移除元素，直接让快指针+1跳过不赋值
continue;
}
else {
// 2.2 是有效元素——赋值
s[slowIndex++] = s[fastIndex];
}
}
// 3.移除尾缀多余的空格，最后如果有多余的空格，在上一步只会有一个被移动到slow上一个位置
if(slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') {
// 删除这个空格——直接resize字符串就好了
s.resize(slowIndex - 1);
} else {
// 没有尾缀空格
s.resize(slowIndex);
}
}
// 双指针反转字符串，双指针区间左闭右闭
void inverseString(string& s, int begin, int end) {
char temp;
while(begin < end) {
temp = s[begin];
s[begin] = s[end];
s[end] = temp;
++begin;
--end;
}
}
};
5.右旋转字符串
- 题目链接：
- 思路：
- 代码实现：
6.实现strStr()
-
思路：
- 在文本串里面匹配模式串——如果每次匹配失败，就直接在文本串里遍历用下一个起始位置是O(n*m)的暴力解法；
- KMP：如果某一位匹配不上，其实文本串中前面匹配的子串已经判断过一波了，是可以用起来的；
- 怎么用？总要让模式串的前面一部分和文本串刚匹配的子串对应上，而这段子串整体是出现在模式串中的
- 因此，就是模式串中的这部分从头开始的子串，它的前缀（不包含最后一个字符）和它的后缀（不包含第一个字符）有多少个字符能对上，然后就可以不用匹配前缀这一部分了——前缀表来记录
- 前缀表的构造：
- 遍历模式串的每一位，刚好可以作为后缀子串的末尾，然后在用一个控制相等前缀的末尾；
- 对比两个字符，如果对不上，索引0~j这一段子串j位置对不上i，next[j - 1]刚好存储着0
~j-1中最长相等前后缀，用它来回退j；why？--个人理解：其实此时也是一个模式串与文本串的匹配，我们让j的回退是因为前面这一段可能和i前面的部分重合，而j和i又不重合，只能尽可能把j之前的利用起来（同样利用前缀表），哪怕觉得此时这样回退不如j逐步-1回退好，其实这种想法是行不通的，按这种回退，你得每次一位一位比较，只能是从每个开头的暴力遍历；
-
代码实现：
// 思路：在文本串里面匹配模式串——如果每次匹配失败，就直接在文本串里遍历用下一个起始位置是O(n*m)的暴力解法
// KMP：如果某一位匹配不上，其实文本串中前面匹配的子串已经判断过一波了，是可以用起来的
// 怎么用？总要让模式串的前面一部分和文本串刚匹配的子串对应上，而这段子串整体是出现在模式串中的
// 因此，就是模式串中的这部分从头开始的子串，它的前缀（不包含最后一个字符）和它的后缀（不包含第一个字符）有多少个字符能对上，然后就可以不用匹配前缀这一部分了——前缀表来记录
class Solution {
public:
// 构建前缀表，就是一个数组，到这一位索引时，最长相等前后缀
// 参数：
// next -- 前缀表数组，开头到这里，最长相等前后缀的长度；
// s -- 要处理的模式串
void getNext(int *next, string &s) {
// 用i遍历当前索引，那么i就是指向后缀末尾的位置，再用j指向前缀末尾的位置
// 1、初始化，0号位没有前后缀，所以为0，同时j也指向0
int j = 0;
next[0] = j;
// 2、遍历，0号位处理过了，i从1开始
for(int i = 1; i < s.size(); ++i) {
// 3、比较i位置和j位置是否相等，不相等，next[j - 1]就记录了最长相等前后缀，这样进行回退
while(j > 0 && s[i] != s[j]) {
j = next[j - 1];
}
// 4、相等，移动j，为下一个循环i的移动与判断做准备
if(s[i] == s[j]) {
++j;
}
// 5、无论是否判断相等与否，为i的最长相等前后缀赋值，由j决定，要么有，要么为0
next[i] = j;
}
}
int strStr(string haystack, string needle) {
// 1、为模式串needle构造前缀表
vector<int> next(needle.size());
getNext(&next[0], needle);
// 2、准备索引j，控制模式串中当前能匹配上的最长位置
int j = 0;
// 3、遍历文本串
for(int i = 0; i < haystack.size(); ++i) {
// 3.1 如果文本串中当前索引i与模式串对应索引i不匹配，那么就用前缀表对j进行回退
while(j > 0 && haystack[i] != needle[j]) {
j = next[j - 1];
}
// 3.2 如果相等了，就移动j就好了
if(haystack[i] == needle[j]) {
++j;
// 4、j有移动的时候，可能完成了模式串的匹配，要检查
if(j == needle.size()) {
// 返回haystack中的下标
return i - (needle.size() - 1);
}
}
}
// 5、前面没返回就返回-1
return -1;
}
};
7.重复的子字符串
-
思路1：
KMP，如果存在重复子串t，那么s = n*t，并且s的最长相等前后缀是(m - 1) * t，此时 s / t 可以整除，因此，求解s的最长前后缀，用s的长度 - 最长前后缀长度（存放在最后一个索引位置），可以被s整除即存在
-
代码实现1：
class Solution {
public:
// 计算KMP前后缀
void getNext(int *next, const string &s) {
// 1、初始化第0个元素
int j = 0;
next[0] = j;
for(int i = 1; i < s.size(); ++i) {
// 2、如果不相等，j回退到next[j-1]
while(j > 0 && s[i] != s[j]) {
j = next[j - 1];
}
// 3、如果相等，j向后
if(s[i] == s[j]) {
++j;
}
// 4、更新i位置最长相等前后缀
next[i] = j;
}
}
bool repeatedSubstringPattern(string s) {
// 1、计算s的前缀表
vector<int> next(s.size());
getNext(&next[0], s);
// 2、计算差，判断
int sSize = s.size();
int maxNextLength = next[sSize - 1];
// 2.1 如果能整除，存在，注意判断maxNextLength要不为0
if(maxNextLength != 0 && sSize % (sSize - maxNextLength) == 0) {
return true;
}
// 2.2 不能整除，不存在
return false;
}
};
- 思路2：
- 移动匹配，如果s由重复子串组成，s+s中一定可以再出现一个s，这样判断就好了；
- 不过要注意s+s要去掉首尾字符，避免找到原来的两个s；
- 字符串
find()用法：如果没找到，判断是否等于std::string::npos；
- 代码实现2：
class Solution {
public:
bool repeatedSubstringPattern(string s) {
// 1、s+s
string t = s + s;
// 2、掐头去尾
t.erase(t.begin());
t.erase(t.end() - 1);
// 3、再判断包不包含s
if(t.find(s) != std::string::npos) {
return true;
}
return false;
}
};
8.总结篇
- 字符串是若干字符组成的有限序列，可以理解为字符数组；
- C语言：把一个字符串存入一个数组时，也把结束符 '\0'存入数组，并以此作为该字符串是否结束的标志；
- C++：提供一个string类，string类会提供 size接口，可以用来判断string类字符串是否结束，就不用'\0'来判断是否结束；
- vector< char > 和 string 区别：在基本操作上没有区别，但是 string提供更多的字符串处理的相关接口，例如string 重载了+，而vector却没有；
- 高频算法：
- 双指针法：反转字符串、反转字符串里的单词并删除冗余空格；
- 反转字符串：先整体反转在局部反转；
- KMP：重点理解前缀表；
双指针法
- 数组篇：移除元素，快慢双指针，快指针用于跳过要删除的元素，慢指针控制保留元素的位置；
- 字符串篇：
- 反转字符串：首尾双指针；
- 替换数字：先统计出要替换的个数，对字符串进行resize，然后双指针从后往前进行替换，以免从前往后时会有原有元素的移动；
- 反转单词：并删除空格，先按照移除元素的思路对多余空格进行移除，然后整体反转+局部反转实现单词反转；
- 链表篇：
- 反转链表：双指针；
- 删除链表倒数第N个节点：快慢双指针；
- 链表相交：尾部对齐以后快慢双指针；
- 环形链表：快慢双指针；
- N数之和：
- 两数之和：哈希；
- 三数之和、四数之和：用哈希逻辑会很复杂，双指针缩减一层时间复杂度；
栈与队列
1.栈与队列理论基础
- 基础：
- 栈：先进后出；
- 队列：先进先出；
- C++ STL的版本：
- HP STL，其他版本的C++ STL，一般是以HP STL为蓝本实现出来的；
- P.J.Plauger STL，参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的；
- SGI STL，参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。
- 栈：
- 提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)；
- 栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）；
- 所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。
- 栈的底层实现可以是vector，deque，list；默认以 deque为缺省情况下栈的底层结构；
- 队列：
- 同样不允许有遍历行为，不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构；
- 也不被归类为容器，而被归类为container adapter（ 容器适配器）。
2.用栈实现队列
-
思路：
- 两个栈实现队列先入先出——核心就是如何做先入先出的逻辑：
- 用一个栈主要用来装元素，另一个栈用来出元素，每次要出元素时，出元素的栈里面空了就把入元素栈的倒着进来就可以正序出去了
-
代码实现：
class MyQueue {
private:
std::stack<int> inStack;
std::stack<int> outStack;
public:
MyQueue() {
}
void push(int x) {
inStack.push(x);
}
int pop() {
// 关键点：如果outStack为空，就把inStack里面的元素倒进来，outStack出的时候就是正序了
if(outStack.empty()) {
while(!inStack.empty()) {
outStack.push(inStack.top());
inStack.pop();
}
}
// 题目保证空队列不会调用pop或者peek
// 弹出
// 1、先记录下要弹出的元素
int ret = outStack.top();
// 2、弹出
outStack.pop();
// 3、返回
return ret;
}
int peek() {
// 技巧：先调用pop，再塞回去
int ret = this->pop();
outStack.push(ret);
return ret;
}
bool empty() {
return inStack.empty() && outStack.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
3.用队列实现栈
-
思路：
- 用一个队列就可以实现，实现后入先出的关键点是用队列pop的时候，先将队列头的全都pop再push到队尾，然后就能pop出最后一个元素了
-
代码实现：
class MyStack {
public:
std::queue<int> q;
MyStack() {
}
void push(int x) {
q.push(x);
}
int pop() {
int qSize = q.size();
// 将原来末尾的元素移动到队列头
while(--qSize != 0) {
q.push(q.front());
q.pop();
}
// 弹出队头元素
int ret = q.front();
q.pop();
return ret;
}
int top() {
int ret = this->pop();
q.push(ret);
return ret;
}
bool empty() {
return q.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
4.有效的括号
-
思路：
- 栈——正确匹配只需要比较栈顶和当前元素，匹配就消去——即出栈；
- 技巧：每次左括号存入配对元素，如(实际存入)，方便相等判断；
- 对于右括号，与栈顶元素比较，不匹配直接false。
-
代码实现：
class Solution {
public:
bool isValid(string s) {
// 1、创建栈
std::stack<char> myStack;
// 2、遍历s
for(int i = 0; i < s.size(); ++i) {
char cur = s[i];
// 2.1 左括号放入其配对括号
if(cur == '(') myStack.push(')');
else if(cur == '[') myStack.push(']');
else if(cur == '{') myStack.push('}');
// 2.2 右括号的话比较是否配对
else if(myStack.empty() || cur != myStack.top()) return false;
// 2.3 匹配消去
else myStack.pop();
}
// 3、判断栈是否为空
return myStack.empty();
}
};
5.删除字符串中的所有相邻重复项
-
思路：
- 栈，栈顶元素和当前元素相同就删除
- C++语法知识点：
- 从其它容器遍历取出元素组成字符串操作：创建空字符串然后拼接；
- 字符串倒序操作：
std::reverse(s.begin(), s.end())；
-
代码实现：
// 思路：栈，栈顶元素和当前元素相同就删除
class Solution {
public:
string removeDuplicates(string s) {
// 1、定义栈
std::stack<char> st;
// 2、遍历字符串
for(char ch : s) {
// 2.1 如果ch和栈顶元素相同，删除两项
if(st.size() > 0 && ch == st.top()) {
// 当前元素直接跳过，栈顶元素弹出
st.pop();
}
else {
// 2.2 不相同，或者栈内为空，入栈
st.push(ch);
}
}
// 3、将栈内元素放入字符串并倒序
string ret = "";
while(!st.empty()) {
ret += st.top();
st.pop();
}
std::reverse(ret.begin(), ret.end());
return ret;
}
};
6.逆波兰表达式求值
-
思路：
- 栈，遇到数字入栈，遇到算符则取出栈顶两个元素计算，并将结果压入栈中；
- C++语法知识点：
- 注意传入参数
vector<string>& tokens，是一个向量，向量的每个元素是一个字符串，这点需要注意； - push进栈的字符串需要注意转换为数字，这里用的是字符串转int：
stoi，类似的还有stoll；
- 注意传入参数
-
代码实现：
// 思路：栈，遇到数字入栈，遇到算符则取出栈顶两个元素计算，并将结果压入栈中
class Solution {
public:
int evalRPN(vector<string>& tokens) {
// 1、定义栈
std::stack<int> st;
// 2、遍历tokens
for(int i = 0; i < tokens.size(); ++i) {
string s = tokens[i];
if(s == "+" || s == "-" || s == "*" || s == "/"){
// 2.1 如果为运算符，按照四种情况执行运算
int num2 = st.top();
st.pop();
int num1 = st.top();
st.pop();
int temp;
if(s == "+") {
temp = num1 + num2;
}
else if(s == "-") {
temp = num1 - num2;
}
else if(s == "*") {
temp = num1 * num2;
}
else if(s == "/") {
temp = num1 / num2;
}
// 结果入栈
st.push(temp);
}
else {
// 2.2 如果是数值，压入栈中，注意将字符串转换为数字
st.push(stoi(s));
}
}
// 3、栈中最后元素就是结果
return st.top();
}
};
7.滑动窗口最大值
-
思路：
- 单调队列，队列里面按照滑动窗口中的元素从队头到队尾单调递减，那么取出队头元素即可；
- 如何维护单调队列？
- 对于滑动窗口移入元素，其实不用保持所有元素，进元素的时候如果队尾的元素小于该元素就丢掉，然后把该元素放入，那些被丢掉的元素不可能成为当前窗口内最大值了；
- 对于滑动窗口移动移出的元素，如果恰等于队头的元素移除；
- 对于该单调队列按照上述规则可以知道：在该元素之前且比该元素小的按照移入规则不会在队列里（都被丢弃了），在该元素之后比该元素小的可能会成为后面窗口的最大值，此时还在队列里面（同时队列里也不会维持不可能成为最大值的）；
- C++语法知识点：
- 双端队列
deque：- 队头、队尾插入、移除：
q.push_back、q.push_front、q.pop_back、q.pop_front； - 获取队头、队尾元素：
q.front()、q.back()；
- 队头、队尾插入、移除：
- 向量
vector：- 插入元素：
vector.push_back()；
- 插入元素：
- 双端队列
-
代码实现：
class Solution {
// 定义单调队列类
private:
class MonotonousQueue {
public:
// 双端队列成员变量
std::deque<int> q;
// 移入元素
void push(int num) {
// 规则：只要队尾元素小于该元素，直接丢掉
while(!q.empty() && q.back() < num) {
q.pop_back();
}
q.push_back(num);
}
// 移出元素
void pop(int num) {
// 规则：要移除的元素和队头元素相同才丢掉，队头后面的都比队头进来的晚
if(num == q.front()) {
q.pop_front();
}
}
// 获得队头——也就是滑动窗口最大值
int front() {
return q.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
// 1、创建自定义单调队列
MonotonousQueue myMonotonousQueue;
std::vector<int> ret;
// 2、先放入开头k个元素
int i;
for(i = 0; i < k; ++i) {
// 2.1 只执行移入操作
myMonotonousQueue.push(nums[i]);
}
// 2.2 获得初始窗口最大值
ret.push_back(myMonotonousQueue.front());
// 3、遍历nums
for(; i < nums.size(); ++i) {
// 3.1 移出nums[i - k]
myMonotonousQueue.pop(nums[i - k]);
// 3.2 移入nums[i]
myMonotonousQueue.push(nums[i]);
// 3.3 获得滑动窗口最大值
ret.push_back(myMonotonousQueue.front());
}
return ret;
}
};
8.前K个高频元素
-
思路：
-
优先级队列，先用map统计各个元素出现的次数，然后放入优先级队列；
-
放入优先级队列的小技巧：采用小顶堆，容量为k，这样当元素超过k弹出队列头的最小的从而保持队列里面最大的
-
C++语法：
-
优先级队列创建：
priority_queue<T, Container, Compare> priority_queue<T> //直接输入元素则使用默认容器和比较函数 a) T就是Type为数据类型 b) Container是容器类型，（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector） c) Compare是比较方法，类似于sort第三个参数那样的比较方式，对于自定义类型，需要我们手动进行比较运算符的重载 -
实现比较方法
struct/class，注意决定排序的bool运算规则； -
pair 与 map；
-
-
注意最后从优先级队列取出的时候用参数 k 做遍历终点，不要用 size() 方法，会随队列弹出更新。
-
-
代码实现：
class Solution {
public:
// 小顶堆
struct compare {
public:
// 参数是pair，比较用第二个参数--频次
bool operator() (const pair<int, int> &l, const pair<int, int> &r) {
return l.second > r.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
// 1、统计频次
std::unordered_map<int, int> map;
for(int num : nums) {
map[num]++;
}
// 2、创建小顶堆优先队列
std::priority_queue<pair<int, int>, vector<pair<int, int>>, compare> priQue;
// 3、遍历map，放入元素，同时基于小顶堆，当元素超过k时弹出队头最小元素
for(std::unordered_map<int, int>::iterator it = map.begin(); it != map.end(); ++it) {
// 3.1 入队
priQue.push(*it);
// 3.2 检查队中元素是否超过k，如是，弹出栈顶小元素
if(priQue.size() > k) {
priQue.pop();
}
}
// 4、遍历队列取出结果，放入vector
std::vector<int> ret;
// for(int i = 0; i < priQue.size(); ++i) {
for(int i = 0; i < k; ++i) {
// 取出pair，将第一个元素放入
ret.push_back(priQue.top().first);
priQue.pop();
}
return ret;
}
};
9.栈与队列总结
- 栈与队列的理论基础：
- C++中stack，queue 是容器适配器，不是容器，底层容器使用不同的容器；
- 单调队列：保证队列里单调递增或递减，注意和优先级队列区分，单调队列不是单纯对窗口里面的数进行排序，记得其pop、push操作规则；
- 优先级队列：本质上是披着队列外衣的堆；
- 堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
二叉树
- 二叉树分类：
- 满二叉树：二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上；
- 完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置；
- 优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系；
- 二叉搜索树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树。
- 平衡二叉搜索树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树；
- C++中map、set、multimap、multiset的底层实现都是平衡二叉搜索树，unordered_map、unordered_set的底层实现是哈希；
- 二叉树的存储方式：链式存储与顺序存储；
- 链式存储方式就用指针， 顺序存储的方式就是用数组；
- 二叉树的遍历方式：
- 深度优先遍历：
- 前序遍历；
- 中序遍历；
- 后序遍历；
- 广度优先遍历：层序遍历；
- 深度优先遍历：
回溯算法
贪心算法
动态规划
单调栈
1、每日温度
- 题目链接：739. 每日温度 - 力扣（LeetCode）
- 思路：单调栈
- 要找每个元素后面第一个比他大的元素--栈内元素栈顶到栈底单调递增；
- 当新遍历一个元素，比较与栈顶元素的大小，当前元素大，对应栈顶元素下一个更大元素出现；
- 持续遍历，直到将当前元素放入栈中
- 代码实现：
// 思路：单调栈
// 要找每个元素后面第一个比他大的元素--栈内元素栈顶到栈底单调递增
// 当新遍历一个元素，比较与栈顶元素的大小，当前元素大，对应栈顶元素下一个更大元素出现
// 持续遍历，直到将当前元素放入栈中
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
// 1、创建结果变量
vector<int> ans = vector<int>(temperatures.size());
// 2、创建单调栈，并放入第一个元素，注意栈中元素放的是索引
stack<int> mystack;
mystack.push(0);
for(int i = 1; i < temperatures.size(); ++i) {
// 2.1 持续比较栈顶元素和当前元素
while(!mystack.empty() && temperatures[mystack.top()] < temperatures[i]) {
ans[mystack.top()] = i - mystack.top();
mystack.pop();
}
// 2.2 当前元素入栈
mystack.push(i);
}
// 3、返回结果
return ans;
}
};
- 知识点：
- 栈stack--是容器适配器而不是容器，容器适配器主要有栈适配器、队列适配器和优先队列适配器；
- 栈可以基于deque或vector进行实现；
2、下一个更大元素Ⅰ
-
思路：
- 关键：nums1是nums2的子集，直接对nums2单调栈处理，找到每个元素的下一更大元素
- 然后遍历，看nums1是否存在对应元素
-
代码实现：
// 思路：
// 关键：nums1是nums2的子集，直接对nums2单调栈处理，找到每个元素的下一更大元素
// 然后遍历，看nums1是否存在对应元素
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
// 1、先按单调栈处理nums2
// 用map装nums2的单调栈结果，键是元素，值是下一个更大元素
unordered_map<int, int> myMap;
// 栈里面装索引
stack<int> mystack;
mystack.push(0);
for(int i = 1; i < nums2.size(); ++i) {
// 找下一个更大的，栈顶到栈底应当单调递增
while(!mystack.empty() && nums2[mystack.top()] < nums2[i]) {
// 设置值
myMap[nums2[mystack.top()]] = nums2[i];
// 栈顶元素出栈
mystack.pop();
}
// 当前元素入栈
mystack.push(i);
}
// 2、遍历nums1，看map中是否有下一个更大元素
// 初始化结果
vector<int> ans = vector<int>(nums1.size(), -1);
// 遍历
for(int i = 0; i < nums1.size(); ++i) {
if(myMap.find(nums1[i]) != myMap.end()) {
ans[i] = myMap[nums1[i]];
}
}
return ans;
}
};
- 知识点：
- 初始化为指定个数、指定值的vector：
vector<T> vec(nums, val);； - eg：
std::vector<int> myVector(5, 10);
- 初始化为指定个数、指定值的vector：
3、下一个更大元素Ⅱ
- 题目链接：503. 下一个更大元素 II - 力扣（LeetCode）
- 思路：单调栈，循环数组解决--将nums拼接两个，第一个里面对应元素都能找到下一个更大元素
- 代码实现：
// 思路：单调栈，循环数组解决--将nums拼接两个，第一个里面对应元素都能找到下一个更大元素
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
// 1、数据准备
int numsSize = nums.size();
// 返回结果
vector<int> ans(numsSize, -1);
// nums拼两个
vector<int> doubleNums(2 * numsSize);
for(int i = 0; i < 2 * numsSize; ++i) {
doubleNums[i] = nums[i % numsSize];
}
// 2、单调栈逻辑
stack<int> st;
// 里面放索引，这样才能对应住位置
st.push(0);
for(int i = 1; i < doubleNums.size(); ++i) {
// 下一个更大，所以栈顶到栈底递增
while(!st.empty() && doubleNums[st.top()] < doubleNums[i]) {
// 注意索引会是ans尺寸的两倍
ans[st.top() % numsSize] = doubleNums[i];
st.pop();
}
st.push(i);
}
return ans;
}
};
- 知识点：
- 改进点：可以不用创建出来 doubleNums，直接在遍历的时候按照2倍 nums 的 size ，然后处理好索引和实际 nums 的索引即可。
4、接雨水
- 题目链接：
- 思路：
- 代码实现：
- 知识点：
5、柱状图中最大的矩形
- 题目链接：
- 思路：
- 代码实现：
- 知识点：