1.21#
无重复字符的最长子串 (掌握程度： 中)#
部分还是存在忘了的，中间关于哈希表的有点没掌握
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
unordered_map<char, int> map;
int ans = 0, left = 0;
for (int right = 0; right < n; right++) {
map[s[right]]++;
while (map[s[right]] > 1) {
map[s[left]]--;
left++;
}
ans = max(ans, right - left + 1);
}
return ans;
}
};LRU缓存 (掌握程度： 高)#
这个我已经会背了😓
type Node struct {
key, val int
prev, next *Node
}
type LRUCache struct {
Capacity int
Cache map[int]*Node
Head *Node
Tail *Node
}
func Constructor(capacity int) LRUCache {
head := &Node{}
tail := &Node{}
head.next = tail
tail.prev = head
return LRUCache{
Capacity: capacity,
Cache: make(map[int]*Node),
Head: head,
Tail: tail,
}
}
func (l *LRUCache) addToHead(node *Node) {
node.prev = l.Head
node.next = l.Head.next
l.Head.next.prev = node
l.Head.next = node
}
func (l *LRUCache) deleteNode(node *Node) {
node.next.prev = node.prev
node.prev.next = node.next
}
func (l *LRUCache) Get(key int) int {
if node, ok := l.Cache[key]; ok {
l.deleteNode(node);
l.addToHead(node);
return node.val
}
return -1
}
func (l *LRUCache) Put(key int, value int) {
if node, ok := l.Cache[key]; ok {
node.val = value
l.deleteNode(node)
l.addToHead(node)
} else {
if len(l.Cache) >= l.Capacity {
deleteNode := l.Tail.prev
l.deleteNode(deleteNode)
delete(l.Cache, deleteNode.key)
}
newNode := &Node{key: key, val: value}
l.addToHead(newNode)
l.Cache[key] = newNode
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/反转链表 (掌握程度： 高)#
简单题还是拿下还是比较简单的
/**
* 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:
ListNode* reverseList(ListNode* head) {
ListNode* cur = head;
ListNode* pre = nullptr;
while (cur != nullptr) {
ListNode* nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
};数组中的第K个最大元素 (掌握程度： 中)#
这个快速选择还是略微不太熟
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
srand(time(0));
int n = nums.size();
return quickSelect(nums, n - k, 0, n - 1);
}
int quickSelect(vector<int>& nums, int k, int left, int right) {
if (left == right) return nums[left];
int random = left + rand() % (right - left + 1);
swap(nums[left], nums[random]);
int pivot = nums[left];
int i = left - 1, j = right + 1;
while (true) {
do i++; while (nums[i] < pivot);
do j--; while (nums[j] > pivot);
if (i >= j) break;
swap(nums[i], nums[j]);
}
if (k <= j) return quickSelect(nums, k, left, j);
else return quickSelect(nums, k, j + 1, right);
}
};K个一组翻转链表 (掌握程度： 中)#
处理p0和尾部的时候没记住
/**
* 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:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* p0 = dummy;
int n = 0;
for (ListNode* cur = head; cur != nullptr; cur = cur->next) {
n++;
}
ListNode* cur = head;
while (n >= k) {
n -= k;
ListNode* tail = cur;
ListNode* pre = nullptr;
for (int i = 0; i < k; i++) {
ListNode* nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
p0->next = pre;
tail->next = cur;
p0 = tail;
}
return dummy->next;
}
};