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.

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; } };

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;
    }
};

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; } };