DEV Community: Jiayi Ouyang

day 13-14|Binary Tree Traversal | leetcode 144,145,94,107,199,637,429,515,116,104, 111,226, 101

Jiayi Ouyang — Tue, 30 Jul 2024 11:36:48 +0000

[!definition]
Binary Tree is a tree data structure(non-linear) in which each node can have at most two children which are referred to as the left child and right child.
The topmost node is called root, and the bottom-most nodes are called leaves.

Terminology of Binary Tree

Root: no incoming edge
Child: has incoming edge
Sibling: nodes having the same parent are sibling.
Degree of a node: number of children of a particular parent. range from 0 to 2
Internal/External nodes: leaf nodes are external nodes, non leaf nodes are internal nodes
height: number of edges to reach the root. height of root is 0.
level: number of nodes to reach the root. level of root is 0.

Types of Binary Tree On the basis of the completion of levels

1. Perfect Binary Tree 满二叉树

[!definition] A Binary tree is a Perfect Binary Tree in which all the internal nodes have two children and all leaf nodes are at the same level.

When depth is $k$, there are $2^{k}-1$ nodes

2. Complete Binary Tree 完全二叉树

[!definition] where all the levels are completely filled except possibly the last level and the last level has all keys as left as possible

[!info] ==heap is actual a complete binary tree== with guarantee on the orders between parents and children

[!tip] Perfect Binary Tree vs Complete Binary Tree:
A complete binary tree of height $h$ is a perfect binary tree up to height $h-1$, and in the last level element are stored in left to right order.

3. Balanced Binary Tree

[!definition] A binary tree is balanced if the height of the tree is O(Log n) where n is the number of nodes.
For Example, the AVL tree maintains O(Log n) height by making sure that the difference between the heights of the left and right subtrees is at most 1.
Red-Black trees maintain O(Log n) height by making sure that the number of Black nodes on every root to leaf paths is the same and that there are no adjacent red nodes.
Balanced Binary Search trees are performance-wise good as they provide O(log n) time for search, insert and delete.

Special Binary Trees

1. ==Binary Search Tree(BST)==

[!Definition] Binary Search Tree has the following properties:

the left subtree of a node contains only nodes with keys lesser than the node's key

the right subtree of a node contains only nodes with keys greater than the node's key

the left and right subtree must also be a binary search tree

2. AVL -- Balanced Search Tree

[!Definition] AVL tree is a self-balancing Binary Search Tree(BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

[!info] C++
map set multimap multiset are all implemented by Balanced Search Tree.
That's why their insertion/deletion's time complexity if $O(logn)$
Remember unordered_map unordered_set are implemented by hash table

Storage of Binary Tree

linked list

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

Array say the index of a node is i:
- the index of its left child is i * 2 + 1
- the index of its right child is i * 2 + 2

Traversal of Binary Tree

Depth-First Search(DFS)

Can be implemented in both Recursion or Iteration method

Preorder Traversal(cur-left-right)
Inorder Traversal(left-cur-right)
Postorder Traversal(left-right-cur) ### Breadth-First Search(BFS) Can only be implemented by iteration method
Level order Traversal

[!Tip]

Stack is a data structure for recursion, so we can write recursion from stack code

BFS is usually done by Queue, since FIFO

How to write recursion

1. Determine the parameters and return type

2. Determine the termination conditions

3. Determine the logic of single-level recursion.

DFS in Recursion

Parameter and return type: the parameters should be a pointer to a node and a reference of a vector that records the results
Termination condition: the passed-in node is nullptr
logic of single-level recursion: keep traversing on children nodes, while insert the cur->val at right order

144 Binary Tree Preorder Traversal

void traversal(TreeNode* root, vector<int>& vec)
{
    if(root == nullptr) return;
    vec.push_back(root->val);
    traversal(root->left, vec);
    traversal(root->right, vec);    
}


vector<int> preorderTraversal(TreeNode* root) {
    vector<int> vec;
    traversal(root, vec);
    return vec;
}

145 Binary Tree Postorder Traversal

void traversal(TreeNode* root, vector<int> & vec)
{
    if(root == nullptr) return;
    traversal(root->left, vec);
    traversal(root->right, vec);
    vec.push_back(root->val);
}

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> vec;
    traversal(root, vec);
    return vec;
}

94 Binary Tree Inorder Traversal

void traversal(TreeNode* root, vector<int>& vec)
{
    if(root == nullptr) return;
    traversal(root->left, vec);
    vec.push_back(root->val);
    traversal(root->right, vec);
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> vec;
    traversal(root, vec);
    return vec;
}

DFS in Iteration

Using Stack, FILO.

Preorder(cur-left-right)

[!important] Preorder does us a huge favor, since we are visiting the middle node first and we output it first, so we only need to push right and left children
we should operate in following order, so that the right child will be out of the stack later than the left:

st.push(root);
while(!st.empty())
{
    cur = st.top(); // get middle
    st.pop();
    vec.push_back(cur->val); // visit middle
    // .. insert cur->val to result
    if(right) push(right);   // right in deeper of stack
    if(left)  push(left);    // left in higher of the stack
}

Inorder(left-cur-right)

[!important] we are visiting middle first but can't output it, we have to push middle nodes in the stack and keep looking for the most left child:

cur = root;
while(cur != nullptr || !st.empty())
{
    if(cur) //push middle and visit left
    {
        st.push(cur); // push every left we find until hit the nullptr
        cur = cur->left;
    }
    else // reach the most left node in a branch
    {
        // pop out its parent, in this situation -- a middle
        // which is also previous left
        cur = st.top();
        st.pop();
        vec.push_back(cur->val); // record result
        cur = cur -> right; // look for the most left in the right branch
    }
}

Postorder(left-right-cur)

[!Tip]
Preorder(cur-left-right)
--reverse left and right--> (cur-right-left) --reverse all-->(left-right-cur)

st.push(root)
while(!st.empty())
{
    cur = st.top();
    st.pop();
    // vec.push...
    if(left) st.push(left);
    if(right) st.push(right);
}

reverse(vec...);

Iteration All-in-one

[!Tip] Push the visited but not dealt middle node to the stack and append an extra nullptr as an indicator

Inorder

st.push(root)
while(!st.empty())
{
    cur = st.top();
    st.pop();

    if(cur)
    {
        if(right) st.push(right); // right
        st.push(cur);             // middle
        st.push(nullptr);             // indicator of undealed middle
        if(left) st.push(left);   // left
    }
    else // meet indicator
    {
        cur = st.top(); // get acutual middle
        st.pop();

        vec.push_back(cur->val);
    }
}

Preorder

st.push(root)
while(!st.empty())
{
    cur = st.top();
    st.pop();

    if(cur)
    {
        if(right) st.push(right); // right
        if(left) st.push(left);   // left
        st.push(cur);             // middle
        st.push(nullptr);             // indicator of undealed middle
    }
    else // meet indicator
    {
        cur = st.top(); // get acutual middle
        st.pop();

        vec.push_back(cur->val);
    }
}

Postorder

st.push(root)
while(!st.empty())
{
    cur = st.top();
    st.pop();

    if(cur)
    {
        st.push(cur);             // middle
        st.push(nullptr);             // indicator of undealed middle
        if(right) st.push(right); // right
        if(left) st.push(left);   // left
    }
    else // meet indicator
    {
        cur = st.top(); // get acutual middle
        st.pop();

        vec.push_back(cur->val);
    }
}

