LeetCode Find Minimum in Rotated Sorted Array II a short one

LeetCode Find Minimum in Rotated Sorted Array II a short one

class Solution {

public:

    int search(vector<int>& nums,int l,int r)

    {

        if(l>r)

          return INT_MAX;

        else if(l==r)

          return nums[l];

        else if(nums[l]<nums[r])

          return nums[l];

        int mid=(l+r)/2;

        return min(search(nums,l,mid),search(nums,mid+1,r));

    }

    int findMin(vector<int>& nums) {

        return search(nums,0,nums.size()-1);

    }

};

LeetCode Binary Tree Maximum Path Sum nice bottom up recursion

LeetCode Binary Tree Maximum Path Sum nice bottom up recursion

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    int fun(TreeNode* root,int *max_sum)

     {

         if(root==NULL)

           return 0;

         int ls=fun(root->left,max_sum);

         int rs=fun(root->right,max_sum);

         int mx=max(max(root->val+ls,root->val+rs),root->val+ls+rs);

           mx=max(mx,root->val);

          if(mx>(*max_sum))

             (*max_sum)=mx;

          return max(max(root->val+ls,root->val+rs),root->val);

     }

    int maxPathSum(TreeNode* root) {

        int max_sum=INT_MIN;

        fun(root,&max_sum);

        return max_sum;

    }

};

LeetCode Symmetric Tree

LeetCode Symmetric Tree

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    bool fun(TreeNode* root1,TreeNode* root2){

        if(root1==NULL && root2==NULL)

         return true;

        if(root1==NULL || root2==NULL)

         return false;

        return (root1->val==root2->val && fun(root1->left,root2->right) && fun(root1->right,root2->left));

    }

    bool isSymmetric(TreeNode* root) {

        if(root==NULL)

          return true;

         return fun(root->left,root->right);

       

    }

};

LeetCode Symmetric Tree

LeetCode Symmetric Tree

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    bool fun(TreeNode* root1,TreeNode* root2){

        if(root1==NULL && root2==NULL)

         return true;

        if(root1==NULL || root2==NULL)

         return false;

        return (root1->val==root2->val && fun(root1->left,root2->right) && fun(root1->right,root2->left));

    }

    bool isSymmetric(TreeNode* root) {

        if(root==NULL)

          return true;

         return fun(root->left,root->right);

       

    }

};

LeetCode Validate Binary Search Tree

LeetCode Validate Binary Search Tree

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    bool fun(TreeNode* root,int mn,int mx,int * cmn,int * cmx){

        if(root==NULL)

         return true;

        if(root->val <= mn){

         if(mn==-2147483648 && *cmn==0)

             {

             *cmn=1;

             return (fun(root->left,mn,root->val,cmn,cmx) && fun(root->right,root->val,mx,cmn,cmx));

             }

           return false;

        }

        if(root->val >= mx)

         {

             if(mx==2147483647 && *cmx==0)

             {

             *cmx=1;

             return (fun(root->left,mn,root->val,cmn,cmx) && fun(root->right,root->val,mx,cmn,cmx));

             }

            return false;

         }

        return (fun(root->left,mn,root->val,cmn,cmx) && fun(root->right,root->val,mx,cmn,cmx));

    }

    bool isValidBST(TreeNode* root) {

        int cmn=0;

        int cmx=0;

        return fun(root,INT_MIN,INT_MAX,&cmn,&cmx);

    }

};

LeetCode Restore IP Addresses O(n3) still accepted

LeetCode  Restore IP Addresses

class Solution {

public:

    vector<string> restoreIpAddresses(string s) {

     vector < string > ans;

     int l=s.size();

     if(l>12 || l<4)

       return ans;

     int i,j,k;

     int first,second,third,fourth;

     for(i=0;i<l-3;i++){

          string temp(s.begin(),s.begin()+i+1);

          if(temp.size()>=2 && temp[0]=='0')

           break;

          first=stoi(temp);

          if(first>255)

            break;

         for(j=i+1;j<l-2;j++){

            string temp1(s.begin()+i+1,s.begin()+j+1);

            if(temp1.size()>=2 && temp1[0]=='0')

             break;

            second=stoi(temp1);

            if(second>255)

            break;

         for(k=j+1;k<l-1;k++){

            string temp3(s.begin()+j+1,s.begin()+k+1);

            if(temp3.size()>=2 && temp3[0]=='0')

              break;

            third=stoi(temp3);

            string temp4(s.begin()+k+1,s.end());

            if(temp4.size()>=2 && temp4[0]=='0')

               continue;

            fourth=stoi(temp4);

            if(third<=255 && fourth<=255)

             {

                 string s1(s.begin(),s.end());

                 s1.insert(s1.begin()+i+1,'.');

                 s1.insert(s1.begin()+j+2,'.');

                 s1.insert(s1.begin()+k+3,'.');

                 ans.push_back(s1);

             }

          }

         }

       }

       return ans;

    }

};

LeetCode Reverse Linked List II

LeetCode Reverse Linked List II

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode* reverseBetween(ListNode* head, int m, int n) {

       if(head==NULL || head->next==NULL || (m==n))

         return head;

       ListNode * current=head;

       ListNode * prev=NULL;

       ListNode * next;

       ListNode * temp;

       ListNode *p;

       int cnt=n-m;

       while(m--){

           p=prev;

           prev=current;

           current=current->next;

       }

       temp=prev;

       while(cnt--){

           next=current->next;

           current->next=prev;

           prev=current;

           current=next;

       }

       if(p==NULL)

         head=prev;

       else

         p->next=prev;

       temp->next=current;

       return head;

    }

};