Leetcode 2O24 June

[nuoxoxo]

• nuoxoxo/sea#1834

[nuoxoxo]

June

:date:	:clipboard:
30	1579. Remove Max Number of Edges to Keep Graph Fully Traversable	🔴
Graph Union find OOP - classic UnionFind
29	2192. All Ancestors of a Node in a Directed Acyclic Graph	🟡
Graph - classic Toposort - DFS done in cc

/*
[0,3],[0,4],
[1,3],
[2,4],[2,7],
[3,5],[3,6],[3,7],
[4,6]
- look at all 2nd-positions: 0, 1, 2 have no ancestors
- from (0,3) (1,3) we know 3 has two: 0, 1
- from (0,4) (2,4) we know 4 has two: 0, 2
- but these having direct ancestors are coincident
- for eg. 5 has 3 ancestors:
    - degree-1 ---> 3
    - degree-2 ---> 0,1
    - we can think this way: [5]--1-->[3](0,1) so 1+2
- 6 has 5 ancestors:
    - degree-1 ---> 3,4
    - degree-2 ---> 0,1,2
    - we can think this way:
        - [6]--1-->[3](0,1)
        - [6]--1-->[4](0,2) so a set(3,4,0,1,2)
- 7 has 4:
    - [7]--1-->[2]
    - [7]--1-->[3](0,1) so a set(2,3,0,1)
*/
#define vi vector<int>
#define si set<int>

// for each child of someone, save its direct parent
vector<vi> ADJ(n, vi{});
for (auto e : E)
{
    int src = e[0], des = e[1];
    ADJ[ des ].push_back( src );
}

// def. DFS
std::function<void(int, si &, si &)> DFS;
DFS = [&](int node, si & SEEN, si & path){
    if (SEEN.find(node) == end(SEEN))
    {
        SEEN.insert(node);
        path.insert(node);
        for (int next: ADJ[node])
        {
            if (SEEN.find(next) == end(SEEN))
                DFS(next, SEEN, path);
        }
    }
};

// DFS - get to the bottom of each nodev ~ [0,n-1]
int node = -1;
vector<vi> res;
while (++node < n)
{
    si SEEN;
    si parents;
    for (int parent : ADJ[node])
    {
        if (SEEN.find(parent) == end(SEEN))
            DFS(parent, SEEN, parents);
    }
    res.push_back(vector<int>(begin(parents), end(parents)));
}
return res;

:date:	:clipboard:
28	2285. Maximum Total Importance of Roads	🟡
greedy + sorting
27	1791. Find Center of Star Graph	🟢
Graph - common sense soln
26	1382. Balance a Binary Search Tree
todo
25	1038. Binary Search Tree to Greater Sum Tree
todo
24	995. Minimum Number of K Consecutive Bit Flips	🔴
Greedy Sliding window w/ Deque
23	1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit	🟡
Sliding window w/ SortedList
22	1248. Count Number of Nice Subarrays	🟡
Sliding window using deque
21	1052. Grumpy Bookstore Owner	🟡
fun - sliding window or running sum
20	1552. Magnetic Force Between Two Balls	🟡
Binary search
19	1482. Minimum Number of Days to Make m Bouquets	🟡
Binary search
18	826. Most Profit Assigning Work	🟡
greedy
17	633. Sum of Square Numbers	🟡
2 ways: complement set like DP - Two pointers / BS
16	330. Patching Array	🔴
Greedy
15	502. IPO	🔴
Greedy heapq
14	945. Minimum Increment to Make Array Unique	🟡
13	2037. Minimum Number of Moves to Seat Everyone	🟢
12	75. Sort Colors	🟡🟢
11	1122. Relative Sort Array	🟢
89. Gray Code 🆕	🟡
bitwise - from ready set boole
10	1051. Height Checker	🟢
9	974. Subarray Sums Divisible by K	🟡
Prefix Sum Math
560. Subarray Sum Equals K 🆕	🟡
Prefix Sum Math

// Subarray Sum Equals K

/*
a subarr can be expressed this way

-> a0 + a1 + a2 + ... + a[i - 1] + ai + ... + aj
->                                 ^^^^^^^^^^^^^ = f(j) - f(i - 1)

This is because in terms of line segment
-> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ = f(j)
-> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ = f(i - 1)

Conclusion
a subarr sums to k IF :
-> f(j) - f(i - 1) === k, ... from which we can have
-> f(j) - k === f(i - 1) ... this is what we want
-> so, keeping track of DICT[f(j) - k] == counting how many such subarrays
*/

// Subarray Sums Divisible by K

/*
a subarr sums 'divisible by k' IF :
-> (f(j) - f(i - 1)) === 0
-> f(j) % k === f(i - 1) % k ... this is what we want
-> so, keeping track of DICT[f(j) - k] == counting how many such subarrays
*/

:date:	:card_index:
8	523. Continuous Subarray Sum	🟡
- set - logic: Prefix Sum
7	648. Replace Words	🟡
trie
6	846. Hand of Straights	🟡
- idea: sorted dict keys
5	1002. Find Common Characters	🟢
4	409. Longest Palindrome	🟡
2131. Longest Palindrome by Concatenating Two Letter Words 🆕	🟡
- really weird : map works but unordered_map does not
- might come back later on this
3	2486. Append Characters to String to Make Subsequence	🟡
2	344. Reverse String	🟢
1	3110. Score of a String	🟢

Solution array and embedded func

  ```cc // cc std::function recurse = [&](TreeNode * node, long long res [2]) ``` ```go // Go func solver(s string, t string) int { solutions := []func(string, string) int { solve, } return solutions[0](s, t) } func Solver(s, t string) int { var recurse func(int, int) int recurse = func(is, it int) int { /* */ } } ``` ```c // C typedef int (* solution)(char *, char *); int recurse (char *, char *); int Solver(char* s, char* t) { solution Solutions[] = { recurse, }; return Solutions[0](s, t); } ``` ```rb // scala def Solver(s: String, t: String): Int = { val solutions: List [(String, String) => Int] = List ( recurse, ) solutions.head(s, t) } def recurse (s: String, t: String): Int = { /* */ } ```