Vodka编程菜菜

NYU + Gatech

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while (p != q) {
p = p ? p->next : headB;
q = q ? q->next : headA;
}
return p;
}
};


class MinStack {
public:
/** initialize your data structure here. */
stack<int> st;
stack<int> st_min;
MinStack() {

}

void push(int x) {
st.emplace(x);
int cur_min = st_min.empty()? x: min(x,st_min.top());
st_min.emplace(cur_min);
}

void pop() {
if(!st.empty())st.pop();
if(!st_min.empty())st_min.pop();
}

int top() {
return st.top();
}

int getMin() {
return st_min.top();
}
};

/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/


class Solution {
public:
int findMin(vector<int>& nums) {

int l = 0, r = nums.size()-1;
int res = -1;
while(l<=r){
int m = l + (r-l)/2;
if(nums[m]>nums[nums.size()-1]) {
l = m+1;
}else{
res = m;
r = m-1;
}
}
return nums[res];
}
};


class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = nums[0];
int min_val = nums[0], max_val = nums[0];
for(int i =1; i < nums.size();++i){
int max_new = max_val*nums[i];
int min_new = min_val*nums[i];
min_val = min(min(max_new, min_new), nums[i]);
max_val = max(max(min_new, max_new), nums[i]);
res = max(max_val, res);
}
return res;
}
};


class Solution {
public:

string reverseWords(string s) {
if(s.size() == 0) return s;
int n = s.size();
int l = 0, r = s.size()-1;
while(l<n && s[l] ==' ') l++;
while(r>=0 && s[r] == ' ') r--;
string res = "";
int pos = r;
while(pos >=l ){
int p = pos;
while(p >=l && s[p] !=' ') p--;
string tmp = s.substr(p+1, pos-p);
res += tmp +" ";
while(p >=l && s[p] ==' ') p--;
pos = p;
}
if(res.size())res.pop_back();
return res;
}
};


class Solution {
public:
int gcd(int y, int x){
if(x == 0) return y;
return gcd(x, y % x);
}
int maxPoints(vector<vector<int>>& points) {
//核心是如何表示除数
int n  = points.size();
if(n == 0) return 0;
if(n == 1) return 1;
int res = 0;
for (int i = 0; i <n-1; ++i){
unordered_map<string, int> slop_map;
int repeat = 0;
int cur_max = 0;
for(int j = i+1; j < n; ++j){
int dy = points[i][1] - points[j][1];
int dx = points[i][0] - points[j][0];
if(dy == 0 && dx == 0) {
repeat++;
continue;
}
int g = gcd(dy, dx);
if(g !=0){
dy /= g;
dx /= g;
}
string key = to_string(dy) +"/"+to_string(dx);
slop_map[key]++;
cur_max = max(cur_max, slop_map[key]);
}
res = max(res, repeat + cur_max+1);
}
return res;
}
};


class LRUCache {
private:
int capacity_;
list<pair<int,int>> lst;
unordered_map<int, list<pair<int,int>>::iterator> key_iter_map;
public:
LRUCache(int capacity) {
capacity_ = capacity;
}

int get(int key) {
auto iter = key_iter_map.find(key);
if(iter == key_iter_map.end()){
return -1;
}
int val = iter->second->second;
lst.splice(lst.begin(), lst, iter->second);
return val;
}

void put(int key, int value) {
if(get(key) != -1){
key_iter_map[key]->second = value;
return;
}
if(lst.size() == capacity_){
auto item = lst.back();
lst.pop_back();
key_iter_map.erase(item.first);
}
lst.emplace_front(key,value);
key_iter_map[key] = lst.begin();
return ;
}
};

/**
* 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);
*/


class Solution {
public:
ListNode *dummy = new ListNode(-1), *cur = dummy;
cur = dummy;
while (cur->next && cur->next->val <= head->val) {
cur = cur->next;
}
}
return dummy->next;
}
};


/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:

ListNode* merge(ListNode* l, ListNode* r){
ListNode* dummy = new ListNode(-1);
ListNode* tmp = dummy;
while(l && r){
if(l->val < r->val){
tmp->next = l;
l = l->next;
}else {
tmp->next = r;
r = r->next;
}
tmp = tmp->next;
}
if(l) tmp->next = l;
if(r) tmp->next = r;
return dummy->next;
}

while (fast && fast->next) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = nullptr;
}
};


class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(auto& str : tokens){
if(str == "+"){
int right = st.top();st.pop();
int left = st.top();st.pop();
int val = left + right;
st.emplace(val);
}else if(str == "-") {
int right = st.top();st.pop();
int left = st.top();st.pop();
int val = left - right;
st.emplace(val);
}else if(str == "*") {
int right = st.top();st.pop();
int left = st.top();st.pop();
int val = left * right;
st.emplace(val);
}else if(str == "/") {
int right = st.top();st.pop();
int left = st.top();st.pop();
int val = left / right;
st.emplace(val);
}else{
int val = stoi(str);
st.emplace(val);
}
}
return st.top();
}
};