Spring 2021 daily question [week7 not finished]

1011. stay D The ability to deliver packages within days 【 Two points 】

class Solution {
    
public:
    bool check(vector<int> ve,int x,int w)
    {
    
        int cnt=1,sum=0;
        for(int i=0;i<ve.size();i++)
        {
    
            if(ve[i]>x) return false;
            sum+=ve[i];
            if(sum>x) cnt++,sum=ve[i];
        }
        return cnt<=w;
    }
    int shipWithinDays(vector<int>& weights, int days) 
    {
    
        int l=0,r=1e9;
        while(l<r)
        {
    
            int mid=l+r>>1;
            if(check(weights,mid,days)) r=mid;
            else l=mid+1;
        }
        return l;
    }
};

680. Cut the rope 【 Two points 】

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
double a[N];
int n,m;
bool check(double mid)
{
    
    int cnt=0;
    for(int i=0;i<n;i++) cnt+=a[i]/mid;
    return cnt>=m;
}
int main(void)
{
    
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a[i];
    double l=0,r=1e9;
    while(r-l>1e-4)
    {
    
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.2lf",l);
    return 0;
}

938. The range of binary search tree and

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    int sum=0;
    void dfs(TreeNode* root, int l, int r)
    {
    
        if(root->val>=l&&root->val<=r) sum+=root->val;
        if(root->left) dfs(root->left,l,r);
        if(root->right) dfs(root->right,l,r);
    }
    int rangeSumBST(TreeNode* root, int low, int high) 
    {
    
        dfs(root,low,high);
        return sum;
    }
};

1589. Build a binary search tree

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
unordered_map<int,int>l,r;
int n,a[N],idx,ans[N];
void dfs(int u)
{
    
    if(l[u]!=-1) dfs(l[u]);
    ans[u]=a[idx++];
    if(r[u]!=-1) dfs(r[u]);
}
void print()
{
    
    queue<int>q; q.push(0);
    vector<int>ve;
    while(q.size())
    {
    
        int t=q.front(); q.pop();
        ve.push_back(ans[t]);
        if(l[t]!=-1) q.push(l[t]);
        if(r[t]!=-1) q.push(r[t]);
    }
    for(int i=0;i<ve.size();i++) 
    {
    
        if(i) cout<<" ";
        cout<<ve[i];
    }
}
int main(void)
{
    
    cin>>n;
    for(int i=0;i<n;i++)
    {
    
        int id1,id2; cin>>id1>>id2;
        l[i]=id1,r[i]=id2;
    }
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    dfs(0);
    print();
    return 0;
}

633. Sum of squares

class Solution {
    
public:
    bool judgeSquareSum(int c) 
    {
    
        if(!c) return true;
        for(int i=1;i<=sqrt(c);i++)
        {
    
            int sum=c-i*i;
            int temp=sqrt(sum);
            if(temp*temp==sum) return true;
        }
        return false;
    }
};

1221. The sum of four squares 【 thinking + Two points 】

#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e7+10;
struct node
{
    
    int x,y,s;
}ve[N];
int n;
bool cmp(node a,node b)
{
    
    if(a.s==b.s) 
    {
    
        if(a.x==b.x) return a.y<b.y;
        return a.x<b.x;
    }
    return a.s<b.s;
}
int main(void)
{
    
    cin>>n;
    int k=0;
    for(int i=0;i*i<=n;i++)
        for(int j=i;j*j+i*i<=n;j++)
            ve[k++]={
    i,j,i*i+j*j};
    sort(ve,ve+k,cmp);
    for(int i=0;i*i<=n;i++)
    {
    
        for(int j=i;j*j+i*i<=n;j++)
        {
    
            int temp=n-i*i-j*j;
            int l=0,r=k-1;
            while(l<r)
            {
    
                int mid=(l+r)/2;
                if(ve[mid].s>=temp) r=mid;
                else l=mid+1;
            }
            if(ve[l].s==temp)
            {
    
                printf("%d %d %d %d\n",i,j,ve[l].x,ve[l].y);
                return 0;
            }
        }
    }
    return 0;
}

403. Frogger Helmet Chaos 【 Hang in the air DP】

1205. The number that can't be bought

#include<bits/stdc++.h>
using namespace std;
int a,b;
int main(void)
{
    
    cin>>a>>b;
    cout<<(a-1)*(b-1)-1;
    return 0;
}

137. A number that appears only once II

class Solution {
    
public:
    int singleNumber(vector<int>& nums) 
    {
    
        map<int,int>mp; 
        for(int i=0;i<nums.size();i++) mp[nums[i]]++;
        int ans=0;
        for(auto i=mp.begin();i!=mp.end();i++) 
            if(i->second==1) ans=i->first;
        return ans;
    }
};

73. Two numbers that appear only once in the array

class Solution {
    
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) 
    {
    
        vector<int>ans;
        map<int,int>mp;
        for(int i=0;i<nums.size();i++) mp[nums[i]]++;
        for(auto i=mp.begin();i!=mp.end();i++) 
            if(i->second==1) ans.push_back(i->first);
        return ans;
    }
};

690. The importance of employees 【DFS】

/* // Definition for Employee. class Employee { public: int id; int importance; vector<int> subordinates; }; */

class Solution {
    
public:
    map<int,int>mp;
    int dfs(int id,vector<Employee*> employees)
    {
    
        int u=mp[id];
        int sum=employees[u]->importance;
        vector<int>ve=employees[u]->subordinates;
        for(int i=0;i<ve.size();i++)
            sum+=dfs(ve[i],employees);
        return sum;
    }
    int getImportance(vector<Employee*> employees, int id) 
    {
    
        for(int i=0;i<employees.size();i++)
        {
    
            int k=employees[i]->id;
            mp[k]=i;
        }
        return dfs(id,employees);
    }
};

53. The smallest k Number

class Solution {
    
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
    
        sort(input.begin(),input.end());
        vector<int> ans;
        for(int i=0;i<k;i++) ans.push_back(input[i]);
        return ans;
    }
};

554. Brick walls 【 Hang in the air 】

1540. Dominant color

#include<bits/stdc++.h>
using namespace std;
int x,n,m;
stack<int>st;
int main(void)
{
    
    cin>>m>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
    
            int x; cin>>x;
            if(st.empty()) st.push(x);
            else if(st.top()!=x) st.pop();
            else if(st.top()==x) st.push(x);
        }
    cout<<st.top();
    return 0;
}