实现两个线程进行打排球
思路： 通过使用wait()和notify()进行控制顺序或者通过使用信号量Semapore类
import java.util.Random;
import java.util.concurrent.Semaphore;
public class Main {
public static void main(String[] args) {
System.out.println("Hello World!");
MyRun t = new MyRun();
Thread t1 = new Thread(t, "1");
Thread t2 = new Thread(t, "2");
t1.start();
t2.start();
try {
t1.join();
t2.join();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("main thread exit");
}
static class MyRun implements Runnable{
static volatile int cnt = 0;
public Object lock = new Object();
public final Semaphore sem = new Semaphore(1);
public final Semaphore sem2 = new Semaphore(0);
public void run() {
while(true) {
synchronized(lock) {
if(cnt == -1)
break;
Random r = new Random();
int n = r.nextInt(100);
String name = Thread.currentThread().getName();
if(n % 13 == 0) {
System.out.println(name + "won!!!!");
cnt = -1;
lock.notify();
break;
}
cnt ++;
System.out.println(name + " : " + cnt);
try{
lock.notify();
lock.wait();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
}
// public void run() {
// while(true) {
// try{
// String name = Thread.currentThread().getName();
// if("1".equals(name))
// sem.acquire();
// else
// sem2.acquire();
// if(cnt == -1)
// break;
// Random r = new Random();
// int n = r.nextInt(100);
// if(n % 13 == 0) {
// System.out.println(name + "miss!!!!");
// cnt = -1;
// sem.release();
// sem2.release();
// break;
// }
// cnt ++;
// System.out.println(name + " : " + cnt);
// if("1".equals(name))
// sem2.release();
// else
// sem.release();
// } catch (Exception e) {
// e.printStackTrace();
// }
// }
// }
}
}
LRU 缓存实现
思路：通过双向链表，实现movenode 和 addtohead两个函数，对双向链表进行操作，利用map记录key对应的node
/**
* 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);
*/
struct LRUNode{
int key, value;
LRUNode* pre;
LRUNode* nxt;
LRUNode():key(0),value(0),pre(nullptr),nxt(nullptr){}
LRUNode(int _key, int _value) : key(_key),value(_value),pre(nullptr),nxt(nullptr){}
LRUNode(int _key, int _value, LRUNode* _pre, LRUNode* _nxt) {
key = _key;
value = _value;
pre = _pre;
nxt = _nxt;
}
};
class LRUCache {
private:
int capacity;
int size;
LRUNode* head;
LRUNode* tail;
map<int, LRUNode*> cache;
public:
LRUCache(int _capacity) {
capacity = _capacity;
size = 0;
head = new LRUNode();
tail = new LRUNode();
head -> nxt = tail;
tail -> pre = head;
}
int get(int key) {
if(!cache.count(key)) {
return -1;
}
LRUNode* cur = cache[key];
moveToHead(cur);
return cur -> value;
}
void put(int key, int value) {
if(!cache.count(key)) {
LRUNode* node = new LRUNode(key, value);
cache[key] = node;
addToHead(node);
size ++;
if(size > capacity) {
LRUNode* cur = moveTail();
cache.erase(cur -> key);
delete cur;
size --;
}
} else {
LRUNode* cur = cache[key];
cur -> value = value;
moveToHead(cur);
}
}
LRUNode* moveTail() {
LRUNode* cur = tail -> pre;
removeNode(cur);
return cur;
}
void moveToHead(LRUNode* node){
removeNode(node);
addToHead(node);
}
void removeNode(LRUNode* node) {
node -> pre -> nxt = node -> nxt;
node -> nxt -> pre = node -> pre;
}
void addToHead(LRUNode* node) {
node -> pre = head;
node -> nxt = head -> nxt;
head -> nxt -> pre = node;
head -> nxt = node;
}
};
二叉树的前序、中序、后序
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if(root == nullptr)
return ans;
stack<TreeNode*> s;
s.push(root);
while(!s.empty()) {
TreeNode* t = s.top();
s.pop();
if(t != nullptr) {
if(t -> right)
s.push(t -> right);
if(t -> left)
s.push(t -> left);
s.push(t);
s.push(nullptr);
} else {
TreeNode* t = s.top();
s.pop();
ans.emplace_back(t -> val);
}
}
return ans;
}
};
输入n个整数，进行加减组合，能够组成计算结果为s的方案数
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
int n, s;
int a[i];
int dp[2][2000];
cin >> n;
int tot = 0;
for(int i = 0; i < n; i ++) {
cin >> a[i];
tot += (a[i] >= 0 ? a[i] : -a[i]);
}
cout << tot << endl;
int pos = s;
dp[0][pos] = 1;
int k = 0;
for(int i = 0; i < n; i ++) {
int t = (k + 1) % 2;
for(int j = 0; j <= 2 * s; j ++) {
dp[t][j] = 0;
if(j >= a[i]) {
dp[t][j] = dp[k][j - a[i]];
}
if(j + a[i] <= 2 * s) {
dp[t][j] += dp[k][j + a[i]];
}
}
}
return 0;
}
/*
5 3
1 1 1 1 1
*/
#
题目，给你一堆信封大小，问你最多能相互套多少个，只有第二的信封长和宽都大于前一个才能套进去。 排序加单调队列
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<vector<int>> q;
struct cmp{
bool operator()(const vector<int>& a, const vector<int>& b)const {
if(a[0] == b[0])
return a[1] > b[1];
return a[0] < b[0];
}
};
int maxEnvelopes(vector<vector<int>>& envelopes) {
int n = envelopes.size();
if(n <= 0)
return 0;
sort(envelopes.begin(), envelopes.end(), cmp());
vector<int> f = {envelopes[0][1]};
for(int i = 1; i < n; i ++) {
int num = envelopes[i][1];
if(num > f.back()) {
f.emplace_back(num);
} else {
int l = 0, r = f.size();
while(l < r) {
int mid = (l + r) >> 1;
if(f[mid] >= num) {
r = mid;
} else {
l = mid + 1;
}
}
cout << l << ' ' << r;
f[l] = num;
}
}
return f.size();
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i ++) {
int x, y;
cin >> x >> y;
q.push_back({x, y});
}
ans = maxEnvelopes(q);
cout << ans << endl;
return 0;
}
/*
5
2 3
4 6
1 3
2 5
7 3
*/
给你一个单向链表，获得倒数第n个值
思路：通过快慢指针进行计算