NFYD

2.3万

Hxxj

cuola

ctOS
psychopath_6
LittleLily
Present.

Wiselnn

aa123

ZXG_DXX

novice_7

NFYD
13小时前

### 快速选择排序

class Solution {
public:
int quick_sort(vector<int>& q, int l, int r, int k)
{
if(l == r) return q[k];
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while(i < j)
{
while(q[++ i] > x); //求第k大元素，这里要写大于号，与快排相反
while(q[-- j] < x); //写小于号，与快排相反
if(i < j) swap(q[i], q[j]);
}
if(k <= j) return quick_sort(q, l, j, k);
return quick_sort(q, j + 1, r, k);
}
int findKthLargest(vector<int>& nums, int k) {
return quick_sort(nums, 0, nums.size() - 1, k - 1);
}
};


NFYD
18小时前

### BFS写法

typedef pair<int, int> PII;
class Solution {
public:
vector<vector<char>> g;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void bfs(int x, int y)
{
g[x][y] = '0';
queue<PII> q;
q.push({x, y});

while(q.size())
{
PII t = q.front();
q.pop();

for(int i = 0; i < 4; i ++ )
{
int a = t.first + dx[i], b = t.second + dy[i];
if(a >= 0 && a < g.size() && b >= 0 && b < g[a].size() && g[a][b] == '1')
{
q.push({a, b});
g[a][b] = '0';
}
}
}
}

int numIslands(vector<vector<char>>& grid) {
g = grid;
int res = 0;
for(int i = 0; i < g.size(); i ++ )
for(int j = 0; j < g[0].size(); j ++ )
if(g[i][j] == '1')
{
bfs(i, j);
res ++ ;
}
return res;
}
};


### DFS写法

class Solution {
public:
vector<vector<char>> g;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x, int y)
{
g[x][y] = '0';
for(int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if(a >= 0 && a < g.size() && b >= 0 && b < g[a].size() && g[a][b] == '1')
dfs(a, b);
}
}

int numIslands(vector<vector<char>>& grid) {
g = grid;
int res = 0;
for(int i = 0; i < g.size(); i ++ )
for(int j = 0; j < g[0].size(); j ++ )
if(g[i][j] == '1')
{
dfs(i, j);
res ++ ;
}
return res;
}
};


NFYD
21小时前

class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> f(n + 1), g(n + 1);
for(int i = 1; i <= n; i ++ )
{
f[i] = g[i - 1] + nums[i - 1];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[n], g[n]);
}
};


NFYD
22小时前
/**
* 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;
}
};


NFYD
2天前

### DP

class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = nums[0];
int f = nums[0], g = nums[0];
for (int i = 1; i < nums.size(); i ++ )
{
int a = nums[i], fa = f * a, ga = g * a;
f = max(a, max(fa, ga));
g = min(a, min(fa, ga));
res = max(res, f);
}
return res;
}
};


NFYD
3天前
class MinStack {
public:
stack<int> stk;
stack<int> stk_min;
MinStack() {

}

void push(int val) {
stk.push(val);
if (stk_min.size()) {
int x = stk_min.top();
stk_min.push(min(x, val));
} else {
stk_min.push(val);
}
}

void pop() {
stk.pop();
stk_min.pop();
}

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

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

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


NFYD
5天前

### 双链表 + 哈希表

class LRUCache {
public:
struct Node
{
int key, val;
Node *left, *right;
Node(int _key, int _val): key(_key), val(_val), left(NULL), right(NULL) {}
}*L, *R;
unordered_map<int, Node*> hash;
int n;

LRUCache(int capacity) {
n = capacity;
L = new Node(-1, -1), R = new Node(-1, -1);
L->right = R;
R->left = L;
}

void remove(Node* p)
{
p->left->right = p->right;
p->right->left = p->left;
}

void insert(Node* p)
{
p->right = L->right;
p->left = L;
L->right->left = p;
L->right = p;
}

int get(int key) {
if(hash.count(key) == 0) return -1;
auto p = hash[key];
remove(p);
insert(p);
return p->val;
}

void put(int key, int value) {
if(hash.count(key))
{
auto p = hash[key];
p->val = value;
remove(p);
insert(p);
}
else
{
if(hash.size() == n)
{
auto p = R->left;
remove(p);
hash.erase(p->key);
delete p;
}
auto p = new Node(key, value);
hash[key] = p;
insert(p);
}
}
};

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


NFYD
5天前

### 摩尔投票法

class Solution {
public:
int majorityElement(vector<int>& nums) {
int val, cnt = 0;
for(auto c : nums)
{
if(cnt == 0) val = c, cnt ++ ;
else if(c == val) cnt ++ ;
else cnt -- ;
}
return val;
}
};


NFYD
5天前
class Solution {
public:
int countSubstrings(string s) {
int res = 0;
for(int i = 0; i < s.size(); i ++ )
{
//枚举回文串长度为奇数的情况
for(int j = i, k = i; j >= 0 && k < s.size(); j --, k ++ )
{
if(s[j] != s[k]) break;
res ++ ;
}

//枚举回文串长度为偶数的情况
for(int j = i, k = i + 1; j >= 0 && k < s.size(); j --, k ++ )
{
if(s[j] != s[k]) break;
res ++ ;
}
}
return res;
}
};


NFYD
6天前
class Solution {
public:
stack<int> num;
void eval(string c)
{
auto b = num.top(); num.pop();
auto a = num.top(); num.pop();
int x;
if(c == "+") x = a + b;
else if(c == "-") x = a - b;
else if(c == "*") x = a * b;
else if(c == "/") x = a / b;
num.push(x);
}
int evalRPN(vector<string>& tokens) {
unordered_set<string> S{"+", "-", "*", "/"};
for(auto& c: tokens)
{
if(S.count(c)) eval(c);
else num.push(stoi(c));
}
return num.top();
}
};