leetcode刷题集合（简单篇）

type

status

date

slug

summary

859.亲密字符串

题目描述

给你两个字符串 s 和 goal ，只要我们可以通过交换一次 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。

交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。

例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。

思路

长度不相等时，返回false

s等于goal时，判断是否还有大于2频次的字母，存在返回true，否则false

s不等于goal时，给定两个初始化为-1的索引first和second，遍历s，依次将其赋值为遇到的两个对应不相等字符的索引，最后判断交换后是否相等即可

代码

28. 找出字符串中第一个匹配项的下标

题目描述

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

两种解法

暴力

1047. 删除字符串中的所有相邻重复项

题目描述：

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

思路

用栈的数据结构来存储之前访问的且留下来的元素，栈顶即为上一个访问元素

遍历字符串，只需要判断栈顶和当前字符的关系来进行删除或保留的操作

最后反转结果字符串

代码

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

思路

首先考虑相距最远的两个柱子，此时的水量=索引差*矮一点的柱子高度

接下来就是考虑怎么移动柱子的问题，显然向左移动高的柱子不会改变最小高度甚至可能会减小高度，加上宽度减少，所以面积一定会减少

所以要移动矮一点的柱子，才可能会增加面积，记录每次移动的后的面积并更新最大面积，直到两个索引相遇

代码

134. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的。

说明:

示例 1:

示例 2:

思路

证明命题:如果总的 gas 量大于 cost ，则一定有解。

1、当 n = 2 时，一定可以找到一个点 A ，它的 gas >= cost ;假设另一个点为 B ，则 A 点可以到达 B 点，到达 B 点之后总gas 量根据题设，大于 B 点的 cost ，所以也可以回到 A 点;

2、当n = 3 时，一定可以找到两个点，它们的 gas 之和大于等于 cost 之和，把他们当作一个整体点 A ，剩余的点为 B 。那么根据 n = 2 的情况，A 可以到达 B 再返回A 。对于 A 内部来说，它们也符合 n = 2 的情况，所以同样可以互通。

3、当 n > 3时，一定可以找到 n - 1 个点，它们的 gas 之和大于等于 cost 之和，把他们当作一个整体点 A ，剩余的点为B 。那么根据 n - 1 的情况，A 可以到达 B 再返回 A 。对于 A 内部来说，它们也符合 n - 1 的情况，所以同样可以互通。

所以，证明若 gas 总量大于 cost ，则一定有解。

代码

138. 复制带随机指针的链表

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

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

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

返回复制链表的头节点。

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

val：一个表示 Node.val 的整数。

random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码只接受原链表的头节点 head 作为传入参数

思路

先将原有的节点都创建出来

再遍历复制其对应的关系

其中的map的key为原来的旧节点，value为节点值相同的新创建的节点

代码

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

思路

快慢指针

假设如下

相遇时慢指针走了x+y步，快指针走了x+y+n(y+z)

于是有x+y = (x+y+n(y+z))/2

代码

我真的学不下去了啊啊啊啊！

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

思路

先从小到大排序

三个指针 i left right

遍历i 每次只需要查看i右边的数，left right 向中间靠近

如果三者之和 == 0 加入结果集

如果小于0 left++，大于0 right--

关于去重

遍历i时，除了第一个元素，判断当前元素和i-1 相等就跳过

遍历left 和 right 时，如果当前left和下一个left的元素相等跳过

同理，当前right和下一个right（right--）相等时跳过

代码

160. 相交链表

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

代码

朴素解法（我自己想的）

快一点的

相当于让这两个指针都走一遍所有的节点相遇的第一个节点就是目标节点

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

思路

用map存储当前遍历的 key数和 val索引

遍历时target和当前的数做差值查看map是否存在对应的数如果有返回如果没有存到map中继续遍历

代码

2. 两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

思路

越靠近头位数越低

所以可以同时遍历两个链表相加当前位的两个数

如果有进位做标记

代码

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

每个右括号都有一个对应的相同类型的左括号。

思路

用栈来匹配最近的括号

字符串长度必须为偶数因为要两两匹配

及时判断不合理的情况直接返回可以减少运行时间

代码

206. 反转链表

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

思路

递归

在递归回溯的时候更改当前节点的next指针和当前节点的下一个节点的next指针

