做一个卖东西的网站多少钱,网络广告的优缺点,南昌谁做网站设计,商标在线设计logo图案今天无意点进一个回文串的题目#xff0c;对于回文串我第一印象就用双指针#xff0c;但是确实没写出来#xff0c;看了评论区题解#xff0c;绝大多数都是用dp来做的#xff0c;但是找到一个用双指针做的#xff0c;刚好延续思路#xff0c;先把题目贴出来。
5、最长回…今天无意点进一个回文串的题目对于回文串我第一印象就用双指针但是确实没写出来看了评论区题解绝大多数都是用dp来做的但是找到一个用双指针做的刚好延续思路先把题目贴出来。
5、最长回文子串
给你一个字符串 s找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同则该字符串称为回文字符串。 示例 1
输入s babad
输出bab
解释aba 同样是符合题意的答案。示例 2
输入s cbbd
输出bb提示
1 s.length 1000s 仅由数字和英文字母组成 这道题目之前一直做不对的原因是我一直想的是回文串的中心点只能从给的字符串中心点取这就思想有问题了。okok看看这道题目双指针的解法先说复杂度时间复杂度on^2空间复杂度o1。核心思想其实是回文串就两种可能一种是中间一个数值一种是中间两个数值因此就一个一个试然后找到最长的但是需要记录下来最长的start和end这个公式反正有点迷糊但是一写还真是这样。
class Solution {
public:string longestPalindrome(string s) {int len s.size();if(len 0 || len 1)return s;int start 0;int end 0;int mlen 0;for(int i 0;i len;i){int len1 expendaroundcenter(s, i, i);int len2 expendaroundcenter(s, i, i1);mlen max(max(len1, len2), mlen);if(mlen end - start 1){start i - (mlen-1) / 2;end i mlen / 2;}}return s.substr(start, mlen);}
private:int expendaroundcenter(string s, int left, int right){int L left;int R right;while(L 0 R s.length() s[R] s[L]){L--;R;}return R - L - 1;}
};
今天的每日一题目题没看懂等状态好了再看看。 前几天看的背包问题今天看到一道纯种的背包太纯了
279、完全平方数
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。
示例 1
输入n 12
输出3
解释12 4 4 4
示例 2
输入n 13
输出2
解释13 4 9
提示
1 n 104 class Solution {
public:int numSquares(int n) {vectorint dp(n 1, INT_MAX);dp[0] 0;for (int i 0; i n; i) { for (int j 1; j * j i; j) {dp[i] min(dp[i - j * j] 1, dp[i]);}}return dp[n];}
}; 75、颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums 原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1
输入nums [2,0,2,1,1,0]
输出[0,0,1,1,2,2]示例 2
输入nums [2,0,1]
输出[0,1,2]提示
n nums.length1 n 300nums[i] 为 0、1 或 2
进阶
你能想出一个仅使用常数空间的一趟扫描算法吗 这道题目看到评论区有很巧妙的写法但是呢我选择直接冒泡前几天总结了点冒泡排序和快排这里就用上了巧妙的做法就不贴了。
class Solution {
public:void sortColors(vectorint nums) {for(int i 0;i nums.size() - 1;i){for(int j 0;j nums.size() - i -1;j){if(nums[j] nums[j 1]){int tmp nums[j];nums[j] nums[j 1];nums[j 1] tmp;}}}}
};
