面试题 08.11. 硬币
题目
硬币。给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。 (结果可能会很大,你需要将结果模上1000000007)
示例1:
输入: n = 5
输出:2
解释:
有两种方式可以凑成总金额:
- 5=5
- 5=1+1+1+1+1
示例2:
输入: n = 10
输出:4
解释:
有四种方式可以凑成总金额:
- 10=10
- 10=5+5
- 10=5+1+1+1+1+1
- 10=1+1+1+1+1+1+1+1+1+1
注意:
你可以假设: 0 <= n (总金额) <= 1000000
题解
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
// 初始颜色
int oldColor = image[sr][sc];
// 初始颜色和新颜色一致
if (oldColor == newColor) {
return image;
}
int rows = image.length, columns = image[0].length;
BiConsumer<Integer, Integer> dfs = new BiConsumer<Integer, Integer>() {
@Override
public void accept(Integer row, Integer column) {
// 数组越界或者给定位置不是初始值颜色
if (row >= rows || row < 0 || column >= columns || column < 0 || image[row][column] != oldColor) {
return;
}
image[row][column] = newColor;
// 继续遍历上下左右
this.accept(row - 1, column);
this.accept(row + 1, column);
this.accept(row, column - 1);
this.accept(row, column + 1);
}
};
dfs.accept(sr, sc);
return image;
}