# Differences

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

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

coding_cheat_sheet [2020/06/01 19:04] paul |
coding_cheat_sheet [2020/07/08 18:58] (current) paul [Power Function] |
||
---|---|---|---|

Line 79: | Line 79: | ||

We are giving an array that represents the parth a yearbook will take to get signed. The index of each element represents the student. We optimize by keeping track of what students are part of a circuit of signatures. Those student's path do not then need to be calculated. | We are giving an array that represents the parth a yearbook will take to get signed. The index of each element represents the student. We optimize by keeping track of what students are part of a circuit of signatures. Those student's path do not then need to be calculated. | ||

| | ||

+ | ==== First Missing Positive ==== | ||

+ | |||

+ | This a problem that requires us to use constant extra memory, forcing us to use the input array itself to encode more data on it without losing the element information. Information about key assumptions must be had. | ||

+ | |||

+ | The minimum positive element is going to be anywhere between 1 and n+1. Here is why. | ||

+ | If we have the perfectly ordered array with n = 5: | ||

+ | [1 2 3 4 5] | ||

+ | The next positive element is 6 (n+1). | ||

+ | The smaller possible positive element is going to be 1. This means our range spans the same number of elements as we have in the input. Which means if there was a way to overlay this boolean state of whether or not we have seen this number in the array, we can solve this problem with no further memory required. | ||

+ | |||

+ | We do this in three steps: | ||

+ | |||

+ | First pass: | ||

+ | Search for a 1, and if we find any numbers out of possible solutions (negative or greater than n), we reset them to 1. | ||

+ | |||

+ | Second pass: | ||

+ | Map the value of each element to its index and then set that value to negative if present in the array. Hard problems would not be hard if they were easy to explain. | ||

+ | |||

+ | Thirst pass: | ||

+ | Look for the first non present negative number. If not found, handle the edge case and return n+1. | ||

+ | |||

+ | YOU GO THIS! | ||

+ | |||

+ | ==== Permutations and Combinations ==== | ||

+ | |||

+ | Theres like... all these different kinds of permutations and combinations with repetitions, with unique values, etc. | ||

+ | |||

+ | === Unique permutations with unique result === | ||

+ | https://www.youtube.com/watch?v=9lQnt4p7_nE | ||

+ | - Sort input candidates. | ||

+ | - Make a boolean flag array to track used elements. | ||

+ | - Recurse over the canditations, choosing and building a solution, and then unchoosing. | ||

+ | - If the next option is the same, skip it. | ||

+ | |||

+ | |||

+ | ==== Power Function ==== | ||

+ | |||

+ | Implement your own power function. The following is the naive algorithm and takes too much time: | ||

+ | |||

+ | <code c> | ||

+ | |||

+ | class Solution { | ||

+ | public: | ||

+ | double myPow(double x, int n) { | ||

+ | | ||

+ | double ans = 1; | ||

+ | | ||

+ | if(n == 0) | ||

+ | return 1; | ||

+ | | ||

+ | for(int i = 1; i <= abs(n); i++) | ||

+ | { | ||

+ | ans = x * ans; | ||

+ | } | ||

+ | | ||

+ | if(n < 0) | ||

+ | ans = 1/ans; | ||

+ | | ||

+ | return ans; | ||

+ | | ||

+ | } | ||

+ | };</code> | ||

+ | |||

+ | {{::screen_shot_2020-07-08_at_11.55.31_am.png?400|}} | ||

+ | |||

+ | <code c> | ||

+ | class Solution { | ||

+ | public: | ||

+ | double fastPow(double x, long long n) | ||

+ | { | ||

+ | if ( n == 0) | ||

+ | return 1.0; | ||

+ | double half = fastPow(x, n / 2); | ||

+ | if( n % 2 == 0) | ||

+ | { | ||

+ | return half * half; | ||

+ | } | ||

+ | else | ||

+ | { | ||

+ | return half * half * x; | ||

+ | } | ||

+ | } | ||

| | ||

+ | double myPow(double x, int n) { | ||

+ | long long N = n; | ||

+ | if(N < 0) | ||

+ | { | ||

+ | x = 1/x; | ||

+ | N = -N; | ||

+ | } | ||

+ | | ||

+ | return fastPow(x, N); | ||

+ | } | ||

+ | };</code> |