代码随想录算法训练营day57|647.回文子串516.最长回文子序列 剑指offer39、66

647.回文子串

题目链接

本题主要是确定如何定义合适的dp数组，如果定义一维的数组不好找到递推关系，如果定义二维的，向两边拓展来判断回文子串是比较合适的，所以dp[i][j]表示[i,j]的子串是否是回文子串，注意这里是是否是，而不是直接表示数量。

class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));int res=0;for(int i=s.size()-1;i>=0;i--){for(int j=i;j<s.size();j++){if(s[i]==s[j]){if(j-i<2){dp[i][j]=true;res++;}else if(dp[i+1][j-1]==true){dp[i][j]=true;res++;}}}}return res;}
};

516.最长回文子序列

题目链接

比较简单，注意单个字符一定是回文子序列，长度为1。

class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));for(int i=0;i<s.size();i++) dp[i][i]=1;for(int i=s.size()-1;i>=0;i--){for(int j=i+1;j<s.size();j++){if(s[i]==s[j]){dp[i][j]=dp[i+1][j-1]+2;}else{dp[i][j]=max(dp[i+1][j],dp[i][j-1]);}}}return dp[0][s.size()-1];}
};

错因：往里缩的时候写成了[i-1][j-1]，应该是[i+1][j-1]。

剑指 Offer 39. 数组中出现次数超过一半的数字

题目链接

方法一：哈希表。先统计每个元素出现的次数，同时进行判断，如果当前元素出现次数已经超过数组长度一半了，就返回该元素。

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int,int> hash;int n=nums.size();for(int num:nums){hash[num]++;if(hash[num]>n/2){return num;}}return -1;}
};

方法二：排序。因为题目中说了元素出现的次数超过数组长度一半，所以排序后中位数一定是众数。

class Solution {
public:int majorityElement(vector<int>& nums) {sort(nums.begin(),nums.end());int index=nums.size()/2;return nums[index];}
};

空间复杂度是O(1)的，时间复杂度是O(nlogn)，也不是最优的。

方法三：摩尔投票法。先假设第一个元素时众数，票数为1，不断向后遍历，同时进行抵消，如果已经抵消为0了，就要重新选取众数，票数为1。因为要求的数字x出现次数超过长度一半了，所以其他所有元素挨个和x抵消一遍，最后剩下的一定还是x。为什么代码中最后留下的票数不为0的一定就是x，因为最后剩下元素，说明该元素的票数没有被抵消完，又因为最后剩下的一定是x，所以最后留下的就是x。

class Solution {
public:int majorityElement(vector<int>& nums) {if(nums.size()<=2) return nums[0];int x=nums[0];int sum=1;for(int i=1;i<nums.size();i++){if(sum==0){x=nums[i];sum=1;}else{if(x==nums[i]){sum++;}else{sum--;}}}return x;}
};

时间复杂度是O(1),空间复杂度是O(n)。

注意特殊情况的判断，只有一个或两个元素的时候直接返回第一个元素值即可。

剑指 Offer 66. 构建乘积数组

题目链接

正常的思路是先求出所有元素的乘积，然后用for循环遍历，遍历到某元素时用乘积除以该元素即可，但本题不让用除法，所以只能先累乘左边的元素，再累乘右边的元素，再相乘。但是代码还是有一定技巧性的，需要注意。

class Solution {
public:vector<int> constructArr(vector<int>& a) {if(a.empty()) return vector<int>();int n=a.size();vector<int> b(n);for(int i=0,p=1;i<n;i++){b[i]=p;//记录每个元素左边元素的乘积，第一个元素左边元素乘积记为1,p开始也是记录的当前元素左边元素的乘积p*=a[i];//这执行了之后p记录的就是下一个元素左边所有元素的乘积}for(int i=n-1,p=1;i>=0;i--){b[i]*=p;//p开始记录的是当前元素右边元素的乘积，又因为b[i]已经记录了当前元素左边元素的乘积了，所以直接相乘即可p*=a[i];//开始从右向左累乘}return b;}
};