最长专题
poj3261（可重复k次的最长子串）
题意：可重复k次的最长子串 解题思路：求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N，但实际复杂度很低。题目数据也比较水，不然估计过不了。 代码入下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)
求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
hihocoder1050 : 树中的最长路
时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上回说到，小Ho得到了一棵二叉树玩具，这个玩具是由小球和木棍连接起来的，而在拆拼它的过程中，小Ho发现他不仅仅可以拼凑成一棵二叉树！还可以拼凑成一棵多叉树——好吧，其实就是更为平常的树而已。 但是不管怎么说，小Ho喜爱的玩具又升级换代了，于是他更加爱不释手（其实说起来小球和木棍有什么好玩的是吧= =）。小Ho手
POJ1631最长单调递增子序列
最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ
计蒜客 Skiing 最长路
In this winter holiday, Bob has a plan for skiing at the mountain resort. This ski resort has MM different ski paths and NN different flags situated at those turning points. The ii-th path from the
day-50 求出最长好子序列 I
思路 二维dp,dp[i][h]表示nums[i] 结尾，且有不超过 h 个下标满足条件的最长好子序列的长度（0<=h<=k），二维数组dp初始值全为1 解题过程 状态转换方程： 1.nums[i]==nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h]+1) 2.nums[i]!=nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h-1
LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度
3177. 求出最长好子序列 II 题目链接 题目描述 给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标i满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。 实例1: 输入：nums = [1,2,1,1,3],
Leetcode面试经典150题-128.最长连续序列-递归版本另解
之前写过一篇这个题的，但是可能代码比较复杂，这回来个简洁版的，这个是递归版本 可以看看之前的版本，两个版本面试用哪个都保过 解法都在代码里，不懂就留言或者私信 class Solution {/**对于之前的解法，我现在提供一共更优的解，但是这种可能会比较难懂一些（思想方面）代码其实是很简洁的，总体思想如下：不需要排序直接把所有数放入map，map的key是当前数字，value是当前数开始的
【UVA】10066-The Twin Towers（最长公共子串问题）
赤裸裸的最长公共子串问题，没什么好说的，注意的是，每组数据后面都有一个空行。 13996019 10066 The Twin Towers Accepted C++ 0.015 2014-08-06 00:34:53 #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using
【UVA】10534 - Wavio Sequence（LIS最长上升子序列）
这题一看10000的数据量就知道必须用nlog(n)的时间复杂度。 所以特意去看了最长上升子序列的nlog(n)的算法。 如果有2个位置，该位置上的元素为A[i]和A[j],并且他们满足以下条件: 1.dp[i] = dp[j] (dp[x]代表以x结尾的最长上升子序列长度) 2.A[i] < A[j] 3.i < j 那么毫无疑问，选择dp[i] 一定优于选择dp[j] 那么
leetcode：3176 求出最长好子序列 使用动态规划
3176. 求出最长好子序列 题目链接https://leetcode.cn/problems/find-the-maximum-length-of-a-good-subsequence-i/ 题目描述 给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标 i 满足 seq[i] != se
动态规划-最长定差子序列
题目描述 给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。 子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。 示例 ： 输入：arr = [1,5,7,8,5,3,4,2,1,0], difference = -2 输
leetcode:516 最长回文字序列 动态规划
516. 最长回文字序列 题目链接https://leetcode.cn/problems/longest-palindromic-subsequence/ 题目描述 给定一个字符串 s，找到 s 中最长的回文子序列。你可以假设 s 的最大长度为 1000。 示例 1: 输入: "bbbab" 输出: 4解释: 一个可能的最长回文子序列是 "bbbb"。
leetcode： 5. 最长回文子串
5. 最长回文子串 题目链接https://leetcode.cn/problems/longest-palindromic-substring/ 题目描述 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2：
Python高效计算两个字符串的最长公共子序列
Python高效计算两个字符串的最长公共子序列 在Python面试中，考官通常会关注候选人的编程能力、问题解决能力以及对Python语言特性的理解。计算两个字符串的最长公共子序列（Longest Common Subsequence, LCS）是一个经典的动态规划问题，广泛应用于文本比较、DNA序列分析等领域。本文将详细介绍如何编写一个函数，计算两个字符串的最长公共子序列，确保代码实用性强，条理
java常用算法之最长回文子串(Longest Palindromic Substring)
方法一：时间复杂度为O(n^3) public static String longestPalindrome1(String s) {int maxPalinLength = 0;String longestPalindrome = null;int length = s.length();// check all possible sub stringsfor (int i = 0; i
每日一练：无重复字符的最长字串
一、题目要求 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。 示例 1: 输入: s = "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: s = "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 输入: s = "
【LeetCode】03.无重复字符的最长子串
题目要求 做题链接3.无重复字符的最长子串 解题思路 我们通过参考给出的输入很容易就会从每一个字符开始，看看最长能延续多长。我们通过画图发现一旦一个字符可以延续到另一个字符，那么我们就不需要考虑他中间仍然存在字符重复的问题。因此而后我们发现可以使用滑动窗口进行优化。 代码实现 class Solution {public:int lengthOfLongestSubstring(s
3、无重复字符的最长子串
题目 链接：leetcode链接 思路分析（滑动窗口） 子串是连续的，很容易联想到滑动窗口，处理连续子串问题很方便。 先设置left和right两个指针，从0位置开始移动。 为了去判断窗口里面有没有出现重复的子串，可以使用一个hash表来存出现的次数， 这里为了防止有些小伙伴不会用hash表，就先用数组模拟一下hash表吧。 当hash表里面没出现right字符时，就插入hash表，r
psd面试（最长回文子序列+动态规划）；
点击打开链接 链接：https://www.nowcoder.com/acm/contest/90/D来源：牛客网 题目描述 掌握未来命运的女神 psd 师兄在拿了朝田诗乃的 buff 后决定去实习。 埃森哲公司注册成立于爱尔兰，是一家全球领先的专业服务公司，为客户提供战略、咨询、数字、技术和运营服务及解决方案。他们立足商业与技术的前沿，业务涵盖40多个行业，以及企业日常运营部门的各个
后缀数组 - 求最长回文子串 + 模板题 --- ural 1297
1297. Palindrome Time Limit: 1.0 second Memory Limit: 16 MB The “U.S. Robots” HQ has just received a rather alarming anonymous letter. It states that the agent from the competing «Robots Unlim
【hot100篇-python刷题记录】【最长回文子串】
R7-多维dp篇 思路： 两种情况，中心1个数，中心2个数 大体：中间点扩展原则 class Solution:def expand(self,s,left,right):while left>=0 and right<len(s) and s[left]==s[right]:left-=1right+=1#不满足就回退return left+1,right-1def longe
探索C++编程技巧：计算两个字符串的最长公共子串
探索C++编程技巧：计算两个字符串的最长公共子串 在C++面试中，考官通常会关注候选人的编程能力、问题解决能力以及对C++语言特性的理解。一个常见且经典的问题是计算两个字符串的最长公共子串（Longest Common Substring, LCS）。本文将详细介绍如何编写一个函数来解决这个问题，并深入探讨相关的编程技巧和优化方法。 目录 引言问题描述解决思路实现步骤 基础实现动态规划优化代
Bellman_Ford变形求最长路+正权回路或spfa——POJ 1860
对应POJ题目：点击打开链接 Currency Exchange Time Limit: 1000MS Memory Limit: 30000KTotal Submissions: 20814 Accepted: 7451 Description Several currency exchange points are working in our city. L
最长上升子序列 二分做法
给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。 输入格式 第一行包含整数N。 第二行包含N个整数，表示完整序列。 输出格式 输出一个整数，表示最大长度。 数据范围 1≤N≤10001≤N≤1000， −109≤数列中的数≤109−109≤数列中的数≤109 输入样例： 73 1 2 1 8 5 6 输出样例： 4 二分做出的答案只有数量是最长上升子