Algorithm Preorder(tree) 1. Visit the root; 2. Traverse the left subtree, i.e., call Preorder(left-subtree); 3. Traverse the right subtree, i.e., call Preorder(right-subtree).
Recursive
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
public List<Integer> preorderTraversal(TreeNode root) { List<Integer> ans = newArrayList<>(); preOrder(root, ans); return ans; }
We can see the fibonacci series seqences in the natrual world like the sunflower, the nautilus and the galaxy.Fibonacci Natrual
In mathematical terms, the sequence \(F(n)\) of Fibonacci numbers is defined by the recurrence relation
\[ F(n) = F(n-1) + F(n-2) \]
with seed values \(F(0) = 0\) and \(F(1) = 1\).
The Fibonacci sequence is often used in introductory computer science courses to explain recurrence relations, dynamic programming, and proofs by induction. Because the Fibonacci sequence is central to several core computer science concepts, the following programming problem has become fairly popular in software engineering interviews.
Given an input \(n\), return the \(nth\) number in the Fibonacci sequence.
Below I’ve listed \(9\) approaches to this problem. These different solutions illustrate different programming and algorithmic techniques that can be used to solve other problems. You’ll notice that many of these solutions build from previous solutions.
Solution 1 Lookup Table - 32 bit signed integers only
If we don’t need to solve very large values and are time-sensitive, we can calculate all values in advance.
This function will work strictly in the case that we’re dealing with \(32\) bit signed integers (which could be a constraint in languages like Java, C/C++, etc.)
The Fibonacci sequence grows very quickly. So fast, that only the first \(47\) Fibonacci numbers fit within the range of a \(32\) bit signed integer. This method requires only a quick list lookup to find the nth Fibonacci number, so it runs in constant time. Since the list is of fixed length, this method runs in constant space as well.
We are familiar base \(10\). How do we calculate a number?
From high to low, starting with \(ans\) as \(0\), update \(ans\) with the current digit value each time, the update rule is \(ans = ans \times 10 + val\).
If there is a decimal number, encoded as \(\textit{ABC}\) not the arabic number, what’s it?
1 2 3 4
ans = 0 ans = ans * 10 + 1 => A ans = ans * 10 + 2 => B ans = ans * 10 + 3 => C
The answer is: \(123\).
from High to Low
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
publicinttitleToNumber(String columnTitle) { intn= columnTitle.length(); intans=0; intbase=1; for (inti= n - 1; i >= 0; i--) { inttemp=0; if (columnTitle.charAt(i) == 'Z') { temp = 26; } else { temp = columnTitle.charAt(i) - 'A' + 1; } ans = ans + base * temp; base *= 26; }