Algo Advance

Recursion - Medium Level - Question 2 Leetcode 1922  Count Good Numbers A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7). For example, "2582" is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd positions are prime. However, "3245" is not good because 3 is at an even index but is not even. Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 10^9 + 7. A digit string is a string consisting of digits 0 through 9 that may contain leading zeros. Constraints: 1 <= n <= 10^15 Analysis: One of the keys is how to keep the question still the "same question". It is clear that for this question, the total number is "5 * 4 * 5 * 4 * 5 * 4 ...", which are apparently repetitive operations. So we do not need to calculate it one by one, which is NOT the most eff

Recursion - Interview Questions - Question 2 Please reverse a singly linked list using a recursion method. Analysis: We can view the reverse process in a three steps: 1. sperate the first element from the rest ones; 2. recursively reverse the rest ones; 3. connect the reversed rest linked list with the former first element (which become the last one now). See the code below: /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { if(!head||!head->next) return head; ListNode* p=head; // recursive call head=reverseList(p->next); // the former second element becomes the last second one, and // needs to pointe to the former head (to be the last one) p->next->next=p; // make the former head to be the last one p->next=NULL; retur

Recursion - Easy Level - Question 2 Question 2 Leetcode 509  Fibonacci Number The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1. Given n, calculate F(n). Constraints: 0 <= n <= 30 Analysis: 1. the base case is obvious: F(0) and F(1); 2. the converging formula is given directly as well; So just need to convert them into code. See the code below: class Solution { public: int fib(int N) { if(N<2) return N; return fib(N-1) + fib(N-2); } }; But if you have learned some algorithm before and had some understanding of time and space complexity, you can immediately realize that the above method is NOT the most efficient one. The reason is that we re-calculated so many inter-mediates many times! For example, fib(N-2) was calculated when calculating fib(N-1), which was cal

Dynamic Programming - Medium Level - Question 2 Leetcode 174  Dungeon Game The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight was initially positioned in the top-left room and must fight his way through dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers). To reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step. Return the knight's minimum initial health so that he can rescue the princess. Note that any room ca

Dynamic Programming - Easy Level - Question 2 Leetcode 62  Unique Paths A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there? Constraints: 1 <= m, n <= 100 It's guaranteed that the answer will be less than or equal to 2 * 10^9. Analysis: We can apply the same idea in Question1 to the current one, which is from 1D to 2D. One of the key information is: the robot can only go down or right. So if we define f[i][j] means the total number of ways to reach this position, then f[i][j] = f[i-1][j] + f[i][j-1] The first term on the right side is for "go right", and the second for "go down". After having the state definition and transition formula, we just need to figure out the initial states'

Breadth-first Search - Hard - Question 1 815. Bus Routes You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever. For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever. You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only. Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible. Constraints: 1 <= routes.length <= 500. 1 <= routes[i].length <= 10^5 All the values of routes[i] are unique. sum(routes[i].length) <= 10^5 0 <= routes[i][j] < 10^6 0 <= source, target < 10^6 Analysis: One of key steps to this question is to build the connections. For example, once we start with the source stop, then we know what is the next stops to go. Wi