Palindrome Linked lists

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

Solution:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* temp = head;
        stack<int> st;
        while (temp != NULL) {
            st.push(temp->val);
            temp = temp -> next;
        }
     
        while (!st.empty()) {
            if (st.top() != head -> val) {
                return false;
            } else {
                st.pop();
                head = head -> next;
            }
        }
        return true;
    }
    // For o(1) space,
    // 1. Find pointer to center node.
    // 2. Reverse the link list from center node.
    // Finally compare.
};

======== o(1) =======

 ListNode * reverse(ListNode *head) {
        ListNode *cur = head, *pre = NULL, *next = NULL;
       
        while (cur != NULL) {
            next = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    bool isPalindrome(ListNode* head) {
        ListNode *trav = head, *center = head;
       
        if (head == NULL || head -> next == NULL) {
            return true;
        }
       
        while (trav != NULL) {
            if (trav -> next != NULL) {
                trav = trav -> next -> next;
                center = center -> next;
            } else {
                trav = NULL;
            }
        }
       
        ListNode *end = reverse(center);
       
        while (end != NULL) {
            if (head -> val != end -> val) {
                return false;
            }
            head = head -> next;
            end = end -> next;
        }
        return true;
    }
};

Lowest Common Ancestor of a Binary Search Tree

Problem:

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Solution:

/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) {
            return NULL;
        } else if (root -> val == p ->val ||
                    root -> val == q -> val ||
                    (root -> val > p -> val && root -> val < q -> val) ||
                    (root -> val > q -> val && root -> val < p -> val)) {
            return root;
        } else if (root -> val > p -> val &&
                    root -> val > q -> val) {
            return lowestCommonAncestor(root -> left, p, q);
        } else {
            return lowestCommonAncestor(root -> right, p, q);
        }
    }
};

=== Nicer one ===

 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        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 root;
    }

==== Another one =====

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

Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

Solution:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        if (node == NULL)
            return;
        if (node -> next != NULL) {
            ListNode* temp = node -> next;
            node -> val = node -> next -> val;
            node -> next = node -> next -> next;
            delete(temp);
        }
        return;
    }
};

Valid Anagrams

Problem:

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

Solution:
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.empty() && t.empty())
            return true;
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

Another one:

1. class Solution {  
2. public:  
3.     bool isAnagram(string s, string t) {  
4.         int len1 = s.length();  
5.         int len2 = t.length();  
6.         if(len1!=len2){  
7.             return false;  
8.         }  
9.         vector<int> count(26, 0);  
10.         for(int i=0; i<len1; i++){  
11.             count[s[i]-'a']++;  
12.         }  
13.         for(int i=0; i<len2; i++){  
14.             if(--count[t[i]-'a']<0){  
15.                 return false;  
16.             }  
17.         }  
18.         return true;  
19.     }  
20. };  

======= Another one =====

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) {
            return false;
        }
        unordered_map<char, int> mp;
       
        for (auto ch: s) {
            mp[ch]++;
        }
       
        for (auto ch: t) {
            if (!mp.count(ch)) {
                return false;
            }
            mp[ch]--;
            if (mp[ch] < 0) {
                return false;
            }
        }
       
        return true;
    }
};

Binary Tree Paths

Problem:

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

Solution:

