模式识别1
1.涉及出现次数，考虑散列表
2.构造子串，散列表存其下标
模式识别2
1.涉及子串，考虑滑动窗口
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int start(0),end(0),curLen(0),maxLen(0);
while (end<s.size()) {
char cur_s=s[end];//更新当前位置的字符
for (int i=start; i<end; i++) {
//判断有无重复字符
//有,更新窗口起点;没有则滑动窗口，增加窗口长度
if (cur_s==s[i]) {
start=i+1;
curLen=end-start;//计算当前窗口长度
break;
}
}
end++;//延长窗口
curLen++;//计算当前窗口长度
maxLen=max(curLen,maxLen);//更新最长的值
}
return maxLen;
}
};
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> curSet;
int begin(0),maxLen(0);
for (int i=0; i<s.size(); i++) {
while (curSet.count(s[i])) {
curSet.erase(s[begin]);//找到，删除
begin++;//重新设置起点
}
//放入新的数据
maxLen = max(maxLen,i-begin+1); //比较当前窗口长度和历史长度
curSet.insert(s[i]);//
}
return maxLen;
}
};
这道题看起来很简单，但是需要多做，不然容易阴沟里翻船
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}//剪枝
ListNode* front = nullptr;//双指针，同时front为虚拟头节点
ListNode* cur = head;
while (cur!=NULL) {
ListNode* tep = cur->next;//保存链表后面的元素
//保存完毕，可以操作cur改变其指向
cur->next=front;//当前节点指向前面的节点
front=cur;//换位置
cur=tep;//恢复cur
}
return front;
}
};
刚开始接触递归可能会比较抽象，想要理解的还是要动手画画图，想清楚递归到最后的逻辑
class Solution {
public:
int count=0;
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode *res;
res=reverseList(head->next);
//递归每退出一层，函数中 head 指针的指向都会发生改变，都指向上一个节点。
//递归函数,考虑最底层逻辑，走到这里至少有两个节点，依次是head,res(即new_head),null
head->next->next=head;//head 在往回退出
head->next=NULL;
return res;//每次递归都返回新的头指针
}
};
LRU（Least Recently Used）也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。 由于需要O(1)的put()和get()，所以要想到哈希。哈希链表 LinkedHashMap，C++需要用双向链表去实现。由于需要手搓一个双向链表，时间久了很多细节容易忘记，只能当作默写题了。
// Node成员都是public的，推荐定义Node为struct
struct Node {
int key;
int val;
Node *next, *prev;
Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
};
class DoubleLinkedList {
Node *head, *tail;
public:
DoubleLinkedList() {
head = new Node(-1, -1);
tail = new Node(-1, -1);
head->next = tail;
tail->prev = head;
}
void push_front(Node* node) {
node->next = head->next;
node->prev = head;
node->next->prev = node;
head->next = node;
}
void erase(Node* node) {
node->next->prev = node->prev;
node->prev->next = node->next;
}
Node* back() {
return tail->prev;
}
void pop_back() {
erase(tail->prev);
}
};
class LRUCache {
public:
int cap;
unordered_map<int, Node*> key_node_map;
DoubleLinkedList* node_list;
LRUCache(int capacity) {
cap = capacity;
node_list = new DoubleLinkedList();
}
int get(int key) {
// 不存在该key
if (key_node_map.find(key) == key_node_map.end()) {
return -1;
} else {
// 将当前节点在移动到双链表的首位
Node* node = key_node_map[key];
node_list->erase(node);
node_list->push_front(node);
return node->val;
}
}
void put(int key, int value) {
// 如果key存在，则修改对应的value并移动至链表首端
if (key_node_map.find(key) != key_node_map.end()) {
Node *node = key_node_map[key];
node->val = value;
node_list->erase(node);
node_list->push_front(node);
} else {
// 如果缓存已满，则删除双链表末端节点
if (key_node_map.size() == cap) {
key_node_map.erase(node_list->back()->key);
node_list->pop_back();
}
// 插入新节点
Node *node = new Node(key, value);
key_node_map[key] = node;
node_list->push_front(node);
}
}
};
// 作者：ravenlite
// 链接：https://leetcode.cn/problems/lru-cache/solution/kan-lai-kan-qu-huan-shi-wo-de-zui-zhi-gu-cj9w/
当然，要是真的忘了或者不想造轮子，可以纯用哈希去做
class LRUCache {
//首先，要实现O(1)时间get只能使用hash表
public:
LRUCache(int capacity) : capacity(capacity) {
//直接使用capacity初始化capacity，（不懂的话搜：初始化成员列表）
time = 0;
poptime = 0;
}
int get(int key) {
if(umap.find(key) != umap.end()){
//如果找到了，我们更新使用时间
int lasttime = times[key];
times[key] = time;
time_to_key.erase(lasttime);
time_to_key[time] = key;
time++;
return umap[key];
}else{
return -1;
}
}
void put(int key, int value) {
//首先将其添加进新时间序列
if(times.find(key) != times.end()){
//如果之前就存在，我们要同时更新
int lasttime = times[key];
time_to_key.erase(lasttime);
time_to_key[time] = key;
times[key] = time;
time++;
}else{
//如果之前不存在，则直接加入
times[key] = time;
time_to_key[time] = key;
time++;
}
//然后将其插入
umap[key] = value;
//然后判断是否满员
if(umap.size() == capacity + 1){
//首先获取第一个有效的弹出时间节点
while(time_to_key.find(poptime) == time_to_key.end()){
poptime++;
}
//然后弹出它
int theKey = time_to_key[poptime];
times.erase(theKey);
umap.erase(theKey);
time_to_key.erase(poptime);
poptime++;
}
}
private:
int capacity;
int time; //标记节点的插入序号
int poptime; //标记最久未使用序号
unordered_map<int,int> umap; //记录<key,value>
unordered_map<int,int> times; //记录<key,插入时间>
unordered_map<int,int> time_to_key; //记录<插入时间,key>
};
// 作者：wo-sun-ai-xue-xi
// 链接：https://leetcode.cn/problems/lru-cache/solution/146bu-shi-yong-lian-biao-shi-yong-san-ge-jz93/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
由于库函数的解是O(nlogn)的，所以不能一句话就糊弄过去，比如：
return sort(nums.begin(), nums.end(), greater<int>()), nums[k - 1];
要是下面的解法实在没写出来，这句话可以多提交几次，保证AC。
当k较小的时候，期望的时间复杂度是趋近O(n)的，严格来说其复杂度为O(nlog(k))
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<>> q;
for (const auto &num: nums) {
if (q.size() < k) {
q.push(num);
} else if (q.top() < num) {
q.pop();
q.push(num);
}
}
return q.top();
}
};
// 作者：XiaoCaiGang
// 链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/solution/you-xian-dui-lie-by-xiaocaigang-arcc/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
手搓堆排解法，先把数组放进一个完全二叉树 [记一个二叉树的深度为ℎ，若除第ℎ层外，该二叉树的其它各层[1,ℎ−1]的节点数均达到最大值(满的)，且第ℎ层所有的节点均连续集中在最左边，那么这棵树即为一棵完全二叉树.]
class Solution
{
public:
int findKthLargest(vector<int>& nums, int k)
{
int n = nums.size();
build_maxHeap(nums);
for (int i = 0; i < k - 1; i ++)
{
swap(nums[0], nums[n-1-i]);
adjust_down(nums, 0, n-1-i - 1);
}
return nums[0];
}
void build_maxHeap(vector<int> & nums)
{
int n = nums.size();
for (int root = n/2; root > -1; root --)
adjust_down(nums, root, n - 1);
}
void adjust_down(vector<int> & nums, int root, int hi)
{
if (root > hi)
return ;
int t = nums[root];
int child = 2 * root + 1;
while (child <= hi)
{
if (child + 1 <= hi && nums[child] < nums[child + 1])
child ++;
if (t > nums[child])
break;
nums[root] = nums[child];
root = child;
child = 2 * root + 1;
}
nums[root] = t;
}
};
// 作者：XingHe_XingHe
// 链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/solution/cpython3java-1da-gen-dui-diao-ku-2shou-l-xveq/
笔试的时候只是想AC的话用栈容易想一点（短时间内，想做出这题要基础很好），想要O(1)空间解决要画图，把逻辑理清楚，不过我懒得做了。
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
stack<ListNode*> stk;
ListNode* dumphead = new ListNode(0,head);//记录一下结果的头指针
ListNode* pre = dumphead;//活动的指针pre
ListNode* cur = head;
//可以先算算有几轮,当然也可以写while循环，我怎么写是为了容易看懂
int count = 0, group = 0;
while (cur!=nullptr) {
cur=cur->next;
count++;
}
group = count/k;
//cout <<"group="<< group << endl;
cur=head;//恢复
for (int i=0; i<group; i++) {
//每一轮的操作
for (int i=0; i<k; i++) {
stk.emplace(cur);
cout<<cur->val<<" "<<"入栈"<<" ";
cur=cur->next;
}//进栈
cout<<endl;
for (int i=0; i<k; ++i) {
pre->next=stk.top();
stk.pop();
cout<<"stk.size="<<stk.size()<<" ";
pre=pre->next;//指针右移
cout<<"pre->val="<<pre->val<<endl;
}//出栈
}
pre->next=cur;//连接上后面的,不需要反转的
return dumphead->next;
}
};
本文章使用limfx的vscode插件快速发布