Wednesday, May 20, 2020

297. Serialize and Deserialize Binary Tree

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

There may be two perspectives to serialize/deserialize a tree: 1). show the clear range/boundary of each section (left, mid, right), 2). keep the details and small hints of the traversal during serialization.

Using option 1: show the clear range/boundary of each section

IMO, this is the macro-way to resolve this problem. For example, 
   1
  /  \
2     3

We can log the level(depth) information as indicator of the structure. e.g. "(2) 1 (3)". During serialization, the range of each subtree can be kept.
  • Pros: of this approach is it applies to all of pre-order, in-order and post-order serialization.
  • Cons: needs more data to log range information, and requires look-back during deserialization.


Using option 2: keep details of traversal

With this option, it is unlikely that a human can know the structure of the tree clearly through a glance of the serialized data. However, the algorithm itself should be smart enough to reconstruct the tree piece by piece.

If using pre-order, we can serialize like this. "2,up,1,right,left,4,up,3,down,5,up,up"

If using in-order, we can serialize like this. "1,2,null,null,3,null,null". Although the range is not straightforward itself, the traversal will reveal the boundary by checking the end (leaf node)  of each subtree.

  • Pros: with careful design, save the size of serialized data. 
  • Cons: need further caution to avoid ambiguity in interpreting data especially for similar but different subtree, or whether it goes to parent node or sibling node.

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).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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).

 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
40
41
42
43
44
45
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;
    }
};