/**
 * 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:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans; string path;
        if (root == NULL) {
            return ans;
        } else {
            btPath(ans, path, root);
        }
        return ans;
    }
    void btPath(vector<string>& ans, string path, TreeNode* root) {
       path += (path != "" ? "->" + to_string(root -> val): to_string(root -> val));
       if (root -> left == NULL && root -> right == NULL) {
            ans.push_back(path);
        }
        if (root -> left != NULL) {
            btPath(ans, path, root->left);
        }
        if (root -> right != NULL) {
            btPath(ans, path, root->right);
        }
    }
};

===== Another ========
    void btpath(TreeNode *root, string str, vector<string>& ans) {
        if (str == "") {
            str += to_string(root -> val);
        } else {
            str += "->" + to_string(root->val);
        }
     
        if (root -> left == NULL && root -> right == NULL) {
            ans.push_back(str);
        }
        if (root -> left != NULL) {
            btpath(root->left, str, ans);
        }
        if (root -> right != NULL) {
            btpath(root->right, str, ans);
        }
    }
 
    vector<string> binaryTreePaths(TreeNode* root) {
        string str;
        vector<string> ans;
        if (root == NULL) {
            return ans;
        }
        btpath(root, str, ans);
        return ans;
    }

======= Additional complications :) =====

/**
 * 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:
    void helper(TreeNode* root, vector<string>& ans, string s) {
        if (root == NULL) {
            return;
        } else if (root -> left == NULL && root -> right == NULL) {
            if (!s.empty()) {
                ans.push_back(s + "->" + to_string(root->val));
            } else {
                ans.push_back(to_string(root->val));
            }
        } else {
            if (!s.empty()) {
                s = s + "->" + to_string(root->val);
                helper(root -> left, ans, s);
                helper(root -> right, ans, s);
            } else {
                helper(root -> left, ans, to_string(root->val));
                helper(root -> right, ans, to_string(root->val));
            }
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        string s;
        helper(root, ans, s);
        return ans;
    }
};

=========== 2020 ========

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

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

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

 * };

 */

class Solution {

public:

    vector<string> binaryTreePaths(TreeNode* root) {

        // BFS.

        vector<string> ans;

        queue<pair<TreeNode*, string>> q;

        if (root == NULL) {

            return ans;

        }

        q.push(make_pair(root, to_string(root -> val)));

        while (!q.empty()) {

            pair<TreeNode*, string> node = q.front(); q.pop();

            if (node.first -> left != NULL) {

                q.push(make_pair(node.first -> left, node.second + "->" + to_string(node.first->left -> val)));

            }

            if (node.first -> right != NULL) {

                q.push(make_pair(node.first -> right, node.second + "->" + to_string(node.first->right -> val)));

            }

            if (node.first -> left == NULL && node.first -> right == NULL) {

                ans.push_back(node.second);

            }

        }

        return ans;

        

        /*

        // DFS

        void btpath(TreeNode *root, string str, vector<string>& ans) {

            if (str == "") {

                str += to_string(root -> val);

            } else {

                str += "->" + to_string(root->val);

            }

            if (root -> left == NULL && root -> right == NULL) {

                ans.push_back(str);

            }

            if (root -> left != NULL) {

                btpath(root->left, str, ans);

            }

            if (root -> right != NULL) {

                btpath(root->right, str, ans);

            }

        }

        vector<string> binaryTreePaths(TreeNode* root) {

            string str;

            vector<string> ans;

            if (root == NULL) {

                return ans;

            }

            btpath(root, str, ans);

            return ans;

        }

        */

    }

};

Add Digits

Problem:

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

Hint:

1. A naive implementation of the above process is trivial. Could you come up with other methods?
2. What are all the possible results?
3. How do they occur, periodically or randomly?
4. You may find this Wikipedia article useful.

Solution:

class Solution {
public:
    int addDigits(int n) {
        /*
        int sum = 0;
        while (n != 0) {
            sum += n % 10;
            n = n/10;
            if (n == 0 && sum/10 != 0) {
                n = sum;
                sum = 0;
            }
        }
        return sum;
        */
        // Awesome : Simple beauty of digits.
        if (n == 0) {
            return 0;
        } else if (n % 9 == 0) {
            return 9;
        } else {
            return n % 9;
        }
    }
};

Ugly Number

Problem:

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

Solution:

class Solution {
public:
    bool isUgly(int num) {
        if (num < 1)
            return false;
        if (num == 1) {
            return true;
        } else if (num % 2 == 0) {
            return isUgly(num/2);
        } else if (num % 3 == 0) {
            return isUgly(num/3);
        } else if (num % 5 == 0) {
            return isUgly(num/5);
        }
        return false;
    }
};

Another Approach:

int maxDivide(int a, int b)

{

  while (a%b == 0)

   a = a/b;

  return a;

}  

 

/* Function to check if a number is ugly or not */

int isUgly(int no)

{

  no = maxDivide(no, 2);

  no = maxDivide(no, 3);

  no = maxDivide(no, 5);

   

  return (no == 1)? 1 : 0;

}