3. 无重复字符的最长子串
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
示例 4:
输入: s = "" 输出: 0
思路分析:
该题有如下坑
1.输入的字符不一定是26个字母(虽说案例没提到) 由于字符Ascii是从0-255 s[i]-'0’可能出现负数,所以可以定义大点(有点类似于Hash表的思想)
2.该序列可能就有一条,所以求maxlen = max(maxlen,temp);的步骤在循环外也得再来一次.
3. 然后就是暴力法解决就OK.
AC代码
int lengthOfLongestSubstring(string s) { int maxlen = 0,temp = 0; int ch[505]; memset(ch,0,sizeof(ch)); int len1 = s.size(); for(int i = 0;i < len1;i++){ if(ch[(s[i]-'0' + 500) % 500 ]==0){ ch[(s[i]-'0' + 500) % 500 ]= 1; temp++; }else{ maxlen = max(maxlen,temp); memset(ch,0,sizeof(ch)); i = i-temp; temp = 0; } } maxlen = max(maxlen, temp); return maxlen; } int main(){ string s = "bbbbb"; int ans = lengthOfLongestSubstring(s); cout<<ans<<endl; return 0; }
4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
示例 1:
输入:nums1 = [1,3], nums2 = [2] 输出:2.00000 解释:合并数组 = [1,2,3] ,中位数 2
示例 2:
输入:nums1 = [1,2], nums2 = [3,4] 输出:2.50000 解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
示例 3:
输入:nums1 = [0,0], nums2 = [0,0] 输出:0.00000
示例 4:
输入:nums1 = [], nums2 = [1] 输出:1.00000
示例 5:
输入:nums1 = [2], nums2 = [] 输出:2.00000
分析:水题一道:
AC代码:
//水题一道 #include<bits/stdc++.h> using namespace std; double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { vector<int> nums3; int len1 = nums1.size(); int len2 = nums2.size(); for(int i = 0;i<len1;i++){ nums3.push_back(nums1[i]); } for(int i = 0;i<len2;i++){ nums3.push_back(nums2[i]); } sort(nums3.begin(),nums3.end()); if((len1+len2)%2==0){//nums3是偶数 4 2,3 0 1 2 3 return (nums3[(len1+len2)/2-1] + nums3[(len1+len2)/2])/2.0; }else{ return nums3[(len1+len2)/2]*1.0;//2 1 3/2 0 1 2 } } int main(){ vector<int> nums1={1,2}; vector<int> nums2 = {3,4}; double ans = findMedianSortedArrays( nums1, nums2); cout<<ans<<endl; return 0; }
5. 最长回文子串
给你一个字符串 s,找到 s 中最长的回文子串。
示例 1:
输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd" 输出:"bb"
示例 3:
输入:s = "a" 输出:"a"
示例 4:
输入:s = "ac" 输出:"a"
方法一:暴力法+优化
296ms 13.9MB string longestPalindrome1(string s) { int flag = 0; string ans=""; for(int i = 0;i < s.size();i++){//字符串:i--->j for(int j = i;j<s.size();j++){ if(j-i+1 <= ans.size()){//如果待判断的字符串长度比已经找到的还要小,则寻找下一个,因为我们的目的是寻找长的回文串. continue; } flag = 1; //判断i-j是不是回文的. for(int k = 0;k<(j-i+1)/2;k++){//0- (j-i+1)/2-1 if(s[i+k]!=s[j-k]){ flag = 0;//不是回文. break; } } if(flag){ if(j-i+1 > ans.size()){ ans = s.substr(i,j-i+1); } } } } return ans; }
方法二:反转字符串
先把字符串S反转S1,然后再依次枚举子串,如果子串能在S1中找到,则说明该子串S3可能是回文的.然后把该子串反转为S4,如果S3==S4,则说明该S3一定是回文的.
同样也要用到和上个方法一样的优化.
// 1512ms 577.7MB string longestPalindrome(string s) { string s2 = s;//存放反转的字符串. reverse(s2.begin(),s2.end()); if(s==s2){ return s; } string ans=""; string temp;//存放待验证子串 for(int i = 0;i < s.size();i++){//字符串:i--->j temp=""; for(int j = i;j<s.size();j++){ temp = temp+s[j]; if(j-i+1 <= ans.size()){ continue; } if(s2.find(temp)!=-1){//如果s2可以找到 string q = temp; reverse(q.begin(),q.end());//进行反转 if(temp==q){//如果反转后和temp相等,说明是个回文的. ans = temp; } }else{//如果找不到说明,说明temp开头的这个不可能是回文串的子序列.因为 回文串 如:abcdefgfedcba cde edc break; } } } return ans; }