题目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;
}
};
题目102：二叉树的层序遍历（YES）
- 这算比较容易的中等难度题了，直接使用层序遍历，也就是广度优先遍历算法即可，关键是对队列的使用。
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>>ans;
if(root==nullptr)
{
return ans;
}
//层序遍历
queue<TreeNode*>que;
que.push(root);
while(!que.empty())
{
//处理当前层的
int size=que.size();
vector<int>ret;
for(int i=0;i<size;i++)
{
TreeNode*temp=que.front();
que.pop();
ret.push_back(temp->val);
if(temp->left!=nullptr)
{
que.push(temp->left);
}
if(temp->right!=nullptr)
{
que.push(temp->right);
}
}
ans.push_back(ret);
}
return ans;
}
};
题目33：搜索旋转排序数组（YES）
- 解题思路：以第一个结点为依据来判断是向上查找还是向下查找。
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
class Solution {
public:
int search(vector<int>& nums, int target) {
//这题的难度在于时间复杂度上的要求
int len=nums.size();
//我打算以第一个为基础进行查找
if(nums[0]>target)
{
//向下查找
int i=len-1;
while(nums[i]!=target)
{
i--;
if(i<0||nums[i]<target)
{
return -1;
}
}
return i;
}else
{
//向上查找
int i=0;
while(nums[i]!=target)
{
i++;
if(i>=len||nums[i]>target)
{
return -1;
}
}
return i;
}
return -1;
}
};
题目200：岛屿数量（NO）
- 解题思路：广度优先遍历，设置访问数组这里很容易出错。
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty()) { // 如果网格为空，返回岛屿数量为0
return 0;
}
int row = grid.size(); // 获取网格行数
int col = grid[0].size(); // 获取网格列数
int ans = 0; // 岛屿数量
vector<vector<bool>> visited(row, vector<bool>(col, false)); // 二维visited数组用来记录已访问过的位置
for (int i = 0; i < row; i++) { // 遍历网格行
for (int j = 0; j < col; j++) { // 遍历网格列
if (grid[i][j] == '1' && !visited[i][j]) { // 如果当前位置是陆地且未访问过
ans++; // 岛屿数量加一
queue<pair<int, int>> que; // 定义队列用于广度优先搜索
que.push({i, j}); // 将当前陆地位置加入队列
visited[i][j] = true; // 标记当前位置已访问
while (!que.empty()) { // 开始广度优先搜索
int current_x = que.front().first;
int current_y = que.front().second;
que.pop(); // 弹出当前位置
int dx[4] = {-1, 1, 0, 0}; // 定义方向数组
int dy[4] = {0, 0, -1, 1};
for (int k = 0; k < 4; k++) { // 遍历四个方向
int next_x = current_x + dx[k];
int next_y = current_y + dy[k];
if (next_x >= 0 && next_x < row && next_y >= 0 && next_y < col
&& grid[next_x][next_y] == '1' && !visited[next_x][next_y]) { // 判断边界，未访问过，以及为陆地
que.push({next_x, next_y});
visited[next_x][next_y] = true; // 将相邻陆地加入队列并标记为已访问
}
}
}
}
}
}
return ans; // 返回岛屿数量
}
};
题目46：全排列（NO）
- 解题思路：使用了回溯算法，核心的地方其实是递归算法的使用。
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
vector<int> temp; // 用于临时存储排列的容器
vector<int> visited(nums.size(), 0); // 记录每个数是否已经访问过的标志数组
backtrack(nums, res, temp, visited);
return res;
}
void backtrack(vector<int>& nums, vector<vector<int>>& res, vector<int>& temp, vector<int>& visited) {
if (temp.size() == nums.size()) { // 如果临时排列的长度等于输入数组的长度，则将当前排列加入结果集
res.push_back(temp);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (visited[i] == 0) { // 如果当前数字未被访问过
visited[i] = 1; // 标记当前数字为已访问
temp.push_back(nums[i]); // 将当前数字加入临时排列
backtrack(nums, res, temp, visited); // 递归填充下一个位置
temp.pop_back(); // 撤销操作，将当前数字移出临时排列
visited[i] = 0; // 恢复当前数字为未访问状态，以便后续排列中再次使用
}
}
}
};