# Differences

This shows you the differences between two versions of the page.

Both sides previous revision Previous revision Next revision | Previous revision | ||

algorithm_problems [2020/10/10 07:14] 127.0.0.1 external edit |
algorithm_problems [2020/10/19 19:58] (current) |
||
---|---|---|---|

Line 18: | Line 18: | ||

===== Top K Frequent Words ===== | ===== Top K Frequent Words ===== | ||

[[https:// | [[https:// | ||

+ | |||

**Given a non-empty list of words, return the k most frequent elements. | **Given a non-empty list of words, return the k most frequent elements. | ||

Line 2807: | Line 2808: | ||

return ans; | return ans; | ||

} | } | ||

+ | </ | ||

+ | |||

+ | ===== Minimum Window Substring ===== | ||

+ | [[https:// | ||

+ | |||

+ | **Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity '' | ||

+ | |||

+ | You can solve this problem not in '' | ||

+ | |||

+ | You keep a running '' | ||

+ | |||

+ | **Algorithm: | ||

+ | <code pseudo [enable_line_numbers=" | ||

+ | build a map called dic of letters and count of the t string | ||

+ | |||

+ | min_size = 0 | ||

+ | start = 0; | ||

+ | |||

+ | factor is the number of unique characters of atleast a count | ||

+ | factor = size of dict | ||

+ | |||

+ | pointer left = 0, right = -1 | ||

+ | while right is less than length - 1 | ||

+ | | ||

+ | advanced the right and add it | ||

+ | | ||

+ | while window valid // while factors are equal | ||

+ | check if min_size is 0 or greater than right - left + 1 | ||

+ | start = left | ||

+ | update min_size | ||

+ | advance the left | ||

+ | | ||

+ | if min_size == 0, return "" | ||

+ | return s.sub(start, | ||

+ | | ||

+ | | ||

+ | add a character: | ||

+ | if char isn't in dic return | ||

+ | window[char]++ | ||

+ | if window[char] == dic[char] | ||

+ | factor++ | ||

+ | | ||

+ | remove a char: | ||

+ | if char isn't in dic return | ||

+ | window[char]-- | ||

+ | if window[char] == dic[char] - 1 | ||

+ | factor-- | ||

+ | </ | ||

+ | |||

+ | **Code** | ||

+ | |||

+ | <code cpp [enable_line_numbers=" | ||

+ | class Solution { | ||

+ | public: | ||

+ | unordered_map< | ||

+ | int factor; | ||

+ | | ||

+ | void addChar(char c){ | ||

+ | if(dict.count(c) == 0){ | ||

+ | return; | ||

+ | } | ||

+ | window[c]++; | ||

+ | if(dict[c] == window[c]){ | ||

+ | factor++; | ||

+ | } | ||

+ | } | ||

+ | | ||

+ | void removeChar(char c){ | ||

+ | if(window.count(c) == 0){ | ||

+ | return; | ||

+ | } | ||

+ | window[c]--; | ||

+ | if(dict[c] - 1 == window[c]){ | ||

+ | factor--; | ||

+ | } | ||

+ | } | ||

+ | | ||

+ | string minWindow(string s, string t) { | ||

+ | if(t.length() == 0 || s.length() == 0){ | ||

+ | return ""; | ||

+ | } | ||

+ | |||

+ | for(auto& | ||

+ | dict[c]++; | ||

+ | } | ||

+ | |||

+ | factor = 0; | ||

+ | int start = 0, min_size = 0; | ||

+ | int left = 0, right = -1; | ||

+ | |||

+ | while(right < (int)s.length() - 1){ | ||

+ | //advance right | ||

+ | right++; | ||

+ | addChar(s[right]); | ||

+ | |||

+ | while(factor == dict.size()){ | ||

+ | int win_size = right - left + 1; | ||

+ | if(win_size < min_size || min_size == 0){ | ||

+ | start = left; | ||

+ | min_size = win_size; | ||

+ | } | ||

+ | removeChar(s[left]); | ||

+ | left++; | ||

+ | } | ||

+ | } | ||

+ | return (min_size == 0) ? "" | ||

+ | } | ||

+ | }; | ||

</ | </ | ||

Line 2883: | Line 2992: | ||

} | } | ||

return out; | return out; | ||

+ | } | ||

+ | </ | ||

+ | |||

+ | |||

+ | ===== Longest Palindromic Substring ===== | ||

+ | |||

+ | [[https:// | ||

+ | |||

+ | **Given a string '' | ||

+ | |||

+ | This is an '' | ||

+ | '' | ||

+ | |||

+ | {{: | ||

+ | |||

+ | You solve this by doing the following: | ||

+ | |||

+ | - Iterate through each character in the string | ||

+ | - For every character try middle out from that character | ||

+ | - For every character assume prev character is the same and middle out it | ||

+ | |||

+ | I fell in a bit of a pitfall with this problem when coding the middle out | ||

+ | palindrome checker. I kept getting tripped up on what the set the condition of | ||

+ | the while loop. I kept getting off by one and had a hard time coming down with a | ||

+ | case that didn't give me off by one. Should I check for the current case and | ||

+ | then increment the pointers and invalidate them? What about the initial case? | ||

+ | |||

+ | If yes, then simply subtract one from the output! The assumption that I needed | ||

+ | to grasp is that is we check to see if the current case is valid, and we | ||

+ | increment, we will always have a result that is one bigger. Which is fine, just | ||

+ | need to correct for it. | ||

+ | |||

+ | **Algorithm: | ||

+ | |||

+ | <code psuedo [enable_line_numbers=" | ||

+ | int isPali(string, | ||

+ | while char at left and char at right are the same and left and right are in bounds | ||

+ | move left left and right right | ||

+ | return out with left pointer + 1, and count with r - l + 1 | ||

+ | |||

+ | struct POD start len | ||

+ | for every letter | ||

+ | single = isPali(index index) | ||

+ | double = isPali(index - 1, index) | ||

+ | pick the bigger one and max against global | ||

+ | | ||

+ | return substring | ||

+ | </ | ||

+ | |||

+ | **Code:** | ||

+ | |||

+ | <code cpp [enable_line_numbers=" | ||

+ | struct Out{ | ||

+ | int index; | ||

+ | int len; | ||

+ | Out(int i = 0, int l = 0){ | ||

+ | index = i; | ||

+ | len = l; | ||

+ | } | ||

+ | }; | ||

+ | |||

+ | Out pal(string& | ||

+ | // while inbounds and same char | ||

+ | while(l >= 0 && r < s.length() && s[l] == s[r]){ | ||

+ | l--; | ||

+ | r++; | ||

+ | } | ||

+ | // Shift back the start pointer because it's gonna be off by one | ||

+ | // r will be off by one to the right, so subtract r from l and then dec 1 | ||

+ | return Out(l + 1, r - l - 1); | ||

+ | } | ||

+ | |||

+ | string longestPalindrome(string s) { | ||

+ | // first is index, second is len | ||

+ | Out max; | ||

+ | |||

+ | // first pass single char mid out | ||

+ | for(int i = 0; i < s.length(); i++){ | ||

+ | |||

+ | // Single character check | ||

+ | Out cur1 = pal(s, i, i); | ||

+ | // Double character check | ||

+ | Out cur2 = pal(s, i-1, i); | ||

+ | // Pick the biggest one | ||

+ | Out cur = (cur1.len > cur2.len) ? cur1 : cur2; | ||

+ | max = (max.len > cur.len) ? max : cur; | ||

+ | } | ||

+ | return s.substr(max.index, | ||

} | } | ||

</ | </ | ||

Line 2964: | Line 3161: | ||

} | } | ||

</ | </ | ||

- | |||

- | ===== Longest Palindromic String ===== | ||

- | |||

- | Tricky son-of-a-gun. Easiest way is to brute force, and check if every possible substring is a palindrome. | ||

- | |||

- | Next best thing is '' | ||

- | |||

- | {{: | ||

===== Palindrome Pairs ===== | ===== Palindrome Pairs ===== | ||

Line 4302: | Line 4491: | ||

} | } | ||

return true; | return true; | ||

+ | } | ||

+ | </ | ||

+ | |||

+ | ===== Open the Lock ===== | ||

+ | [[https:// | ||

+ | |||

+ | **You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: | ||

+ | '' | ||

+ | and wrap around: for example we can turn 9 to be 0, or 0 to be 9' Each | ||

+ | move consists of turning one wheel one slot. | ||

+ | |||

+ | The lock initially starts at '' | ||

+ | wheels. | ||

+ | |||

+ | You are given a list of deadends dead ends, meaning if the lock displays any of | ||

+ | these codes, the wheels of the lock will stop turning and you will be unable to | ||

+ | open it. | ||

+ | |||

+ | Given a target representing the value of the wheels that will unlock the lock, | ||

+ | return the minimum total number of turns required to open the lock, or -1 if it | ||

+ | is impossible.** | ||

+ | |||

+ | This is a really interesting problem that I thought was a backtracking problem | ||

+ | at first. It is a graph problem. Each string has 8 neighbors and you have to | ||

+ | make the mental connection that for every turn you can only change one digit at | ||

+ | a time. You also need to realize that a BFS is the way to go here, because we | ||

+ | are looking for one target, and if you do DFS you'll be digging into every path. | ||

+ | |||

+ | Standard BFS techniques apply. I got a litle tripped up with implementing a | ||

+ | seperator based system for the queue instead of keeping track of layer size. | ||

+ | |||

+ | Also for keeping track of turns you have to realize that every layer is a turn. | ||

+ | |||

+ | **Algorithm: | ||

+ | |||

+ | <code pseudo [enable_line_numbers=" | ||

+ | Build a set of deadends and a seen set | ||

+ | Create a queuefor BFS. For less code, you keep a count for the layer | ||

+ | |||

+ | add ' | ||

+ | |||

+ | while the queue isn't empty | ||

+ | increment a turn count | ||

+ | iterate the number of the size of the queue | ||

+ | pop off the top element | ||

+ | if the element is our target, we're good | ||

+ | if the element isn't a dead or seen | ||

+ | add it to seen | ||

+ | add each of its neighbors the queue | ||

+ | | ||

+ | return -1 if we get out | ||

+ | </ | ||

+ | |||

+ | **Code:** | ||

+ | |||

+ | <code cpp [enable_line_numbers=" | ||

+ | int openLock(vector< | ||

+ | unordered_set< | ||

+ | |||

+ | queue< | ||

+ | q.push(" | ||

+ | |||

+ | int turns = 0; | ||

+ | |||

+ | while(!q.empty()){ | ||

+ | int layer = q.size(); | ||

+ | while(layer--){ | ||

+ | string cur = q.front(); | ||

+ | q.pop(); | ||

+ | if(cur == target){ | ||

+ | return turns; | ||

+ | } | ||

+ | if(d.count(cur) == 0 && seen.count(cur) == 0){ | ||

+ | // Push in our cur to seen | ||

+ | seen.insert(cur); | ||

+ | for(int d = -1; d < 2; d+=2){ | ||

+ | for(int i = 0; i < 4; i++){ | ||

+ | // generate 8 strings that are increments and decrements | ||

+ | string n = cur; | ||

+ | n[i] += d; | ||

+ | n[i] = (n[i] > ' | ||

+ | q.push(n); | ||

+ | } | ||

+ | } | ||

+ | } | ||

+ | } | ||

+ | // We are done with a layer so increment the code | ||

+ | turns++; | ||

+ | } | ||

+ | return -1; | ||

} | } | ||

</ | </ | ||

Line 4459: | Line 4738: | ||

===== Merge k Sorted Lists ===== | ===== Merge k Sorted Lists ===== | ||

- | [[https:// | + | [[https://. |

+ | | ||

+ | **You are given an array of k linked-lists lists, each linked-list is sorted in | ||

+ | ascending order. | ||

+ | | ||

+ | Merge all the linked-lists into one sorted linked-list and return it.** | ||

Very nice little problem. Many ways to solve but here's the nice optimized way. | Very nice little problem. Many ways to solve but here's the nice optimized way. | ||

Line 4523: | Line 4807: | ||

return dh.next; | return dh.next; | ||

+ | } | ||

+ | </ | ||

+ | |||

+ | ===== Sort List ===== | ||

+ | |||

+ | [[https:// | ||

+ | |||

+ | **Given the head of a linked list, return the list after sorting it in ascending order.** | ||

+ | |||

+ | This problem is easily solved by using ordered containers giving you '' | ||

+ | n)'' | ||

+ | |||

+ | You can get '' | ||

+ | merge sort is to use a fast and slow pointer to find the middle of the list. | ||

+ | |||

+ | We do this recursively and our base case is a '' | ||

+ | |||

+ | **Algorithm: | ||

+ | |||

+ | <code psuedo [enable_line_numbers=" | ||

+ | Merge sort | ||

+ | divide the list in two | ||

+ | mergesort left list | ||

+ | mergesort right list | ||

+ | merge left and right | ||

+ | </ | ||

+ | |||

+ | **Code:** | ||

+ | |||

+ | <code cpp [enable_line_numbers=" | ||

+ | ListNode* mergeSort(ListNode* node){ | ||

+ | // If we're a null node | ||

+ | if(node == NULL){ | ||

+ | return NULL; | ||

+ | } | ||

+ | // If we're a single node | ||

+ | if(node-> | ||

+ | return node; | ||

+ | } | ||

+ | |||

+ | // find the middle with fast and slow pointer | ||

+ | ListNode *fast = node, *slow = node, *slowPrev = NULL; | ||

+ | while(fast && fast-> | ||

+ | slowPrev = slow; | ||

+ | slow = slow-> | ||

+ | fast = fast-> | ||

+ | } | ||

+ | // break the lists in two | ||

+ | if(slowPrev){ | ||

+ | slowPrev-> | ||

+ | } | ||

+ | |||

+ | // Node is gonna be head of left list, | ||

+ | // slow is head of right list | ||

+ | ListNode* left = mergeSort(node); | ||

+ | ListNode* right = mergeSort(slow); | ||

+ | |||

+ | // Merge two sorted lists: | ||

+ | ListNode dh, *cur; | ||

+ | cur = &dh; | ||

+ | |||

+ | while(left && right){ | ||

+ | // find the smallest of the two | ||

+ | |||

+ | if(left-> | ||

+ | // left has the smaller value | ||

+ | cur-> | ||

+ | left = left-> | ||

+ | }else{ | ||

+ | // right has the smaller value | ||

+ | cur-> | ||

+ | right = right-> | ||

+ | } | ||

+ | cur = cur-> | ||

+ | } | ||

+ | |||

+ | // Take care of any remaining nodes | ||

+ | if(left){ | ||

+ | cur-> | ||

+ | } | ||

+ | else if(right){ | ||

+ | cur-> | ||

+ | } | ||

+ | |||

+ | return dh.next; | ||

+ | } | ||

+ | |||

+ | ListNode* sortList(ListNode* head) { | ||

+ | return mergeSort(head); | ||

} | } | ||

</ | </ | ||

Line 4580: | Line 4953: | ||

} | } | ||

}; | }; | ||

+ | </ | ||

+ | |||

+ | ===== Word Ladder II ===== | ||

+ | [[https:// | ||

+ | |||

+ | **Given two words (beginWord and endWord), and a dictionary' | ||

+ | shortest transformation sequence(s) from beginWord to endWord, such that: | ||

+ | |||

+ | - Only one letter can be changed at a time | ||

+ | - Each transformed word must exist in the word list. Note that beginWord is not a transformed word. ** | ||

+ | |||

+ | I learned some new concepts with this problem. Particularly how to store a trace | ||

+ | of a path when doing BFS. | ||

+ | |||

+ | This problem breaks down in first identifying that this is a graph problem. We | ||

+ | have a bunch of vertices that are one edit distance away. We then have to find | ||

+ | the SHORTEST paths to the end. | ||

+ | |||

+ | If we needed to find all paths, an exhaustive DFS would work. But in this case | ||

+ | we need all shortest paths. This means if we do a BFS, all the shortest paths | ||

+ | will be on one layer. | ||

+ | |||

+ | At first I built a graph represented by an adjacency list, which was | ||

+ | '' | ||

+ | '' | ||

+ | a map of word combinations of each letter removed, requiring | ||

+ | '' | ||

+ | |||

+ | The other tricky part is the handling seen words. I handled it by removing words | ||

+ | in the wordset that we used on this level. | ||

+ | |||

+ | **Algorithm: | ||

+ | |||

+ | <code psuedo [enable_line_numbers=" | ||

+ | Create a wordList set to give us O(1) lookup in the words | ||

+ | Create a queue of string paths | ||

+ | Create a bool flag called done and set to false | ||

+ | Create an output list of strings | ||

+ | Add in the begin word in the queue as the seed path. | ||

+ | |||

+ | While we're not done and q isn't empty: | ||

+ | Grab the level size | ||

+ | While levesize-- | ||

+ | get the path in the front of the q and pop it | ||

+ | If the path is the end word | ||

+ | add the path to the output list and set done to true | ||

+ | add all the neighbors of this word to the base path | ||

+ | push these new paths to the queue | ||

+ | Add the added words to a visited list | ||

+ | remove all the visited words from the word list | ||

+ | </ | ||

+ | |||

+ | **Code:** | ||

+ | |||

+ | <code cpp [enable_line_numbers=" | ||

+ | vector< | ||

+ | |||

+ | queue< | ||

+ | |||

+ | unordered_set< | ||

+ | for(auto w : wL){ | ||

+ | wordList.insert(w); | ||

+ | } | ||

+ | |||

+ | q.push({beginWord}); | ||

+ | |||

+ | bool done = false; | ||

+ | |||

+ | vector< | ||

+ | |||

+ | // Do a BSF Search | ||

+ | while(!done && !q.empty()){ | ||

+ | int level = q.size(); | ||

+ | // run this loop for every path in this level | ||

+ | list< | ||

+ | while(level--){ | ||

+ | vector< | ||

+ | q.pop(); | ||

+ | |||

+ | if(path.back() == endWord){ | ||

+ | out.push_back(path); | ||

+ | done = true; | ||

+ | } | ||

+ | |||

+ | // add our the neighbors: | ||

+ | // Theres multiple ways of doing this. | ||

+ | for(int i = 0; i < path.back().length(); | ||

+ | string orig = path.back(); | ||

+ | for(char c = ' | ||

+ | orig[i] = c; | ||

+ | if(wordList.count(orig)){ | ||

+ | path.push_back(orig); | ||

+ | q.push(path); | ||

+ | path.pop_back(); | ||

+ | visited.push_back(orig); | ||

+ | } | ||

+ | } | ||

+ | } | ||

+ | } | ||

+ | for(auto & w : visited){ | ||

+ | wordList.erase(w); | ||

+ | } | ||

+ | } | ||

+ | return out; | ||

+ | } | ||

+ | </ | ||

+ | |||

+ | ===== Word Ladder ===== | ||

+ | [[https:// | ||

+ | |||

+ | **Given two words (beginWord and endWord), and a dictionary' | ||

+ | the length of the shortest transformation sequence(s) from beginWord to endWord, | ||

+ | such that: | ||

+ | |||

+ | - Only one letter can be changed at a time | ||

+ | - Each transformed word must exist in the word list. Note that beginWord is not a transformed word. ** | ||

+ | |||

+ | I did this problem after I did part 2 and it was easier. There are a couple of | ||

+ | things that are different that you don't need. Namely, we don't need to track | ||

+ | paths, so it becomes a much easier BFS problem. | ||

+ | |||

+ | **Algorithm: | ||

+ | |||

+ | <code psuedo [enable_line_numbers=" | ||

+ | build a set of words | ||

+ | make a queue of paths and add first word in it | ||

+ | int dist = 0 | ||

+ | while q isn't empty | ||

+ | dist++ | ||

+ | layer = q size | ||

+ | make a seen word list | ||

+ | while(layer--) | ||

+ | pop off path in the q | ||

+ | curword = end of path | ||

+ | if curword is out end word | ||

+ | retun dist | ||

+ | iterate over every char in the curword | ||

+ | mod = curword | ||

+ | iterate c from a to z | ||

+ | mod[i] = c | ||

+ | if(mod in word set) | ||

+ | add it to the path and add it to the q | ||

+ | add mod to the seen word list | ||

+ | remove all the seen words from the wordSet | ||

+ | dist++ | ||

+ | return 0 | ||

+ | </ | ||

+ | |||

+ | **Code:** | ||

+ | |||

+ | <code cpp [enable_line_numbers=" | ||

+ | int ladderLength(string beginWord, string endWord, vector< | ||

+ | unordered_set< | ||

+ | |||

+ | // build the word set | ||

+ | for(auto& | ||

+ | wordSet.insert(w); | ||

+ | } | ||

+ | |||

+ | queue< | ||

+ | q.push(beginWord); | ||

+ | int dist = 0; | ||

+ | |||

+ | while(!q.empty()){ | ||

+ | dist++; | ||

+ | int layer = q.size(); | ||

+ | while(layer--){ | ||

+ | string cur = q.front(); | ||

+ | q.pop(); | ||

+ | if(cur == endWord){ | ||

+ | return dist; | ||

+ | } | ||

+ | for(int i = 0; i < cur.length(); | ||

+ | string mod = cur; | ||

+ | for(char c = ' | ||

+ | mod[i] = c; | ||

+ | if(wordSet.count(mod) != 0){ | ||

+ | wordSet.erase(mod); | ||

+ | q.push(mod); | ||

+ | } | ||

+ | } | ||

+ | } | ||

+ | } | ||

+ | } | ||

+ | return 0; | ||

+ | } | ||

+ | </ | ||

+ | |||

+ | ===== Copy List With Random Pointer ===== | ||

+ | [[https:// | ||

+ | |||

+ | **A linked list is given such that each node contains an additional random | ||

+ | pointer which could point to any node in the list or null. | ||

+ | |||

+ | Return a deep copy of the list.** | ||

+ | |||

+ | I first approached this problem by thinking I can just two pass it and build a | ||

+ | vector array that I can use to index the nodes. I had the right idea but the | ||

+ | random pointers point to a node and not a number, and the numbers aren't unique. | ||

+ | What is unique is the memory location. | ||

+ | |||

+ | You have to look at the problem and not be scared of writing down the high level | ||

+ | algo. That's the whole point of psuedo code, very high level code. | ||

+ | |||

+ | I solved it with a map. You can also solve this problem recursively, | ||

+ | map and a very neat way of building the copy. The recursive function returns a | ||

+ | copy of the node that was called with the following cases: | ||

+ | |||

+ | - If the node is null return null | ||

+ | - If the node has been seen already, return the copy in the seen map | ||

+ | - If none of the above, make a copy and add it to the seen | ||

+ | - Then set the next pointer to a copy of the next node | ||

+ | - Then set the randomon pointer to a copt of the random pointer | ||

+ | - Return the copy | ||

+ | |||

+ | **Algorithm Iterative: | ||

+ | |||

+ | <code psuedo [enable_line_numbers=" | ||

+ | make a dummy head | ||

+ | make a curcopy pointer, cur original | ||

+ | while cur orignal isn't null | ||

+ | curcopy next = new node with val of original | ||

+ | add curcopy to a vector | ||

+ | curcopy = curcopy next | ||

+ | curorig = curorign next | ||

+ | |||

+ | second pass for random index: | ||

+ | walk the original list and keep a counter: | ||

+ | int randpointer = cur random | ||

+ | vector[counter]-> | ||

+ | counter++ | ||

+ | |||

+ | return dummy head next | ||

+ | </ | ||

+ | |||

+ | **Code Iterative: | ||

+ | |||

+ | <code cpp [enable_line_numbers=" | ||

+ | Node* copyRandomList(Node* head) { | ||

+ | Node dh(0), *curOrig = head, *curCopy; | ||

+ | curCopy = &dh; | ||

+ | |||

+ | // key is orig, val is the copy | ||

+ | unordered_map< | ||

+ | |||

+ | // make a first pass copy | ||

+ | while(curOrig != NULL){ | ||

+ | curCopy-> | ||

+ | |||

+ | // add it to the array | ||

+ | map[curOrig] = curCopy-> | ||

+ | |||

+ | // advanced our pointers | ||

+ | curCopy = curCopy-> | ||

+ | curOrig = curOrig-> | ||

+ | } | ||

+ | |||

+ | // second pass to copy the random pointers | ||

+ | curOrig = head; | ||

+ | while(curOrig){ | ||

+ | map[curOrig]-> | ||

+ | curOrig = curOrig-> | ||

+ | } | ||

+ | |||

+ | return dh.next; | ||

+ | |||

+ | } | ||

+ | </ | ||

+ | |||

+ | **Algorithm Recursive: | ||

+ | |||

+ | <code psuedo [enable_line_numbers=" | ||

+ | maintain a visisted map key: original val: copy | ||

+ | |||

+ | helper(node) return the copy | ||

+ | if(null ) return null | ||

+ | if( node is in visited ) | ||

+ | return the copy | ||

+ | | ||

+ | Node copy = new node with original' | ||

+ | Copy next = helperCopy(original' | ||

+ | Copy rand = helperCopy(original' | ||

+ | | ||

+ | add copy to the visited map | ||

+ | return copy | ||

+ | </ | ||

+ | |||

+ | **Code Recursive: | ||

+ | |||

+ | <code cpp [enable_line_numbers=" | ||

+ | class Solution { | ||

+ | public: | ||

+ | unordered_map< | ||

+ | |||

+ | Node* helper(Node* orig){ | ||

+ | if(!orig){ | ||

+ | return NULL; | ||

+ | } | ||

+ | |||

+ | if(seen.count(orig)){ | ||

+ | return seen[orig]; | ||

+ | } | ||

+ | |||

+ | Node* copy = new Node(orig-> | ||

+ | |||

+ | // This is very important that we add it our seen list here, beause if not | ||

+ | // we will hit infinite recursion with the random pointers | ||

+ | seen[orig] = copy; | ||

+ | |||

+ | copy-> | ||

+ | copy-> | ||

+ | |||

+ | return copy; | ||

+ | } | ||

+ | |||

+ | Node* copyRandomList(Node* head) { | ||

+ | return helper(head); | ||

+ | } | ||

+ | }; | ||

+ | </ | ||

+ | ===== Two Sum ===== | ||

+ | |||

+ | [[https:// | ||

+ | |||

+ | **Given an array of integers nums and an integer target, return indices of the | ||

+ | two numbers such that they add up to target.** | ||

+ | |||

+ | You can quickly do an '' | ||

+ | with '' | ||

+ | complement number. You have to keep in mind that you can't return the same | ||

+ | number! | ||

+ | |||

+ | You can two pass it by building a dictionary, or do it better and simpler by | ||

+ | building the numbers as we go along and looking for the complement in the | ||

+ | previous numbers. | ||

+ | |||

+ | **Algorithm: | ||

+ | |||

+ | <code psuedo [enable_line_numbers=" | ||

+ | iterate over all the numbers with an index | ||

+ | check if complement exists in the map | ||

+ | return it if so | ||

+ | add this number to the map | ||

+ | </ | ||

+ | |||

+ | **Code:** | ||

+ | |||

+ | <code cpp [enable_line_numbers=" | ||

+ | vector< | ||

+ | |||

+ | // key: number val val: index | ||

+ | unordered_map< | ||

+ | |||

+ | for(int i = 0; i < nums.size(); | ||

+ | if(map.count(target-nums[i])){ | ||

+ | return {i, map[target-nums[i]]}; | ||

+ | } | ||

+ | map[nums[i]] = i; | ||

+ | } | ||

+ | return {}; | ||

+ | } | ||

</ | </ | ||