题目3：无重复字符的最长子串（YES）
- 解题思路：其实最好想到的方法就是使用两层for,让每个字符都可以是子串的首字符，查看哪个子串的长度最长即可。
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串的长度。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
//暴力的一次for,检查每个字符作为首字符时候的最长子串
if(s.size()==0)
{
return 0;
}
int max_ans=INT_MIN;
for(int i=0;i<s.size();i++)
{
unordered_map<int,int>map;
int temp=0;
for(int j=i;j<s.size();j++)
{
//使用哈希表来检测是否重复
map[s[j]]++;
if(map[s[j]]>1)
{
break;
}
temp++;
if(temp>max_ans)
{
max_ans=temp;
}
}
}
return max_ans;
}
};
题目146：LRU缓存（YES）
- 解题思路：使用双链表加上哈希表来实现，哈希表用来查看节点是否存在，双链表用来刷新优先级。这题需要非常关注。
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
- LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
- void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
//这题使用使用双链表+哈希表
//双链表是用来每次要刷新优先级的时候都将节点移动到表头
//哈希表是用来查看节点中是否存在key对应的节点
struct DLinkList
{
int key,value;
DLinkList*prev;//前指针
DLinkList*next;//后指针
//无参构成
//这个主要是为了构造虚拟头尾节点
DLinkList():key(0),value(0),prev(nullptr),next(nullptr){}
//有参构造
DLinkList(int key,int value):key(key),value(value),prev(nullptr),
next(nullptr){}
};
class LRUCache {
private:
int size;//当前节点的大小
int capacity;//实际可存储的大小
//虚拟头尾节点，主要是方便进行插入删除操作
DLinkList*head;
DLinkList*tail;
//哈希表,用key来查找是否存在节点
unordered_map<int,DLinkList*>map;
public:
LRUCache(int capacity) {
this->size=0;
this->capacity=capacity;
//构造虚拟头尾节点
head=new DLinkList();
tail=new DLinkList();
head->next=tail;
tail->prev=head;
}
int get(int key) {
//查看节点是否存在，且要刷新一次优先级
if(!map.count(key))
{
//不存在
return -1;
}
//存在，则刷新优先级,就是移动到表头
//先取出节点
DLinkList*node=map[key];
moveTohead(node);
return node->value;
}
void put(int key, int value) {
//存放节点
if(!map.count(key))
{
//不存在，新建一个节点
DLinkList*node=new DLinkList(key,value);
//插入到表头
InsertToHead(node);
size++;
//存入哈希表中
map[key]=node;
//判断是否超出
if(size>capacity)
{
//要删除末尾的节点，也就是最久为使用的关键字
DLinkList*temp = move_tail();
//要从哈希表中删除这个节点
map.erase(temp->key);
//释放要删除的节点
delete temp;
size--;
}
}else
{
//存在，修改value
//先取出节点
DLinkList*node=map[key];
node->value=value;
//这个也要修改优先级
moveTohead(node);
}
}
void moveTohead(DLinkList*node)
{
//将节点移动到表头，这是节点本来就有的
//先删除这个节点
node->prev->next=node->next;
node->next->prev=node->prev;
//将节点放入到表头
//未了防止连接断掉，先处理后面的
head->next->prev=node;
node->next=head->next;
head->next=node;
node->prev=head;
}
void InsertToHead(DLinkList*node)
{
//这个是刚刚申请的直接插入表头即可
//先处理后面的
head->next->prev=node;
node->next=head->next;
head->next=node;
node->prev=head;
}
DLinkList*move_tail()
{
//删除末尾的节点
DLinkList*temp=tail->prev;
tail->prev=temp->prev;
temp->prev->next=temp->next;
return temp;
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
题目215：数组中第K个最大元素（NO）
- 解题思路：使用快速排序算法，切记快速排序算法是递归算法，递归终止条件不要忘。
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
class Solution {
public:
//快速排序算法
void quick_sort(vector<int>&nums,int left,int right)
{
//递归终止条件要有
if(left>=right)
{
return ;
}
//快速排序的思想就是每次都用中间节点最为排序中间的元素
//比它大的放后面，比它小的放前面
int mid=nums[(left+right)/2];//中间元素
int i=left;
int j=right;
while(i<j)
{
while(nums[i]<mid)
{
i++;
}
while(nums[j]>mid)
{
j--;
}
//找到了要交换的值
if(i<=j)
{
swap(nums[i],nums[j]);
i++;
j--;
}
}
//检测左边
if(i<right)
{
quick_sort(nums,i,right);
}
if(j>left)
{
quick_sort(nums,left,j);
}
}
int findKthLargest(vector<int>& nums, int k) {
//这题看似和简单表面上sort一下就解决了，但是这题考察的就是
//排序算法的使用，我这题直接使用快排
int len=nums.size();
quick_sort(nums,0,len-1);
return nums[len-k];
}
};
题目15:三数之和（NO）
- 解题思路：排序加双指针
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//使用排序加上双指针
sort(nums.begin(),nums.end());
vector<vector<int>>ans;
int len=nums.size();
//每个节点都可以最为第一个节点
for(int i=0;i<len-2;i++)
{
//判断是否可前面的节点相同
if(i>0&&nums[i]==nums[i-1])
{
//确保首元素不同
continue;
}
//目标元素是当前的相反数
int target=-nums[i];
//查找后面的两个元素
//使用while首尾开始查找
int left=i+1;
int right=len-1;
while(left<right)
{
int sum=nums[left]+nums[right];
if(sum<target)
{
//小了
left++;
}else if(sum>target)
{
//大了
right--;
}else
{
//找到相加为零的三个数了
vector<int>temp;
temp.push_back(nums[i]);
temp.push_back(nums[left]);
temp.push_back(nums[right]);
ans.push_back(temp);
left++;
right--;
//查看元素是否不重复
while (left < right && nums[left] == nums[left-1]) // 跳过重复元素
++left;
while (left < right && nums[right] == nums[right+1]) // 跳过重复元素
--right;
}
}
}
return ans;
}
};
题目53：最大子数组和（NO）
- 动态规划，典型的人不为己，天诛地灭。
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre = 0, maxAns = nums[0];
for (const auto &x: nums) {
//原先的最大值可以当作前一个数
//如果前面的值加上自己比自己小了，这显然拖累自己了果断抛弃
//如果是自己拖累了前面的，那就不管了
//典型的人不为己，天诛地灭。
pre = max(pre + x, x);
maxAns = max(maxAns, pre);
}
return maxAns;
}
};
题目5：最长回文子串（NO）
- 解题思路：暴力节，使用s.substr截取每个子串判断是否是回文数
给你一个字符串 s，找到 s 中最长的 回文子串。
class Solution {
public:
string longestPalindrome(string s) {
//暴力算法
//截取出每个子串然后判断是否是回文数
string res=s.substr(0,1);
for(int i=0;i<s.size();i++)
{
for(int j=i+1;j<s.size();j++)
{
if(j-i+1>res.size()&&isPalindrome(s,i,j))
{
//substr是截取子串,i是首字符，j-i+1是长度
res=s.substr(i,j-i+1);
}
}
}
return res;
}
bool isPalindrome(string &s,int left,int right)
{
while(left<=right)
{
if(s[left]!=s[right])
{
return false;
}
left++;
right--;
}
return true;
}
};