代码

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路

优先队列

根据题意，正好符合优先队列的特征

默认优先级的优先队列 pop的是最小值

相当于优先队列替我们维护了一个识别大小顺序的一组数据，top和pop的都是最小值

这样就只需要保证优先队列的长度为k并且每当访问的数据大于top（最小值），就推入

代码

21. 合并两个有序链表

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

思路

比较直接的一道题，同时遍历这两条链表按照大小插入即可

最后将剩余没有遍历的那部分链表接到最后即可

代码

224. 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

思路

只有括号和加减法

减法可以等效成加一个负数

所以需要一个标志变量，用来标记前一个运算符为加法还是减法

遇到左括号就把之前算的结果和左括号之前的标识位入栈

遇到右括号就将之前算的结果和当前结果整合起来

代码

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾

int pop() 从队列的开头移除并返回元素

int peek() 返回队列开头的元素

boolean empty() 如果队列为空，返回 true ；否则，返回 false

思路

两个栈实现

一个用于推入队列

一个用于推出队列

代码

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

思路

快慢指针

先通过快慢指针将原链表一分为二

slow要么在中间节点要么是中间的左边（奇偶节点数

将右侧链表翻转

同时遍历左侧部分和右侧翻转后的节点比较节点值即可

注意临界情况：

空和一个节点都为回文链表
两个节点如果值相同也是回文链表

翻转链表用的递归

代码

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值

思路

一开始窗口没有任何值，所以窗口是需要生成的

生成后每次移动都要判断当前窗口的最大值

比较朴素的思路就是移动一次遍历判断一次，显然复杂度为O(n*k)有一点高

遍历数组的n是无法改变的，所以我们要使得拿到当前窗口的最大值的复杂度降低

考虑维护一个递减的数组，并且可以随时从头和尾删除，vector和deque双端队列都可以实现

这里用的双端队列

维护一个递减的双端队列，重复判断当前考察的元素是否大于队尾，不断将队尾元素移出直到能够放入队列

代码

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

示例 2:

提示:

1 <= s.length, t.length <= 5 * 104

s 和 t 仅包含小写字母

思路

只有小写字母就直接用一个26大小的数组存储每个字符出现的次数

遇到s中的就++，遇到t中的就--

最后判断数组中的26个位置是否都为0即可

代码

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

思路

类似于之前的反转链表

只不过现在要做的是每次递归两个每个函数中需要交换两个节点后返回那个头节点

代码

25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

思路

这是反转链表的进阶版

与之前不同的是，要进行多次的局部反转

每个子链的反转和之前一样

不同的是如何找到子链对应的那部分和如何将新反转好的链表接起来

用到几个变量的解释

pre : 本次要反转链表的头节点（上次反转链表的最后一个节点或者是dummy）

start：本次要反转链表的第一个节点（头节点的next）

end：本次要反转的链表的最后一个节点

next：下次要反转的第一个节点（为了能把新反转的链表和后面的接起来）

算法过程

找到本次的k个节点的链表用end后移k次

保存next = end→next,并将end节点和后面的节点断开,第一个节点也要和上一个节点断开（pre—>next = null)

设置pre→next = reverse(start)（reverse函数就是一个递归反转链表的函数，比较好实现）

反转好这部分剩下的就是将断开的和后面的连起来并更新pre和end值

继续下一个k长的链表的反转

代码

328.奇偶链表

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是奇数， 第二个节点的索引为偶数，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

思路

设置两个指向奇数和偶数hao节点的指针

奇数的下一个节点应该是当前偶数的下一个节点

然后将奇数节点更新为他的下一个节点此时奇数节点指向当前偶数的下一个

所以偶数的next应该为当前奇数的next

最后将两个链表接起来就行了

代码

376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

思路

三种状态：开始，上升，下降

如果之前的状态是开始状态：只需要比较当前和上一个元素的大小关系并将此次情况标记为上升或者下降总长度加一

如果之前是上升状态：那么只有当前元素和上一个元素处于下降状态时才做处理并标记为下降状态

如果之前是下降状态：那么只有当前元素和上一个元素是上升状态才做处理，并将本次状态标记为上升状态

持续遍历即可算出最长的长度 da