目录
[toc]
1 两数之和
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
我的做法如下,直接暴力,复杂度是O(n2),我们试图通过遍历数组的其余部分来寻找它对应的目标,这将耗费O(n)*O(n)的时间。
也可以使用哈希表
优化版的哈希表如下:
2 两数相加(链表)(回到目录)
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
例如:
我一开始的做法:错的!
参考做法
3 无重复字符的最长子串(回到目录)
给定一个字符串,找出不含有重复字符的最长子串的长度。
示例:
|
|
更简便的方法,维护一个窗口
4 两个排序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
你可以假设 nums1 和 nums2 均不为空。
示例 1:
示例 2:
|
|
5 最长回文子串(回到目录)
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1:
示例 2:
|
|
6 Z字形变换(回到目录)
将字符串 “PAYPALISHIRING” 以Z字形排列成给定的行数:
|
|
7 反转整数
给定一个 32 位有符号整数,将整数中的数字进行反转。
示例 1:
示例 2:
示例 3:
|
|
8 字符串转整数 (atoi)(回到目录)
实现 atoi,将字符串转为整数。
在找到第一个非空字符之前,需要移除掉字符串中的空格字符。如果第一个非空字符是正号或负号,选取该符号,并将其与后面尽可能多的连续的数字组合起来,这部分字符即为整数的值。如果第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。
字符串可以在形成整数的字符后面包括多余的字符,这些字符可以被忽略,它们对于函数没有影响。
当字符串中的第一个非空字符序列不是个有效的整数;或字符串为空;或字符串仅包含空白字符时,则不进行转换。
若函数不能执行有效的转换,返回 0。
说明:
假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。如果数值超过可表示的范围,则返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
|
|
9 回文数
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
|
|
10. 正则表达式匹配(回到目录)
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符。
‘*’ 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ,而不是部分字符串。
说明:
s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。
|
|
11 盛水(回到目录)
LINK
给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
我的做法是错的,以为只需要找到最大的两个数,其实不是!还需要考虑index的距离。
还有一种做法,不知道哪里错了。(后来发现是temp的地方放错了!!!)
下面的这个方法可以ac:
12 整数转换成罗马数字(回到目录)
我的做法如下:
参考做法
13 罗马数字转换城整数(回到目录)
|
|
15 三数之和(回到目录)
链接:
给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意: 答案中不可以包含重复的三元组。
|
|
启发于4数之和的做法,有以下的代码:
16 最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
与 target 最接近的三个数的和为 2(-1 + 2 + 1 = 2).
可以通过的做法之一,使用左右指针往中间夹逼。
17 电话号码的字母组合(回到目录)
定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1:
不对应任何字母。
示例:
|
|
==大坑==:
实际上这行代码是省略了的,因为对于一个字符串来说,结束符是‘\0’,index加到最后面递归函数自然会return,所以可以不用return。我一开始,是直接在res.push_back(local);
的下一行加return,那肯定是错的。因为index还没大于digits.size,就不能return.
18 四数之和(回到目录)
|
|
19 删除倒数第N个节点(回到目录)
我一开始的做法
21 合并两个有序链表(回到目录)
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
|
|
20 有效的括号(回到目录)
给定一个只包括 '(',')','{','}','[',']'
的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
23 合并K个有序链表(回到目录)
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
方法1:分治归并
方法2: 将所有的节点放在一个vector,然后再排序,最后相连。
24 两两交换链表中相邻的节点(回到目录)
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
说明:
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
26 删除排序数组中的重复项(82,83)(回到目录)
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
示例 2:
你不需要考虑数组中超出新长度后面的元素。
方法1
方法2(我更倾向)
快慢指针:同方法2
80 删除排序数组中的重复项 II(回到目录)
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
|
|
31 下一个排列(回到目录)
实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
32 最长有效括号(回到目录)
给定一个只包含 ‘(‘ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。
使用栈
33 搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
|
|
二分查找
这道题让在旋转数组中搜索一个给定值,若存在返回坐标,若不存在返回-1。我们还是考虑二分搜索法,但是这道题的难点在于我们不知道原数组在哪旋转了,我们还是用题目中给的例子来分析,对于数组[0 1 2 4 5 6 7] 共有下列七种旋转方法:
二分搜索法的关键在于获得了中间数后,判断下面要搜索左半段还是右半段,我们观察上面红色的数字都是升序的,由此我们可以观察出规律,如果中间的数小于最右边的数,则右半段是有序的,若中间数大于最右边数,则左半段是有序的,我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内,这样就可以确定保留哪半边了,代码如下:
34 在排序数组中查找元素的第一个和最后一个位置(回到目录)
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]。
|
|
二分查找法:
使用两次二分查找法,第一次找到左边界,第二次调用找到右边界即可
35 搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
视频上解法
其他解法1
其他解法2:二分查找法
39 组合总和 I
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
示例 1:
示例 2:
|
|
40 组合总和 II(回到目录)
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明:
所有数字(包括目标数)都是正整数。
解集不能包含重复的组合。
示例 1:
示例 2:
方法1
另一种做法:使用set容器,代码和上面那题一样的
45 跳跃游戏 II
给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
|
|
46 全排列
给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
|
|
注:我们来仔细推敲一下循环体里的代码,当我们对序列进行交换之后,就将交换后的序列除去第一个元素放入到下一次递归中去了,递归完成了再进行下一次循环。这是某一次循环程序所做的工作,这里有一个问题,那就是在进入到下一次循环时,序列是被改变了。可是,如果我们要假定第一位的所有可能性的话,那么,就必须是在建立在这些序列的初始状态一致的情况下,所以每次交换后,要还原,确保初始状态一致。
47 全排列II(回到目录)
给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:
|
|
48 旋转图像(回到目录)
给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。
说明:你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
代码
49 字母异位词分组
给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
示例:
说明:
所有输入均为小写字母。
不考虑答案输出的顺序。
|
|
另一种更为巧妙地方法:使用哈希
51 N皇后(回到目录)
|
|
53 最大子序和
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
进阶:
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。
动态规划
常规方法
55 跳跃游戏(回到目录)
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
示例 2:
代码
另一个好的解法
61 旋转链表(回到目录)
给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。
代码
64 最小路径和
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例:
代码1:
代码2:
66 加一(回到目录)
给定一个非负整数组成的非空数组,在该数的基础上加一,返回一个新的数组。
最高位数字存放在数组的首位, 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
67 二进制求和(回到目录)
给定两个二进制字符串,返回他们的和(用二进制表示)。
输入为非空字符串且只包含数字 1 和 0。
示例 1:
示例 2:
|
|
69 x 的平方根(回到目录)
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
解法1
解法2
70 爬楼梯答(回到目录)
假设你正在爬楼梯。需要 n 步你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
|
|
76 最小覆盖子串
给定一个字符串 S 和一个字符串 T,请在 S 中找出包含 T 所有字母的最小子串。
示例:
说明:
如果 S 中不存这样的子串,则返回空字符串 “”。
如果 S 中存在这样的子串,我们保证它是唯一的答案。
77 组合(回到目录)
给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。
示例:
递归回溯
78 子集(回到目录)
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
小象写法
for循环里递归
90 子集 II(回到目录)
给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
小象解法:
for循环里面递归
82 删除排序链表中的重复元素II(回到目录)
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。
示例 1:
示例 2:
新建链表头结点指针pDel,pDel->next=head
,并设置指针prev
指针指向pDel
,curr
指针指向head->next
(代表遍历指针);当curr->next
不为NULL
,如果curr->next->val == curr->val,curr=curr->next
;如果curr->next->val != curr->val
;则需判断prev->next=curr
?如果是,则prev=curr
;如果不是,则prev->next=curr->next
.(这里是说,prev
先假设一个next
指针,即curr=curr->next
;当进行下一步判断时,如果curr->next->val != curr->val
且 prev->next==curr
,则说明假设正确,prev直接指向curr)
83 删除排序链表中的重复元素(回到目录)
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
示例1:
|
|
示例2:
代码
86 分割链表(回到目录)
给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
|
|
88 合并有序数组
给定两个有序整数数组nums1
和 nums2
,将nums2
合并到nums1
中,使得num1
成为一个有序数组。
说明:
初始化 nums1
和 nums2
的元素数量分别为m
和n
。
你可以假设nums1
有足够的空间(空间大小大于或等于 m + n
)来保存nums2
中的元素。
示例:
|
|
92 反转链表II(回到目录)
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:1 ≤ m ≤ n ≤ 链表长度
。
示例:
|
|
94 二叉树的中序遍历(144,145)(回到目录)
递归方法
迭代方法
101 对称二叉树(回到目录)
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树[1,2,2,3,4,4,3]
是对称的。
代码
102 二叉树的层次遍历
非递归
分析:先建立一个queue,然后先把根节点放进去,这时候找根节点的左右两个子节点,这时候去掉根节点,此时queue里的元素就是下一层的所有节点,用一个for循环遍历它们,然后存到一个一维向量里,遍历完之后再把这个一维向量存到二维向量里,以此类推,可以完成层序遍历。代码如下:
|
|
递归做法
107 二叉树的层次遍历 II
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
递归方式
迭代方式
104 二叉树的最大深度(递归)
深度优先
宽度优先
111 二叉树的最小深度(回到目录)
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
|
|
108 将有序数组转换为二叉搜索树(回到目录)
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:
代码
109 有序链表转换二叉搜索树
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
使用了递归,和那个24题差不多,关键是如何找到链表的中间位置。
110 平衡二叉树(回到目录)
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
示例 2:
代码
112 路径之和(二叉树)(回到目录)
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
118 杨辉三角
给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
119 杨辉三角II(回到目录)
给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。
示例:
|
|
125 验证回文串(回到目录)
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
|
|
121 买卖股票的最佳时机(回到目录)
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
134 加油站
在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。
如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1。
说明:
如果题目有解,该答案即为唯一答案。
输入数组均为非空数组,且长度相同。
输入数组中的元素均为非负数。
示例 1:
贪心相关:
135 分发糖果(回到目录)
老师想给孩子们分发糖果,有 N个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。
你需要按照以下要求,帮助老师给这些孩子分发糖果:
每个孩子至少分配到 1 个糖果。
相邻的孩子中,评分高的孩子必须获得更多的糖果。
那么这样下来,老师至少需要准备多少颗糖果呢?
示例 1:
示例 2:
思路:
假设每个孩子分到的糖果数组为A[N]
,初始化为{1},因为每个人至少分到一颗糖。
1、与前面的邻居比较,前向遍历权重数组ratings,如果ratings[i]>ratings[i-1],则A[i]=A[i-1]+1
;
2、与后面的邻居比较,后向遍历权重数组ratings,如果ratings[i]>ratings[i+1]且A[i]<A[i+1]+1
,则更新A
,A[i]=A[i+1]+1
;
3、对A求和即为最少需要的糖果。
时间复杂度:O(n)
空间复杂度:O(n)
|
|
136 只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
我的做法
按位异或
用到位运算之异或的特性:n ^ n = 0, 0 ^ x = x。
137 只出现一次的数字II(回到目录)
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现三次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
我的做法
位运算
141 环形链表(回到目录)
给定一个链表,判断链表中是否有环。
方法1
方法2
142 环形链表II
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
说明:不允许修改给定的链表。
144 二叉树的前序遍历
题目描述提示帮助提交记录社区讨论阅读解答
给定一个二叉树,返回它的 前序 遍历。
示例:
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
递归方法
迭代方法
145 二叉树的后序遍历
递归方法
递归1
递归2
迭代法
160 求两个链表的交点。(回到目录)
已知链表A的头节点指针headA,链表B的头节点指针headB,两个链表相交,求两个链表交点对应的节点。
方法一:使用std中的set函数
方法二
169 求众数
给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在众数。
示例 1:
示例 2:
|
|
189 旋转数组
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
示例 1:
示例 2:
我的做法
191 位1的个数
编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。
示例 :
示例 2:
|
|
法2:位运算
199 二叉树的右视图(回到目录)
递归做法
普通方法
206 反转链表(回到目录)
反转一个单链表。
示例:
|
|
215 数组中的第k个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
|
|
225 用队列实现栈
|
|
226 翻转二叉树(回到目录)
使用递归方法
非递归
258 各位相加(回到目录)
给定一个非负整数 num,反复将各个位上的数字相加,直到结果为一位数。
解释: 各位相加的过程为:3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数,所以返回 2。
进阶:
你可以不使用循环或者递归,且在 O(1) 时间复杂度内解决这个问题吗?
递归方法
循环方法
295 数据流的中位数(回到目录)
中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。
例如:
示例:
|
|
315 计算右侧小于当前元素的个数(回到目录)
给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例:
|
|
389 找不同
给定两个字符串 s 和 t,它们只包含小写字母。
字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
示例:
|
|
402 移掉k个数字(回到目录)
给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
示例 1 :
示例 2 :
示例 3 :
|
|
414 第三大的数
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
|
|
520 检测大写字母(回到目录)
给定一个单词,你需要判断单词的大写使用是否正确。
我们定义,在以下情况时,单词的大写用法是正确的:
全部字母都是大写,比如”USA”。
单词中所有字母都不是大写,比如”leetcode”。
如果单词不只含有一个字母,只有首字母大写, 比如 “Google”。
否则,我们定义这个单词没有正确使用大写字母。
注意: 输入是由大写和小写拉丁字母组成的非空单词。
633 平方数之和
给定一个非负整数c,你要判断是否存在两个整数a和b,使得$a^{2}+b^{2}=c$
我的做法如下:
下面这种方法用到了集合set,从0遍历到c的平方根,对于每个i*i
,都加入集合set中,然后计算c-i*i
,如果这个差值也在集合set中,返回true,遍历结束返回false,参见代码如下:
784 字母大小写全排列(回到目录)
给定一个字符串S,通过将字符串S中的每个字母转变大小写,我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
|
|
或者:
50. Pow(x, n)(回到目录)
实现 pow(x, n) ,即计算 x 的 n 次幂函数。
|
|
54 螺旋矩阵(59)(回到目录)
给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。
|
|
58 最后一个单词的长度(回到目录)
给定一个仅包含大小写字母和空格 ‘ ‘ 的字符串,返回其最后一个单词的长度。
如果不存在最后一个单词,请返回 0 。
说明:一个单词是指由字母组成,但不包含任何空格的字符串。
示例:
|
|
59 螺旋矩阵 II(54)(回到目录)
题目描述提示帮助提交记录社区讨论阅读解答
给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
|
|
62 不同路径(回到目录)
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径?
例如,上图是一个7 x 3 的网格。有多少可能的路径?
说明:m 和 n 的值均不超过 100。
方法1
|
|
方法2
这跟之前那道 Climbing Stairs
爬梯子问题 很类似,那道题是说可以每次能爬一格或两格,问到达顶部的所有不同爬法的个数。而这道题是每次可以向下走或者向右走,求到达最右下角的所有不同走法的个数。那么跟爬梯子问题一样,我们需要用动态规划Dynamic Programming
来解,我们可以维护一个二维数组dp,其中dp[i][j]表示到当前位置不同的走法的个数,然后可以得到递推式为:dp[i][j] = dp[i - 1][j] + dp[i][j - 1],
这里为了节省空间,我们使用一维数组dp,一行一行的刷新也可以,代码如下:
63 不同路径 II(回到目录)
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明:m 和 n 的值均不超过 100。
|
|
98. 验证二叉搜索树(回到目录)
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
|
|
120 三角形最小路径和(回到目录)
给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如,给定三角形:
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
使用常规的动态规划解法
使用原地覆盖
198 打家劫舍(回到目录)
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
|
|
213 打家劫舍 II(回到目录)
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
在打家劫舍(198)的基础上改动,先去掉第一个,计算一下最高金额,然后只去掉最后一个,计算最高金额。然后比较两种方式的结果,取较大值。
287 寻找重复数(回到目录)
给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。
不能更改原数组(假设数组是只读的)。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字,但它可能不止重复出现一次。
分析:二分查找这道题和抽屉原理差不多,例如九个抽屉是个钥匙,一定会有一个抽屉是两个要是的。题目要求我们不能改变原数组,即不能给原数组排序,又不能用多余空间,那么哈希表神马的也就不用考虑了,又说时间小于O(n2),也就不能用brute force的方法,那我们也就只能考虑用二分搜索法了,我们在区别[1, n]中搜索,首先求出中点数mid,然后遍历整个数组,统计所有小于等于mid的个数。如果count 小于等于mid, 说明 1 到 mid 这些数字没有重复项, 重复项在右半边 mid+1 到n, 所以缩小到右半边继续搜索;如果count 大于mid, 说明 1 到 mid 这些数字中有重复项,缩小到 左半边继续搜索。
303 区域和检索 - 数组不可变(回到目录)
给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。
示例:
说明:
你可以假设数组不可变。
会多次调用 sumRange 方法。
动态规划
441 排列硬币(回到目录)
你总共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须正好有 k 枚硬币。
给定一个数字 n,找出可形成完整阶梯行的总行数。
n 是一个非负整数,并且在32位有符号整型的范围内。
|
|
442 数组中重复的数据(回到目录)
给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗?
示例:
使用正负替换法,由于数组中的数字都是在[1,n]区间内,所以,可以数组的元素可以转化成index,将访问过的元素取相反数。如果再次遇到这个数(此时必然是负数了),则将它加入result数组。
461 汉明距离(回到目录)
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y,计算它们之间的汉明距离。
注意:
0 ≤ x, y < 231.
分析:只要将x和y的二进制形式的每一位取出来按位异或,若为1,则res++,最后的res就是汉明距离。
526 优美的排列(回到目录)
假设有从 1 到 N 的 N 个整数,如果从这N个数字中成功构造出一个数组,使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个,我们就称这个数组为一个优美的排列。
条件:
第 i 位的数字能被 i 整除
i 能被第 i 位上的数字整除
现在给定一个整数 N,请问可以构造多少个优美的排列?
说明:
N 是一个正整数,并且不会超过15。
分析:
这道题给了我们1到N,总共N个正数,然后定义了一种优美排列方式,对于该排列中的所有数,如果数字可以整除下标,或者下标可以整除数字,那么我们就是优美排列,让我们求出所有优美排列的个数。那么对于求种类个数,或者是求所有情况,这种问题通常要用递归来做。而递归方法等难点在于写递归函数,如何确定终止条件,还有for循环中变量的起始位置如何确定。那么这里我们需要一个visited数组来记录数字是否已经访问过,因为优美排列中不能有重复数字。我们用变量pos来标记已经生成的数字的个数,如果大于N了,说明已经找到了一组排列,结果res自增1。在for循环中,i应该从1开始,因为我们遍历1到N中的所有数字,如果该数字未被使用过,且满足和坐标之间的整除关系,那么我们标记该数字已被访问过,再调用下一个位置的递归函数,之后不要忘记了恢复初始状态。
|
|
667 优美的排列 II(回到目录)
定两个整数 n 和 k,你需要实现一个数组,这个数组包含从 1 到 n 的 n 个不同整数,同时满足以下条件:
① 如果这个数组是 [a1, a2, a3, … , an] ,那么数组 [|a1 - a2|, |a2 - a3|, |a3 - a4|, … , |an-1 - an|] 中应该有且仅有 k 个不同整数;.
② 如果存在多种答案,你只需实现并返回其中任意一种.
提示:
n 和 k 满足条件 1 <= k < n <= 104.
分析:这题的意思是给出1到n的不同整数,求k种不同相邻数的绝对值差值情况下的排列(任意一种即可)。
其实,k的最大值是n-1,使用最小最大相邻就可以了。
- 如果给出n=4,k=2,则ans=[4,1,2,3],也就是说,把最大数放在最小数之前,k自动减1,当k减到1时,之后的数按升序排列,就是两种排法了。
如果给出n=4,k=3,则ans=[1,4,2,3],把最大数依次插入在最小的数之后,当k减到1时,之后的数依次按升序排列。
12345678910111213141516171819202122232425262728293031class Solution {public:vector<int> constructArray(int n, int k){vector<int> res;int i=1,j=n;while(i<=j){if(k>1){if(k%2){res.push_back(i);i++;}else{res.push_back(j);j--;}k--;}else{res.push_back(i);i++;}}return res;}};
简化版的代码
283 移动零(回到目录)
题目描述提示帮助提交记录社区讨论阅读解答
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
说明:
- 必须在原数组上操作,不能拷贝额外的数组。
- 尽量减少操作次数。
分析:这道题很简单,使用双指针i和j,同时指向0。其中i用于扫描nums数组的每一个元素,遇到非零的元素,就和nums[j]交换,然后j++。
|
|
605 种花问题(回到目录)
假设你有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花卉不能种植在相邻的地块上,它们会争夺水源,两者都会死去。
给定一个花坛(表示为一个数组包含0和1,其中0表示没种植花,1表示种植了花),和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花?能则返回True,不能则返回False。
注意:数组内已种好的花不会违反种植规则。
输入的数组长度范围为 [1, 20000]。
n 是非负整数,且不会超过输入数组的大小。
分析:对于连续的0来说,主要是考虑边界问题。例如000,如果是放在边界,则101,即种2盆花;如果两边是1,就只能放1盆(010)。所以这里有个技巧是,若两边是0,则直接插入一个0,这样,原来的边界处就可以放心的种花了。
643 子数组最大平均数 I(回到目录)
给定 n 个整数,找出平均数最大且长度为 k 的连续子数组,并输出该最大平均数。
示例 1:
注意:
分析:这道题,我的思路比较暴力,直接计算每个k元组元素的和,计算出最大的那个。然后得到平均数。
665 非递减数列(回到目录)
给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的: 对于数组中所有的 i (1 <= i < n),满足 array[i] <= array[i + 1]。
说明: n 的范围为 [1, 10,000]。
分析:这道题给了我们一个数组,说我们最多有1次修改某个数字的机会,问能不能将数组变为非递减数组。题目中给的例子太少,不能覆盖所有情况,我们再来看下面三个例子:
我们通过分析上面三个例子可以发现,当我们发现后面的数字小于前面的数字产生冲突后,有时候需要修改前面较大的数字(比如前两个例子需要修改4),有时候却要修改后面较小的那个数字(比如前第三个例子需要修改2),那么有什么内在规律吗?是有的,判断修改那个数字其实跟再前面一个数的大小有关系,首先如果再前面的数不存在,比如例子1,4前面没有数字了,我们直接修改前面的数字为当前的数字2即可。而当再前面的数字存在,并且小于当前数时,比如例子2,-1小于2,我们还是需要修改前面的数字4为当前数字2;如果再前面的数大于当前数,比如例子3,3大于2,我们需要修改当前数2为前面的数3。这是修改的情况,由于我们只有一次修改的机会,所以用一个变量cnt,初始化为1,修改数字后cnt自减1,当下次再需要修改时,如果cnt已经为0了,直接返回false。遍历结束后返回true。
修改的原则:尽量使把数字往小的改。
131 分割回文串(回到目录)
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
这是一道需要用DFS来解的题目,既然题目要求找到所有可能拆分成回文数的情况,那么肯定是所有的情况都要遍历到,对于每一个子字符串都要分别判断一次是不是回文数,那么肯定有一个判断回文数的子函数,还需要一个DFS函数用来递归,再加上原本的这个函数,总共需要三个函数来求解。代码如下:
注:那么,对原字符串的所有子字符串的访问顺序是什么呢,如果原字符串是 abcd, 那么访问顺序为:a -> b -> c -> d -> cd -> bc -> bcd-> ab -> abc -> abcd
, 这是对于没有两个或两个以上子回文串的情况。那么假如原字符串是aabc
,那么访问顺序为:a -> a -> b -> c -> bc -> ab -> abc -> aa -> b -> c -> bc -> aab -> aabc
,中间当检测到aa时候,发现是回文串,那么对于剩下的bc当做一个新串来检测,于是有b -> c -> bc
,这样扫描了所有情况,即可得出最终答案。
股票问题
121 买卖股票的最佳时机(回到目录)
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
引入两个变量,最小买入价格和最大利润,遍历数组,判断最大和最小值来得到最后的结果。
122 买卖股票的最佳时机 II(回到目录)
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
分析:炒股想挣钱当然是低价买入高价抛出,那么这里我们只需要从第二天开始,如果当前价格比之前价格高,则把差值加入利润中,因为我们可以昨天买入,今日卖出,若明日价更高的话,还可以今日买入,明日再抛出。以此类推,遍历完整个数组后即可求得最大利润。
说明:其他几个股票问题有点难,现在不想做了
516 最长回文子序列(回到目录)
给定一个字符串s,找到其中最长的回文子序列。可以假设s的最大长度为1000。
这道题给了我们一个字符串,让我们求最大的回文子序列,子序列和子字符串不同,不需要连续。而关于回文串的题之前也做了不少,处理方法上就是老老实实的两两比较吧。像这种有关极值的问题,最应该优先考虑的就是贪婪算法和动态规划,这道题显然使用DP更加合适。我们建立一个二维的DP数组,其中dp[i][j]表示[i,j]区间内的字符串的最长回文子序列,那么对于递推公式我们分析一下,如果s[i]==s[j],那么i和j就可以增加2个回文串的长度,我们知道中间dp[i + 1][j - 1]的值,那么其加上2就是dp[i][j]的值。如果s[i] != s[j],那么我们可以去掉i或j其中的一个字符,然后比较两种情况下所剩的字符串谁dp值大,就赋给dp[i][j],那么递推公式如下:
代码
74 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
这段代码里用到了两次二分查找,两次查找的代码模板不一样。
这道题要求搜索一个二维矩阵,由于给的矩阵是有序的,所以很自然的想到要用二分查找法,我们可以在第一列上先用一次二分查找法找到目标值所在的行的位置,然后在该行上再用一次二分查找法来找是否存在目标值,代码如下:
240 搜索二维矩阵 II
题目描述提示帮助提交记录社区讨论阅读解答
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:
|
|
107 二叉树的层次遍历 II
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
递归方式
迭代方式
344 反转字符串
编写一个函数,其作用是将输入的字符串反转过来。
我的解法
参考解法
349 两个数组的交集
给定两个数组,编写一个函数来计算它们的交集。
说明:
- 输出结果中的每个元素一定是唯一的。
- 我们可以不考虑输出结果的顺序。
使用set容器
788 旋转数字
我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后,我们仍可以得到一个有效的,且和 X 不同的数。要求每位数字都要被旋转。
如果一个数的每位数字被旋转以后仍然还是一个数字, 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己;2 和 5 可以互相旋转成对方;6 和 9 同理,除了这些以外其他的数字旋转以后都不再是有效的数字。
现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数?
N 的取值范围是 [1, 10000]。
|
|
796 旋转字符串
给定两个字符串, A 和 B。
A 的旋转操作就是将 A 最左边的字符移动到最右边。 例如, 若 A = ‘abcde’,在移动一次之后结果就是’bcdea’ 。如果在若干次旋转操作之后,A 能变成B,那么返回True。
A 和 B 长度不超过 100。
|
|
804 唯一摩尔斯密码词
国际摩尔斯密码定义一种标准编码方式,将每个字母对应于一个由一系列点和短线组成的字符串, 比如: “a” 对应 “.-“, “b” 对应 “-…”, “c” 对应 “-.-.”, 等等。
为了方便,所有26个英文字母对应摩尔斯密码表如下:
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
给定一个单词列表,每个单词可以写成每个字母对应摩尔斯密码的组合。例如,”cab” 可以写成 “-.-.-….-“,(即 “-.-.” + “-…” + “.-“字符串的结合)。我们将这样一个连接过程称作单词翻译。
返回我们可以获得所有词不同单词翻译的数量。
注意:
- 单词列表words 的长度不会超过 100。
- 每个单词 words[i]的长度范围为 [1, 12]。
- 每个单词 words[i]只包含小写字母。
|
|
371 两整数之和
题目描述提示帮助提交记录社区讨论阅读解答
不使用运算符 + 和-,计算两整数a 、b之和。
示例:
若 a = 1 ,b = 2,返回 3。
使用位运算的方法:我们在做加法运算的时候,每位相加之后可能会有进位Carry产生,然后在下一位计算时需要加上进位一起运算,那么我们能不能将两部分拆开呢,我们来看一个例子759+674
如果我们不考虑进位,可以得到323
如果我们只考虑进位,可以得到1110
我们把上面两个数字假期323+1110=1433就是最终结果了
然后我们进一步分析,如果得到上面的第一第二种情况,我们在二进制下来看,不考虑进位的加,0+0=0, 0+1=1, 1+0=1, 1+1=0
,这就是异或的运算规则,如果只考虑进位的加0+0=0, 0+1=0, 1+0=0, 1+1=1
,而这其实这就是与的运算,而第三步在将两者相加时,我们再递归调用这个算法,终止条件是当进位为0时,我们直接返回第一步的结果,参见代码如下:
迭代法:
172 阶乘后的零
给定一个整数 n,返回 n! 结果尾数中零的数量。
说明: 你算法的时间复杂度应为 O(log n) 。
分析:这道题是求一个数的阶乘末尾0的个数,也就是要找乘数中10的个数,而10可分解为2和5,而我们可知2的数量又远大于5的数量,那么此题只需要找出5的个数。仍需注意的一点就是,像25,125,这样的不只含有一个5的数字需要考虑进去。
235 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
|
|
236 二叉树的最近公共祖先
代码同235
661 图片平滑器
包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ,平均灰度的计算是周围的8个单元和它本身的值求平均,如果周围的单元格不足八个,则尽可能多的利用它们。
注意:
- 给定矩阵中的整数范围为 [0, 255]。
- 矩阵的长和宽的范围均为 [1, 150]。
|
|
217 存在重复元素
给定一个整数数组,判断是否存在重复元素。
如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。
代码:一看到题目(和 389 找不同 类似的思路)就写出来了代码,我的思路非常简单。使用map记录每个元素出现的次数,然后每个元素的次数都-1,再判断该元素的次数是否>0,若是,则返回true。
219 存在重复元素 II
给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为 k。
首先定义一个pair的vector,目的是绑定元素和它对应的index,r然后进行元素大小排列,先判断两个元素相等时候,index之差是否<=k,如果是,就返回true.
220 存在重复元素 III
给定一个整数数组,判断数组中是否有两个不同的索引 i 和 j,使得 nums [i] 和 nums [j] 的差的绝对值最大为 t,并且 i 和 j 之间的差的绝对值最大为 ķ。
和上一题的代码基本类似
231 2的幂
给定一个整数,编写一个函数来判断它是否是 2 的幂次方。
法1
万能法
326 3的幂
|
|
342 4的幂
|
|
237 删除链表中的节点
请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。
现有一个链表 – head = [4,5,1,9],它可以表示为:
4 -> 5 -> 1 -> 9
说明:
- 链表至少包含两个节点。
- 链表中所有节点的值都是唯一的。
- 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
- 不要从你的函数中返回任何结果。
因为题目给的是删除节点,那说明这个节点可以舍弃了,我们把下一个节点的值拷贝给当前要删除的节点,再删除下一个节点。
大致过程如下(删除3):
这题太骚了:用覆盖的方法
203 删除链表中的节点
删除链表中等于给定值 val 的所有节点。
示例:
方法1:和上面那题(237)类似的思路,删除目标节点
经典方法:跳过目标节点
876 链表的中间结点
给定一个带有头结点 head 的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
代码:和 109类似的套路
205 同构字符串
给定两个字符串 s 和 t,判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。
说明:
- 你可以假设 s 和 t 具有相同的长度。
|
|
739. 每日温度
题目描述提示帮助提交记录社区讨论阅读解答
根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高的天数。如果之后都不会升高,请输入 0 来代替。
例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的都是 [30, 100] 范围内的整数。
分析:我的思路很简单,遍历每一个元素,对某一个元素来说,找到第一个大于它的数,此时:如果此时的是小于数组的size的,直接push_back(j-i),否则push 0.
496 下一个更大元素 I
给定两个没有重复元素的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在,对应位置输出-1。
注意:
- nums1和nums2中所有元素是唯一的。
- nums1和nums2 的数组大小都不超过1000。
和上一题的套路有点像
503 下一个更大元素 II
给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1。
示例 1:
注意: 输入数组的长度不会超过 10000。
分析:依次遍历每一个元素。由于数组是循环的,所以先从前面往后面找第一个比它大的数字,如果找不到,就要那么就要从头开始找,第一个比它大的数字。
556 下一个更大元素 III
给定一个32位正整数 n,你需要找到最小的32位整数,其与 n 中存在的位数完全相同,并且其值大于n。如果不存在这样的32位整数,则返回-1。
这道题给了我们一个数字,让我们对各个位数重新排序,求出刚好比给定数字大的一种排序,如果不存在就返回-1。这道题给的例子的数字都比较简单,我们来看一个复杂的,比如12443322,这个数字的重排序结果应该为13222344,如果我们仔细观察的话会发现数字变大的原因是左数第二位的2变成了3,细心的童鞋会更进一步的发现后面的数字由降序变为了升序,这也不难理解,因为我们要求刚好比给定数字大的排序方式。那么我们再观察下原数字,看看2是怎么确定的,我们发现,如果从后往前看的话,2是第一个小于其右边位数的数字,因为如果是个纯降序排列的数字,做任何改变都不会使数字变大,直接返回-1。知道了找出转折点的方法,再来看如何确定2和谁交换,这里2并没有跟4换位,而是跟3换了,那么如何确定的3?其实也是从后往前遍历,找到第一个大于2的数字交换,然后把转折点之后的数字按升序排列就是最终的结果了。最后记得为防止越界要转为长整数型,然后根据结果判断是否要返回-1即可.
268 缺失数字
给定一个包含 0, 1, 2, …, n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。
说明:
- 你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
|
|
113 路径总和 II
给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
|
|
257 二叉树的所有路径
题目描述提示帮助提交记录社区讨论阅读解答
给定一个二叉树,返回所有从根节点到叶子节点的路径。
说明:
- 叶子节点是指没有子节点的节点。
|
|
|
|
437 路径总和 III
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。
示例:
|
|
415 字符串相加
给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。
注意:
- num1 和num2 的长度都小于 5100.
- num1 和num2 都只包含数字 0-9.
- num1 和num2 都不包含任何前导零。
- 你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式。
之前LeetCode出过几道类似的题目,比如 67 二进制求和,还有 2 链表相加,和 258 各位相加 基本思路很类似,都是一位一位相加,然后算和算进位,最后根据进位情况看需不需要补一个高位
我之前 2,67 题不是按照这题的代码结构写的,现在重写。
2 链表相加
|
|
67 二进制求和
|
|
43 字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
说明:
- num1 和 num2 的长度小于110。
- num1 和 num2 只包含数字 0-9。
- num1 和 num2 均不以零开头,除非是数字 0 本身。
- 不能使用任何标准库的大数类型(比如 BigInteger)或直接将输入转换为整数来处理。
分析:
首先我们把每一位相乘,得到一个没有进位的临时结果,如图中中间的一行红色数字就是临时结果,然后把临时结果从低位起依次进位。对于一个m位整数乘以n位整数的结果,最多只有m+n位。
这道题让我们求两个字符串数字的相乘,输入的两个数和返回的数都是以字符串格式储存的,这样做的原因可能是这样可以计算超大数相乘,可以不受int或long的数值范围的约束,那么我们该如何来计算乘法呢,我们小时候都学过多位数的乘法过程,都是每位相乘然后错位相加,那么这里就是用到这种方法,把错位相加后的结果保存到一个一维数组中,然后分别每位上算进位,最后每个数字都变成一位,然后要做的是去除掉首位0,最后把每位上的数字按顺序保存到结果中即可。
202 快乐数
编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。如果可以变为 1,那么这个数就是快乐数。
示例:
这道题,很容易超出时间限制。大神的做法:我们可以用set来记录所有出现过的数字,然后每出现一个新数字,在set中查找看是否存在,若不存在则加入表中,若存在则跳出循环,并且判断此数是否为1,若为1返回true,不为1返回false。
263. 丑数
编写一个程序判断给定的数是否为丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
说明:
- 1 是丑数。
- 输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]。
输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]。
我习惯性写成下面的代码,少了else,那么它就会一行一行往下走。错错错
正确的写法:
72 编辑距离
给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符123456789101112131415161718示例 1:输入: word1 = "horse", word2 = "ros"输出: 3解释:horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')示例 2:输入: word1 = "intention", word2 = "execution"输出: 5解释:intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u')
分析:动态规划题。我觉得还是那位大神牛逼,能把别人认为那么难的问题,一下解释的那么好,顿时开光。题目关键是你要确定好状态变量。这里我们用dp[i][j]来表示word1的前i个字符串变换到word2的前j个字符串的最少操作数。那么我们思考前0个字符串到前j个字符串的解,有几个呢?答案是有j个。请看下图:
可以把可以把前0个字符串用空集来表示,空集到空集自然不用操作。空集到任何数量(设长度为j)的字符串的操作数就是j(就是把j个元素都作 插入 操作。)这样我们就处理好了边界。对于非边界呢,可以观察到,如果word1[i]=word2[j],那么说明dp[i][j]和(word1前i-1个)=>(word2前j-1个) 相等。其他的情况就是看dp[i][j]的相邻位置哪个更小,取最小的,然后+1。
583. 两个字符串的删除操作
给定两个单词 word1 和 word2,找到使得 word1 和 word2 相同所需的最小步数,每步可以删除任意一个字符串中的一个字符。
说明:
- 给定单词的长度不超过500。
- 给定单词中的字符只含有小写字母。
分析:
这一题和上一题【编辑距离】其实是一样的,用dp[i][j]来表示word1前i个字符变换到word2前j个字符的最少操作数。只不过没有插入操作,也就不能考虑那个dp[i-1][j-1]了
289 生命游戏(回到目录)
根据百度百科,生命游戏,简称为生命,是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。
给定一个包含 m × n 个格子的面板,每一个格子都可以看成是一个细胞。每个细胞具有一个初始状态 live(1)即为活细胞, 或 dead(0)即为死细胞。每个细胞与其八个相邻位置(水平,垂直,对角线)的细胞都遵循以下四条生存定律:
如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡;
如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活;
如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡;
如果死细胞周围正好有三个活细胞,则该位置死细胞复活;
根据当前状态,写一个函数来计算面板上细胞的下一个(一次更新后的)状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的,其中细胞的出生和死亡是同时发生的。
由于题目中要求我们用置换方法in-place来解题,所以我们就不能新建一个相同大小的数组,那么我们只能更新原有数组,但是题目中要求所有的位置必须被同时更新,但是在循环程序中我们还是一个位置一个位置更新的,那么当一个位置更新了,这个位置成为其他位置的neighbor时,我们怎么知道其未更新的状态呢,我们可以使用状态机转换:
状态0: 死细胞转为死细胞
状态1: 活细胞转为活细胞
状态2: 活细胞转为死细胞
状态3: 死细胞转为活细胞
最后我们对所有状态对2取余,那么状态0和2就变成死细胞,状态1和3就是活细胞,达成目的。我们先对原数组进行逐个扫描,对于每一个位置,扫描其周围八个位置,如果遇到状态1或2,就计数器累加1,扫完8个邻居,如果少于两个活细胞或者大于三个活细胞,而且当前位置是活细胞的话,标记状态2,如果正好有三个活细胞且当前是死细胞的话,标记状态3。完成一遍扫描后再对数据扫描一遍,对2取余变成我们想要的结果。
|
|
383 赎金信(回到目录)
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成,返回 true ;否则返回 false。
(题目说明:为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。)
注意:
你可以假设两个字符串均只含有小写字母。
老套路,哈希统计出现的次数
387 字符串中的第一个唯一字符(回到目录)
给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。
案例:
老套路了
451 根据字符出现频率排序(回到目录)
给定一个字符串,请将字符串里的字符按照出现的频率降序排列。
注意’A’和’a’被认为是两种不同的字符。
这道题,比较简单,主要是重写cmp
|
|
347 前K个高频元素(回到目录)
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
说明:
- 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
|
|
242 有效的字母异位词(回到目录)
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的一个字母异位词。
说明:
- 你可以假设字符串只包含小写字母。
老套路,使用map来统计字符数量是否匹配
438 找到字符串中所有字母异位词(回到目录)
给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。
字符串只包含小写英文字母,并且字符串 s 和 p 的长度都不超过 20100。
说明:
- 字母异位词指字母相同,但排列不同的字符串。
- 不考虑答案输出的顺序。1234567891011121314151617181920212223示例 1:输入:s: "cbaebabacd" p: "abc"输出:[0, 6]解释:起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。示例 2:输入:s: "abab" p: "ab"输出:[0, 1, 2]解释:起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
这道题我也想直接用两个map来做的,但是map不能直接比较,所以就选择了两个vector来模拟哈希表。
567 字符串的排列(回到目录)
给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
换句话说,第一个字符串的排列之一是第二个字符串的子串。
注意:
- 输入的字符串只包含小写字母
- 两个字符串的长度都在 [1, 10,000] 之间
和上面那一题(438)一模一样
234 回文链表(回到目录)
请判断一个链表是否为回文链表。
关键是找出链表中点
174. 地下城游戏(回到目录)
一些恶魔抓住了公主(P)并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士(K)最初被安置在左上角的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。
有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。
为了尽快到达公主,骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如,考虑到如下布局的地下城,如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下,则骑士的初始健康点数至少为 7。
说明:
- 骑士的健康点数没有上限。
- 任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。
分析:
304 二维区域和检索 - 矩阵不可变(回到目录)
给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2)。
上图子矩阵左上角 (row1, col1) = (2, 1) ,右下角(row2, col2) = (4, 3),该子矩形内元素的总和为 8。
示例:
|
|
300 最长上升子序列(回到目录)
给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
|
|
338 比特位计数(回到目录)
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。
方法:假设构造一颗二叉树,根节点为1,从左到右从上到下分别是1,2,3,4…的二进制,可以发现如下规律:左子树是给根节点在末尾加0,右结点是给根节点在末尾加1,可得10和11;后来,10成为根节点,它左子树是100,右子树是101;11为根节点的树,左子树是110,右子树是111,同样是左边加0,右边加1…也就是当前数为偶数就在左子树,加0;如果当前数是奇数就在右子树,加1。如下图:
279 完全平方数(回到目录)
给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
分析:建立一个n+1长度的数组dp,dp[i]表示i这个数构成平方和需要数字的最小个数。
当jxj小于i的时候,temp中保存j从1开始每加1得到的dp[i-jxj] + 1的最小值
当jXj=i的时候,dp[i]的值就直接为1。从2一直到n可以计算出dp[i]的所有值。。
最后return dp[n]的值。
|
|
91 解码方法
一条包含字母 A-Z 的消息通过以下方式进行了编码:
这道题要求解码方法,跟之前那道 Climbing Stairs 爬梯子问题 非常的相似,但是还有一些其他的限制条件,比如说一位数时不能为0,两位数不能大于26,其十位上的数也不能为0,出去这些限制条件,根爬梯子基本没啥区别,也勉强算特殊的斐波那契数列,当然需要用动态规划Dynamci Programming来解。建立一位dp数组,长度比输入数组长多多2,全部初始化为1,因为斐波那契数列的前两项也为1,然后从第三个数开始更新,对应数组的第一个数。对每个数组首先判断其是否为0,若是将改为dp赋0,若不是,赋上一个dp值,此时相当如加上了dp[i - 1], 然后看数组前一位是否存在,如果存在且满足前一位不是0,且和当前为一起组成的两位数不大于26,则当前dp值加上dp[i - 2], 至此可以看出来跟斐波那契数组的递推式一样,代码如下:
96 不同的二叉搜索树(回到目录)
给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?
示例:
二分查找树的定义是,左子树节点均小于root,右子树节点均大于root,所以可以用递推的方法,把dp[i]表示i个数能够构成的二叉搜索树的个数.初始化边界值是 dp[0]=1,dp[1]=1,dp[2]=2。
当i>=3的时候,若以j为root结点,dp[j-1]等于root结点左边的j-1个结点能构成的BST个数.
dp[i-j]等于root结点右边i-j个结点能构成的BST个数。因为j+1~i的种数和0~i-j的种数一样,所以就是dp[i-j]所以dp[j-1] * dp[i-j]等于以j为root结点能构成的BST种数
j可以取1~i中的任意一个值,把这些所有计算出来的总数相加就是v[i]的值
|
|
|
|
443 压缩字符串
给定一组字符,使用原地算法将其压缩。
压缩后的长度必须始终小于或等于原数组长度。
数组的每个元素应该是长度为1 的字符(不是 int 整数类型)。
在完成原地修改输入数组后,返回数组的新长度。
注意:
所有字符都有一个ASCII值在[35, 126]区间内。
1 <= len(chars) <= 1000。
|
|
693 交替位二进制数
给定一个正整数,检查他是否为交替位二进制数:换句话说,就是他的二进制数相邻的两个位数永不相等。
|
|