刷题记录——LeetCode

本文最后更新于：2021年7月28日 下午

刷题记录——LeetCode

数组

二分法

适用情况

  • 在一组有序数字中，进行查找操作

注意

  • 根据不同的情况，要对while的循环条件和里面的if选择条件进行修改

基本格式

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
```



**题目练习**

- [704. Binary Search](https://leetcode-cn.com/problems/binary-search/)
- [35. Search Insert Position](https://leetcode-cn.com/problems/search-insert-position/)
- [34. Find First and Last Position of Element in Sorted Array](https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)(==题解==)---2021.7.1
- [69. Sqrt(x)](https://leetcode-cn.com/problems/sqrtx/)（==题解==）----2021.7.2
- [367. Valid Perfect Square](https://leetcode-cn.com/problems/valid-perfect-square/)---2021.7.3

### 快慢指针法----移除元素

**适用情况**

- 在有序数组中，需要移动元素位置（包括移除、移动元素）

**注意**

- 不同的移除条件，循环里有不同的写法

**题目练习**

- [27.Remove Element]([26. Remove Duplicates from Sorted Array](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/))
- [26.Remove Duplicates from Sorted Array]([26. Remove Duplicates from Sorted Array](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/))---2021.7.3
- [283.Move Zeroes](https://leetcode-cn.com/problems/move-zeroes/)
- [844.Backspace String Compare](https://leetcode-cn.com/problems/backspace-string-compare/)---2020.7.5
- [977.Squares of a Sorted Array](https://leetcode-cn.com/problems/squares-of-a-sorted-array/)

### 滑动窗口

**适用情况**

- 查找连续子数组问题，不断的调节子序列的起始位置和终止位置，从而得出我们想要的结果
- 特殊情况也可使用前缀和思想

**注意**

- 根据要求，设计每次窗户扩展后的处理方法非常关键

**模版**

```c++
根据题目，for循环内窗口扩展操作作准备
int i=0;	//窗口起始位置
int result=？		//看情况初值（最大或最小），保存每次结果和最终结果
for（int j=0;j<size;j++){	//滑动窗口开始扩展
    根据题目要求，设计每次窗户扩展的处理操作并保存记录
    while(窗口操作后的记录的临界情况){	//记录数据，并开始滑动窗口
        int ans=j-i+1;	//此时窗口大小
        result=result>ans?result:ans;	//根据要求写判断逻辑
        窗口起始位置向前滑动后对记录的影响
        i++;	//窗口起始位置向前滑动
    }
}

题目练习

其它

链表

用while循环遍历链表时，要根据自己的处理逻辑，选择是用while(node->next)还是while(node)，一般来说如果能确定进入循环前的node必有值的话，就用前一个，否则用后一个

虚拟头结点

适用情况

  • 一般来说，如果对单链表进行操作，除头结点外结点操作基本相同，那么可以添加一个虚拟头结点，使得原头结点变成子节点，统一操作

注意

  • 工作指针指向虚拟头结点后，要从node->next开始判断
  • 返回vir_head->next才是真正头指针

模板

1
2
3
ListNode* vir_head=new ListNode();	//初始化虚拟结点
vir_head->next=head;	//构造虚拟头结点
ListNode* node=vir_head;	//工作指针从虚拟结点开始

题目练习

链表翻转

方法

  • 头插法：新建一个虚拟头结点，利用头插法构造逆序链表
  • 双指针法：利用前后指针，将next的指向逆转过来

题目练习

双指针法——一遍找倒数位置元素

注意

  • 要确定last、fast指针的距离，以及要选择最后fast是走到最后一个位置处，还是走到null处时，此时的fast的位置到底是不是符合要求的

题目

双指针法——找链表相交结点位置

注意

  • 要先确定两个指针的距离，然后同步移动找到指针值相同的结点即可

题目

环形链表——确定环及环入口位置

注意

  • 根据快慢指针找环
  • 环的入口位置需要数学证明

题目

  • [142.Link List Cycle II（题解）—2021.7.13

哈希表

适用情况

  • 需要记录元素出现的次数–map
  • 需要记录元素是否出现过–set\map

注意

  • 如果数据比较少，key可以用int且最大值不大，直接用数组即可

  • 如果数据比较少，但特别分散、跨度大，可以用unordered_map

  • 如果只是需要记录是否出现过，可以用unordered_set作集合操作，用find判断

    也可用map只读一次数据

题目

扩展阅读

字符串

反转

题目

栈和队列

预备知识

  • 栈、队列是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的。STL中栈的队列往往不被归类为容器，而被归类为container adapter（容器适配器）

注意

  • stack.pop()返回值是void,stack.top()返回值才是具体数值

应用类型

  • 对称匹配类问题——栈
    • 两个元素匹配，匹配后可再有操作

题目练习