West Pavilion: August 2015

Thursday, August 6, 2015

Palindrome Linked List #LeetCode

Problem Reference:
https://leetcode.com/problems/palindrome-linked-list/

Problem Statement:
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:
Reverse the second half. And compare two halves.

/**
 * 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) {
        if (!head || !head->next) {
            return true;
        }

        ListNode* slow = head;
        ListNode* fast = head;

        // find center
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }

        // cut in the middle
        ListNode* secondHalf = slow->next;
        slow->next = NULL;

        // reverse second half
        ListNode* p = secondHalf;
        ListNode* reversedSecondHalf = NULL;
        while(p) {
            ListNode * current = p;
            p = p->next;
            
            current->next = reversedSecondHalf;
            reversedSecondHalf = current;
        }

        // compare two halves.
        // The middle node is present when n = 2k + 1.
        // It will be in the second half and will be skipped because of the condition (list1 && list2)
        ListNode* list1 = head;
        ListNode* list2 = reversedSecondHalf;
        while(list1 && list2) {
            if (list1->val != list2->val) {
                return false;
            }
            list1 = list1->next;
            list2 = list2->next;
        }
        return true;
    }
};

Tuesday, August 4, 2015

Lowest Common Ancestor of a Binary Search Tree #LeetCode

Problem Reference:
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Problem Statement:

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:

Binary tree traversal.

Termination case :
1). find LCA in left subtree
2). find LCA in right subtree
3). find LCA at current Node, (left + current, right + current, left + right)

Declare a struct Result to log searching result
struct Result {
bool isPFind;
bool isQFind;
}
or use a integer where bit is used to indicate whether node is found or not.

/**
 * 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) {
        result = NULL;
        find(root, p, q);
        return result;
    }

    unsigned find(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) {
            return 0;
        }
        unsigned left = find(root->left, p, q);
        unsigned current = 0 | (root == p ? 1 : 0 ) | (root == q ? 2 : 0);
        unsigned right = find(root->right, p, q);
        if (left == 3) {
            return 3;
        } else if (right == 3) {
            return 3;
        } else if ((left | current | right) == 3) {
            result = root;
            return 3;
        }
        return left | current | right;
    }

    TreeNode* result;
};

Delete Node in a Linked List #LeetCode

Problem Reference:
https://leetcode.com/problems/delete-node-in-a-linked-list/

Problem Statement:
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) {
        ListNode* next = node->next;
        node->val = next->val;
        node->next = next->next;
    }
};

Valid Anagram #LeetCode

Question Reference:
https://leetcode.com/problems/valid-anagram/

Question Statement:

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.

Solution:

Solution 1:
Get statistics map for each string and compare these two maps.

class Solution {
public:
    bool isAnagram(string s, string t) {
        std::unordered_map stats1 = getStats(s);
        std::unordered_map stats2 = getStats(t);
        if (stats1.size() != stats2.size()) {
            return false;
        }
        for (auto iter = stats1.begin(); iter != stats2.end(); iter++) {
            if (stats2.find(iter->first) == stats2.end() || stats2[iter->first] != iter->second) {
                return false;
            }
        }
        return true;
    }

    std::unordered_map getStats(string s) {
        std::unordered_map stats;
        for (char c : s) {
            if (stats.find(c) == stats.end()) {
                stats[c] = 1;
            } else {
                stats[c]++;
            }
        }
        return stats;
    }
};

Solution2:
Use an array to store statistics information.

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) {
            return false;
        }
        vector stats(256, 0);
        for (char c : s) {
            stats[c]++;
        }
        for (char c : t) {
            stats[c]--;
        }
        for (int i = 0; i < 256; i++) {
            if (stats[i] != 0) {
                return false;
            }
        }
        return true;
    }
};

Pascal's Triangle #LeetCode

Problem Reference:
https://leetcode.com/problems/pascals-triangle/

Problem Statement:

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

Solution:

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result;

        for (int i = 0; i <= numRows - 1; i++) {
            vector<int> current(i+1, 1);
            for (int j = 1; j < i; j++) {
                current[j] = result[i-1][j-1] + result[i-1][j];
            }
            result.push_back(current);
        }

        return result;
    }
};

Saturday, August 1, 2015

Sliding Window Maximum #LeetCode

https://leetcode.com/problems/sliding-window-maximum/

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Solution 1:

For each window, get maximum using a simple 1 by 1 comparison. O(k)
Total time complexity O(k) * N = O(kN).

class Solution {
public:
    // quick solution
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        int size = nums.size();
        if (size == 0)
          return result;
        for (int i = 0; i <= size - k; i++) {
            result.push_back(max(nums, i, i + k - 1));
        }
        return result;
        
    }
    
    int max(vector<int>& nums, int start, int end) {
        int max = nums[start];
        for (int i = start + 1; i <= end; i++) {
            if (nums[i] > max)
              max = nums[i];
        }
        return max;
    }
};

Solution 2:

Using a heap, for each window, remove 1 instance of the beginning element of previous window, and add 1 ending element or current window.
For each window, get maximum using 2 * O(log k)
Total time complexity 2 * O(log k) * N = O(logk * N).

class Solution {
public:
    // quick solution
    std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
        std::vector<int> result;
        int size = nums.size();
        if (size == 0)
          return result;

        // created an ordered std::map for numbers within window
        std::map<int, int> window;
        for (int i = 0; i < k; i++) {
            insertToMap(window, nums[i]);
        }
        result.push_back(window.rbegin()->first);

        int p = 0;
        while(p < size && p + k < size) {
            // update window
            popOffMap(window, nums[p]);
            insertToMap(window, nums[p+k]);
            
            // get the maximum within window
            result.push_back(window.rbegin()->first);

            p++;
        }
        return result;
        
    }
    
    void insertToMap(std::map<int, int>& map, int val) {
        if (map.find(val) != map.end())
          map[val] = map[val] + 1;
        else
          map[val] = 1;
    }

    void popOffMap(std::map<int, int>& map, int val) {
        if (map[val] == 1)
          map.erase(val);
        else
          map[val] = map[val] - 1;
    }
};