题解: 给定一个数组nums和目标值target,找出和为目标值的两个整数,并返回下标。
·暴力法:双循环,时间复杂度O(n^2),空间复杂度O(1)。
·两遍哈希表:哈希表保存元素与索引。哈希表将查找时间从O(n)降到O(1),时间复杂的O(n),空间复杂度O(n)。
·一遍哈希表法:一边遍历一边存入哈希表,时间复杂的O(n),空间复杂度O(n)。
题解: 排序,固定一个数字然后头尾双指针。时间复杂度O(n^2),空间复杂度O(1)。
题解: 排序+双指针
题解: 双循环+双指针。--时间还可继续优化。
题解: 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""。
·依次扫描法:依次遍历字符串,遍历第i个字符串的时候,找到公共前缀,时间复杂的O(s),s是所有字符数量总和,空间复杂度O(1)。
·同时扫描法:水平扫描时遍历所有字符串,如果相同,继续扫描。时间复杂的O(s),s是所有字符数量总和,空间复杂度O(1)。
·分治:将原问题分成两个子问题。时间复杂的O(s),s是所有字符数量总和,空间复杂度O(mlog(n))。
·二分查找法:时间复杂的O(slog(n)),s是所有字符数量总和,空间复杂度O(1)。
题解: 双指针法。设置左右指针,向中间判断,跳过非数字字母的字符;将字母全部装化为小写。
python可使用filter(str.isalnum,s)。
题解: 倒序遍历字符串,遇到字母记录位置i,继续遍历遇到空格记录j,添加s[j+1:i+1]。由于首部没有空格,可以在字符串前加' ',或者最后加上s[:i+1]。
题解: 二分查找法,时间复杂度O(logn)。
题解: 二分查找法,时间复杂度O(logn)。
题解: 对于两个小写字符串A、B,通过交换A中两个字母得到B相等的结果则返回True,否则返回False。首先判断字符串A、B长度是否相等,如果不相等直接返回False。
·A、B如果相等,需要交换两个相同的元素,判断A中是否有相同元素;
·如果不等,且不相等的字符为两个,判断能否交换两个字母使A、B相等,否则返回False。
题解: 给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照逆序的方式存储的,并且它们的每个节点只能存储一位数字。注意进位。
题解: 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
题解: 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
解法一:暴力(列表加速)
解法二:逐一比较(用队列优化)
解法三:逐一两两合并
解法四:分治
题解: 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
解法一:两次遍历法
解法二:双指针一次遍历
解法三:列表作弊法。
题解: 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
解法一:列表法 一个列表存单数,一个列表存偶数,然后连起来。
解法二:递归。
解法三:直接翻转(栈思想)。
题解: 给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
解法一:用栈,把K个数压入栈中,然后弹出来的顺序就是翻转的。
解法二:尾插法,一个指针移动到要翻转部分的最后一个元素(tail),从要翻转的第一个元素一次翻转
解法三:递归。
题解: 给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。主要优化k大于链表长度的情况。
题解: 一个机器人位于一个 m x n 网格的左上角。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径?
解法一:动态规划 时间复杂度O(mn),空间复杂度可优化至O(n)
解法二:排列组合(比较简单)
题解: 现在考虑网格中有障碍物。网格中的障碍物和空位置分别用 1 和 0 来表示。使用动态规划,遇到1跳过并且置0,时间复杂度O(mn),空间复杂度O(1)
题解: 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
依然动态规划,grid[i][j] += min(grid[i][j-1], grid[i-1][j]),第一行与第一列单独算。时间复杂度O(mn),空间复杂度O(1)。
题解: 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
解法一:滑动窗口法,起始点固定,终点滑动,遍历每个点。
解法二:双边滑动法,起始点与重点均滑动。
题解: 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
中位数将数组划为两个长度相等的部分,其中一个部分的元素总大于另一个元素。nums1和nums2的左边部分最大值都应小于nums1、nums2右边部分最小值,根据这个标准使用二分查找。
题解: 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
解法一:最长公共子串,s与s的翻转字符串的最长公共子串,还必须满足下标条件。
解法二:动态规划,初始化一、二字母回文,然后找到所有三字母回文,以此类推。时间复杂度O(n^2),空间复杂度O(n^2)。
解法三:中心扩展,2n-1个中心逐个扩展。时间复杂度O(n^2),空间复杂度O(1)。
解法四:Manacher算法,字符之间和前后加同一字符(字符串里没有的),不用考虑偶数长度回文字符串情况。
题解: 将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。
按行排序,将对应字符放入对应行即可。
题解: 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。
使用数学方法实现弹出数字与推入数字。
题解: 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。
题解: 判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
解法一:如果非负反转判断是否相等。
解法二:左右同时往之间移动比较是否相等。
题解: 给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*'的正则表达式匹配。
解法一:回溯
解法二:动态规划
题解: 给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
两头双指针,短的一边向中心移动,当长边变短边计算面积。
题解: 从大到小每一位数字顺序判断, 等于9进入下个循环,大于4小于9减5继续此循环,等于4,小于4。
题解: 构建一个字典记录所罗马数字子串,遍历整个s判断当前位置和后一个位置组成的字符串是否在字典内,如果在就记录值,不在则直接记录当前字符的值。
题解: 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
递归:递归过程中记录组合
迭代:从头取出字符串,加上当前数字对应的几个字符从队尾进入。
题解: 小、中、大括号的左边对应数字1、2、3,右边对应-1、-2、-3,指针顺序遍历。定义一个栈。遇到左括号(数字大于0),进栈该数字,遇到右括号,等于栈顶相反数,出栈,否则无效。最后栈中物元素,则返回True。否则返回False。
题解: 给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
解法一:动态规划?,初始化列表['(']与[(1,n-1)],元组第一个数代表这个字符串有1个多余的左括号,第二个数字代表还可以放置n-1个左括号。顺序取出所列表里的所有字符串,如果还可以放置左括号(元组第二个数字大于0),放置左括号加入列表;如果左括号多余右括号(元组第一个数子大于0),放置右括号加入列表。
解法二:递归,'('+i组括号+')'+n-1-i组括号,i的范围是0到n。
题解: 双指针,第一个指针固定,第二个指针往后寻找不相等的数放在第一个指针后面,然后第一个指针移动一个,第二个指针继续移动到尾部。
题解: 双指正,一头一尾,头找等于val的值,尾找不等于val的值,将尾指针的值付给头针。
题解: 给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。遍历haystack中的所有needle长度的字符串。
题解: 直观解法,被除数不断减去除数,直到被除数小于除数,符号额外处理。但是当商比较大时,循环次数过多。
加速方法:减数每一次循环增加一个除数,当除数大于被除数,减数重新等于除数。
再加速:减速每一次循环左移一位,变为2倍。
题解: 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
解法一:逐一判断s中对应长度的子串是否满足要求。
解法二:速度优化,每次移动一个单词,移动到尾部之后,再移动一个字符。
题解: 从右边找到第一对两个连续的数字满足a[i]>a[i-1],将i-1右侧大于a[i-1]的最小数字与a[i-1]交换
题解: 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。 ·我的解法:初始化一个变量lab = 0,当前长度tmp = 0,遍历字符串,遇到'('lab加一,遇到')'减一。当lab小于0,lab与tmp重新初始化为0;lab大于0,tmp加一;lab等于0,此时有一个长度为tmp的有效括号字串。将字符串反向,重复一遍上述操作。时间复杂度O(n),空间复杂度O(1). ·动态规划: ·栈:
题解: 给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
二分查找:没啥好说的@_@
题解: 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。二分查找法。
题解: 判断一个数独是否有效。遍历数独,遍历过程中将数字加入所在的行、列、块,并判断是否重复。
题解: 回溯法:先遍历一遍矩阵,记录每行、列、块包含的数字与待填空白。遍历代填空白,根据所在位置找出能填入的数字,选择一个填入,如无可填入数字,回溯到上一空白处更换数字。
题解: 报数序列是一个整数序列,按照其中的整数的顺序进行报数,得到下一个数。采用递归法。
题解: 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
回溯法:
题解: 回溯法
题解: 给定一个未排序的整数数组,找出其中没有出现的最小的正整数。先对数组排序,寻找一个元素,它后一个书大于1且比它大超过1,返回该元素+1或者1。
题解: 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。双指针法,一个指向开始,一个指向结尾,水面高度最高h为较小的值,小的一方向中心移动。新高度小于h,能蓄水h-该处高度;新高度大于h不能蓄水。更新h。
题解: 竖式乘法。
题解: 给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?' 和 '*' 的通配符匹配。'?' 可以匹配任何单个字符。'*' 可以匹配任意字符串。
·双指针
·动态规划
题解: 数组中的每个数字加上对应索引为该处能跳到的最远位置,再跳跃范围内选择能跳最远位置的位置。
题解: 给定一个没有重复数字的序列,返回其所有可能的全排列。
解法一:顺序放入序列中的元素,可以放的位置有数组长度加一个。比如先放1,只有[1],再放二,有[1,2],[2,1],再放3,有[3,1,2],[1,3,2],[1,2,3],[3,2,1],[2,3,1],[2,1,3]。
解法二:递归,取出一个元素,剩下的元素求全排列,然后将取出元素放在这些全排列的首位。
题解: 给定一个可包含重复数字的序列,返回所有不重复的全排列。
递归:先排序,取出一个元素,如果与前一个元素相同,跳过。
题解: 旋转矩形:目标为值与原位置关系,nti = j,ntj = n-i-1,四次循环交换四个数位置。需要操作的头位置为[0,n//2],[i,n-i-1]。
转置加翻:转置矩阵然后翻转每一行。
题解: 给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。取出字符串之后排序,排序之后为列表,再换为元组或字符串作为字典的键, value是包含原始字符串的列表。返回字典values。
题解: 初始化out为1,循环n次乘x。进一步优化,每次乘的数逐渐增加。
题解: 回溯法:
题解: 回溯法:返回数量,求个len
题解: 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
一遍遍历法:记录当前和,若小于0则置0。
分治法:数组分为两部分,最大和是左边部分最大和,右边部分最大和,中间部分最大和的最大值。
题解: 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。
转置法:移除第一行,加入输出列表,利用zip(*matrix)完成矩阵转置,然后将行顺序翻转,继续移除第一行。
顺序遍历法:按照规定顺序遍历矩阵。元素放入输出列表后,赋值为None,di,dj初始化为0,1,当下一个元素不存在(超出列表范围),或为None,di=dj,dj=-di,转换遍历方向。
题解: 如果数组中没有0,则返回True。当数组中有0,按照45.跳跃游戏II的方式跳跃,跳到O元素上则返回False,跳到终点返回True。
题解: 给出一个区间的集合,请合并所有重叠的区间。先按区间开始点排序,顺序取出区间放入返回列表,将取出的列表与返回列表最后一个区间比较能够合并。
题解: 给出一个无重叠的 ,按照区间起始端点排序的区间列表。在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。
解法一:加入区间,排序,找到新区间,检查左右两边能否合并,注意右边可能连续合并。
解法二:顺序遍历,找到能合并的区间或插入位置。
题解: 给定一个仅包含大小写字母和空格 ' ' 的字符串,返回其最后一个单词的长度。如果不存在最后一个单词,请返回 0 。倒序双指针,第一个指针找到非空字符,第二给指针找到空字符或开头。
题解: 给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。初始化n*n的全零矩阵,按顺序遍历(同54.螺旋矩阵)。
题解: 给出集合 [1,2,3,...,n],其所有元素共有 n! 种排列。给定 n 和 k,返回第 k 个排列。
k//(n-1)!的值加1即为首位数,采用递归从高位开始逐为确定。
题解: 可以出现的字符包括nums = ['0','1','2','3','4','5','6','7','8','9'],e = ['e'],point = ['.'],signs = ['+','-']。
·数字nums无限制;
·指数e只能出现在数字后面,且只能出现一次;
·小数点point,e前后各可出现一次,小数点之前或之后至少有边是数字;
·符号signs,只能出现在开头或e之后,后面必须有数字。
题解: 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。从尾部开始遍历,没进位终止遍历。