BFS -- level order (lc102)

Iteration `queue`

vector<vector<int>> levelOrderBy(TreeNode* root) {

    queue<TreeNode*> que;
    vector<vector<int>> vec;
    if(root)    que.push(root);

    // tmp value defines outside of loop for once to avoid duplicated
    // construction and destruction
    int levelSize = 0;
    TreeNode* cur;

    while(!que.empty())
    {
        // at the start of each level, retrieve the size of it
        levelSize = que.size();
        vector<int> levelVec(levelSize);

        // get all the children of current level at left to right order
        for(int i = 0; i < levelSize; ++i)
        {
            cur = que.front();
            que.pop();
            levelVec[i] = cur->val; // record cur val
            if(cur->left)   que.push(cur->left); // push left
            if(cur->right)  que.push(cur->right);// push right
        }

        // append cur level's vals to finnal results
        vec.push_back(levelVec);
    }
    return vec;
}

Recursion

void traversal(TreeNode* node, vector<vector<int>>& vec, int depth)
{
    if(!node)   return;

    if(depth == vec.size())
    {
        vec.push_back(vector<int>());
    }

    vec[depth].push_back(node->val);

    traversal(node->left, vec, depth + 1);
    traversal(node->right, vec, depth + 1);
}

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> vec;
    traversal(root, vec, 0);
    return vec;
}

107 Binary Tree Level Order Traversal II

BFS + reverse vector at the end
or push each level vector to the front of vec.emplace(vec.begin(), move(levelVec));

199 Binary Tree Right Side View

imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

[!info] BFS + only record the most right of each level to the results
To optimize the number of times of finding the most right of each level, we push the children from right to the left, the first of each level 'front()' is the most right one

vector<int> rightSideView(TreeNode* root) {
    queue<TreeNode*> que;
    vector<int> vec;
    if(root)    que.push(root);
    while(!que.empty())
    {
        size_t levelSize = que.size();
        TreeNode* node = que.front();
        // the first of each level is the most right
        vec.emplace_back(node->val);
        while(levelSize-- > 0)
        {
            node = que.front();
            que.pop();
            // each level push right to left
            if(node->right) que.push(node->right);
            if(node->left) que.push(node->left);
        }
    }
    return vec;
}

637. Average of Levels in Binary Tree

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.

[!info] record sum and number of nodes for each level during recursion, and divide them in the end for calculating average

void traversal(TreeNode* node, vector<pair<double, size_t>>& res, int depth)
{
    if(!node)   return;
    if(depth == res.size())
        res.emplace_back(0, 0);

    res[depth].first += node->val;
    ++res[depth].second;

    traversal(node->left, res, depth + 1);
    traversal(node->right, res, depth + 1);
}

vector<double> averageOfLevels(TreeNode* root) {
    vector<pair<double, size_t>> info;
    traversal(root, info, 0);

    vector<double> res(info.size());
    for(int i = 0; i < info.size(); ++i)
    {
        res[i] = info[i].first / static_cast<double>(info[i].second);
    }
    return res;
}

429 N-ary Tree level Order Traversal

[info] BFS + just replace push left and right to push every valid children

vector<vector<int>> levelOrder(Node* root) {
    queue<Node*> que;
    vector<vector<int>> vec;
    if(root)    que.push(root);
    while(!que.empty())
    {
        size_t size = que.size();
        vector<int> levelVec(size);
        for(size_t i = 0; i < size; ++i)
        {
            Node* node = que.front();
            que.pop();
            levelVec[i] = node->val;
            for(auto& child : node->children)
            {
                if(child)
                    que.push(child);
            }
        }
        vec.emplace_back(move(levelVec));
    }
    return vec;
}

515 Find Largest Value in Each Tree Row

vector<int> largestValues(TreeNode* root) {
    queue<TreeNode*> que;
    vector<int> vec;
    if(root)    que.push(root);

    while(!que.empty())
    {
        size_t size = que.size();
        int maxValue = INT_MIN;

        for(size_t i = 0; i < size; ++i)
        {
            TreeNode* node = que.front();
            que.pop();
            maxValue = max(maxValue, node->val);
            if(node->left)  que.push(node->left);
            if(node->right)  que.push(node->right);
        }
        vec.emplace_back(maxValue);
    }
    return vec;
}

116 Populating Next Right Pointers in Each Node

[!info] Same question as 117. Populating Next Right Pointers in Each Node II
We don't care if the tree is perfect or not, we are breadth-first-searching anyway.

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.

[!tip] when iterating each level, after retrieving cur and pop it out, the new que->front() is our cur->next

Node* connect(Node* root) {
    queue<Node*> que;
    if(root)    que.push(root);
    while(!que.empty())
    {
        int sz = que.size();
        while(sz-- > 0)
        {
            Node* cur = que.front();
            que.pop();
            if(cur->left)   que.push(cur->left);
            if(cur->right)  que.push(cur->right);

            if(sz == 0)
                cur->next = nullptr;
            else
                cur->next = que.front();
        }
    }

    return root;
}

104 Maximum Depth of Binary Tree

root at depth 1, get the max depth

int maxDepth(TreeNode* root) {
    if(!node)   return 0;
    return max(maxDepth(node->left), maxDepth(node->right)) + 1;
}

111 Minimum Depth of Binary Tree

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children. So when we reach the first leave, return its depth.

Iteration

int minDepth(TreeNode* root) {
    queue<TreeNode*> que;
    if(root)    que.push(root);
    int depth = 0;
    while(!que.empty())
    {
        ++depth;
        size_t sz = que.size();
        while(sz-- > 0)
        {
            TreeNode* node = que.front();
            que.pop();

            if(!node->left && !node->right) return depth;
            if(node->left) que.push(node->left);
            if(node->right) que.push(node->right);
        }
    }

    return 0;
}

Recursion

int minDepth(TreeNode* root) {
    if(!root)   return 0; // this is a leave

    if(!root->left && root->right) // not leave
        return 1 + minDepth(root->right);

    if(root->left && !root->right)
        return 1 + minDepth(root->left);

    return 1 + min(minDepth(root->left),  minDepth(root->right));  

}

Operations on the BT

226 Invert Binary Tree

[!caution]
preordered and postordered traversal would both be fine, except the inordered. Since it will invert the left subtree first, then swap it to the right, then invert the right subtree
which leads to original left subtree inverted twice while the original right isn't inverted at all.

However, we can invert the left subtree(original right subtree) again after swap in the inordered traversal LOL.

void traversal(TreeNode* root)
{
    if(!root)   return;
    // preorder
    swap(root->left, root->right);
    traversal(root->left);
    traversal(root->right);

    // postorder
    swap(root->left, root->right);
    traversal(root->left);
    traversal(root->right);

    // inorder
    traversal(root->left);
    swap(root->left, root->right);
    traversal(root->left); // do the trick
}

TreeNode* invertTree(TreeNode* root) {
    traversal(root);
    return root;
}

101 Symmetric Tree

[!caution] it's not checking every two children of a node as above question, it only compares the left subtree and right subtree of the root.
Plus we are comparing:

the outside part: left->left to right->right

the inside part: left->right to right->left

bool compare(TreeNode* left, TreeNode* right)
{
    if(!left && !right)  return true;

    else if((left && !right) || (!left && right) 
            || (left->val != right->val)) 
        return false; 

    return compare(left->left, right->right) 
        && compare(left->right, right->left);
}

