- 博客(154)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 5. 最长回文子串
题目给你一个字符串 s，找到 s 中最长的回文子串。示例：输入：s = "babad"输出："bab"解释："aba" 同样是符合题意的答案。输入：s = "cbbd"输出："bb"分析： 此题有两种解法，一种是双指针，一种是动态规划，我们知道回文子串是一个中心对称序列，中心点可能是一个，也可能是两个，取决于子串长度奇偶，双指针法指向回文子串的中心点，然后往两边查找，找到以此为中心的最长回文子串，遍历字符串，分别却其中一个以及相邻两个字符为中心点，进行查找，见方法1方法1： 双指针法，
2021-11-08 20:53:14
196
原创 3. 无重复字符的最长子串
题目给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。示例：输入: s = "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。输入: s = "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。来源：力扣（LeetCode）链接：https://leetcode-cn.com/problem
2021-11-05 19:23:22
207
原创 128. 最长连续序列
题目给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。示例1：输入：nums = [100,4,200,1,3,2]输出：4解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例2：输入：nums = [0,3,7,2,5,8,4,6,0,1]输出：9分析： 如果是先排序，再对排序好的数组遍历的话时间复杂度是O(nlog(n))O(nlog(n))O(nlog(
2021-11-03 20:33:49
216
原创 卷积计算代码实现
问题写代码实现卷积操作问题解答有两种方式实现，一种是通过滑动窗口的方式，一种是通过转化为矩阵乘法的方式， 后者比前者执行速度快许多将卷积运算转化为矩阵乘法，从乘法和加法的运算次数上看，两者没什么差别，但是转化成矩阵后，运算时需要的数据被存在连续的内存上，这样访问速度大大提升（cache），同时，矩阵乘法有很多库提供了高效的实现方法，像BLAS、MKL等，转化成矩阵运算后可以通过这些库进行加速。缺点呢？这是一种空间换时间的方法，消耗了更多的内存——转化的过程中数据被冗余存储。还有两张形象化的图片
2021-11-02 15:32:43
896
原创 72. 编辑距离
题目给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符示例：输入：word1 = "horse", word2 = "ros"输出：3解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')分析： 编辑距离问题，详解见动态规划：编辑距离
2021-10-28 18:05:42
62
原创 494. 目标和
题目给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。示例1：输入：nums = [1,1,1,1,1], target = 3输出：5解释：一共有 5 种方法让最终目标和为 3 。
2021-10-27 20:10:51
84
原创 面试题 16.21. 交换和
题目给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。示例：输入: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]输出: [1, 3]分析： 先求出两个数组和之间的差值，假设差值diff = sum1 - sum2, 那么只有当数组1中的元素减去数组2
2021-10-21 20:18:43
115
原创 面试题 16.20. T9键盘
题目在老式手机上，用户通过数字键盘输入，手机将提供与这些数字相匹配的单词列表。每个数字映射到0至4个字母。给定一个数字序列，实现一个算法来返回匹配单词的列表。你会得到一张含有有效单词的列表。映射如下图所示：示例：输入: num = "8733", words = ["tree", "used"]输出: ["tree", "used"]**分析：**对匹配列表中的每一个单词进行判断，看每一个位置的字母是否存在于待检索的数字对应的字母串中，如果全部满足，则此单词符合映射。此外还有一个种更简单的做法，
2021-10-21 19:36:28
133
原创 面试题 17.24. 最大子矩阵
题目给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。示例：输入：[ [-1,0], [0,-1]]输出：[0,1,0,1]解释：输入中标粗的元素即为输出所表示的矩阵分析： 我们知道一维数组和最大子序列可以用动态规划解决，见连续数列， 那么此题是二维数
2021-10-20 20:22:46
89
原创 面试题 17.19. 消失的两个数字
题目给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？以任意顺序返回这两个数字均可。示例1：输入: [1]输出: [2,3]示例2：输入: [2,3]输出: [1,4]分析： 本题要求空间复杂度是O(1)O(1)O(1), 有以下三种方法：方法1： 假设缺失的两个数是a, b, 那么对N个数求和减去数组中的元素，就能得到a+ba+ba+b的结果，同理对N个数求平方和减去数组中元素的平方和，就能得到a2+b2a^
2021-10-15 18:20:20
223
原创 2021-10-1面试题 17.18. 最短超串4
题目假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。示例1：输入:big = [7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]small = [1,5,9]输出: [7,10]示例2：输入:big = [1,2,3]small = [4]输出: []分析： 滑动窗口算法class Sol
2021-10-14 11:01:18
116
原创 面试题 16.24. 数对和
题目设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。示例1：输入: nums = [5,6,5], target = 11输出: [[5,6]]示例2：输入: nums = [5,6,5,6], target = 11输出: [[5,6],[5,6]]分析： 先对数组进行升序排序，然后通过左右双指针，两数相加等于target,则记录，同时两个指针均位移一步，如果大于target,则右指针位移一步，小于target则左指针位移一步。方法1： 排序+双指针c
2021-10-12 21:08:47
166
原创 面试题 10.02. 变位词组
题目编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。示例：输入: ["eat", "tea", "tan", "ate", "nat", "bat"],输出:[ ["ate","eat","tea"], ["nat","tan"], ["bat"]]分析： 遍历字符串数组，通过哈希字典用来存储变位词，key值可以用词排序后的结果，value是一个list,用来存储变位词，排序的时间复杂度为O(klogk)O(klogk)O(kl
2021-10-12 20:09:31
109
原创 面试题 17.11. 单词距离
题目有个内含单词的超大文本文件，给定任意两个单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?示例：输入：words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student"输出：1分析： 一种解法是采用双指针，遍历数组，记录找到的单词的位置，两个指针单词不同则计算中间的距离，
2021-10-11 21:08:14
104
原创 面试题 17.10. 主要元素
题目数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。示例1：输入：[1,2,5,9,5,9,5,5,5]输出：5示例2：输入：[3,2]输出：-1分析： 如果没有要求空间复杂度是O(1),此问题可以创建一个哈希表统计每一个数出现的次数即可，但是在O(1)空间复杂度的情况下，我们可以采用摩尔投票法，假设数组中一定存在超过一半的众数，每次消除数组中两个不同的数，那么数组
2021-10-11 20:29:44
77
原创 面试题 17.09. 第 k 个数
题目有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。示例：输入: k = 5输出: 9分析： 对所有因子只能为3，5，7的数字进行排序，找到第k位，暴力解法是对此前出现的所有的数都与3，5，7相乘，找到大于k-1位且最小的那个数即为第k位数，动态规划暴力枚举，见方法1方法1： dp暴力解法，时间复杂度O(3n2)O(3n^2)O(3n2)class Solut
2021-09-29 16:24:49
107
原创 python常见语法
key=lambda x:(x[0], x[1])在python中隐函数常用于对数组进行排序，上述隐函数的含义指的是优先基于数组元素中的第一位进行排序，若遇到相等的情况，则基于第二位元素进行排序a = [[2, 3], [5, 2], [4, 7], [4, 6], [4, 8]]a.sort(key=lambda x:(x[0], x[1]))print(a)[[2, 3], [4, 6], [4, 7], [4, 8], [5, 2]]key=lambda x:(x[0], -x[1.
2021-09-29 14:55:55
394
原创 面试题 17.08. 马戏团人塔
题目有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。示例：输入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]输出：6解释：从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)分析：
2021-09-28 21:06:27
144
原创 面试题 17.06. 2出现的次数
题目编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。示例：输入: 25输出: 9解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次)分析： 数位DP问题，重点是看出不同位之间的关联，通过递归法进行解决class Solution: def numberOf2sInRange(self, n: int) -> int: if n < 2: return 0
2021-09-28 17:01:58
139
原创 面试题 17.05. 字母与数字
题目给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。示例：输入: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]输出: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]分析： 首先前
2021-09-28 14:23:27
159
原创 面试题 17.04. 消失的数字
题目数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？示例：输入：[3,0,1]输出：2分析： 直观上的一种解法是对数组中的所有数字相加，然后与1到n的和求差值，差值就是缺失的整数。第二种解法充分利用到异或运算特性，即异或运算具备交换律和结合律，a^b ^a=b, a ^a=0, a ^0=a, 对数组中所有的数字进行异或运算，然后与1到n的数进行异或运算，最终的结果就是缺失的值。方法1： 求和取差值class Solution
2021-09-27 19:32:20
52
原创 面试题 08.14. 布尔运算
题目给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成。实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。示例：输入: s = "1^0|0|1", result = 0输出: 2解释: 两种可能的括号方法是1^(0|(0|1))1^((0|0)|1)分析： 区间动态规划，重要的是找到该问题的子问题，找到状态转移方程，假设字符串长度为l, 从下标
2021-09-27 17:43:56
534
原创 面试题 17.22. 单词转换
题目给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。示例1：输入:beginWord = "hit",endWord = "cog",wordList = ["hot","dot","dog","lot","log","cog"]输出:["hit","hot","dot","lot","log","cog"]示例2：输
2021-09-24 19:47:50
149
原创 面试题 17.21. 直方图的水量
题目给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。示例：输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6分析： 只有凹槽处能存水，判断是否为凹槽只需要判断左右两边是否均存在高度大于自己的直方图，且该处存水的量取决于左右两边直方图高度较小的那个与自身的高度差，因此，一种暴力解法是：遍历每一个位置，对当前位置找到左侧大于自身高度的直方图，右侧大于自身高度的直方图，然后求较小的那个与自身的高度差，即为当前位置可存水的量。第
2021-09-24 17:41:24
185
原创 面试题 16.26. 计算器
题目给定一个包含正整数、加(+)、减(-)、乘()、除(/)的算数表达式(括号除外)，计算其结果。表达式仅包含非负整数，+， - ，，/ 四种运算符和空格 。 整数除法仅保留整数部分。示例：输入: "3+2*2"输出: 7输入: " 3+5 / 2 "输出: 5分析： 通过栈实现运算，对于遇到“+”则将或者“-”则将数字入栈，遇到“*”或者“/”则将栈顶的数字出栈运算，之后运算的结果入栈，创建一个变量用来记录当前运算符号的前一个运算符，最后将栈中的数字累加即可class Soluti
2021-09-24 11:09:19
98
原创 面试题 17.01. 不用加号的加法
题目设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。示例：输入: a = 1, b = 1输出: 2分析： 本题目考察的是位运算，在位运算中，异或运算^可以看作是不进位的加法运算，因为只有当相同位置均为1的时候才会考虑进位，因此，可以通过&运算获取对应位置均是1的信息，然后左移一位，与上述的异或运算值相加，就可以得到最终的结果，即a+b=(a ^b)+(a&b)<<1, 可以看到右边同样使用到了加法，因此等号右侧可以看成左右两个值相加，可以通过递归实现加
2021-09-22 21:04:24
143
原创 面试题 17.17. 多次搜索
题目给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。输出smalls中的字符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。示例：输入：big = "mississippi"smalls = ["is","ppi","hi","sis","i","ssippi"]输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]分析： 第
2021-09-22 20:10:36
141
原创 面试题 17.16. 按摩师
题目一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。示例1：输入： [1,2,3,1]输出： 4解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。示例2：输入： [2,1,4,5,3,1,1,3]输出： 12解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3
2021-09-22 18:21:42
103
原创 面试题 17.15. 最长单词
题目给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。示例：输入： ["cat","banana","dog","nana","walk","walker","dogwalker"]输出： "dogwalker"解释： "dogwalker"可由"dog"和"walker"组成。分析： 题目要求找到长度最大的单词，且该单词是由单词组中其它单词组成，首先可以对单词
2021-09-18 16:15:21
499
原创 面试题 17.14. 最小K个数
题目设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。示例：输入： arr = [1,3,5,7,2,4,6,8], k = 4输出： [1,2,3,4]分析： 一种方法是创建一个长度为k的数组，保留最小的k个元素，从左往右遍历arr时，对当前元素与数组中元素做比较，替换掉大于当前元素的数组中的最大的那个元素，时间复杂度O(n∗k)O(n*k)O(n∗k)， 第二种方法是，先进行排序，然后返回前k个元素，时间复杂度O(nlogn)O(nlogn)O(nlogn)方法1： 遍历，
2021-09-18 14:58:36
114
原创 面试题 17.13. 恢复空格
题目哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!“已经变成了"iresetthecomputeritstilldidntboot”。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。注意：本题相对原题稍作改动，只
2021-09-18 11:44:06
65
原创 面试题 17.12. BiNode
题目二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。返回转换后的单向链表的头节点。注意：本题相对原题稍作改动示例：输入： [4,2,5,1,3,null,6,0]输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]分析： 对二叉树结构重新构建，左节点为None，右节点为二
2021-09-17 13:53:13
114
原创 面试题 16.05. 阶乘尾数
题目设计一个算法，算出 n 阶乘有多少个尾随零。示例1：输入: 3输出: 0解释: 3! = 6, 尾数中没有零。分析： 连续相乘的若干个数中，尾数为0的个数取决于这些数中能拆分出多少2和5相乘，比如3456就能拆出一个25，那么积的尾数就只有一个0，对于阶乘来说，拆分出的2肯定比5多，因此，0的个数取决于拆分出5的个数，5的倍数均能拆出一个因子5，5的平方倍数均能拆出两个因子5，5的立方能拆出3个因子5，以此类推。统计出n的范围内5的倍数，525^252的倍数，5t(5t<=n)5^t
2021-09-16 10:52:08
83
原创 面试题 10.09. 排序矩阵查找
题目给定M×N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。示例：[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]给定 target = 5，返回 true。给定 target = 20，返回 false。分析： 因为矩阵每一行每一列都具备升序的特征，假如从（0， 0）点开始查找，只需要
2021-09-15 20:27:22
317
原创 面试题 08.06. 汉诺塔问题
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:(1) 每次只能移动一个盘子;(2) 盘子只能从柱子顶端滑出移到下一根柱子;(3) 盘子只能叠在比它大的盘子上。请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。你需要原地修改栈。示例1： 输入：A = [2, 1, 0], B = [], C = [] 输出：C = [2, 1, 0
2021-09-15 15:19:08
56
原创 面试题 10.11. 峰与谷
题目在一个整数数组中，“峰”是大于或等于相邻整数的元素，相应地，“谷”是小于或等于相邻整数的元素。例如，在数组{5, 8, 4, 2, 3, 4, 6}中，{8, 6}是峰， {5, 2}是谷。现在给定一个整数数组，将该数组按峰与谷的交替顺序排序。示例：输入: [5, 3, 1, 2, 3]输出: [5, 1, 3, 2, 3]分析： 题目中没有说明按照峰-谷-峰还是谷-峰-谷的顺序，自己定义一种即可，直观上的一种解法是先对数组进行排序，然后按照步长为2从左往右调换相邻两位数即可，第二种方法就是
2021-09-14 20:47:28
164
原创 面试题 10.01. 合并排序的数组
题目给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。初始化 A 和 B 的元素数量分别为 m 和 n。示例：输入:A = [1,2,3,0,0,0], m = 3B = [2,5,6], n = 3输出: [1,2,2,3,5,6]分析： 对两个已经排序好的数组合并排序，直观上一种解法是先合并两个数组，然后进行排序，可以选择插入排序或者快排，第二种解法是采用双指针，从左到右遍历两个数组，每次取较小的放到新
2021-09-14 14:32:15
110
原创 面试题 08.02. 迷路的机器人
设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角移动到右下角的路径。网格中的障碍物和空位置分别用 1 和 0 来表示。返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径，返回空数组。示例：输入:[ [0,0,0], [0,1,0], [0,0,0]]输出: [[0,0],[0,1],[0,2],[1,2],[2,2]]解释:
2021-09-13 20:56:41
86
原创 面试题 04.09. 二叉搜索树序列
题目从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。给定一个由不同节点组成的二叉搜索树，输出所有可能生成此树的数组。示例： 2 / \ 1 3返回：[[2,1,3],[2,3,1]] 6 / \ 3 9 / \ 1 4 返回：[[6,3,9,1,4],[6,3,9,4,1],[6,3,1,9,4],[6,3,1,4,9],[6,3,4,9,1]
2021-09-10 19:54:26
101
原创 面试题 04.12. 求和路径
题目给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。示例：给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ /
2021-09-10 15:50:29
87
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人