在排序数组中查找元素的第一个和最后一个位置 34 在排序数组中查找元素的第一个和最后一个位置 LeetCode-Python-35....字典序排数(排序 + DFS) 386 字典序排数 LeetCode-Python-387. 字符串中的第一个唯一字符 387 字符串中的第一个唯一字符 LeetCode-Python-389....按字典序排列最小的等效字符串 1061 按字典序排列最小的等效字符串 2019年力扣杯决赛-LeetCode-1062-3....按字典序排在最后的子串 1163 按字典序排在最后的子串 LeetCode-Python-1165. 单行键盘 1165 单行键盘 LeetCode-Python-1166.....在受污染的二叉树中查找元素(DFS + 集合) 1261 在受污染的二叉树中查找元素 LeetCode-Python-1262.
,找到 s 中最长的回文子串。...也就是最长回文子串。...但是这个思路是错误的,比如说字符串aacxycaa,反转之后是aacyxcaa,最长公共子串是aac,但是最长回文子串应该是aa。...def maxSubArray( nums): '''查找连续子数组的最大和 ''' # 比较当前子序和,最大子序和,返回最大值 # 定义当前子序和以及最大子序和为第一个元素...因为本身就是有序,通过 双指针法 达到 的时间复杂度。 最直接的算法实现是将指针p1 置为 nums1的开头, p2为 nums2的开头,在每一步将最小值放入输出数组中。
而无权有向图最长路径中 q-t的最长路径是是q-r-t 但 q-r缺不是q-r的最长路径 q-s-t-r是一条更长的路径 所以无权有向图最长路径不具有最优子结构 2、关于动态规划的另一个要点便是思考稍小的子问题和下一个子问题间是如何转化的也就是如何定义状态转移方程...状态转移方程的定义和我们是如何定义子问题的有关 比如:求最长连续回文串: 给出一个字符串S,求最长的连续回文串,例如串 babcbabcbaccba 最长回文是:abcbabcba 我们如果定义...,减掉的部分不需要考虑,例如:二分查找 动态规划:将原问题分成多个子问题,不同子问题间存在一定的联系,相互间有重叠的子问题 这里我个人认为动态规划分治 减治都是将大问题拆分成小问题 进行求解 区别在于...,在考虑了通向最优解的那一条路 常见的可以用动态规划解决的问题 1、最大连续子序列和: 给定k个整数的序列{N1,N2,......3、求最长连续回文串: 给出一个字符串S,求最长的连续回文串,例如串 babcbabcbaccba 最长回文是:abcbabcba 4、字符串相似度: 把两个字符串变成相同的基本操作定义如下: 1
算法 系列博客 【算法】刷题范围建议 和 代码规范 【算法】复杂度理论 ( 时间复杂度 ) 【字符串】最长回文子串 ( 蛮力算法 ) 【字符串】最长回文子串 ( 中心线枚举算法 ) 【字符串】最长回文子串...( 动态规划算法 ) ★ 【字符串】字符串查找 ( 蛮力算法 ) 【字符串】字符串查找 ( Rabin-Karp 算法 ) 【算法】双指针算法 ( 双指针算法分类 | 相向双指针 | 有效回文串..., 其合并两个数组时 , 不能在原数组中进行 ; 快速排序 , 始终都在原数组中进行 , 只涉及到交换数组中的元素 ; 正式由于该额外数组的存在 , 因此归并排序 , 并不是排序的最优算法 ; 算法要点...// 右侧排序 mergeSort(array, (start + end) / 2 + 1, end, mergeArray); // 进行归并操作, 将已经排好序的两侧的数组进行合并...merge(array, start, end, mergeArray); } // 合并两个已经排好序的数组 private void merge(int[
Unidirectional TSP 简单递推 输出字典序最小解 从后往前推 10131 – Is Bigger Smarter?...DAG的最长路 10066 – The Twin Towers LCS 10192 – Vacation LCS 147 – Dollars 全然背包求方案数 357 – Let Me Count...10306 – e-Coins 全然背包 dp[i][j] 为 横坐标为i纵坐标为y的最小数量 最后求i*i+j*j=s*s的最小的dp[i][j] 10739 – String to Palindrome...最少操作几次变成回文串 10304 – Optimal Binary Search Tree 区间dp 花费最少的二叉树 一颗二叉树的权值是全部点的权值*深度在求和 dp[i][j] = dp[i]...10154 – Weights and Measures 10453 – Make Palindrome 最少改动次数边回文+输出回文 ?
Longest Substring Without Repeating Characters 问题描述: 给定一个字符串,在不重复字符的情况下找出最长子字符串的长度。...我的方法:循环遍历字符串的每个字符,对每个字符相加,新加入的字符要查找前面的字符串是否存在新加入的字符,不存在继续下一个字符,存在比较当前最大长度。...Longest Palindromic Substring ❤️ 给定一个字符串s,找出s中最长的回文子串。可以假设s的最大长度为1000。...==Manacher‘s Algorithm==,也叫马拉车方法,方法建立了一个数组,数组第i个元素表示以 i 为中心的最长回文的半径,利用回文数的对称性,在一个大的回文数后面的索引可以利用对称性映射前面而大大简化计算...,建立了一个符号标志,然后依次生成数字,终止条件是发现字符不是数字,另外,这里为了防止溢出,在c++中使用long类型进行数字的计算,在循环的过程中会判断是否超过了整形的最大值,超过返回最大值或者最小值
无重复字符的最长子串 4. 寻找两个正序数组的中位数 5. 最长回文子串 10. 正则表达式匹配 11. 盛最多水的容器 15. 三数之和 17. 电话号码的字母组合 19....在排序数组中查找元素的第一个和最后一个位置 39. 组合总和 42. 接雨水 46. 全排列 48. 旋转图像 49. 字母异位词分组 53. 最大子数组和 55. 跳跃游戏 56....最小路径和 70. 爬楼梯 72. 编辑距离 75. 颜色分类 76. 最小覆盖子串 78. 子集 79. 单词搜索 84. 柱状图中最大的矩形 85. 最大矩形 94. 二叉树的中序遍历 96....不同的二叉搜索树 98. 验证二叉搜索树 101. 对称二叉树 102. 二叉树的层序遍历 104. 二叉树的最大深度 105. 从前序与中序遍历序列构造二叉树 114. 二叉树展开为链表 121....数组中的第K个最大元素 221. 最大正方形 226. 翻转二叉树 234. 回文链表 236. 二叉树的最近公共祖先 238. 除自身以外数组的乘积 239. 滑动窗口最大值 240.
目录 第1题:字典序排数 第2题:字符串解码 第3题:查找常用字符 第4题:所有奇数长度子数组的和 第5题:长按键入 第6题:分割字符串的最大得分 第7题:回文链表 第8题:有多少小于当前数字的数字 第...9题:两个相同字符之间的最长子字符串 第10题:分式化简 ---- 力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。...第1题:字典序排数 试题要求如下: ? 解题思路: 字典或词典顺序(也称为词汇顺序,字典顺序,字母顺序或词典顺序)是基于字母顺序排列的单词按字母顺序排列的方法。...---- 第3题:查找常用字符 试题要求如下: ? 解题思路: 遍历所有的字符串,记录(26个小写字母)每个字符在所有字符串中都出现过的“最小”次数,则为结果。...---- 第9题:两个相同字符之间的最长子字符串 试题要求如下: ?
算法小白:最近一直在研究算法,刷了很多算法题,正好活动活动大脑,来来来,赶快出题! 算法君:听好了,题目是:求一个字符串中最长的回文字符串。...算法君:算你小子聪明一回,没错,是要将已经确认的回文字符串保存起来,但并不是保存回文字符串本身。而是要保存字符串是否为回文的结果。...通过key搜索是否为回文的历史记录,也就是搜索value,在Python中字典可以实现这个功能。用字典可以吗? 算法君:字典算是一种实现,你想想用字典具体应该如何实现呢?...继续扫描长度为5的回文字符串(不存在),然后是长度为6的回文字符串(不存在),所以这个唯一的长度为4的回文字符串就是acxxcd的最长回文字符串。 算法君:这种算法还有一个名字:动态规划法。...= -1: print('最长回文字符串:',s1[p.start_index:p.start_index + p.array_len]) else: print('查找失败')
无重复字符的最长子串 4. 寻找两个正序数组的中位数 5. 最长回文子串 7. 整数反转 14. 最长公共前缀 15. 三数之和 20. 有效的括号 21. 合并两个有序链表 22....最小覆盖子串 88. 合并两个有序数组 92. 反转链表 II 94. 二叉树的中序遍历 102. 二叉树的层序遍历 103. 二叉树的锯齿形层序遍历 105....二叉树的最近公共祖先 239. 滑动窗口最大值 300. 最长递增子序列 322. 零钱兑换 394. 字符串解码 415. 字符串相加 704. 二分查找 887. 鸡蛋掉落 912....无重复字符的最长子串 4. 寻找两个正序数组的中位数 5. 最长回文子串 7. 整数反转 14. 最长公共前缀 15. 三数之和 20. 有效的括号 21. 合并两个有序链表 22....最小覆盖子串 88. 合并两个有序数组 92. 反转链表 II 94. 二叉树的中序遍历 102. 二叉树的层序遍历 103. 二叉树的锯齿形层序遍历 105.
最坏的情况下需要遍历 \cfrac{n}{2} 次 ; 因此最暴力的方法验证回文子串 , 就是验证 \cfrac{n(n+1)}{2} +1 个子字符串是否是回文串 , 每次都要遍历 \cfrac...给出一个字符串(假设长度最长为1000),求出它的最长回文子串,你可以假定只有一个满足条件的最长回文串。...1、动态规划算法 如果不使用中心线枚举算法 , 在蛮力算法的基础上 , 快速判定字符串是否是回文串 ; 使用基于动态规划的算法可以实现上述要求 ; 回文串存在特点 : 两种类型的回文串 “abba”..., “abcba” , 正序 和 倒序 是一样的 ; 回文串两头的字符相等 ; 回文串除去两头的两个字符 , 中间部分也是回文串 ; 字符串中 i ~ j 之间的字符串是回文串 ; 则...; 因此推导任意两个索引区间 i, j 之间的字符串是否是回文串时 , 将 i, j 之间的字符串是否是回文串 , 存储在一个二维布尔数组中 ; // 表示 n 个字符串中所有的字符索引之间是否是回文串
1.12 查找字符串最后一次出现位置 输出指定字符串A在字符串B中最后出现的位置,如果B中不包含A,则输出-1 从 0 开始计数 A = “hello” B = “hi how are you hello...(从0开始),若不存在该元素,返回-1。...请你找出其中不含有重复字符的最长子串的长度。...5.21 一个字符串中所有子串是回文的次数(子串) 回文是指正序(从左向右)和倒序(从右向左)读都是一样的。...,不考虑数字的顺序 连续的数字是指:123, 456, 78 这种,可以是连续的2个,也可以是多个,135 这种是不连续的。
PS:刷题为了过面试是一回事,但其实日常写写算法/数据结构题也是不错的,可以让常见的数据结构和算法可以潜移默化的影响你,进而影响日常编码,也算是一种锻炼吧。...5-最长回文子串 647-回文子串 72-编辑距离 343-剪绳子/整数拆分 91-解码方法 offer10-斐波那契数列 64-最小路径和 offer47-礼物的最大价值 62-不同路径 96...;二分查找) 23-合并K个升序链表(堆) 347-前 K 个高频元素(堆、哈希表) 字符串 题目 409-最长回文串(哈希表) offer05-替换空格 offer58/151-翻转单词顺序/ 翻转字符串里的单词...20-有效的括号(栈) 125-验证回文串(双指针) 344-反转字符串(双指针) 415-字符串相加 38-外观数列 767-重构字符串(堆、贪心算法、排序) 排序 题目 offer45-把数组排成最小的数.../在排序数组中查找元素的第一个和最后一个位置(先找左边界、再找右边界) offer53-0~n-1 中缺失的数字 287-寻找重复数(跟“数组中重复的数字”类似,但是稍微有点区别) 162-寻找峰值
Problem 2: Leetcode 316 给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。...比方说如果输入是s = "bcabc",那么输出就是"abc",可以看到确实有一个子字符串"abc",并且很明显它是字典序最小的。...对于这个问题其实很容易发现,因为我们要找的是“字典序最小的”,且不能重复,那么很明显,一个单调上升的字符串肯定是必要的(想想为什么?)。这个情况促使我们想到单调栈这个做法。...出栈的关键在于,假如说栈顶元素是 ,出栈的元素是 ,那么如果 ,说明如果入栈的话,就是之后的元素要比之前的元素小,相当于一个逆序,我们之前说过,单调上升的字符串才有可能是字典序最小的,所以这是矛盾的...给定一个字符串ss,如何去掉其中的一个字符ch,使得得到的字符串字典序最小呢?答案是:找出最小的满足 s[i]>s[i+1]的下标i,并去除字符s[i]。
LZW算法的基本原理是利用编码数据本身存在字符串重复特性来实现数据压缩,所以一个很好的选择是使用后缀树的形式来组织存储字符串及其对应压缩码值的字典。 找出字符串S的最长回文子串S1。...第一部分、Trie树 1.1、什么是Trie树 Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。...至于,有关Trie树的查找,插入等操作的实现代码,网上遍地开花且千篇一律,诸君尽可参考,想必不用我再做多余费神。 1.4、查询 Trie树是简单但实用的数据结构,通常用于实现字典查询。...注意我们需要区分不同单词的后缀,所以叶节点用不同的特殊符号与后缀位置配对。 2.3、最长回文问题的解决 有了上面的概念,本文引言中提出的查找最长回文问题就相对简单了。...查找两次的原因是我们需要考虑奇数回文和偶数回文的情况。这步要考察每坨i,所以复杂度是O(N) ; 找到最大的LCA,我们也就得到了回文的中心i以及回文的半径长度,自然也就得到了最长回文。
题目描述 这是 LeetCode 上的「516. 最长回文子序列」,难度为「中等」。 Tag : 「动态规划」、「区间 DP」 给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。...子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 示例 1: 输入:s = "bbbab" 输出:4 解释:一个可能的最长回文子序列为 "bbbb" 。...示例 2: 输入:s = "cbbd" 输出:2 解释:一个可能的最长回文子序列为 "bb" 。 提示: s 仅由小写英文字母组成 动态规划 这是一道经典的区间 DP 题。...两个具有公共回文部分的回文串之间存在拓扑序(存在由「长度较小」回文串指向「长度较大」回文串的有向边)。...在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
之前有两篇文章写了回文串和回文序列相关的问题: 经典面试题:最长回文子串 子序列解题模板:最长回文子序列 我们知道,寻找回文串的核心思想是从中心向两端扩展: string palindrome(string...return s.substr(l + 1, r - l - 1); } 因为回文串长度可能为奇数也可能是偶数,长度为奇数时只存在一个中心点,而长度为偶数时存在两个中心点,所以上面这个函数需要传入...traverse(root.right); // 后序遍历代码 } 在 学习数据结构的框架思维 中说过,链表兼具递归结构,树结构不过是链表的衍生。...我知道肯定有读者会问:这种解法虽然高效,但破坏了输入链表的原始结构,能不能避免这个瑕疵呢?...三、最后总结 首先,寻找回文串是从中间向两端扩展,判断回文串是从两端向中间收缩。 对于单链表,无法直接倒序遍历,可以造一条新的反转链表,可以利用链表的后序遍历,也可以用栈结构倒序处理单链表。
和”)”的字符串中最长的有效子字符串的长度。...Maximum Subarray/ 最大子序和 由 N 个整数元素组成的一维数组 (A[0], A[1],…,A[n-1], A[n]),这个数组有很多连续子数组,那么其中数组之和的最大值是什么呢?...(比爬楼梯需要多考虑情况) Unique Binary Search Trees/不同的二叉查找树 给出一个n,求1-n能够得到的所有二叉搜索树 Triangle/三角形最小路径和 将一个二维数组排列成金字塔的形状...二维DP 布尔数组 Longest Palindromic Substring/最长回文子串 给出一个字符串S,找到一个最长的连续回文串。...Minimum Path Sum/最小路径和 一个矩阵的左上角出发到右下角,只能向右或向下走,找出哪一条路径上的数字之和最小。
给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。...示例 示例 1: 输入:s = "bbbab" 输出:4 解释:一个可能的最长回文子序列为 "bbbb" 。...示例 2: 输入:s = "cbbd" 输出:2 解释:一个可能的最长回文子序列为 "bb" 。...解题 https://www.cnblogs.com/luo-c/p/13948591.html 子序列是非连续的,子串是连续的,注意区分; 最大最小,最长最短,首先想到的就是动态规划,在子串 s[i…...j] 中,最长回文子序列为 dp[i][j],即,在二维数组 dp 中,i,j 的下标表示的是子串的起始终止位置,这个一定要理解; 对于 dp[i][j] , 如果 s[i] == s[j] ,则 d
最长回文串 题目二、144. 二叉树的前序遍历 题目三、589. N 叉树的前序遍历 题目一、409. 最长回文串 原题链接:409....最长回文串 题目描述: 给定一个包含大写字母和小写字母的字符串 s ,返回 通过这些字母构造成的 最长的回文串 。 在构造过程中,请注意 区分大小写 。...比如 “Aa” 不能当做一个回文字符串。 / 示例 1: 输入:s = “abccccdd” 输出:7 解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。...,就是从根节点开始,先遍历左孩子,再遍历右孩子; 当根节点为空的时候,直接返回空即可; 存在根节点,我们可以使用栈结构,先进后出的特点,将根节点以及一路而下的左孩子压栈,当没有左孩子,我们就能让栈顶元素出栈...n 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null 分隔(请参见示例)。
领取专属 10元无门槛券
手把手带您无忧上云