All posts for the month May, 2023

Longest Inc


Given a vector of ints, find the max number, of which the ints keeps rising.
E.g 1 0 2 1 2 0 1 max is 3, as seen at index 1 3 4 we see 0 1 2.

I was trying to find which ones lead to the max. This is harder than what’s asked.
The focus should be the ending index of the max, and the max at this index depends on all before it.
A temp vector is needed to store the max at each index.
At each iteration, we figure out the max at index i based on the max-s before i.
Again, the solution doesn’t track where it starts and the middle ones; it only track the last element index.
Output from test data:

input: 2 1 3   
    endAt = 2, maxNum = 2
input: 1 0 2 1 2 0 1   
    endAt = 4, maxNum = 3

Download: http://riowing.net/p/wp/MaxNumRise.cpp

by Rio Wing on May 29, 2023  •  Permalink
Posted in algo

Posted by Rio Wing on May 29, 2023

https://riowingwp.wordpress.com/2023/05/29/longest-inc/

Graph


Graph is unweighted and directed.
Goals: 1. traverse the whole, 2. find shortest path for a certain node.
Ways: 1 DFS 2. BFS
Data structure: CNode { label and children }

GraphTraversalDFS (&stack, & bFound, &setVisited, &stackMin)
    all process happens beween push and pop.
    to traverse, setVisited so that code won't go into a loop.
        current is added so that stack keep the path from root to current. not used if not finding path
    to find shorest path: stackMin hold the smallest stack when the search is found.
        bFoundL might be just stackMin.size() != 0
GraphTraversalBFS(sPath, & bFound, &visited, &stackMin)
    to traverse, no recursion, just add all children to Q.
        all process after q.pop for simlilcity and consistency.
    to find shorest path: stackMin hold the shorest path from root to searched.
        queue< stack<CNode *> > Q: hold the nephew after my brothers are printed
        stack<CNode *> temp hold paths from root to me, and to be appended with each my child and push.

Download: http://riowing.net/p/wp/Graph2305.cpp

by Rio Wing on May 21, 2023  •  Permalink
Posted in algo
Tagged

Posted by Rio Wing on May 21, 2023

https://riowingwp.wordpress.com/2023/05/21/graph/

r-value reference


This is about function parameter type: T&&.
I will talk about it in the context of assignment operator T& operator =(T& vs T&&)

Why we need T&&: so that two versions of =: e.g. & to copy, && to move
&& version often destroys the object as expected

How to call the T&& version: two ways:

  1. pass it r-value, AKA temp or unnamed l-value, e.g. someVar = MyClass() or = MyFunc(), which is non-ref-type.
  2. pass it l-value with move: someVar = std::move(MyVar)

move semantics: is just one thing, and most common thing, that can be done by && version of the function.

by Rio Wing on May 14, 2023  •  Permalink
Posted in intermediate
Tagged ,

Posted by Rio Wing on May 14, 2023

https://riowingwp.wordpress.com/2023/05/14/r-value-reference/