String
- 158 哈希表
写出一个函数
anagram(s, t)
判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。 写出一个函数anagram(s, t)
判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。
- 55 哈希表
比较两个字符串A和B,确定A中是否包含B中所有的字符。字符串A和B中的字符都是 大写字母
- 13 暴力查找 len1-len2
对于一个给定的 source 字符串和一个 target 字符串,你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在,则返回
-1
。
- 171 排序后的字符串作为哈希值
给出一个字符串数组S,找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串,那么他存在一个字母集合相同,但顺序不同的字符串也在S中。
- 79 动态规划
给出两个字符串,找到最长公共子串,并返回其长度。
- 78 以第一个字符串为基准,暴力查找
给k个字符串,求出他们的最长公共前缀(LCP)
Array
- 172 双指针
给定一个数组和一个值,在原地删除与值相同的数字,返回新数组的长度。
元素的顺序可以改变,并且对新的数组不会有影响。
- 138 双指针
给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置
- 100 遍历,使用变量pre保存前一个数
给定一个排序数组,在原数组中删除重复出现的数字,使得每个元素只出现一次,并且返回新的数组的长度。不要使用额外的数组空间,必须在原地没有额外空间的条件下完成。
- 64 双指针,从后往前比较
合并两个排序的整数数组A和B变成一个新的数组。
你可以假设A具有足够的空间(A数组的大小大于或等于m+n)去添加B中的元素。
- 56 遍历数组,map存储每个数的位置,同时寻找差值
给一个整数数组,找到两个数使得他们的和等于一个给定的数 target。 你需要实现的函数
twoSum
需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。
- 50 暴力 or 用数组保存 i 位左边和右边的乘积
给定一个整数数组A。
定义B[i] = A[0] * … * A[i-1] * A[i+1] * … * A[n-1], 计算B的时候请不要使用除法。
- 189 通过交换,进行一种特殊的排序(众神归位),然后找第一个对不上的位置
给出一个无序的整数数组,找出其中没有出现的最小正整数。
- 59 三指针,先排序,固定left,根据差值大小移动mid和right
给一个包含 n 个整数的数组 S, 找到和与给定整数 target 最接近的三元组,返回这三个数的和。
- 57 同59
给出一个有n个整数的数组S,在S中找到三个整数a, b, c,找到所有使得a + b + c = 0的三元组。
- 31 快排中的partition操作
给出一个整数数组 nums 和一个整数 k。划分数组(即移动数组 nums 中的元素),使得:
- 所有小于k的元素移到左边
- 所有大于等于k的元素移到右边
返回数组划分的位置,即数组中第一个位置 i,满足 nums[i] 大于等于 k。
Binary Search
- 141 二分查找,小心溢出
实现
int sqrt(int x)
函数,计算并返回 x 的平方根。
- 60 二分查找
给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。
- 28 二分查找
写出一个高效的算法来搜索 m × n矩阵中的值。
- 14 二分查找,注意是第一次出现的下标
给定一个排序的整数数组(升序)和一个要查找的整数
target
,用O(logn)
的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1
。
- 159 [first, second]两个递增序列,first中的值大于second中的值,比较中间值与右端点值的大小
假设一个旋转排序的数组其起始位置是未知的(比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2)。
你需要找到其中最小的元素。
你可以假设数组中不存在重复的元素。
- 75 产生峰的条件:两边各有一个上坡。现端点两边已形成一个上坡,寻找另一个上坡。
给出一个整数数组(size为n),其具有以下特点:
- 相邻位置的数字是不同的
- A[0] < A[1] 并且 A[n - 2] > A[n - 1]
假定P是峰值的位置则满足
A[P] > A[P-1]
且A[P] > A[P+1]
,返回数组中任意一个峰值的位置。
- 74 二分查找,注意使用int会超时
代码库的版本号是从 1 到 n 的整数。某一天,有人提交了错误版本的代码,因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。
- 62 根据159题,先找到有序区间,再进行二分查找
假设有一个排序的按未知的旋转轴旋转的数组(比如,0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索,如果在数组中找到目标值返回数组中的索引位置,否则返回-1。
- 61 先找到与target值相等的位置,再分别向前、向后查找
给定一个包含 n 个整数的排序数组,找出给定目标值 target 的起始和结束位置。
如果目标值不在数组中,则返回[-1, -1]
- 183 二分查找小段木头的长度,初始为0和最大木头长度,注意int溢出
有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目至少为
k
。当然,我们希望得到的小段越长越好,你需要计算能够得到的小段木头的最大长度。
Math
Greedy
- 82 使用异或运算,相同的数异或为0,0异或任何数等于该数本身
给出2*n + 1 个的数字,除其中一个数字之外其他每个数字均出现两次,找到这个数字。
- 46 抵消法,当一个数组去掉两个不同的元素时,其主元素不改变(用count统计元素个数)
给定一个整型数组,找出主元素,它在数组中的出现次数严格大于数组元素个数的二分之一。
- 187 出发点符合两个条件,总油量大于总消耗且当前油量大于0
在一条环路上有 N 个加油站,其中第 i 个加油站有汽油
gas[i]
,并且从第i个加油站前往第i+1个加油站需要消耗汽油cost[i]
。
你有一辆油箱容量无限大的汽车,现在要从某一个加油站出发绕环路一周,一开始油箱为空。
求可环绕环路一周时出发的加油站的编号,若不存在环绕一周的方案,则返回-1
。
- 184 自定义cmp函数进行排序,排序依据为两个数不同组合方式的大小
给出一组非负整数,重新排列他们的顺序把他们组成一个最大的整数。
- 182 删除出现的第一个左边>右边的数,因为删除之后高位减小(贪心)
给出一个字符串 A, 表示一个 n 位正整数, 删除其中 k 位数字, 使得剩余的数字仍然按照原来的顺序排列产生一个新的正整数。
找到删除 k 个数字之后的最小正整数。
- 116 遍历,记录从头开始能跳跃的最远距离,若当前距离大于最远距离,则无法到达
给出一个非负整数数组,你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
判断你是否能到达数组的最后一个位置。
- 52 找到排列中的递增点,在该点后找比其大的最小值与其互换,并将该点后的数字排序,注意单增和单减
给定一个整数数组来表示排列,找出其之后的一个排列。
Linked List
- 174 post指针先移动n的距离,然后pre与post同时移动,post指向null时,pre指向待删除项的前一个
给定一个链表,删除链表中倒数第n个节点,返回链表的头节点。
- 165 双指针同时遍历,并比较大小
将两个排序链表合并为一个新的排序链表
- 112 遍历
给定一个排序链表,删除所有重复的元素每个元素只留下一个。
- 96 遍历,用两个链表分别存储,最后合并
给定一个单链表和数值x,划分链表使得所有小于x的节点排在大于等于x的节点之前。
你应该保留两部分内链表节点原有的相对顺序。
- 35 遍历,用指针临时保存
翻转一个链表
- 170 类似174题,注意移动位置k可能大于链表长度,要循环遍历
给定一个链表,旋转链表,使得每个节点向右移动k个位置,其中k是一个非负数
- 106 快慢指针找到中间节点(快指针要双重判断),然后递归
给出一个所有元素以升序排序的单链表,将它转换成一棵高度平衡的二分查找树
- 105 插入拷贝节点,复制random指针,分离两个链表
给出一个链表,每个节点包含一个额外增加的随机指针可以指向链表中的任何节点或空的节点。
返回一个深拷贝的链表。
- 102 快慢指针
给定一个链表,判断它是否有环。
- 99 先找中间点,翻转后半部分链表,再插入前半部分链表中
给定一个单链表L: L0→L1→…→Ln-1→Ln,
重新排列后为:L0→Ln→L1→Ln-1→L2→Ln-2→…
必须在不改变节点值的情况下进行原地操作。
- 98 归并排序,合并两个有序链表,参考165
在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。
Binary Tree
- 97 递归,最大深度为根节点左右子树深度较大值加1
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的距离。
- 93 类似97,在求子树深度的同时判断深度的差值
给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是:一棵二叉树中每个节点的两个子树的深度相差不会超过1。
- 85 根据根节点与插入节点的大小关系判断插入位置
给定一棵二叉查找树和一个新的树节点,将节点插入到树中。
你需要保证该树仍然是一棵二叉查找树。
- 69 bfs,插入None作为结束信号,实现分层输出
给出一棵二叉树,返回其节点值的层次遍历(逐层从左往右访问)
- 66 递归
给出一棵二叉树,返回其节点值的前序遍历。
- 95 中序遍历,二叉查找树的中序遍历从小到大排列
给定一个二叉树,判断它是否是合法的二叉查找树(BST)
- 73 先序遍历的第一个值为根节点,在中序遍历中找根节点,左(右)半部分为左(右)子树
前序遍历和中序遍历树构造二叉树
- 11 三种情况,递归讨论
Given a binary search tree and a range
[k1, k2]
, return all elements in the given range.
- 7 通过先序遍历进行序列化与反序列化
设计一个算法,并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”,读取文件后重建同样的二叉树被称为“反序列化”。
Search & Recursion
- 152 递归,插入 -> 递归 -> 弹出
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
- 135 先排序,另外辅助函数应有起始位置,虽然数字可重复,但要从比当前数字大的数字开始遍历
给出一个候选数字的set(C)和目标数字(T),找到C中所有的组合,使找出的数字和为T。C中的数字可以无限制重复被选取。
- 127 dfs,注意把节点 push 进 vector 的时机
给定一个有向图,图节点的拓扑排序被定义为:
- 对于每条有向边A--> B,则A必须排在B之前
- 拓扑排序的第一个节点可以是任何在图中没有其他节点指向它的节点
找到给定图的任一拓扑排序
- 120 bfs,使用结构体存储长度,遍历替换单词中的字母,看是否在字典中,注意unordered_set的用法
给出两个单词(start和end)和一个字典,找到从start到end的最短转换序列
- 33
- 18 递归,类似17,注意去重(当前数字和前一个数字相同时,跳过)
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
- 17 递归
给定一个含不同整数的集合,返回其所有的子集
- 16 先排序,然后参照15,注意去重
给出一个具有重复数字的列表,找出列表所有不同的排列。
- 15 递归,从集合中依次选出每一个元素,作为排列的第一个元素,然后对剩余的元素进行全排列
给定一个数字列表,返回其所有可能的排列。
Dynamic Programming
- 115 状态转移方程:当前格的路径数 = 上一格的路径数 + 左一格的路径数
现在考虑网格中有障碍物,那样将会有多少条不同的路径?
网格中的障碍和空位置分别用 1 和 0 来表示。
- 111 状态转移方程:爬 n 步的方法数 = 爬 n-1 步的方法数 + 爬 n-2 步的方法数
假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?
- 109 状态转移方程:到该数字的路径 = min(到该数字左上角的路径,到该数字右上角的路径) + 该数字的值
给定一个数字三角形,找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。
- 41 状态转移方程:dp[i] = max(nums[i], dp[i-1] + nums[i])
给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。
- 191 两个数组,一个存乘积最大,一个存乘积最小
找出一个序列中乘积最大的连续子序列(至少包含一个数)。
- 119 状态转移方程:
- word1[n] == word2[m] word1[0..n] => word2[0..m] = word[0..n-1] => word2[0..m-1]
- word1[n] != word2[m] word1[0..n] => word2[0..m] = min(word1[0..n-1] => word2[0..m], word1[0..n] => word2[0..m-1], word1[0..n-1] => word2[0..m-1]) + 1
给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。
你总共三种操作方法:插入一个字符,删除一个字符,替换一个字符。
- 118 状态转移方程:
- S[n] != T[m] S[0…n]的不同的子序列中T[0…m]出现的个数 = S[0…n-1]的子序列中T[0…m]出现的个数
- S[n] == T[m] S[0…n]的不同的子序列中T[0…m]出现的个数 = S[0…n-1]的子序列中T[0…m]出现的个数 + S[0…n-1]的子序列中T[0…m-1]出现的个数
给出字符串S和字符串T,计算S的不同的子序列中T出现的个数。
子序列字符串是原始字符串通过删除一些(或零个)产生的一个新的字符串,并且对剩下的字符的相对位置没有影响。(比如,“ACE”是“ABCDE”的子序列字符串,而“AEC”不是)。
- 107 状态转移方程:dp[j]可拆 + s[j:i]在dict中 => dp[i]可拆,注意细节
给出一个字符串s和一个词典,判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。
- 92 dp表示大小为 i 的背包,放前 j 个物品的最大重量,使用vector,不使用数组
- 状态转移方程:
c++ if 当前物品重量>背包重量:dp[i][j] = dp[i][j-1] else: dp[i][j] = max(dp[i][j-1], A[j-1] + dp[i-A[j-1]][j-1])
- 状态转移方程:
在n个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为m,每个物品的大小为A[i]
- 29 dp表示 s1 的前 i 位,s2 的前 j 位能否交叉构成 s3 的前 i+j 位
- 能构成的条件:
- s1 的 i 位 = s3 的 i+j 位且 s1 的前 i-1 位与 s2 的前 j 位 能交叉构成…
- s2 的 j 位 = s3 的 i+j 位且 s1 的前 i 位与 s2 的前 j-1 位 能交叉构成…
给出三个字符串:s1、s2、s3,判断s3是否由s1和s2交叉构成。
Data Structure
- 124
- 104
- 40 定义两个栈 in 和 out,进栈时直接压入 in,出栈时看 out
- 如果 out 不为空,则弹出栈顶元素
- 否则将 in 中的全部元素倒入out中
- 12
- 4