Ryan Does Leetcode

 A river-crossing frog Given an arrangement of stones, and the ability of a frog to jump k-1 , k , or k+1 distances, determine if the frog can successfully cross the river A variegated golden frog, taken by Charles J. Sharp , distributed by via Wikipedia under the Creative Commons Attribution-Share Alike 4.0 International license.  No changes made The dependencies of previous answers to later answers demonstrates overlapping subproblems, and is a candidate for solving with dynamic programming. We first identify our state variables.  What does each subproblem consist of? There is the frog's index on the stones array, we are trying to find if the frog can travel from one index to the last index.  Also, since the distance a frog can jump depends on the previous jump, the second state variable is the length of the previous jump. With the state variables in mind, we can begin developing the dynamic programming recursive function dp.  It accepts 2 variables, the ...

 Pair Chain Lengths Given a collection of pairs, where the first element is less than the second, find the longest chain that can be formed by placing pairs together, where the last element in the first pair is less than the first element in the second pair The overlapping nature of the problem suggests dynamic programming.  We will employ a top-down approach coupled with a memo table.  The table will be of 1 dimension, as the lone state variable in the problem is the index in the pairs array First, since any pair may be selected in any order, it will be helpful to sort the pairs array.  Also, we declare a few global variables to keep the function calls more readable.  This includes the memo table, initialized to be the length of pairs, with default value of 0; int findLongestChain ( vector < vector < int >> & pairs ) { n= pairs . size (); memo= vector < int >(n, 0 ); this -> pairs =pairs; sort ( thi...

 Interwoven strings Given three strings, determine if the third string can be formed by interleaving the first two strings The overlapping nature of the subproblems suggest a dynamic programming approach.  This problem is also similar to the longest common subsequence .  We will approach this problem in a top-down manner. Declare a 2-dimensional array as a global variable.  The 2 state variables are the indices to string 1 and string 2.  This will be our memo vector<vector< int > > memo; To reduce the number of parameters to our dp function, we also declare the 3 strings as global variables      string s1, s2, s3; In the main function, first check that the length of string 1 and 2 equal the length of string 3.  If not, then the answer is false.   bool isInterleave ( string s1 , string s2 , string s3 ) { if ( s1 . size ()+ s2 . size ()!= s3 . size ()) return false ;          ...

 Text Justification Given an array of words and a maximum width, format the text so that each line has exactly a maximum width for characters fully justified Text justification examples courtesy of Volker Schnebel via Wikipedia .  Licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.  No changes made. First, we will collect and organize the words that will belong in each line. Declare a vector of vector of strings to store the result.  A vector of strings will represent words in the line being processed, and the variable lineLength measures the size of the current line, initialized to 0 vector<vector<string> > result; vector<string> line; int lineLength = 0 ; Iterate through each word in the input words.  If adding the new word to the current line is less than or equal to the maximum width, add the word to the line and update the length.  Otherwise, push the line back in the result, and start a n...

 Reorganize a string Given a string, rearrange the characters so that no 2 adjacent characters are the same The idea is to use a priority queue to repeatedly use the characters of higher frequencies.  To ensure no 2 adjacent characters are the same, we remove a character from both of the top 2 elements in a priority queue To populate the priority queue based on character occurrences, we first calculate character frequencies      vector< int > v ( 26 , 0 ); for ( int i= 0 ; i< s . size (); i++) { v [ s [i]- 97 ]+= 1 ; } Then we populate the priority queue with pairs, where the first element is the frequency of a character, and the second element of the pair is the character itself.  With this organization, we can easily use the priority queue's sorting mechanism priority_queue<pair< int , char > > pq; for ( int i= 0 ; i< 26 ; i++) { if ( v [i]> 0 ) pq . push ( make_pair ( v [i], i+ 97 ) ); } I...

 Excel Column Names Given an integer, convert it to the corresponding column name in Excel Image courtesy of Johannes Jansson via Wikipedia, licensed under the Creative Commons Attribution 2.5 Denmark license.  No changes made. The solution is to basically convert the integer value to a base 26 value as text.  The only hiccup is that the Excel columns are indexed at 1, not 0.  Meaning the first column A corresponds to 1, not 0. This can be fixed by decrementing the value before converting it to text Otherwise it's straight forward.  Take the modulo of the input, at the integer value of 'A' to the number, then add it to the result.  Finally, divide the number by 26.  Continue until the input is 0.     string res ;      while ( columnNumber ) { columnNumber -- ; char c = 'A' + columnNumber % 26 ; res = c + res ; columnNumber /= 26 ; }    ...

 String of substrings Given a string, determine if the string can be built by a substring appended by multiple copies of itself A photo shared via Wikipedia, provided under the Creative Commons   Attribution-Share Alike 4.0 International license.  No changes made The basic solution to the problem is basically brute force: create a string of various sizes beginning from the first character, and check if the following characters in the original string are equal to it.  There are different ways to accomplish this idea.  My first approach, detailed below, was successful, but had a runtime of almost 1200ms and performed poorly, 5th percentile compared to other leetcode solutions.  So I tried a few different implementation techniques.  The graph below shows the runtime for each solution. Approach 1 So in my first solution, I iterated over a string length of 1 to string length n/2, created a substring of length i, then deleted it from the beginning of the s...