LeetCode, GeeksForGeeks Problem of the day solution
Открыть в Telegram
Complete daily challenges from LeetCode, GeeksForGeeks and redeem their rewards Channel link : https://t.me/leetcode_gfg_potd
Больше1 250
Подписчики
+224 часа
+147 дней
+2930 день
Архив постов
class Solution
{
public:
//User function Template for C++
int maxProfit(vector &price){
int n=price.size();
vector dp(n,0);
int ma=price[n-1];
for(int i=n-2;i>=0;i--){
dp[i]=max(dp[i+1],ma-price[i]);
ma=max(ma,price[i]);
}
int mi=price[0];
for(int i=1;i
class Solution {
public:
int findJudge(int n, vector>& trust) {
vector mp(n+1);
for(auto i: trust)
{
int ai = i[0],bi = i[1];
mp[bi]++;
mp[ai]--;
}
for(int i=1;i<=n;i++){
if(mp[i]==n-1) return i;
}
return -1;
}
};
class Solution
{
public:
int M = 1e9+7;
int solve(string &s,string &t,int i,int j,vector>&dp){
//returns the number of subsequece that has jth char at ith char
if(j<0){
return 0;
}
if(i<0){
return 0;
}
if(dp[j][i]!=-1){
return dp[j][i];
}
if(s[i]==t[j]){
int ans = 0;
if(j==0){
return 1;
}
for(int k=0;ks.size()){
return 0;
}
vector>dp(t.size()+1,vector(s.size()+1,-1));
int ans = 0;
for(int i=0;i
class Solution {
public:
int rangeBitwiseAnd(int left, int right) {
if (right<=left || left == 0) return left;
long closest = 1;
int num = 2147483647;
long diff = right - left;
while (closest<=diff)
{
num = num-closest;
closest*=2;
}
int num1 = right & num;
return left&num1;
}
};
class Solution{
public:
int mod = 1003;
int solve(string& s, int i, int j, int isTrue, vector>>& dp){
if(i>j){
return 0;
}
if(i==j){
if(isTrue==1){
return s[i]=='T';
}
else{
return s[i]=='F';
}
}
if(dp[i][j][isTrue] != -1){
return dp[i][j][isTrue];
}
int ways = 0;
for(int index=i+1;index<=j-1;index+=2){
int LT = solve(s, i, index-1, 1, dp)%mod;
int RT = solve(s, index+1, j, 1, dp)%mod;
int LF = solve(s, i, index-1, 0, dp)%mod;
int RF = solve(s, index+1, j, 0, dp)%mod;
if(s[index]=='&'){
if(isTrue==1){
ways = (ways + (LT*RT)%mod)%mod;
}
else{
ways = (ways + ((LT*RF)%mod + (RT*LF)%mod + (LF*RF)%mod)%mod)%mod;
}
}
else if(s[index]=='|'){
if(isTrue==1){
ways = (ways + ((LT*RF)%mod + (LF*RT)%mod + (LT*RT)%mod)%mod)%mod;
}
else{
ways = (ways + (LF*RF)%mod)%mod;
}
}
else{
if(isTrue==1){
ways = (ways + ((LT*RF)%mod + (LF*RT)%mod)%mod)%mod;
}
else{
ways = (ways + ((LT*RT)%mod + (LF*RF)%mod)%mod)%mod;
}
}
}
return dp[i][j][isTrue] = ways;
}
int countWays(int N, string S){
int n=S.size();
int i=0;
int j=n-1;
int isTrue = 1;
vector>> dp(n, vector>(n, vector(2, -1)));
return solve(S, i, j, isTrue, dp);
}
};
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for(int i = 0 ; i < n ; i++)
sum+=nums[i];
return (n*(n+1)/2) - sum;
}
};
class Solution
{
public:
int wordBreak(string s, vector &word) {
vector dp(s.size()+1, 0);
dp[0]=true;
unordered_set st(word.begin(), word.end());
for(int i=1;i<=s.size();i++){
for(int j=0;j
class Solution {
public:
bool isPowerOfTwo(int n) {
for( int i=0; i<=30 ; i++){
int ans = pow(2, i);
if( ans == n){
return true;
}
}
return false;
}
};
class Solution{
public:
int minValue(string s, int k){
int freq[26]={0};
for(int i=0;ifreq[maxidx]){
maxidx=i;
}
}
freq[maxidx]--;
}
long long sum=0;
for(int i=0;i<26;i++){
sum+=pow(freq[i],2);
}
return sum;
}
};
class Solution {
public:
int mostBooked(int n, vector<vector<int>>& meetings) {
vector<int>ans(n,0);
priority_queue<int,vector<int>,greater<int>>avail;
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long, int>>>busy;
for(int i = 0; i< n ;i++){
avail.push(i);
}
sort(meetings.begin(),meetings.end());
for (auto &&meeting : meetings){
int start = meeting[0],end = meeting[1];
while(busy.size() > 0 && busy.top().first <= start){
avail.push(busy.top().second);
busy.pop();
}
if(avail.size() > 0)
{
int top = avail.top();
ans[top]++;
avail.pop();
busy.push({end,top});
}
else
{
auto top = busy.top();
int end1 = top.first, index = top.second;
ans[index]++;
busy.pop();
busy.push({top.first + end-start, index});
}
}
return max_element(ans.begin(),ans.end()) - ans.begin();
}
};
