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:
bool PredictTheWinner(vector& nums) {
int n = nums.size();
vector dp(n);
for (int i = n - 1; i >= 0; i--) {
dp[i] = nums[i];
for (int j = i + 1; j < n; j++) {
dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1]);
}
}
return dp[n - 1] >= 0;
}
};
class Solution{
public:
Node* LCA(Node *root, int n1, int n2)
{
if(root==NULL){
return NULL;
}
if(root->data>n1 && root->data>n2){
return LCA(root->left, n1, n2);
}
else if(root->datadataright, n1, n2);
}
else{
return root;
}
}
};
class Solution {
private:
bool CanRun(long long avg,int n, vector<int>& b){
long long sum = 0;
for(auto it:b){
if(avg>it) sum+=it;
else sum+=avg;
}
return sum>=avg*n;
}
public:
long long maxRunTime(int n, vector<int>& b) {
long long start = 0,end = 0,ans = 0;
for(auto it:b){
end+=it;
}
end/=n;
while(start<=end){
long avg = (start+end)/2;
if(CanRun(avg,n,b)){
ans = avg;
start = avg+1;
}else{
end = avg-1;
}
}
return ans;
}
};
class Solution
{
public:
//Heapify function to maintain heap property.
void heapify(int arr[], int n, int i)
{
int largest=i;
int l=2*i+1;
int r=2*i+2;
if(rarr[largest])
largest=r;
if(larr[largest])
largest=l;
if(largest!=i)
{
swap(arr[largest],arr[i]);
heapify(arr,n,largest);
}
}
public:
//Function to build a Heap from array.
void buildHeap(int arr[], int n)
{
for(int i=(n/2)-1;i>=0;i--)
heapify(arr,n,i);
for(int i=n-1;i>=0;i--)
{
swap(arr[i],arr[0]);
heapify(arr,i,0);
}
}
public:
//Function to sort an array using Heap Sort.
void heapSort(int arr[], int n)
{
buildHeap(arr,n);
return ;
}
};
class Solution {
public:
bool is_possible(vector<int>& dist,int speed, double hour){
double cur_time=0;
for(int i=0;i<dist.size();i++){
cur_time=cur_time+(double)dist[i]/speed;
if(cur_time>hour)return false;
cur_time=ceil(cur_time);
}
return true;
}
int minSpeedOnTime(vector<int>& dist, double hour) {
if(ceil(hour)<dist.size())return -1;
int start=1,end=1e8,mid=0;
while(start<=end){
mid=(start+end)>>1;
if(is_possible(dist,mid,hour)){
end=mid-1;
}
else
start=mid+1;
}
return start;
}
};
Node* solve(Node *root, int& k, int node){
if(root==NULL){
return NULL;
}
if(root->data == node){
return root;
}
Node* leftAns = solve(root->left,k,node);
Node* rightAns = solve(root->right,k,node);
if(leftAns != NULL && rightAns == NULL){
k--;
if(k<=0){
k= INT_MAX;
return root;
}
return leftAns;
}
if(leftAns == NULL && rightAns != NULL){
k--;
if(k<=0){
k= INT_MAX;
return root;
}
return rightAns;
}
return NULL;
}
int kthAncestor(Node *root, int k, int node)
{
Node* ans = solve(root,k,node);
if(ans == NULL || ans->data == node){
return -1;
}
return ans->data;
}
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int start = 0;
int end = arr.size()-1;
while(start<end){
int mid = start + (end - start)/2;
if(arr[mid]<arr[mid+1]){
start = mid + 1;
}
else{
end = mid;
}
}
return end;
}
};
vector findSpiral(Node *root)
{
queue q;
q.push(root);
bool flag = true;
vector ans;
while(!q.empty()){
int len = q.size();
vector temp(len);
for(int i=0;idata);
if(node->left)q.push(node->left);
if(node->right)q.push(node->right);
}
for(auto it:temp){
ans.push_back(it);
}
flag = !flag;
}
return ans;
}
class Solution {
public:
double myPow(double x, int n) {
long long temp = n;
double res=1;
if(n<0){
temp = -temp;
}
while(temp>0){
if(temp%2){
res = res*x;
}
x = x*x;
temp = temp/2;
}
if(n<0){
res = 1/res;
}
return res;
}
};
class Solution
{
public:
//Function to return list containing elements of right view of binary tree.
void solve(Node *root, vector& ans, int level){
if(root==NULL){
return;
}
if(ans.size()==level){
ans.push_back(root->data);
}
solve(root->right, ans, level+1);
solve(root->left, ans, level+1);
}
vector rightView(Node *root)
{
vector ans;
int level=0;
solve(root, ans, level);
return ans;
}
};
