面试题 08.11. 硬币

题目

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。 (结果可能会很大，你需要将结果模上1000000007)

示例1:
输入: n = 5
输出：2
解释:
有两种方式可以凑成总金额:

  1. 5=5
  2. 5=1+1+1+1+1

示例2:
输入: n = 10
输出：4
解释:
有四种方式可以凑成总金额:

  1. 10=10
  2. 10=5+5
  3. 10=5+1+1+1+1+1
  4. 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;
}