Reverse Integer (LeetCode)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public: int reverse(int x) { bool flag = false; if(x<0) { flag = true; x*=-1; } int rev = 0; while(x) { if((rev*10)/10 != rev) return 0; // checking overflow rev = rev*10 + x%10; x/=10; } if(flag) rev*=-1; return rev; } };

Median of Two Sorted Arrays (LeetCode)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int l1 = nums1.size(); int l2 = nums2.size(); if(l1>l2) return findMedianSortedArrays(nums2, nums1); int k = (l1+l2-1)>>1; int lft = 0, rgt = l1; while(lft<rgt) { int md = (lft+rgt)>>1; if(nums1[md]<nums2[k-md]) lft = md+1; else rgt = md; } double x, y; if(lft>0 && (k-lft)>=0) x = max(nums1[lft-1], nums2[k-lft]); else if(lft>0) x = nums1[lft-1]; else if(k-lft>=0) x = nums2[k-lft]; if((l1+l2) & 1) return x; //total odd size, single median if(lft<l1 && (k-lft+1)<l2) y = min(nums1[lft], nums2[k-lft+1]); else if(lft<l1) y = nums1[lft]; else if((k-lft+1)<l2) y = nums2[k-lft+1]; return (x+y)/2.0; } };

Perfect Squares (LeetCode)

Problem: Perfect Squares
Given a positive integer n, find the least number of perfect square numbers which sum to n.

class Solution {
public:
    int dp[100000];
    int numSquares(int n) {
        memset(dp, -1, sizeof(dp));
        return func(n);
        
    }
    int func(int n)
    {
        if(n<=0) return 0;
        
        if(dp[n]!=-1) return dp[n];
        int ret=1e9;
        for(int i=1;i*i<=n;i++)
            ret=min(ret, func(n-i*i)+1);
            
        return dp[n]=ret;
    }
};

Sort List (LeetCode)

Problem: Sort List
Sort a linked list in O(n log n) time using constant space complexity.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        mergeSort(&head);
        return head;
    }
    
    void mergeSort(ListNode **head) //pointer of pointer
    {
        ListNode *hd = *head;
        if(hd==NULL || hd->next==NULL) return;
        
        ListNode *a, *b;
        a=*head;
        split(*head, &b);
        mergeSort(&a);
        mergeSort(&b);
        *head = mergeTwo(a, b);
    }
    
    void split(ListNode *head, ListNode **b)
    {
        ListNode *slow, *fast;
        slow = head;
        fast = head->next;
        while(fast!=NULL && fast->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        *b = slow->next;
        slow->next=NULL;
    }

    ListNode *mergeTwo(ListNode *a, ListNode *b)
    {
        ListNode *head = NULL;
        
        if(a==NULL)
            return b;
        if(b==NULL)
            return a;
            
        if(a->val <= b->val)
        {
            head = a;
            head->next = mergeTwo(a->next, b);
        }
        else 
        {
            head = b;
            head->next = mergeTwo(a, b->next);
        }
        
        return head;
    }
    
};

Regular Expression Matching (LeetCode)

Problem: Regular Expression Matching

class Solution {
public:
    int sl, pl;
    bool isMatch(string s, string p) {
        sl=s.length();
        pl=p.length();
        if(pl==0) return sl==0;
        return allMatch(s, 0, p, 0);
    }
    
    bool allMatch(string s, int scur, string p, int pcur)
    {
        //if(scur==sl) return pcur==pl;
        if(pcur==pl) return scur==sl;
        
        if(pcur+1<pl && p[pcur+1]=='*')
        {
            if(allMatch(s, scur, p, pcur+2)) 
                return true;
            if(p[pcur]=='.' || p[pcur]==s[scur])
            {
              while(scur<sl && (p[pcur]=='.' || p[pcur]==s[scur]))
                {
                    if(allMatch(s, scur+1, p, pcur+2)) 
                        return true;
                    scur++;
                    /*if(scur==sl)
                        break;*/
                }
            }
        }
        else if(p[pcur]=='.' || p[pcur]==s[scur]) 
            return allMatch(s, scur+1, p, pcur+1);
        return false;
    }
};

Longest Common Prefix (LeetCode)

Problem: Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        
        string longestPrefix="";
        int strsSize = strs.size();
        if(strsSize==0) return longestPrefix;
        if(strsSize==1) return strs[0];
        
        int shortestStringLength = strs[0].size();
        for(int i=1;i<strsSize;i++)
            if(shortestStringLength>strs[i].size())
                shortestStringLength = strs[i].size();
            
        for(int i=0;i<shortestStringLength;i++)
        {
            for(int j=1;j<strsSize;j++)
                if(strs[j][i]!=strs[j-1][i])
                    return longestPrefix;
            longestPrefix+=strs[0][i];
        }
        return longestPrefix;
    }
};

Count Numbers with Unique Digits (LeetCode)

Problem: Count Numbers with Unique Digits
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.

class Solution {
public:
    int visit[11], steps;
    int countNumbersWithUniqueDigits(int n) {
        if(n>10) n=10;
        int ret=0;
        for(int i=1;i<=n;i++)
        {
            steps = i;
            ret += backTrack(i);
        }
        return ret+1;
    }
    int backTrack(int stepRemaining)
    {
        if(stepRemaining==0)
            return 1;
        int ret=0;
        for(int i=0;i<10;i++)
            if(stepRemaining==steps && i==0) continue;
            else if(visit[i]==0)
            {
                visit[i]=1;
                ret += backTrack(stepRemaining-1);
                visit[i]=0;
            }
        return ret;
    }
};

Remove Linked List Elements (LeetCode)

Problem: Remove Linked List Elements
Remove all elements from a linked list of integers that have value val.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //if(head==NULL) return NULL;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        
        while(head!=NULL && head->val == val) 
        {
            head = head->next;
            dummy->next = head;
        }
        
        if(head==NULL) return NULL;
        
        while(head->next!=NULL)
        {
            if(head->next->val == val)
                head->next = head->next->next;
            else head=head->next;
        }
        return dummy->next;
    }
};

Reverse Bits (LeetCode)

Problem: Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t reverse=0;
        for(int i=0;i<32;i++)
        {
            if(n & (1<<i)) 
                reverse |= (1<<(31-i));
        }
        return reverse;
    }
};

H-Index (LeetCode)

Problem: H-Index

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end(), greater<int>());
        for(int i=0;i<citations.size();i++)
            if(citations[i]<=i)
                return i;
        return citations.size();
    }
};

Valid Palindrome (LeetCode)

Problem: Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases

class Solution {
public:
    bool isPalindrome(string s) {
        
        bool isEmpty=true;
        for(int i=0;i<s.size();i++)
            if(isalnum(s[i]))
            {
                isEmpty=false;
                break;
            }
            
        if(isEmpty) return 1;
        
        int left = 0, right = s.size()-1;
        while(left<right)
        {
            while(!isalnum(s[left])) left++;
            while(!isalnum(s[right])) right--;
            if(tolower(s[left])!=tolower(s[right])) return 0;
            left++;
            right--;
        }
        return 1;
    }
};