83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Approach : The key to solve the problem is using the right loop condition and maintaining necessary pointers in each loop.

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

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* deleteDuplicates(struct ListNode* head) { struct ListNode *cur, *_next; if(head == NULL || head->next == NULL){ return head; } cur = head; while(cur && cur->next){ //set the pointer of the current next to the next node if duplicate is found if(cur->val == cur->next->val){ _next = cur->next->next; free(cur->next); cur->next = _next; }else{ //else just move forward to next node cur = cur->next; } } return head; }

Read More

100. Same Tree

Given two binary trees, write a function to check if they are equal or not. 

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
Below are some examples:

Ex. 1:
Tree 1:
                   10
        20                   30
  40        50        60        70

Tree 2:    
                  10
        20                   30
  40        50        60        70
Tree 1 & Tree 2 are identical.

Example 2:
Tree 1:    
                 10
        20                   30
  40        50        60        70
Tree 2:
                   10
        20                   30
  40        60        50        70

Trees 1 & 2 are not identical as their structures are same but values at nodes 50 and 60 differ.

Example 3:
Tree 1:
                   10
        20                   30
  40        50        60        
Tree 2:
                   10
        20                   30
  40        50                  60

Trees 1 & 2 are not identical as the structures are not same as 60 is on left subtree of node 30 in Tree 1 but on right subtree of node 30 in Tree 2.

Approach : Use the simple recursive solution.

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

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isSameTree(struct TreeNode* p, struct TreeNode* q) { if(p == NULL && q == NULL){ return true; } if(p == NULL && q != NULL || p != NULL && q == NULL){ return false; } if(p->val == q->val){ return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } return false; }

Read More

70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Approach : The standard recursive solution times out so the idea is to use the iterative solution to find the nth fibonacci number.

int climbStairs(int n) {
    int f1 = 2;
    int f2 = 1;
    if(n == 1) {
        return f2;
    } else if(n == 2) {
        return f1;
    }

    int fn;
    for(int i = 3; i <= n; i++) {
        fn = f1 + f2;
        f2 = f1;
        f1 = fn;
    }
    return fn;
}

Here is the link to the ideone solution : http://ideone.com/ErEU6E

Read More

69. Sqrt(x)

Implement int sqrt(int x).

Return the floor if x is not a perfect square.

Approach :  Using binary search making sure that overflow does not happen by taking long long.

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

class Solution { public: int mySqrt(int x) { if(x <= 1){ return x; } int low = 0, high = x / 2; //long to prevent overflow long long mid; while(low <= high){ mid = (low + high) / 2; //needs to be long to prevent overflow long long t = mid * mid; //second part is to return floor if x is not perfect square if( t == x || ((t < x) && ((mid + 1) * (mid + 1) > x))){ break; } else if(x < t){ high = mid - 1; }else{ low = mid + 1; } } return mid; } };

Here is the link to the ideone solution : http://ideone.com/taTCKu

Read More

38. Count and Say

Problem: The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1

2.     11
3.     21

4.     1211

5.     111221

1 is read off as "one 1" or 11.

11 is read off as "two 1s" or 21.

21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1

Output: "1"

Example 2:

Input: 4

Output: "1211" 

Approach: The solution is straight forward. The appendNext method is run over n times where n is the input.

class Solution {
public:
    public:
 
    string appendNext(string str){
        string str1;
        char ch = str[0];
        int chCount = 1;
        for(int i = 1; i <= str.size(); i++){
            if (str[i] == ch){
                chCount++;
            }
            else {
                char chr = chCount + '0';
                str1 = str1 + chr;
                str1 = str1 + ch;
                ch = str[i];
                chCount = 1;
            }
        }
        return str1;
    }
    
    string countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        string str1 = "1";
        string strn;
        for (int i = 1; i < n; i++){
            strn = appendNext(str1);
            str1 = strn;
        }
        return strn;
    }
};

Here is the link to the ideone solution : http://ideone.com/tbYXUM

Read More