Aug 06, 2020
指在函数的定义中使用函数自身的方法
本身其实没啥好讲的
解 1：
// 容易堆栈溢出
// 判断 A B 大小减少递归次数
const multiplyRecursionAdd = function (A, B) {
if (A === 0) {
return 0;
}
return B + multiply(A - 1, B);
};
解2:
9 * 10 =
(4 * 10) + (5 * 10) =
(4 * 10) + (4 * 10) + 10 =
const multiply = function (A, B) {
// 减少递归次数
if (A > B) {
return calculate(B, A);
}
return calculate(A, B);
};
const calculate = function (a, b) {
if (a == 0) {
return 0;
}
if (a == 1) {
return b;
}
const halfA = a >> 1;
const halfAResult = calculate(halfA, b);
return halfAResult + halfAResult + (a & (1 == 1) ? b : 0);
};
function Foo (p) {
// 边界条件
if p then
return
end if
// 调用自身递归
Foo(p)
}
边界条件
工具函数，先处理边界（异常）逻辑，之后的逻辑就都是正常逻辑。
处理方式包括但不限于 return、throw
树是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由 n (n > 0) 个有限节点组成一个具有层次关系的集合。
进阶
...
前序遍历：ABDECFG中序遍历：DBEAFCG后序遍历：DEBFGCA层序遍历：ABCDEFG
前序遍历（先序遍历） ：自顶向下，从左往右
/**
* 前序遍历 -- 递归写法
*/
function preOrder(TreeNode root) {
if root == null then
return
end if
// TODO: 前序遍历
inOrder(root.left);
inOrder(root.right);
}
/**
* 前序遍历 -- 利用栈 迭代
*/
class Solution {
void preOrder(TreeNode root) {
}
}
中序遍历
如果是二叉搜索树，在中序遍历的结果就是递增排序
/**
*
*/
function inOrder(TreeNode root) {
if root == null then
return
end if
inOrder(root.left);
// TODO 中序遍历
inOrder(root.right);
}
/**
* 中序遍历 -- 利用栈 迭代
*/
function inOrder(TreeNode root) {
stack <- new Stack()
current = root
while current != null or !stack.isEmpty() do
while current != null do
stack.push(curr);
curr = curr.left;
end
curr = stack.pop();
// TODO 中序遍历
curr = curr.right;
end
}
后序遍历
/**
* 后序遍历 -- 递归写法
*/
function postOrder(TreeNode root) {
if root == null then
return
end if
inOrder(root.left);
inOrder(root.right);
// TODO 后序遍历
}
/**
* 后序遍历 -- 利用栈 迭代
*/
function postOrder (root) {
const stack = [];
let prev = null;
while (root != null || stack.length > 0) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.right == null || root.right === prev) {
// TODO: 后序遍历
prev = root
root = null
} else {
stack.push(root)
root = root.right
}
}
}
层序遍历
/**
* 层序遍历 -- 利用队列辅助
*/
class Solution {
void levelOrder(TreeNode root) {
}
}
var maxDepth = function (root) {
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};
进阶
function fib(N) {
if (N === 1 || N === 2) return 1;
return fib(N - 1) + fib(N - 2);
}
class SolutionWithHashMap {
public int fib(int N) {
if (N < 1) {
return 0;
}
HashMap<Integer, Integer> memo = new HashMap<>();
return helper(memo, N);
}
int helper (HashMap<Integer, Integer> memo, int N) {
if (N == 0) {
return 0;
}
if (N == 1 || N == 2) {
return 1;
}
if (memo.get(N) != null) {
return memo.get(N);
}
memo.put(N, helper(memo, N - 1) + helper(memo, N - 2));
return memo.get(N);
}
}
class SolutionWithDpTable {
public int fib(int N) {
ArrayList<Integer> dp = new ArrayList<>(N + 1);
dp.add(0);
dp.add(1);
dp.add(1);
for (int i = 3; i <= N; i++) {
dp.add(dp.get(i - 1) + dp.get(i - 2));
}
return dp.get(N);
}
}
class Solution {
public int fib(int N) {
if (N == 0) return 0;
if (N == 1 || N == 2) return 1;
int prev = 1;
int curr = 1;
for (int i = 3; i <= N; i++) {
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}
}
/**
* 暴力遍历
*/
class SolutionDp {
public int coinChange(int[] coins, int amount) {
if (amount == 0) {
return 0;
}
return getMinCoinNumber(coins, amount, 0);
}
int getMinCoinNumber (int[] coins, int amount, int num) {
int res = Integer.MAX_VALUE;
int nothingNum = 0;
for (int i = 0; i < coins.length; i++) {
int nextAmount = amount - coins[i];
if (nextAmount == 0) {
res = Math.min(res, num + 1);
} else if (nextAmount < 0) {
// -1
nothingNum += 1;
} else {
res = Math.min(res, getMinCoinNumber(coins, nextAmount, num + 1));
}
}
if (nothingNum == coins.length) {
return -1;
}
return res;
}
}
/**
* 带备忘录的递归（自上而下）
*/
class SolutionDpWidthMemo {
public int coinChange(int[] coins, int amount) {
HashMap<Integer, Integer> memo = new HashMap<>();
return dp(coins, amount, memo);
}
int dp (int[] coins, int amount, HashMap<Integer, Integer> memo) {
// base case
if (amount == 0) {
return 0;
}
if (amount < 0) {
return -1;
}
if (memo.get(amount) != null) {
return memo.get(amount);
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < coins.length; i++) {
int subProblem = dp(coins, amount - coins[i], memo);
if (subProblem == -1) {
continue;
}
res = Math.min(res, subProblem + 1);
}
if (res == Integer.MAX_VALUE) {
memo.put(amount, -1);
return -1;
}
memo.put(amount, res);
return res;
}
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i < dp.length; i++) {
for (int coin : coins) {
if (i - coin < 0) {
continue;
}
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}
return (dp[amount] == amount + 1) ? -1 : dp[amount];
}
}
Math.floor(a / 2) 相当于 a >> 1
a % 2 相当于 a & 1