LeetCode刷题day02(空闲时补充其他方法...)

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;	
}

上一篇:leetCode第7题整数反转.java --day02


下一篇:day02 Docker安装及配置镜像加速