- 642. Moving Average from Data Stream(使用queue进行某个大小固定的size的和计算)
- 494. Implement Stack by Two Queues
- 209. First Unique Character in a String
- 657 insert delete getrandom O(1)
- 612. K Closest Points
- 544. Top k Largest Numbers（堆顶可以理解为在后面，greater小顶堆）
- 104. Merge K Sorted Lists(PQ和divide and concour都可以)
- 40. Implement Queue by Two Stacks
- 4.ugly number 2
- 134. LRU Cache
vector
增删 O(n) 查 O（1）改O(1)
queue
只能增删前后的点 O(1)
heap
增O（logn）删（logn）查（堆顶）取决于大顶堆或者小顶堆
c++ 默认大顶堆
priority_queue
make_heap(min.begin(), min.end(), greater
大顶堆不用加最后的东西
- make_heap( )：建立堆（要么大顶堆，要么小顶堆）
- push_heap( ): 在堆中添加元素
- pop_heap( ): 在堆中删除元素
- sort_heap( ): 堆排序
hashtable
增删查改O(1），存储空间大，无法排序，乱序
642. Moving Average from Data Stream(使用queue进行某个大小固定的size的和计算)
class MovingAverage {public:/** @param size: An integer*/MovingAverage(int size) {// do intialization if necessarythis -> size = size;}/** @param val: An integer* @return:*/double next(int val) {// write your code hereif (Q.size() == size){int temp = Q.front();Q.pop();sum -= temp;}Q.push(val);sum += val;double res;res = sum / Q.size();return res;}private:queue<int> Q;double sum = 0;int size;};
494. Implement Stack by Two Queues
在空queue中push进去一个元素之后把所有元素都加进去，就是倒序
class Stack {
public:
queue <int> myqueue1;
queue <int> myqueue2;
/*
* @param x: An integer
* @return: nothing
*/
void push(int x) {
// write your code here
if (myqueue1.empty()) {
myqueue1.push(x);
while (!myqueue2.empty()) {
int temp = myqueue2.front();
myqueue2.pop();
myqueue1.push(temp);
}
}
else {
myqueue2.push(x);
while (!myqueue1.empty()) {
int temp = myqueue1.front();
myqueue1.pop();
myqueue2.push(temp);
}
}
}
/*
* @return: nothing
*/
void pop() {
// write your code here
if (!myqueue1.empty()) {
myqueue1.pop();
}
if (!myqueue2.empty()) {
myqueue2.pop();
}
}
/*
* @return: An integer
*/
int top() {
// write your code here
if (!myqueue1.empty()) {
return myqueue1.front();
}
else {
return myqueue2.front();
}
}
/*
* @return: True if the stack is empty
*/
bool isEmpty() {
// write your code here
return myqueue1.empty() && myqueue2.empty();
}
};
209. First Unique Character in a String
2nd time
class Solution {
public:
/**
* @param str: str: the given string
* @return: char: the first unique character in a given string
*/
char firstUniqChar(string &str) {
// Write your code here
unordered_set <char> notUnique;
vector<int> firstPos(26, -1);
char res;
int pos = INT_MAX;
for (int i = 0; i < str.size(); i ++){
if (notUnique.count(str[i])){
continue;
}
if (firstPos[str[i] - 'a'] == -1){
firstPos[str[i] - 'a'] = i;
}else{
notUnique.insert(str[i]);
}
}
for (int i = 0; i < 26; i ++){
if (firstPos[i] != -1 && !notUnique.count(i + 'a') && firstPos[i] < pos){
pos = firstPos[i];
res = i + 'a';
}
}
return res;
}
};
class Solution {
public:
/**
* @param str: str: the given string
* @return: char: the first unique character in a given string
*/
char firstUniqChar(string &str) {
// Write your code here
vector <int> exist (26);
for (int i = 0; i < str.size(); i ++){
exist[str[i] - 'a'] += 1;
}
for (int i = 0; i < str.size(); i ++ ){
if (exist[str[i] - 'a'] == 1){
return str[i];
}
}
// unordered_map <char, int> existWords;
// for (int i = 0; i < str.size(); i++) {
// if (existWords.find(str[i]) != existWords.end()) {
// existWords[str[i]] += 1;
// }
// else {
// existWords[str[i]] = 1;
// }
// }
// for (int i = 0; i < str.size(); i++) {
// if (existWords[str[i]] > 1) {
// continue;
// }
// else {
// return str[i];
// }
// }
}
};
657 insert delete getrandom O(1)
如何取到随机值
调用swap函数
set和map可以用count判断或者find是否为set.end
class RandomizedSet {
private:
unordered_map <int, int> newSet;
vector <int> vec;
public:
RandomizedSet() {
// do intialization if necessary
}
/*
* @param val: a value to the set
* @return: true if the set did not already contain the specified element or false
*/
bool insert(int val) {
// write your code here
if (newSet.find(val) != newSet.end()) {
return false;
}
newSet[val] = vec.size();
vec.push_back(val);
return true;
}
/*
* @param val: a value from the set
* @return: true if the set contained the specified element or false
*/
bool remove(int val) {
// write your code here
if (newSet.find(val) != newSet.end()) {
int index = newSet[val], last = vec.size() - 1;
vec[index] = vec[last];
newSet[vec[index]] = index;
newSet.erase(val);
swap(vec[index], vec[last]);
vec.pop_back();
return true;
}
return false;
}
/*
* @return: Get a random element from the set
*/
int getRandom() {
// write your code here
return vec[rand() % vec.size()];
}
};
priority_queue
重构compare函数
sort（）前-后是升序
reverse(ret.begin(), ret.end()); 反序数组
612. K Closest Points
Point global_origin;
class Solution {
public:
/**
* @param points: a list of points
* @param origin: a point
* @param k: An integer
* @return: the k closest points
*/
struct compare{
bool operator()(const Point & a, const Point & b)const {
int diff = (a.x - global_origin.x) * (a.x - global_origin.x) + (a.y - global_origin.y) * (a.y - global_origin.y) - (b.x - global_origin.x) * (b.x - global_origin.x) - (b.y - global_origin.y) * (b.y - global_origin.y);
if (diff == 0){
diff = a.x - b.x;
}
if (diff == 0){
diff = a.y - b.y;
}
return diff < 0;
}
};
vector<Point> kClosest(vector<Point> &points, Point &origin, int k) {
// write your code here
global_origin = origin;
priority_queue<Point, vector<Point>, compare> topK;
for (int i = 0; i < points.size(); i ++){
topK.push(points[i]);
if (topK.size() > k){
topK.pop();
}
}
vector<Point> result;
cout << topK.size();
for (int i = 0; i < k; i ++){
result.push_back(topK.top());
topK.pop();
}
reverse(result.begin(), result.end());
return result;
}
};
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
Point global_origin;
int getDistance(Point A, Point B) {
return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}
struct compare {
bool operator() (const Point &a, const Point &b) const {
int diff = getDistance(a, global_origin) - getDistance(b, global_origin);
if (diff == 0)
diff = a.x - b.x;
if (diff == 0)
diff = a.y - b.y;
return diff < 0;
}
};
class Solution {
public:
/**
* @param points: a list of points
* @param origin: a point
* @param k: An integer
* @return: the k closest points
*/
int getDistance(Point A, Point B) {
return (A.x - B.x) ^ 2 + (A.y - B.y) ^ 2;
}
vector<Point> kClosest(vector<Point> &points, Point &origin, int k) {
// write your code here
global_origin = origin;
priority_queue <Point, vector<Point>, compare> topK;
for (int i = 0; i < points.size(); i++) {
Point p = points[i];
topK.push(p);
if (topK.size() > k)
topK.pop();
// if (topK.size() == k && getDistance(origin, topK.top()) > getDistance(origin, points[i])) {
// topK.pop();
// }
// topK.push(points[i]);
}
vector<Point> ret;
for (int i = 0; i < k; i++) {
ret.push_back(topK.top());
topK.pop();
}
reverse(ret.begin(), ret.end());
return ret;
}
};
544. Top k Largest Numbers（堆顶可以理解为在后面，greater小顶堆）
greater 小顶堆
class Solution {
public:
/**
* @param nums: an integer array
* @param k: An integer
* @return: the top k largest numbers in array
*/
vector<int> topk(vector<int> &nums, int k) {
// write your code here
priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 0; i < nums.size(); i ++){
heap.push(nums[i]);
if (heap.size() > k){
heap.pop();
}
}
vector<int> result;
for (int i = 0; i < k ; i ++){
result.push_back(heap.top());
heap.pop();
}
reverse(result.begin(), result.end());
return result;
}
};
104. Merge K Sorted Lists(PQ和divide and concour都可以)
PQ的方法，每次取表第一个数字出来比较
struct compare {
bool operator()(const ListNode* a, const ListNode *b) {
return a->val > b->val;
}
};
class Solution {
public:
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
ListNode *mergeKLists(vector<ListNode *> &lists) {
// write your code here
priority_queue <ListNode*, vector<ListNode*>, compare> pq;
if (lists.empty()) {
return nullptr;
}
for (auto list : lists) {
ListNode * temp = list;
while (temp) {
pq.push(temp);
temp = temp->next;
}
}
ListNode * dummpNode = new ListNode(-1);
ListNode * current = dummpNode;
while (!pq.empty()) {
ListNode * nextNode = new ListNode(pq.top()->val);
pq.pop();
current->next = nextNode;
current = current->next;
}
current->next = nullptr;
return dummpNode->next;
}
};
分治法
class Solution {
public:
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
ListNode *mergeKLists(vector<ListNode *> &lists) {
// write your code here
if (lists.empty()){
return nullptr;
}
return mergeSomeLists(lists, 0, lists.size() - 1);
}
ListNode * mergeSomeLists(vector <ListNode*> & lists, int start, int end){
if (start == end){
return lists[start];
}
int middle = (start + end)/2;
ListNode * left = mergeSomeLists(lists, start, middle);
ListNode * right = mergeSomeLists(lists, middle + 1, end);
return mergeTwoLists(left, right);
}
ListNode * mergeTwoLists(ListNode* head1, ListNode* head2){
ListNode* dummyNode = new ListNode(-1);
ListNode* tail = dummyNode;
while (head1 && head2){
if (head1->val < head2-> val){
tail->next = head1;
head1 = head1-> next;
}
else{
tail->next = head2;
head2 = head2-> next;
}
tail = tail->next;
}
if (head1){
tail->next = head1;
}
if(head2){
tail->next = head2;
}
return dummyNode->next;
}
40. Implement Queue by Two Stacks
class MyQueue {
public:
stack
stack
MyQueue() {
// do intialization if necessary
}
/
@param element: An integer
@return: nothing
/
void push(int element) {
// write your code here
stack1.push(element);
}
/
@return: An integer
*/
int pop() {
// write your code here
if (stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
}
int temp = stack2.top();
stack2.pop();
return temp;
}
/
@return: An integer
*/
int top() {
// write your code here
if (stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
}
return stack2.top();
}
};
4.ugly number 2
class Solution {
private:
priority_queue <int, vector<int>, greater<int>> pq;
unordered_set <int> isUglyNumber;
int temp = 0;
public:
/**
* @param n: An integer
* @return: return a integer as description.
*/
int nthUglyNumber(int n) {
// write your code here
isUglyNumber.insert(1);
pq.push(1);
for (int i = 0; i < n - 1; i ++){
temp = pq.top();
pq.pop();
addUglyNumber(temp);
}
return pq.top();
}
void addUglyNumber(int origin){
addNumber(origin, 2);
addNumber(origin, 3);
addNumber(origin, 5);
}
void addNumber(int origin, int times){
if (isUglyNumber.find(origin * times) == isUglyNumber.end()){
isUglyNumber.insert(origin * times);
pq.push(origin * times);
}
}
};
134. LRU Cache
class Node {
public:
pair <int, int> data;
Node *next;
Node(pair <int, int> data) {
this->data = data;
this->next = NULL;
}
Node() {
this->data = { 0, 0 };
this->next = NULL;
}
};
class LRUCache {
private:
unordered_map <int, Node *> map;
vector <pair <int, int>> vec;
Node * head, *tail;
int cap, size;
void moveToTail(Node* prev) {
if (prev->next == tail) {
return;
}
Node * temp = prev->next;
prev->next = temp -> next;
if (temp->next != NULL) {
map[temp->next->data.first] = prev;
}
tail->next = temp;
map[temp->data.first] = tail;
temp->next = NULL;
tail = temp;
}
public:
/*
* @param capacity: An integer
*/
LRUCache(int capacity) {
// do intialization if necessary
Node * newNode = new Node();
head = newNode;
tail = newNode;
cap = capacity;
}
/*
* @param key: An integer
* @return: An integer
*/
int get(int key) {
// write your code here
if (map.find(key) == map.end()) {
return -1;
}
moveToTail(map[key]);
return map[key]->next->data.second;
}
/*
* @param key: An integer
* @param value: An integer
* @return: nothing
*/
void set(int key, int value) {
// write your code here
if (map.find(key) != map.end()) {
map[key]->next->data.second = value;
moveToTail(map[key]);
}
else {
Node *temp = new Node(make_pair(key, value));
tail->next = temp;
map[key] = tail;
tail = temp;
size++;
if (size > cap) {
map.erase(head->next->data.first);
head->next = head->next->next;
if (head->next != NULL) {
map[head->next->data.first] = head;
}
size--;
}
}
}
};
若有收获，就点个赞吧
0 人点赞
