immerse

4069

ljw11
YZ-S
Mango_C++
V1CI-_-
Tiantian2022
2850g
zst_2001
Lonan
Andrew1729
Ding-yu

dp_5

YAE
-摆烂王-
selfknow

immerse
2个月前
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.empty()) return -1;
int l=0,r=nums.size()-1;
while(l<r){
int mid=l+r+1>>1;
if(nums[mid]>=nums[0]) l=mid;
else r=mid-1;
}
if(target>=nums[0]) l=0;    //前面的区间
else l=r+1,r=nums.size()-1; //后面的区间

while(l<r){
int mid=l+r>>1;
if(nums[mid]>=target) r=mid;
else l=mid+1;
}
if (nums[r] == target) return r;
return -1;
}
};


immerse
2个月前

class Solution {
public:
int f(string & s){
map<char,int> cnt;
for (auto c:s ) cnt[c]++;
return cnt.begin()->second;
}
vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
vector<int> res;
int s[11]={0};//长度0-10
for(auto& w:words) s[f(w)]++;
for(int i=1;i<=10;i++) s[i]+=s[i-1];

for(auto & q :queries){
res.push_back(s[10]-s[f(q)]);
}
return res;
}
};


immerse
3个月前

dp版本

class Solution {
public:
int longestValidParentheses(string s) {
int n = s.length();
vector<int> f(n, 0);
//f[i]以i结尾的最长子串 只考虑s[i]==')'
//s[i]==')'
//1:s[i-1]=='('  f[i]=f[i-1]+2;
//2:s[i-1]==')'&&s[i-f[i-1]-1]=='('  f[i]=f[i-1]+2 +f[i-f[i-1]-1-1]
for (int i = 1; i < n; i++)
if (s[i] == ')') {
if (s[i - 1] == '(') {
f[i] = (i>=2? f[i - 2]:0) + 2;
}
else {
if (i - f[i - 1] - 1 >= 0 && s[i - f[i - 1] - 1] == '(')
f[i] = f[i - 1] + 2 + ((i - f[i - 1] - 2>=0)?f[i - f[i - 1] - 2]:0);
}
}

int ans = 0;
for (int i = 0; i < n; i++)  if(s[i]==')')ans = max(ans, f[i]);

return ans;
}
};


class Solution {
public:
int longestValidParentheses(string s) {
stack<int> stk;
int res=0;
int start=-1;
for(int i=0;i<s.size();i++){
if(s[i]=='('){
stk.push(i);
}
else{

if(stk.size()){
stk.pop();
if(stk.size()) res=max(res,i - (stk.top() + 1) + 1);
else res=max(res,i-start);
}
else{
start=i;
}
}
}
return res;
}
};


immerse
3个月前
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int k=nums.size()-1;
while(k>0&&nums[k-1]>=nums[k]) k--;
//从后往前

//321情况
if(k==0){
reverse(nums.begin(),nums.end());
}
else{
//24531 swap 后23541 =》23145
int t=k;
while(t<nums.size()&&nums[k-1]<nums[t]) t++;
swap(nums[t-1],nums[k-1]);
reverse(nums.begin()+k,nums.end());
}
}
};


immerse
3个月前
class Solution {
public:
//滑动窗口
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
if(!words.size()) return res;
unordered_map<string,int> tot;
for(auto  str:words) tot[str]++;
int n=s.size();
int m=words.size();
int k=words[0].size();
for(int i=0;i<k;i++){//起始位置的不同
unordered_map<string,int> wd;
int cnt=0;//如果暴力计算wd和tot是否匹配会TLE
for(int j=i;j+k<=n;j+=k){
if(j>=i+m*k){
auto word=s.substr(j-m*k,k);
wd[word]--;
//有效单词--
if(wd[word]<tot[word]) cnt--;
}

auto word = s.substr(j, k);//此时的下标为j+k—1<n <==> j+k<=n
wd[word]++;
//有效单词++
if(wd[word]<=tot[word]) cnt++;
//此时j处于倒数第一个单词
if(cnt==m) res.push_back(j-(m-1)*k);
}
}

return res;
}
};



immerse
3个月前
class Solution {
public:
int divide(int dividend, int divisor) {

int flag=1;
if(dividend<0&&divisor>0||dividend>0&&divisor<0) flag=-1;
int x=abs(dividend);
int y=abs(divisor);

long long  l=0,r=x;
while(l<r){
long long  mid=l+r+1>>1;
if(x>=mul(mid,y)) l=mid;
else r=mid-1;
}
long long res=flag==1?l:-l;
if(res>INT_MAX||res<INT_MIN) return INT_MAX;
return res;
}

long long  mul(long long   mid,long long  y){
long long res=0;
while(y){
if((y&1)==1)res+=mid;
y>>=1;
mid+=mid;
}
return res;
}
};

/*
if(dividend==INT_MIN&&divisor==-1) return INT_MAX;
int flag=1;
if(dividend<0&&divisor>0||dividend>0&&divisor<0) flag=-1;

long long  up=abs(dividend);
long long  down=abs(divisor);
long long  res=0;
for(int i=31;i>=0;i--){
if((up>>i)>=down){
res+=1<<i;
up-=(down<<i);
}
}
if (res > INT_MAX || res < INT_MIN) return INT_MAX;

return flag==1?res:-res;
*/


immerse
3个月前

class Solution {
public:
int strStr(string s, string p) {
int n = s.size(), m = p.size();
if(m == 0) return 0;
//设置哨兵
s=" "+s;
p=" "+p;
vector<int> next(m + 1);
//预处理next数组
for(int i = 2, j = 0; i <= m; i++){
while(j&&p[i]!=p[j+1]) j=next[j];
if(p[i] == p[j + 1]) j++;
next[i] = j;
}
//匹配过程
for(int i = 1, j = 0; i <= n; i++){
while(j&&s[i]!=p[j+1]) j=next[j];
if(s[i] == p[j + 1]) j++;
if(j == m) return i - m;//匹配成功 返回下标
}
return -1;
}
};



immerse
3个月前
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int k=0;
for(int i=0;i<nums.size();i++){
if(nums[i]!=val) nums[k++]=nums[i];
}
return k;
}
};


immerse
3个月前
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int k=0;
for(int i=0;i<nums.size();i++){
if(!(i&&nums[i]==nums[i-1])){
nums[k++]=nums[i];
}
}
return k;
}
};


immerse
3个月前
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:

ListNode* reverseKGroup(ListNode* head, int k) {
ListNode * dummy=new ListNode(-1);
ListNode * p=dummy;

while(p){

auto q=p;
for(int i=0;i<k&&q;i++) q=q->next;
if(!q) break;
auto a=p->next;
auto b=a->next;
for(int i=0;i<k-1;i++){
auto c=b->next;
b->next=a;
a=b;
b=c;
}
auto c=p->next;
p->next=a;
c->next=b;
p=c;
}
return dummy->next;
}
};