1. 知识点总结
| 题目 | 难度 | 考点 |
|---|---|---|
| 两数之和 | 🐸(基础可略) | 数组 |
| 两数相加 | 🐸 | 链表+string |
| 无重复字符的最长子串 | 🐸🐸（过很容易，但是时间和空间复杂度做得不太好昂，都是5%的胜率） | |
| 寻找两个正序数组的中位数 | 🐸 | merge的用法 |
本来不喜欢LeetCode的形式的，写顺手之后发现不需要自己处理输入输出真的好爽呀😁😁😁~
2. 分题题解
2.1 两数之和
于是还是充了会员，目前会员x2：哈喽单车+Leetcode
感觉好处就是……题解是真的多，一题多解数量远超之前别的OJ，果然💴是第一驱动力
暴力解法：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//找到sum=traget的下标
vector<int>ans;
int len=nums.size();
for(int i=0;i<len-1;i++){
for(int j=i+1;j<len;j++){
if(nums[i]+nums[j]==target){
ans.push_back(i);
ans.push_back(j);
return ans;
}
}
}
return ans;
}
};map哈希表(时间复杂度会下降，但是空间会上升)：
class Solution {
public:
#include<map>
vector<int> twoSum(vector<int>& nums, int target) {
//找到sum=traget的下标
int len=nums.size();
map<int,int>mp;
for(int i=0;i<len;i++){
if(mp.find(target-nums[i])!=mp.end()&&mp[target-nums[i]]!=i){
int a=min(mp[target-nums[i]],i);
int b=max(mp[target-nums[i]],i);
return{a,b};
}
mp[nums[i]]=i;
}
return {};
}
};2.2 两数相加
这题……ACM入门基础题稍微加了点链表的问题
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
string getNum(ListNode*head){
string num="";
if(head==NULL){
num="0";
}else{
ListNode* p,*pre;
p=pre=head;
while(p!=NULL){
num+=to_string(p->val);
pre=p;
p=p->next;
}
}
return num;
}
//两个数字求和
string ADD(string num1,string num2){
int len1=num1.length();
int len2=num2.length();
string ans="";
int cnt=0;//进位
int sum=0;
for(int i=0;i<min(len1,len2);i++){
sum=cnt+num1[i]-'0'+num2[i]-'0';
ans+=to_string(sum%10);
cnt=sum/10;
}
//对于剩下的继续
if(len1>len2){
for(int i=len2;i<len1;i++){
sum=cnt+num1[i]-'0';
ans+=to_string(sum%10);
cnt=sum/10;
}
}else if(len1<len2){
for(int i=len1;i<len2;i++){
sum=cnt+num2[i]-'0';
ans+=to_string(sum%10);
cnt=sum/10;
}
}
//cout<<"debug"<<ans<<endl;
while(cnt){
ans+=to_string(cnt%10);
cnt/=10;
}
return ans;
}
//从string中获得ListNode*
ListNode*getListFromNum(string num){
ListNode*head,*p,*pre;
head=new ListNode(num[0]-'0');
pre=head;
for(int i=1;i<num.length();i++){
p=new ListNode(num[i]-'0');
pre->next=p;
pre=p;
}
return head;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
//思路：解码
string num1=getNum(l1);
string num2=getNum(l2);
//大数加法
string ans=ADD(num1,num2);
//编码：
return getListFromNum(ans);
}
};2.3 无重复字符的最长子串
map暴力可以通过，但是完全没有优化的思路……想到了KMP
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len=s.length();
if(len==0){
return 0;
}
//当前串长度
int ans=1;
map<char,int>first_appear_pos;//某个字符第一次出现的位置
for(int i=0;i<len-1;i++){
first_appear_pos.clear();
first_appear_pos[s[i]]=i;
int j;
for(j=i+1;j<len;j++){
if(first_appear_pos.find(s[j])!=first_appear_pos.end()&&first_appear_pos[s[j]]>=i&&first_appear_pos[s[j]]<j){
//如果在之前找过了不需要往后了
break;
}else{
first_appear_pos[s[j]]=j;
}
}
ans=max(ans,j-i);
}
return ans;
}
};优化思路是滑动窗口的解法~57%和52%的获胜率
class Solution {
public:
int lengthOfLongestSubstring(string s) {
//滑动窗口题解
int len=s.size();
map<char,int>mp;
int ans=0;
if(len==0){
return ans;
}
for(int start=0,end=0;end<len;){
//在start和end之间是否出现过
char ch=s[end];
if(mp.find(ch)!=mp.end()){
//如果之前出现过并且对当前构成威胁
if(mp[ch]>=start&&mp[ch]<end){
ans=max(ans,end-start);
start++;
}else{
//出现过，但是不构成威胁,更新
ans=max(ans,end-start+1);
mp[ch]=end;
end++;
}
}else{
ans=max(ans,end-start+1);
mp[ch]=end;
}
}
return ans;
}
};2.4 寻找两个正序数组的中位数
merge的用法，两个待merge的数组必须排好序了，其次捏，新的数组需要提前开好空间，具体写法见下，时间KO89%,但是空间开销较大22%
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
//用merge的 方法
vector<int>v;
//合并前需要准备空间
int len=nums1.size()+nums2.size();
v.resize(len);
merge(nums1.begin(),nums1.end(),nums2.begin(),nums2.end(),v.begin());
if(len%2==1){
//0，1，2
return v[len/2];
}else{
//0,1,2,3
return (v[len/2]+v[len/2-1])/2.0;
}
}
};
