Ryan Does Leetcode

Given two strings, return the lowest ASCII sum of the deleted characters to make the strings equal. Returning the lowest ASCII sum of deleted characters to make two strings equal is equivalent to finding the maximum ASCII of a common subsequence.  This problem is a variant of the Longest Common Subsequence  (LCS).  Instead of looking for the length of the longest common subsequence, we'll look for the maximum ASCII sum of a common subsequence.  This solves situations like shown in the example test case, when the string "eet" is chosen over "let". Altering LCS for ASCII sum requires only one change in the recursive function.  In the recurrence relation, when the characters of the two strings are equal, rather than adding 1 for a path length, we add the ASCII total to the answer      int ans; if ( str1 [i]== str2 [j]) { ans=( int ) str1 [i]+ dp (i+ 1 , j+ 1 ); } else { ans = max ( dp (i+ 1 ,j), dp (i,j+ 1 )); } Then i...

How many turns for a strange printer? Consider a strange printer , which can only print a series of the same character at a time.  Given a start and an end, it prints each character, overriding any previous character that may have been there.  Given a string, determine the minimum number of turns for the strange printer to produce the string. The problem asks for the minimum of something.  Also, we can see that with characters overlapping one another that there are overlapping subproblems.   This makes the case that dynamic programming may be an appropriate approach. The Editorial  provides a detailed look at the problem from bottom up.  A helpful video from user vanAmsen also goes in depth bottom up.  However, this problem is a bit complicated, and the rule-of-thumb for dynamic programming problems is that the top down approach is easier to conceptualize and implement (while bottom-up has a faster runtime). To establish our recursive function, let's ...

How will we finish all this soup? Given the volumes of 2 types of soup, and 4 kinds of operations to reduce the amounts of soup, determine probabilities of how the soups will be finished When thinking about how the soup will be consumed, we can imagine reaching the same amounts in different ways.  For instance, if we first eat 75ml of soup A and 25ml of B, then eat 25ml of A and 75ml of B, this would lead to the same amounts as if we consumed 50ml of A and B, twice.   Considering these overlapping subproblems, dynamic programming is an appropriate technique for solving the problem.  The two states to consider are the amounts of soup for A and B Let's approach the problem with top-down dynamic programming, which will utilize memoization.  First we initialize the memo: vector<vector< double > > memo; //global variable double soupServings ( int n ) {           memo= vector < vector < double > >(n+ 1 , vec...

 Can player 1 win? Two players are in a game .  The game has an array.  At each turn, beginning with player 1, a player selects a value from the beginning or end of the array.  The value is added to the player's score.  Each selection reduces the size of the array by 1.  After all values have been selected, the player with the highest score wins.  Return true if planer 1 can with the game. One key observation is that it's not asking for a maximum or minimum like most dp problems, but it's looking to see if player 1 can win.  Victory can be determined by the difference in scores. Also, a player can choose either the right or the left value.  This leads to the dp recurrence relation:      int sl = ns [l] - dp (l+ 1 ,r); int sr = ns [r] - dp (l,r- 1 ); This is because each side is trying to optimize their playing.  The difference in the score becomes what they choose (whether the left or the right), then that total sub...

 Keep all computers powered Given a number of computers, and batteries of various sizes, where batteries can be freely swapped between computers, how long can we keep all computers simultaneously powered ? There are a couple of solutions to this problem.  Here we will use binary search, building off its use these past 2 days. Similar to yesterday, binary search can be used while testing a target solution t .  In this case, given a collection of batteries, can we keep all the computers running for t minutes?   To determine so, we iterate over all the batteries and sum up the available power e : if a given battery length is greater than t , then we add only t  to the available power, because the battery won't be available after t Otherwise, if a battery is smaller than t, we add all its capacity to available power      long e= 0 ; for ( long b : batteries) {      e+= min (t,b); } This capacity can be tested to see if it...

Will you reach the office in time ? Given an array of integers representing distances of train rides, and a decimal hour , determine the minimum positive integer speed  required of the trains in order to arrive to the office by hour .  Trains leave on the hour, so a travel time with a decimal is rounded up.  The last train does not need to be rounded.  See the problem for the detailed description. Using the inputs  dists and hour , we can easily calculate whether or not a train will make it to the office in time for a given speed. Will a given speed allow us to reach the office in time?      bool testspeed ( vector < int > & ds , double hour , int speed ) { int n= ds . size (); double total= 0 ; for ( int i= 0 ; i<n- 1 ; i++) { total+= ceil ( ds [i]/ double (speed) ); } total+= ds [n- 1 ]/ double (speed); return total<=hour ? 1 : 0 ; } Now we need to d...