1.6万

SUPERDOGE
notyour_yei
D.Y.L.

3C81yyn1a3F
soccoder

a-smiling
khalil

R_U_OK

ZQCa

Hearer

10个月前

### 模拟+哈希表+双向链表

#### 代码

struct linknode//定义了一个链表结点结构体
{
int key,value;
};
class LRUCache {
private:
int size;//记录实际大小
int capacity;//记录容量
public:
LRUCache(int _capacity):capacity(_capacity),size(0) {
}

int get(int key) {
if(!cache.count(key))
return -1;
return node->value;
}

void put(int key, int value) {
if(!cache.count(key))
{
cache[key]=node;
size++;
if(size>capacity)
{
cache.erase(removed->key);
delete removed;
size--;
}
}
else
{
node->value=value;
}
}
{
}
{
node->next->prev=node->prev;
node->prev->next=node->next;
}
{
removenode(node);
}
{
removenode(node);
return node;
}
};


10个月前

### 线性DP

#### 代码

class Solution {
public:
const static int N=3e4+10;
int dp[N];
int longestValidParentheses(string s) {
int n=s.size();
int ans=0;
for(int i=1;i<n;i++)
{
if(s[i]==')')
{
if(s[i-1]=='(')
dp[i]=(i>=2?dp[i-2]:0)+2;
else if(i-dp[i-1]-1>=0&&s[i-dp[i-1]-1]=='(')
dp[i]=dp[i-1]+(i-dp[i-1]>=2?dp[i-dp[i-1]-2]:0)+2;
}
ans=max(ans,dp[i]);
}
return ans;
}
};


10个月前

### 二分+思维+细节

#### 代码

class Solution {
public:
int divide(int dividend, int divisor) {
if(dividend==INT_MIN)//越界判断
if(divisor==-1)
return INT_MAX;
else if(divisor==1)
return INT_MIN;

bool flag=false;
if(dividend>0)
{
flag=!flag;
dividend=-dividend;
}
if(divisor>0)
{
flag=!flag;
divisor=-divisor;
}

int left=0,right=INT_MAX;
while(left<right)
{
int mid=left+1+((right-left-1)>>1);
if(quick(dividend,divisor,mid)){
left=mid;
}
else
right=mid-1;
}
if(flag)
return -left;
return left;
}
bool quick(int x,int y,int z)
{
while(z)
{
if(z&1)
{
return false;
}
{
return false;
}
z>>=1;
}
return true;
}
};


10个月前

### 哈希表+思维

#### 代码

class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> ust;

for(auto num:nums)
ust.insert(num);

int len=0;

for(auto num:ust)
{
if(!ust.count(num-1))
{
int current_num=num;
int now_len=1;
while(ust.count(current_num+1))
{
now_len++;
current_num++;
}
len=max(len,now_len);
}
}

return len;
}
};


10个月前

### 链表

#### 代码

class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int cnt=0;
while(l1||l2)
{
int n1=0,n2=0;
if(l1)
n1=l1->val;
if(l2)
n2=l2->val;
int sum=n1+n2+cnt;
else
{
tail->next=new ListNode(sum%10);
tail=tail->next;
}
if(l1)
l1=l1->next;
if(l2)
l2=l2->next;
cnt=sum/10;
}
if(cnt)
tail->next=new ListNode(cnt);
}
};


10个月前

10个月前

### 滑动窗口+有序序列(multiset)

#### 代码

class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
int left=0,right=0,max_len=0,n=nums.size();
multiset<int> mst;
for(;right<n;right++)
{
mst.insert(nums[right]);
while(*mst.rbegin()-*mst.begin()>limit)
{
mst.erase(mst.find(nums[left]));
left++;
}
max_len=max(max_len,right-left+1);
}
return max_len;
}
};


10个月前

### 找规律。。。感觉不是什么DP

#### 代码

class Solution {
public:
const static int N=1e5+10;
int f[N];
int maxRotateFunction(vector<int>& nums) {
int n=nums.size();
int sum=0;
for(int i=0;i<n;i++)
{
f[0]+=i*nums[i];
sum+=nums[i];
}
int ans=f[0];
int j=n-1;
for(int i=1;i<n;i++)
{
f[i]=f[i-1]-(n-1)*nums[j]+sum-nums[j];
j--;
ans=max(f[i],ans);
}
return ans;
}
};


10个月前

### 分类讨论去模拟

#### 代码

class Solution {
public:
string pushDominoes(string s) {
int left=0,right=0,len=s.size();
for(int i=0;i<len;i++)
{
if(s[i]!='.')
{
left=right;
right=i;
if(s[left]=='.'&&s[right]=='L')
for(int j=left;j<=right;j++)
s[j]='L';
else if(s[left]==s[right])
for(int j=left;j<=right;j++)
s[j]=s[left];
else if(s[left]=='R'&&s[right]=='L')
{
int mid=(left+right)/2;
if((left+right)%2==0)
{
for(int j=left;j<mid;j++)
s[j]='R';
for(int j=mid+1;j<=right;j++)
s[j]='L';
}
else
{
for(int j=left;j<=mid;j++)
s[j]='R';
for(int j=mid+1;j<=right;j++)
s[j]='L';
}
}
}
}
if(s[right]=='R')
for(int i=right;i<len;i++)
s[i]='R';
return s;
}
};


10个月前

### dfs+bfs

#### 代码

class Solution {
public:
typedef pair<int,int> PII;
queue<PII> q;
int m,n;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int g[110][110];
void dfs(int x,int y,vector<vector<int>> &grid)
{
grid[x][y]=2;
g[x][y]=0;
q.push({x,y});
for(int i=0;i<4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[nx][ny]==1)
dfs(nx,ny,grid);
}
}
int shortestBridge(vector<vector<int>>& grid) {
m=grid.size(),n=grid[0].size();
memset(g,127,sizeof g);
int flag=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
if(grid[i][j])
{
dfs(i,j,grid);
flag=1;
break;
}
if(flag)
break;
}
int ans=INT_MAX;
while(!q.empty())
{
int x=q.front().first,y=q.front().second;
q.pop();
for(int i=0;i<4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>=0&&nx<m&&ny>=0&&ny<n)
{
if(grid[x][y]==2&&grid[nx][ny]==0&&g[x][y]+1<g[nx][ny])
{
g[nx][ny]=g[x][y]+1;
q.push({nx,ny});
}
else if(((grid[x][y]==2&&grid[nx][ny]==1)||(grid[x][y]==0&&grid[nx][ny]==1))&&g[x][y]+1<ans)
ans=g[x][y]+1;
else if(grid[x][y]==0&&grid[nx][ny]==0&&g[x][y]+1<g[nx][ny])
{
g[nx][ny]=g[x][y]+1;
q.push({nx,ny});
}
}
}
}
return ans-1;
}
};