leetcode 235. Lowest Common Ancestor of a Binary Search Tree

Orignal question can be found here.

My solution is as follows:

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q)
{
        if(root == p || root == q || (root->val > p->val && root->val < q->val) || (root->val > q->val && root->val < p->val))
                return root;
        if(root->val > p->val && root->val > q->val)
                return lowestCommonAncestor(root->left, p, q);
        if(root->val < p->val && root->val < q->val)
                return lowestCommonAncestor(root->right, p, q);
        return NULL;
}

leetcode 383. Ransom Note

Orignal question can be found here.

My solution is as follows:

bool canConstruct(char* ransomNote, char* magazine)
{
        if(ransomNote == NULL)
                return true;
        if(magazine == NULL || strlen(ransomNote) > strlen(magazine))
                return false;

        int magazineLen = strlen(magazine);
        bool* flag = (bool*)malloc(sizeof(bool)*magazineLen);
        memset(flag, 0, magazineLen);

        bool result = false;
        for(int i=0; i<strlen(ransomNote); ++i)
        {
                result = false;
                for(int j=0; j<strlen(magazine); ++j)
                {
                        if(ransomNote[i] == magazine[j] && flag[j] == false)
                        {
                                result = true;
                                flag[j] = true;
                                break;
                        }
                }
                if(result == false)
                        return false;
        }
        return true;
}

leetcode 367. Valid Perfect Square

Orignal question can be found here.

My solution is as follows:

bool isPerfectSquare(int num)
{
        if(num==1)
                return true;
        if(num<4)
                return false;

        int head=2, tail=num/2;
        int mid=(head+tail)/2;
        while(head<=tail)
        {
                mid=(head+tail)/2;
                if(mid*mid<0)  // in case mid*mid is so large that it overflows.
                        tail=mid-1;
                else if(mid*mid==num)
                        return true;
                else if(mid*mid<num)
                        head=mid+1;
                else
                        tail=mid-1;
        }
        return false;
}

leetcode 66. Plus One

Orignal question can be found here.

My solution is as follows:

int* plusOne(int* digits, int digitsSize, int* returnSize)
{
        short all9=1;
        int i=0;

        /*  check if all in digits are 9 */
        for(i=0;i<digitsSize;++i)
                if(digits[i]!=9)
                {
                        all9=0;
                        break;
                }

        if(all9)  /* all in digits are 9 */
        {
                *returnSize=digitsSize+1;
                int* result=(int*)malloc(sizeof(int)*(*returnSize));
                result[0]=1;
                for(i=1;i<*returnSize;++i)
                        result[i]=0;
                return result;
        }
        else   /* not all in digits are 9 */
        {
                *returnSize=digitsSize;
                int* result=(int*)malloc(sizeof(int)*(*returnSize));
                i=*returnSize-1;
                while(digits[i]==9)
                {
                        result[i]=0;
                        --i;
                }
                result[i]=digits[i]+1;
                --i;
                while(i>=0)
                {
                        result[i]=digits[i];
                        --i;
                }
                return result;
        }

        return NULL;
}

leetcode 28. Implement strStr()

Orignal question can be found here.

My solution is as follows:

int strStr(char* haystack, char* needle)
{
        if(strlen(needle)==0)
                return 0;
        if(strlen(haystack)<strlen(needle))
                return -1;
        int i=0, j=0;
        for(i=0; i<(strlen(haystack)-strlen(needle)+1); ++i)
        {
                if(haystack[i] == needle[0])
                {
                        for(j=0; j<strlen(needle); ++j)
                        {
                                if(haystack[i+j]!=needle[j])
                                        break;
                        }
                        if(j==strlen(needle))
                                return i;
                }
        }
        return -1;
}

leetcode 24. Swap Nodes in Pairs

Orignal question can be found here.

My solution is as follows:

struct ListNode* swapPairs(struct ListNode* head)
{
        if(head==NULL)
                return NULL;
        struct ListNode* result=head->next;
        if(result==NULL)
                return head;
        struct ListNode* p=NULL;
        while(head!=NULL)
        {
                p=head->next->next;
                head->next->next=head;
                if(p==NULL)
                {
                        head->next=NULL;
                        break;
                }
                else if(p->next==NULL)
                {
                        head->next=p;
                        break;
                }
                else
                {
                        head->next=p->next;
                        head=p;
                }
        }
        return result;
}

leetcode 21. Merge Two Sorted Lists

Orignal question can be found here.

My solution is as follows:

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
        if(l1==NULL || l2==NULL)
                return (l2==NULL)?l1:l2;
        struct ListNode* ptr;
        struct ListNode* result;
        if(l1->val > l2->val)
        {
                result=l2;
                l2=l2->next;
        }
        else
        {
                result=l1;
                l1=l1->next;
        }

        ptr=result;

        while(l1!=NULL && l2!=NULL)
        {
                if(l1->val > l2->val)
                {
                        ptr->next=l2;
                        l2=l2->next;
                }
                else
                {
                        ptr->next=l1;
                        l1=l1->next;
                }
                ptr=ptr->next;
        }

        if(l1==NULL || l2==NULL)
                ptr->next=(l2==NULL)?l1:l2;

        return result;
}

leetcode 20. Valid Parentheses

Orignal question can be found here.

My solution is as follows:

bool isValid(char *s)
{
        char stack[32];
        int top=0;
        for(int i=0; i<strlen(s); ++i)
        {
                if(s[i]=='(' || s[i]=='[' || s[i]=='{')
                {
                        stack[top]=s[i];
                        ++top;
                }
                else if(top==0)
                        return false;
                else
                {
                        --top;
                        if((s[i]==')' && stack[top]!='(') ||
                           (s[i]==']' && stack[top]!='[') ||
                           (s[i]=='}' && stack[top]!='{'))
                                return false;
                }
        }

        if(top==0)
                return true;
        else
                return false;
}