bool isSymmetric(TreeNode* root) {
    return compare(root->left, root->right);
}

Day10-11|Stack&Queue: leetcode 232, 225, 20, 1047,150,239, 347

Jiayi Ouyang — Sat, 27 Jul 2024 19:10:34 +0000

[!info] Container Adaptor
Stack and queue are not containers, they are container adapters, which can be implemented with different kinds of containers. They don't provide iterators.

232 Implement Queue using Stacks

class MyQueue {
public:

    MyQueue() {

    }
    
    void push(int x) {
        stIn.push(x);
    }

    int pop() {
        move();
        int top = stOut.top();
        stOut.pop();
        return top;
    }

    int peek() {
        move();
        return stOut.top();
    }

    bool empty() {
        return stIn.empty() && stOut.empty();
    }

private:
    void move()
    {
        if(stOut.empty())
        {
            while(stIn.size())
            {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
    }

private:
    stack<int> stIn;
    stack<int> stOut;

};

225 Implement Stack using Queues

class MyStack {
public:

    MyStack() {

    }

    void push(int x) {
        que.push(x);
    }

    int pop() {
        int size = que.size();
        while(size > 1)
        {
            que.push(que.front());
            que.pop();
            --size;
        }

        int top = que.front();
        que.pop();
        return top;

    }

    int top() {
        return que.back();
    }

    bool empty() {
        return que.empty();
    }

private:
    queue<int> que;
};

20 Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

bool isValid(string s) {
    stack<char> st;
    unordered_map<char, char> pairs =
    {
        {')', '('},
        {']', '['},
        {'}', '{'}
    };

    for(const char& c : s)
    {
        if(c == '(' || c == '[' || c == '{')
        {
            st.push(c);
        }    
        else if(!st.empty())
        {
            auto iter = pairs.find(c); 
            if(iter == pairs.end() ||  iter->second != st.top())
                return false;

            st.pop();
        }
        else
            return false;
    }
    return st.empty();
}`

1047 Remove all adjacent duplicates in string

A duplicate removal consists of choosing two adjacent and equal letters and removing them.
We repeatedly make duplicate removals on s until we no longer can.

Example 1
s = "abbaca"
output = "ca"
Example 2
s = "abbbaca"
output = "abaca"

string removeDuplicates(string s) {
    stack<char> st;
    for(const char& c : s)
    {
        if(!st.empty() && st.top() == c)
        {
            st.pop();
        }
        else
        {
            st.push(c);
        }            
    }

    string res(st.size(), 0);
    for(int i = st.size() - 1; i >= 0; --i)
    {
        res[i] = st.top();
        st.pop();
    }
    return res;
}

150 Evaluate Reverse Polish Notation

The operator precedes the two operands.

Example 2:
Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:
Input: tokens = ["10","6","9","3","+","-11","","/","","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5

int evalRPN(vector<string>& tokens) {
    stack<long long> st;
    for(const string& s : tokens)
    {
        // every time encounters a operator
        if(s == "+" || s == "-" || s == "*" || s == "/")
        {
            // pop out the two operands
            // be careful about the first retrieved value should be dividend
            // so the first poped one should be operand2
            long long operand2 = st.top();
            st.pop();
            long long operand1 = st.top();
            st.pop();

            // evaluation:
            long long res = 0;
            char operation = s[0];
            switch(operation)
            {
                case '+':
                    res = operand1 + operand2;
                    break;
                case '-':
                    res = operand1 - operand2;
                    break;
                case '*':
                    res = operand1 * operand2;
                    break;
                case '/':
                    res = operand1 / operand2;
                    break;
            }

            // push result back for further calculatoin
            st.push(res);
        }
        else
        {
            // stoll: string to long long
            // stoi: string to int
            st.push(stoll(s));
        }
    }
    return st.top();
}

Sliding Window

239 Sliding Window Maximum

You are given an array of integers 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.

Return the max sliding window.

[!info] Monotonic queue
We don't need record every number in the window, we just need to keep a monotonic decreasing queue, the biggest number is always at the front. It works as:

the window moves right and pop out a number from front:

if the popped number == the maximum in the window before, due to it's a monotonic decreasing array, the new front of the queue is the new maximum in the window before insertion of new value.

if the popped number != max before sliding, that means the max should not be popped out yet, the original max is still the max before insertion

Either way, we are pretty sure that the front() is the max after popping before inserting.

sliding windows push a new number to the back of the queue:

keep pop_back() until the back() is >= the new number

push(newNumber) >[!important] multiset can work as a monotonic queue >Since: >- when insert , it sorts automatically >- It allows duplicates as we need >- when erase(find(toBeErasedValue)), it sorts automatically >- we can easily retrieve smallest number rbegin() or smallest number begin()

Monotonic Queue implemented by `deque`

class MonotonicQueue
{
public:
    // implemented by deque, we assign front as pop end
    // back as insertion end
    deque<int> que;

    //          -------------- 
    // front  <- ..|..|..|..     <- back
    //          --------------

    // pop from the front
    // since we are not recording every value in the window
    // we only pop when the value == front()
    void pop(int value) {
        if (!que.empty() && value == que.front()) {
            que.pop_front();
        }
    }

    // insert to the back
    // keeps poping out back elements until 
    // the back value is greater than new value, then we push the new value
    // this way, we make sure it's monotonic
    void push(int value) {
        while (!que.empty() && value > que.back()) {
            que.pop_back();
        }
        que.push_back(value);
    }

    int front() {
        return que.front();
    }
};

vector<int> maxSlidingWindowByMyMonotonicQueue(vector<int>& nums, int k) {
    vector<int> res;
    MonotonicQueue que;
    for(int i = 0; i < nums.size(); ++i)
    {
        // before i reaches k, sliding window is not full
        // should not pop yet
         if(i >= k) 
            que.pop(nums[i - k]);

        // either windows is growing to size k
        // or move right
        // push either way
        que.push(nums[i]);

        // when window is full, starts output maximum
        if(i >= k - 1)
        {
            res.emplace_back(que.front());
        }
    }
    return res;
}

`multiset` as a monotonic queue

Since multiset just sorts automatically, we *insert every number in the sliding window to i*t. To achieve pop(), we find(toBeErasedValue) exactly where the number should be popped at, and erase(itr).

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

    multiset<int> monotonicQueue;
    vector<int> res;

    for(int i = 0; i < nums.size(); ++i)
    {
        if(i >= k)
            monotonicQueue.erase(st.find(nums[i - k]));
        monotonicQueue.insert(nums[i]);

        if(i >= k - 1)
            res.emplace_back(monotonicQueue.rbegin());
    }
    return res;
}

heap

Compare function for `priority_queue`

[!caution]

From the above source code, we can see, the compare func in heap is to check whether there should be a swap. So if it returns true, it means fails to meet condition, go swapping, so:

max-heap: should be passed with compare func that returns true if lhs < rhs

min-heap: should be passed with compare func that returns true if lhs > rhs

However, this is opposite for std::sort, if the compare function returns true, it means the order of lhs and rhs is correct, no need for swaption.

347 Top k frequent elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

 // we wanna min-heap, so pass greater comparation
class compareFrequencyPairs
{
public:
    bool operator()(const pair<int, int> & lhs, const pair<int, int> & rhs)
    {
        return lhs.second > rhs.second;
    }
};

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> frequencies;
    for(const int & i : nums)
    {
        ++frequencies[i];
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, compareFrequencyPairs> heap;
    for(auto& pair : frequencies)
    {
        heap.push(pair);
        if(heap.size() > k) // pop all the min and left with largest k pairs
            heap.pop();
    }

    vector<int> result(k);
    for (int i = k - 1; i >= 0; i--) {
        result[i] = heap.top().first;
        heap.pop();
    }
    return result;
}

day 8-9|String|leetcode 344, 541, kama 54,151,kama 55,28, 459

Jiayi Ouyang — Fri, 26 Jul 2024 15:13:32 +0000

344.Reverse String

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

void reverseString(vector<char>& s) {
    int i = 0, j = s.size() - 1;
    while(i < j)
    {
        swap(s[i++], s[j--]);
    }
}

541. Reverse String II

Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.

[!info] reverse(obj.begin() + left, obj.begin() + right) is coped with left-close and right-open rule

string reverseStr(string s, int k) {
    for(int i = 0; i < s.size(); i += 2 * k)
    {
        if(i + k > s.size())
        {
            reverse(s.begin() + i, s.end());
        }
        else
        {
            reverse(s.begin() + i, s.begin() + i + k);
        }            
    }
    return s;
}

Kama 54 Substitute numbers

Given a string s that contains lowercase alphabetic and numeric characters, write a function that leaves the alphabetic characters in the string unchanged and replaces each numeric character with "number". For example, for the input string “a1b2c3”, the function should convert it to “anumberbnumbercnumber”.

void substitudeNumbers(string& s)
{
    auto isNumber = [](const char& c)
    {
        return c >= '0' && c <= '9';
    };

    int count = 0;
    for(const char & c : s)
    {
        if(isNumber(c))
            ++count;
    }

    // expand s to desired length otherwise it have to expand everytime
    // we replace a numeric letter with string "number"
    int oriSize = s.size();
    int newSize = oriSize + count * 5;
    s.resize(newSize, ' ');

    int i = oriSize - 1, j = newSize - 1;
    while(i >= 0)
    {
        if(isNumber(s[i]))
        {
            s[j--] = 'r';
            s[j--] = 'e';
            s[j--] = 'b';
            s[j--] = 'm';
            s[j--] = 'u';
            s[j--] = 'n';
        }
        else
        {
            s[j--] = s[i];
        }
        --i;
    }
}

151 Reverse Words in a String

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

void removeExtraSpace(string& s)
{
    int slow = 0;
    for(int i = 0; i < s.size(); ++i)
    {
        if(s[i] == ' ')
            continue;

        if(slow != 0) s[slow++] = ' '; // add space between words
        while(i < s.size() && s[i] != ' ')
            s[slow++] = s[i++];
    }
    s.resize(slow);
}

string reverseWords(string s) {
    // 1. remove extra spaces
    removeExtraSpace(s);

    // 2. reverse whole string
    reverse(s.begin(), s.end());

    // 3. reverse each word
    int i = 0;
    const int len = s.size();
    while(i < len)
    {
        int j = i;
        while(j < len && s[j] != ' ')
            ++j;

        reverse(s.begin() + i, s.begin() + j);
        i = j + 1;
    }
    return s;
}

Kama 55 Rotate string to right

The right-rotation operation of a string involves shifting a number of characters from the end of the string to the front of the string. Given a string s and a positive integer k, write a function that implements the right-rotation operation on a string by shifting the trailing k characters to the front of the string.

For example, for the input string “abcdefg” and integer 2, the function should convert it to “fgabcde”.

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    string s;
    int n;
    cin >> n >> s;
    // reverse whole string
    reverse(s.begin(), s.end());
    // reverse front n substring
    reverse(s.begin(), s.begin() + n);
    // reverse the rest substring
    reverse(s.begin() + n, s.end());

    cout << s;
    return 0;
}

KMP

[!info] KMP is used in finding substrings with excellent performance O(M+N)

28 Find the Index of the First Occurrence in a String

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

[!Warning] next array
next is trying to mean that when string matching fails at index i, go testing at the previous index next[i]. next[i] records the length of the longest equal prefix and suffix in range of [0, i - 1].

Sample of getting next array
s = "aabaaf"
next[0] = 0;

// a a b a a f
// 0                s[i] == s[j]: ++j; next[1] = 1; ++i
// j i

// a a b a a f
// 0 1              while(j > 0 && s[j] != s[i]) j = next[j - 1] = 0; next[2] = 0; ++i
//   j i

// a a b a a f
// 0 1 0            s[j] == s[i]; ++j; next[3] = 1; ++i
// j     i

// a a b a a f
// 0 1 0 1          s[j] == s[i]; ++j; next[4] = 2; ++i
//   j     i

// a a b a a f
// 0 1 0 1 2        while(j > 0 && s[j] != s[i]) j = next[j - 1] = 0; next[5] = 0; ++i
//   j       i

// a a b a a f
// 0 1 0 1 2 0
[!Tip] strStr()
Comparing an array haystack to needle is quite same as the process of generating next array. Except that we are comparing haystack[i] to needle[j], where i would be steadily increasing by 1 each iteration, yet j goes backwards j = next[j - 1] when unmatching.

vector<int> getNext(const string& s)
{
    vector<int> next(s.size(), 0); // useful records when fails matching at 
                             // index i, it can keep comparing from next[i]

    // j is at the end of prefix
    // i is at the start of suffix
    for(int i = 1, j = 0; i < s.size(); ++i)
    {
        // prefix does not match with suffix, j goes backwards, prefix shrinks
        while(j > 0 && s[j] != s[i])
        {
            j = next[j - 1];
        }

        if(s[j] == s[i])
        {
            ++j;
        }
        next[i] = j;
    }
    return next;
}

int strStr(string haystack, string needle) {
    vector<int> next = getNext(needle);
    // matching process is quite same except that, `getNext` is comparing
    // needle with itself, now we are comparing needle with haystack
    for(int i = 0, j = 0; i < haystack.size(); ++i)
    {
        while(j > 0 && haystack[i] != needle[j])
        {
            j = next[j - 1];
        }

        if(haystack[i] == needle[j])
        {
            ++j;
        }

        if(j == needle.size())
            return i - j + 1;
    }
    return -1;
}

459 Repeated Substring Pattern

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

[!core]
if the string is repeated, suppose the substring with length n, so after first occurrence of the substring patter(range from 0 to n - 1), the values in next array should keep growing 1 by 1. Which means the last value of next is the length of total length of s minus one pattern. So we can easily get the length of repeated substring n = s.size() - next.back(). What's left is just to make sure s is actually repeating the pattern by s.size() % n == 0

For example:
 string s = "aabaabaab";
 string substring = "aab";
 // a a b a a b a a b
 // 0 1 0 1 2 3 4 5 6
 int totalLen = 9;
 int subStringLen = 9 - next.back() = 9 - 6 = 3;
 bool isRepeating = totalLen % subStringLen == 0;

bool repeatedSubstringPattern(string s) {
    int len = s.size();
    vector<int> next(s.size());
    next[0] = 0;
    for(int i = 1, j = 0; i < s.size(); ++i)
    {
        while(j > 0 && s[j] != s[i])
        {
            j = next[j - 1];
        }

        if(s[i] == s[j])
        {
            ++j;
        }
        next[i] = j;
    }
    return next.back() == 0 ? false : len % (len - next.back()) == 0;
}

day 6-7: hash table | leetcode 242, 383, 349,202, 1,454, 15, 18

Jiayi Ouyang — Thu, 25 Jul 2024 11:54:23 +0000

[!Info] A Hash table is defined as a data structure used to insert, look up, and remove key-value pairs quickly.
It operates on the hashing concept, where each key is translated by a hash function into a distinct index in an array. The index functions as a storage location for the matching value. In simple words, it maps the keys with the value.

When to use hash table

When we want to find out if an element appears before or whether an element exists in the set.

Load Factor

It is determined by:
1. number of elements are kept
2. size of the hash table.
When load factor is high: the table may be cluttered and have longer search times and collisions.

Collision resolution techniques:

It happens when two or more keys points to the same array index.

Open Addressing The hash function is applied to the subsequent slots until one is left empty. There are various ways to use this approach: double hashing, linear probing, and quadratic probing.
Separate Chaining: In separate chaining, a linked list of objects that hash to each slot in the hash table is present. Two keys are included in the linked list if they hash to the same slot. This method is rather simple to use and can manage several collisions.
Robin Hood hashing: To reduce the length of the chain, collisions in Robin Hood hashing are addressed by switching off keys. The algorithm compares the distance between the slot and the occupied slot of the two keys if a new key hashes to an already-occupied slot. The existing key gets swapped out with the new one if it is closer to its ideal slot. This brings the existing key closer to its ideal slot. This method has a tendency to cut down on collisions and average chain length.

Hashing in Data structure

array
set
map

`set` and `map` in C++

`set`

	Underlying Implementation	ordered	repeatable	modifiable	query efficiency	addition and deletions efficieny
std::set	Red–black tree	Ordered	No	No	O(log n)	O(log n)
std::multiset	Red–black tree	Ordered	Yes	No	O(log n)	O(log n)
std::unordered_set	Hash Table	Unordered	No	No	O(1)	O(1)

`map`

	Underlying Implementation	ordered	repeatable	modifiable	query efficiency	addition and deletions efficieny
std::map	Red–black tree	Ordered	No	No	O(log n)	O(log n)
std::multimap	Red–black tree	Ordered	Yes	No	O(log n)	O(log n)
std::unordered_map	Hash Table	Unorde	No	No	O(1)	O(1)

Array as Hash Table

[!Important] Only using array as hash table when keys' range is limited

242 Valid Anagram

Given two string s and t, return true if t is an anagram of s, and false otherwise.

the range of the hashes is just from a to z, which is quite small. So we define an array as a hash table, the value of each key is just the occurrence of each letter

bool isAnagram(string s, string t) {

    int record[26] = {0};
    // get occurrences of each letter in `s`
    for(char i : s)
    {
        ++record[i - 'a'];
    }

    // remove letters appeared in `t`
    for(char i : t)
    {
        if(--record[i - 'a'] < 0) // `t` use more of a specific letter than 
            return false;         // `s`, so they cann't be an anagram
    }

    for(int i : record)
    {
        if(i != 0) // `t` couldn't use all of the letters in `s`
            return false;
    }
    return true;
}

383. Ransom Note

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

[!Tip] please notice the range of key is limited to lowercase letters, so we can achieve the hash table with array to save space and time.

bool canConstruct(string ransomNote, string magazine) {
    int record[26] = {0};
    for(char c : magazine)
    {
        ++record[c - 'a'];
    }

    for(char c : ransomNote)
    {
        if(record[c - 'a'] <= 0)
            return false;
        --record[c - 'a'];
    }
    return true;
}

`unordered_set` and `unordered_map` as Hash Table

[!Tip] If the hashes are relatively small, particularly scattered, and span a very large area, using an array results in a huge waste of space.
We should be considering between unordered_set and unordered_map

349. Intersection of Two Arrays

Given two integer arrays num1 and num2, return an array of their intersection. Each element in the result must be unique and you may return in any order.

The range of values from the two arrays could be very large and scattered, while it requires the uniqueness, it only left us with unordered_set

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int> result;
    unordered_set<int> nums1Set(nums1.begin(), nums1.end());

    for(int i : nums2)
    {
        if(nums1Set.find(i) != nums1Set.end())
            result.emplace(i);
    }

    return vector<int>(result.begin(), result.end());
}

202 Happy Number

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

The question gives the tip that if a number is not happy, it will loop endlessly, so we just need to know if the sum appears before. so unordered_set records the sums along the calculations

int getSum(int n)
{
    int sum = 0;
    while(n)
    {
        sum += (n % 10) * (n % 10);
        n /= 10;
    }
    return sum;
}

bool isHappy(int n) 
{
    unordered_set<int> sums;
    int sum = getSum(n);
    while(sum != 1)
    {
        if(sums.find(sum) != sums.end())
        {
            return false;
        }
        sums.emplace(sum);
        sum = getSum(sum);
    }
    return true;
}

1 Tow Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

/*
* iterate the array, get the remain number of each element, if that number
* was in the array, return the pair
* Otherwise, record current element with its index for future returning.
*/
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;
    for(int i = 0; i < nums.size(); ++i)
    {
        if(auto itr = map.find(target - nums[i]); itr != map.end())
        {
            return {itr->second, i};
        }
        map.emplace(nums[i], i);
    }
    return {-1, -1};
}

454 4Sum II

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Steps

using an unordered_map records the sum from an element from nums1 and another from nums2 as key, and the occurrence of the sum as value
Iterating nums3 and nums4, find if 0 - nums3[i] - nums4[j] exists in the map.

int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    unordered_map<int, int> sum12;
    for(int i : nums1)
        for(int j : nums2)
            ++sum12[i+j];

    int count = 0;
    for(int i : nums3)
    {
        for(int j : nums4)
        {
            auto iter = sum12.find(0 - i - j);
            if(iter != sum12.end())
            {
                count += iter->second;
            }
        }
    }
    return count;
}

Hash alike questions

15 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

[!caution] It's easy to be mislead to use hash table to record the sum of first two numbers.
But the question requires unique triplets, which could cost checking duplication every time we find a new combination. As a result, we better solve this by dual pointers.

Since it doesn't require the indexes of the elements, we can sort the array firstly
we have i starts from 0 towards nums.size() - 3
1. make sure that nums[i] is different from nums[i-1] to prevent duplication
we have left = i+1; right = nums.size() - 1
Keeps testing if nums[i] + nums[left] + nums[right] == 0
1. if equals, that means we find a unique result, record it, then moves left and right till unidentical value
2. if greater than 0, --right
3. if lesser than 0, ++left

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());
    for(int i = 0; i < nums.size() - 2; ++i)
    {
        // remove duplication of i
        if(i > 0 && nums[i - 1]==nums[i])
            continue;

        int left = i + 1, right = nums.size() - 1;
        while(left < right)
        {
            int sum = nums[i] + nums[left] + nums[right];
            if(sum == 0)
            {
                res.push_back({nums[i], nums[left], nums[right]});
                // remove duplications of left and right
                while (right > left && nums[right] == nums[right - 1]) --right;
                while (right > left && nums[left] == nums[left + 1]) ++left;
                --right;
                ++left;
            }
            else if(sum < 0)
                ++left;
            else
                --right;
        }
    }
    return res;
}

18 4Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

[!Tip] Still use dual pointers as above one

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());

    // be careful size() return uint, should convert to int for minus
    int size = nums.size(); 
    for(int i = 0; i < size - 3; ++i)
    {
        // pruning
        if(nums[i] > target && target >= 0)
            break;
        // avoid duplication
        if(i > 0 && nums[i] == nums[i - 1])
            continue;
        for(int j = i + 1; j < size - 2; ++j)
        {
            // pruning
            if(nums[i] + nums[j] > target && target >= 0)
                break;
            // avoiding duplication
            if(j > i + 1 && nums[j] == nums[j - 1])
                continue;

            int left = j + 1, right = size - 1;
            while(left < right)
            {
                // sum may be out of int's range
                long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                if(sum == target)
                {
                    res.push_back({nums[i], nums[j], nums[left], nums[right]});
                    // avoiding duplication
                    while(left < right && nums[right] == nums[right - 1]) --right;
                    while(left < right && nums[left] == nums[left + 1]) ++left;
                    --right;
                    ++left;
                }
                else if(sum < target)
                    ++left;
                else
                    --right;
            }
        }
    }
    return res;
}

Day 3-4| Linked List: leetcode 203,706,206,24,19,02.07,142 in Cpp

Jiayi Ouyang — Fri, 19 Jul 2024 15:21:42 +0000

Linked List is a linear structure linked by pointers.

It consists of nodes where each node contains data and a reference (link) to the next node in the sequence.

This allows for dynamic memory allocation and efficient insertion and deletion operations compared to arrays.
The entry node of the list is head

Linked List Vs Arrays:

	Array	Linked List
Data Structure	Contiguous	Non-contiguous
Memory Allocation	Static	Dynamic
Insertion/Deletion	Inefficient O(n)	Efficient O(1)
Access	Random O(1)	Sequential O(n)
Scenario	data is constant, frequently access, rarely add/remove	data varies over time, frequently add/remove, rarely access

Types of Linked List:

Singly Linked List
Doubly Linked List
Circular Linked List

General Class Definition

struct ListNode
{
    int val; // data
    ListNode * next;
    ListNode(int x) : val(x), next(nullptr) {}
}

dummy head node

It's very helpful to declare a dummy head whose next points the head of original list.
In this way, we can handle the situation when deleting the original head, the dummyhead->next is always the actual head.

203 Remove Linked List Elements

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, return the new head

ListNode* removeElements(ListNode* head, int val) {
    ListNode* dummyHead = new ListNode(0, head);
    ListNode* cur = dummyHead;
    while(cur->next != nullptr)
    {
        if(cur->next->val == val)
        {
            ListNode* toRemove = cur->next;
            cur->next = cur->next->next;
            delete toRemove;
        }
        else
            cur = cur->next;
    }
    return dummyHead->next;
}

707 Design Linked List

Design your implementation of the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

MyLinkedList() Initializes the MyLinkedList object.
int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.
void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
void addAtTail(int val) Append a node of value val as the last element of the linked list.
void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

Singly Linked List

Using dummy head as a data member, please pay attention to initialization of cur:

when addAtIndex(index), we want to do cur->next = new .., suppose index = 0, the cur has to be dummyHead, so ListNode* cur = dummy

when get(index), we wanna return cur->value;, when index = 0, the cur has to be at true head, so ListNode* cur = dummyHead->next;

class MyLinkedList {
public:

    struct ListNode
    {
        int val;
        ListNode* next;
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode* nextNode) : val(x), next(nextNode) {}
    };

    MyLinkedList() : size(0) {
        dummyHead = new ListNode(0);
    }

    // index 0 refers to (dummyHead -> next)
    // so 0 <--> dummyHead->next
    int get(int index) {

        if(index > size - 1 || index < 0)    return -1;

        ListNode* cur =  dummyHead->next;
        while(index--)
        {
            cur = cur -> next;
        }
        return cur ? cur->val : -1;
    }

    void addAtHead(int val) {

        dummyHead->next = new ListNode(val, dummyHead->next);
        ++size;
    }

    void addAtTail(int val) {
        ListNode * cur = dummyHead;
        while(cur->next)
        {
            cur = cur->next;
        }
        cur->next = new ListNode(val);
        ++size;
    }

    // add at 0, cur has to be dummyHead to be able to assign the head
    // so 0 <--> dummyHead
    void addAtIndex(int index, int val) {
        if(index > size)    return;

        ListNode * cur = dummyHead;
        while(index--)
        {
            cur = cur->next;
        }
        ListNode* next = cur->next;
        cur->next = new ListNode(val, next);
        ++size;
    }

    // to delete at 0, cur has to be at dummyHead
    // so 0 <--> dummyHead
    void deleteAtIndex(int index) {

        if(index > size - 1 || index < 0)
            return;

        ListNode* cur = dummyHead;
        while(index--)
        {
            cur = cur -> next;
        }
        ListNode* next = cur->next;
        cur->next = next->next;
        --size;
        delete next;
    }

private:
    ListNode* dummyHead;
    int size;
};

Doubly Linked List

class MyLinkedList {
public:

    struct ListNode
    {
        int val;
        ListNode* next;
        ListNode* pre;
        ListNode(int x) : val(x), next(nullptr), pre(nullptr) {}
        ListNode(int x, ListNode* nextNode, ListNode* preNode) : val(x), next(nextNode), pre(preNode) {}
    };

    MyLinkedList() : size(0) {
        dummyHead = new ListNode(0);
    }

    // index 0 refers to (dummyHead -> next)
    // so 0 <--> dummyHead->next
    int get(int index) {
        if(index > size - 1 || index < 0)    return -1;
        ListNode* cur =  dummyHead->next;
        while(index--)
        {
            cur = cur -> next;
        }
        return cur ? cur->val : -1;
    }

    void addAtHead(int val) {
        ListNode* next = dummyHead->next;
        dummyHead->next = new ListNode(val, next, dummyHead);
        if(next)
            next->pre = dummyHead->next;
        ++size;
    }

    void addAtTail(int val) {
        ListNode * cur = dummyHead;
        while(cur->next)
        {
            cur = cur->next;
        }
        cur->next = new ListNode(val);
        cur->next->pre = cur;
        ++size;
    }

    // add at 0, cur has to be dummyHead to be able to assign the head
    // so 0 <--> dummyHead
    void addAtIndex(int index, int val) {
        if(index > size)    return;
        ListNode * cur = dummyHead;
        while(index--)
        {
            cur = cur->next;
        }
        ListNode* next = cur->next;
        cur->next = new ListNode(val, next, cur);
        if(next)
            next->pre = cur->next;
        ++size;
    }

    // to delete at 0, cur has to be at dummyHead
    // so 0 <--> dummyHead
    void deleteAtIndex(int index) {
        if(index > size - 1 || index < 0)
            return;
        ListNode* cur = dummyHead;
        while(index--)
        {
            cur = cur -> next;
        }
        ListNode* next = cur->next;
        cur->next = next->next;
        if(next->next)
        {
            next->next->pre = cur;
        }
        --size;
        delete next;
    }
private:
    ListNode* dummyHead;
    int size;
};

206 Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Method 1 dummy head

 ListNode* reverseList(ListNode* head) {
    ListNode* dummyHead = new ListNode(0);
    ListNode* cur = head;
    while(cur)
    {
        ListNode* newHead = cur;
        ListNode* newHeadNext = dummyHead->next;
        cur = cur->next;
        dummyHead->next = newHead;
        newHead->next = newHeadNext;
    }
    return dummyHead->next;
}

Method 2 Pre and Cur Pointer

Quite same as method 1
Reversing the linked list with new head moving from original head to tail

ListNode* reverseList(ListNode* head) {
    ListNode * pre = nullptr;
    ListNode * cur = head;
    ListNode * nextIter =  nullptr;
    while(cur)
    {
        nextIter = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nextIter;
    }
    return pre;
}

Method 3 recursion with same idea from method 2

ListNode* reverse(ListNode* pre,ListNode* cur){
    if(cur == NULL) return pre;
    ListNode* nextIter = cur->next;
    cur->next = pre;
    // same as method 2:
    // pre = cur;
    // cur = temp;
    return reverse(cur,temp);
}

ListNode* reverseList(ListNode* head)
{
    // same as method 2:
    // pre = nullptr
    // cur = head
    return reverse(nullptr, head);
}

Method 4 recursion from tail to head

Keeping looking for the tail which is the new head, returns for the first time,
head->next->next = nullptr because it's the new tail
Reversing the head and head->next

ListNode* reverseList(ListNode* head) {
    // finding tail which is new head
    if(head == NULL) return NULL;
    if (head->next == NULL) return head;
    ListNode *newHead = reverseList(head->next);

    // imagine you have the newhead, reverse the last second
    head->next->next = head;
    // 此时的 head 节点为尾节点，next 需要指向 NULL
    head->next = NULL;
    return newHead;
}

Simulation of the recursion

24 Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

ListNode* swapPairs(ListNode* head) {

    if(!head || !head->next)    return head;
    ListNode* dummyHead = new ListNode(0, head);

    ListNode * cur = dummyHead;
    ListNode* Swap1Node;
    ListNode* NextPair;

    while(cur->next && cur->next->next)
    {
        Swap1Node = cur->next;
        NextPair = cur->next->next->next;
        cur->next = cur->next->next; // Swap2Node
        cur->next->next = Swap1Node;
        cur->next->next->next = NextPair;
        cur = Swap1Node;
    }
    return dummyHead->next;

}

Dual Pointers Method in Linked List

19 Remove Nth Node From End of List -- fast and slow

Given the head of a linked list, remove the nth node from the end of the list and return its head.

ListNode* removeNthFromEnd(ListNode* head, int n) {

    ListNode* dummyHead = new ListNode(0, head);
    ListNode* slow = dummyHead;
    ListNode* fast = dummyHead;
    while(n-- > -1 && fast) // fast move one more, 
    {                       //since slow has to be front of the last-nth
        fast = fast->next;
    }

    while(fast) // when fast gets to the tail, slow is at the front of
    {           // the last n-th node
        fast = fast->next;
        slow = slow->next;
    }

    ListNode* tmp = slow->next;
    slow->next = tmp->next;
    delete tmp;

    return dummyHead->next;

}

02.07 Intersection of Two Linked Lists LCCI

Given two (singly) linked lists, determine if the two lists intersect. Return the intersecting node. Note that the intersection is defined based on reference, not value. That is, if the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then they are intersecting.

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

    // 1. get lengths of two lists
    int lenA = 0, lenB = 0;
    {
        ListNode* curA = headA;
        ListNode* curB = headB;
        while(curA)
        {
            ++lenA;
            curA = curA->next;
        }

        while(curB)
        {
            ++lenB;
            curB = curB->next;
        }
    }

    // 2. distinguish which list is longer
    ListNode* longer, * shorter;
    int diff = 0;
    if(lenA < lenB)
    {
        diff = lenB - lenA;
        longer = headB;
        shorter = headA;
    }
    else
    {
        diff = lenA - lenB;
        longer = headA;
        shorter = headB;
    }

    // 3. move longer pointer in the longer list, to make longer and shorter 
    // pointers at the same distance to tail
    while(diff-- && longer)
    {
        longer = longer->next;
    }

    // 4. move dual pointers together until they meet
    while(longer && shorter && longer != shorter)
    {
        longer = longer->next;
        shorter = shorter->next;
    }

    // 5. there might be no intersetion at all, so be careful when returning
    return longer == shorter ? longer : NULL;
}

142 Linked List Cycle II

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

Do not modify the linked list.

2 * (x + y) = x + n * (y + z) + y
x + y = n * (y + z)
x = (n - 1) * (y + z) + z // (y + z) is the length of circle.

ListNode *detectCycle(ListNode *head) {
    ListNode* fast = head, *slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow) // get to meeting point
        {
            break;
        }
    }

    if(!fast || !fast->next)    return NULL;

    fast = head;
    while(fast != slow) // x = z, so fast and slow will eventually meet at 
    {                   // the start of intersection
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

Algorithm -- Array

Jiayi Ouyang — Thu, 18 Jul 2024 10:12:36 +0000

An array is a collection of the same type of data stored on a contiguous memory space

Binary Search

leetcode 704
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

Preventing left + right is out of the range of int, so we have
int mid = left + ((right - left) / 2)

Left-closed and right-closed interval [left, right]

left == right is meaning, so while(left <= right)
Since right is valid index, if(midValue < target) right = mid - 1;

    while(left <= right)
    {
        int mid = left + ((right -left) >> 1);
        if(/*equal*/)
            return mid;
        else if(/*less*/)
            left = mid + 1;
        else // greater
            right = mid - 1;
    }
    return -1;

Left-closed, right-open Interval [left, right)

left == right is invalid, so while(left < right)
since right is invalid index, if(midValue < target) right = mid;

        if(/*equal*/)
            return mid;
        else if(/*less*/)
            left = mid + 1;
        else // greater
            right = mid;

Extension Questions

35 Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while(left <= right)
    {
        int mid = left + ((right - left) >> 1);
        cout << left << right << endl;
        if(nums[mid] == target)
            return mid;
        else if(nums[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    // now l > r, three situations:
    // [0, -1] -> 0
    // [x, x - 1] -> x
    // [arraySize, arraySize - 1]
    return left;

}

34 Find First and Last Position of Elements in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

vector<int> searchRange(vector<int>& nums, int target) {
    int leftBorder = getBorder(nums, target, true);
    int rightBorder = getBorder(nums, target, false);
    if(leftBorder == -2 || rightBorder == -2)   return {-1, -1};
    if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
    return {-1, -1};
}



/*
* -2 not set
*/

int getBorder(vector<int>& nums, int target, bool bLeftOrRight)
{
    int left = 0, right = nums.size() - 1;
    int border = -2; // not set
    while(left <= right)
    {
        int mid = left + ((right - left) >> 1);
        // cout << left << right << endl;
        if(!bLeftOrRight) // calc right border
        {
            if(nums[mid] > target)
                right = mid - 1;
            else // let left pointer move towards right border, so left move whenever nums[mid] <= target
            {
                left = mid + 1;
                border = left;
            }
        }

        else // calc for left border
        {
            if(nums[mid] < target)
                left = mid + 1;
            else // let right pointer move towards left border, so right move whenever nums[mid] >= target
            {
                right = mid - 1;
                border = right;
            }
        }
    }
    return border;
}

59 Spiral Matrix

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

Consider how to divide the intervals

4 loops for four sides of a square

each loop is limited to a left-close right-open interval, the last number letting the next loop handle it.

vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> res(n, vector<int>(n, 0)); // 2 dimension array
    int startx = 0, starty = 0; // start position of each loop
    int mid = n / 2; // center index
    int loop = n / 2; // number of loops, if n is odd, extra care at center
    int count = 1; // number to fill in
    int offset = 1; // limit the length of row and  columns
    int i,j;
    while (loop --) {
        i = startx;
        j = starty;
        auto setValueWithLog = [&res, &i, &j, &count]()
        {
            res[i][j] = count;
            cout << "Set(" << i << ", " << j << ") = " << count << endl;
            ++count;
        };

        // Left-closed (draw), right-open(not draw, next for loop will fill it for us)
        // left -> right
        for (; j < n - offset; j++)
            setValueWithLog();
        cout << endl;

        // up -> down
        for (; i < n - offset; i++)
            setValueWithLog();
        cout << endl;

        // right -> left
        for (; j > starty; j--)
            setValueWithLog();
        cout << endl;

        // down -> up
        for (; i > startx; i--)
            setValueWithLog();

        // one loop finished, update the start of next loop
        ++startx;
        ++starty;
        ++offset;
    }

    // if n is odd, extra care at the center
    if (n % 2) {
        res[mid][mid] = count;
    }
    return res;
}

Dual Pointer Method

A fast pointer and a slow pointer can do the work of two loops under one loop

Fast and Slow Pointers

27 Remove Element

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.

int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.size(); fast++) {
            if (val != nums[fast]) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }

Simulation:

f
3 2 2 3 `f++`
s

   f
3 2 2 3 `nums[f] != 3: nums[s++] = 2; f++`
s

    f
2 2 2  3 `nums[f] != 3; nums[s++] = 2; f++`
  s

      f
2 2 2 3 `f++`
    s

`return 2`

Front and Back Pointers

27 Remove Element

int removeElement(vector<int>& nums, int val) {
    int left = 0, right = nums.size() - 1;
    while(left <= right){
        if(nums[left] == val){
            nums[left] = nums[right];
            right--;
        }else {
            // 这里兼容了right指针指向的值与val相等的情况
            left++;
        }
    }
    return left;
}

Simulation:
      r
3 2 2 3  `nums[0] = nums[3] = 3`
l

    r
3 2 2 3 `nums[0] = nums[2] = 2`
l

   r
2 2 2 3
l

   r
2 2 2 3 `left == right: left++;`
   l

return ++1;

977 Square of sorted non-descending array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

vector<int> sortedSquares(vector<int>& nums) {
    int l = 0, r = nums.size() - 1;
    vector<int> res(r + 1);
    int arrayIndex = r;
    while(l <= r)
    {
        if(abs(nums[l]) >= abs(nums[r]))
        {
            res[arrayIndex--] = nums[l] * nums[l];
            ++l;
        }
        else
        {
            res[arrayIndex--] = nums[r] * nums[r];
            --r;
        }
    }
    return res;
}

Simulation:
1.
          r
-4 -1 0 3 10  `(-4)^2 < 10^2 : res[i--] = (10^2); r--`
l

2.             res:
        r    |       i     |
-4 -1 0 3 10 | _ _ _ _ 100 |`(-4)^2 > 3^2 : res[i--]=(-4)^2; l++`
l            |             |

3.             res:
        r    |     i        |
-4 -1 0 3 10 | _ _ _ 16 100 |`(-1)^2 < 3^2 : res[i--]=(3)^2; r--`
    l        |              |

4.             res
      r      |   i          |
-4 -1 0 3 10 | _ _ 9 16 100 |`(-1)^2 > 0^2 : res[i--]=(-1)^2; l++`
    l        |              |

5.             res
      r      | i            |
-4 -1 0 3 10 | _ 1 9 16 100 |`(0)^2 > 0^2 : res[i--]=(0)^2; l++`
      l      |              |

res:
0 1 9 16 100

Sliding Window

The so-called sliding window is a constant adjustment of the starting and ending positions of the subsequence to arrive at the result we want.

209 Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

int minSubArrayLen(int target, vector<int>& nums) {
    int l = 0, r = 0;
    int minLen = INT32_MAX;
    int sum = 0;
    while(r < nums.size())
    {
        sum += nums[r];
        while(l <= r && sum >= target)
        {
            if(minLen > (r - l) + 1)
                minLen = r - l + 1;
            sum -= nums[l++];
        }
        ++r;
    }
    return minLen == INT32_MAX ? 0 : minLen;
}

Simulation:
target = 7

r
2 3 1 2 4 3
l

      r
2 3 1 2 4 3 `sum = 8 > target: minlen = 4;`
l

DEV Community: Jiayi Ouyang

day 13-14|Binary Tree Traversal | leetcode 144,145,94,107,199,637,429,515,116,104, 111,226, 101

Terminology of Binary Tree

Types of Binary Tree On the basis of the completion of levels

Special Binary Trees

Storage of Binary Tree

Traversal of Binary Tree

Depth-First Search(DFS)

How to write recursion

1. Determine the parameters and return type

2. Determine the termination conditions

3. Determine the logic of single-level recursion.

DFS in Recursion

144 Binary Tree Preorder Traversal

145 Binary Tree Postorder Traversal

94 Binary Tree Inorder Traversal

DFS in Iteration

Preorder(cur-left-right)

Inorder(left-cur-right)

Postorder(left-right-cur)

Iteration All-in-one

Inorder

Preorder

Postorder

BFS -- level order (lc102)

Iteration queue

Recursion

107 Binary Tree Level Order Traversal II

199 Binary Tree Right Side View

637. Average of Levels in Binary Tree

429 N-ary Tree level Order Traversal

515 Find Largest Value in Each Tree Row

116 Populating Next Right Pointers in Each Node

104 Maximum Depth of Binary Tree

111 Minimum Depth of Binary Tree

Iteration

Recursion

Operations on the BT

226 Invert Binary Tree

101 Symmetric Tree

Day10-11|Stack&Queue: leetcode 232, 225, 20, 1047,150,239, 347

232 Implement Queue using Stacks

225 Implement Stack using Queues

20 Valid Parentheses

1047 Remove all adjacent duplicates in string

150 Evaluate Reverse Polish Notation

Sliding Window

239 Sliding Window Maximum

Monotonic Queue implemented by deque

multiset as a monotonic queue

heap

Compare function for priority_queue

347 Top k frequent elements

day 8-9|String|leetcode 344, 541, kama 54,151,kama 55,28, 459

344.Reverse String

541. Reverse String II

Kama 54 Substitute numbers

151 Reverse Words in a String

Kama 55 Rotate string to right

KMP

28 Find the Index of the First Occurrence in a String

Sample of getting next array

459 Repeated Substring Pattern

For example:

day 6-7: hash table | leetcode 242, 383, 349,202, 1,454, 15, 18

When to use hash table

Load Factor

Collision resolution techniques:

Hashing in Data structure

set and map in C++

set

map

Array as Hash Table

242 Valid Anagram

383. Ransom Note

unordered_set and unordered_map as Hash Table

349. Intersection of Two Arrays

202 Happy Number

1 Tow Sum

454 4Sum II

Iteration `queue`

Monotonic Queue implemented by `deque`

`multiset` as a monotonic queue

Compare function for `priority_queue`

Sample of getting `next` array

`set` and `map` in C++

`set`

`map`

`unordered_set` and `unordered_map` as Hash Table