微信网站建设方案ppt,如何建立自己的网站去推广,wordpress+主题页脚,开发一个交友软件需要多少钱秘诀#xff1a;确定状态转移方程初始条件和边界情况计算顺序
669 换硬币
669 换硬币 题目描述#xff1a; 给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1。
样…秘诀确定状态转移方程初始条件和边界情况计算顺序
669 · 换硬币
669 · 换硬币 题目描述 给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1。
样例1 输入 [1, 2, 5] 11 输出 3 解释 11 5 5 1
样例2 输入 [2] 3 输出 -1
样例3 输入 [1, 9] 0 输出 0
举例有面值为257三种硬币找出能够使用最少硬币组合成总额为27的方案
首先来看看使用递归的问题——做了很多重复计算效率低下 public class Solution {/*** param coins: a list of integer* param amount: a total amount of money amount* return: the fewest number of coins that you need to make up*/public int coinChange(int[] coins, int amount) {int num coins.length; //the num of given coinsint[] f new int[amount1]; //0...amountf[0] 0; //initfor (int remainValue 1; remainValue amount; remainValue) {f[remainValue] Integer.MAX_VALUE;//select last coin(each choice will consider n coins)for (int i 0; i num; i) {if (remainValue coins[i] f[remainValue-coins[i]] ! Integer.MAX_VALUE f[remainValue-coins[i]]1f[remainValue]) {f[remainValue] f[remainValue-coins[i]]1;}}}if (f[amount] Integer.MAX_VALUE) {return -1;}return f[amount];}
}感觉数组下标还是用ij比较直观具体含义心中有数即可。 114 · 不同的路径
114 · 不同的路径 题目描述 有一个机器人位于一个 m×n 网格的左上角。
机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。
问有多少条不同的路径
样例 1 输入 n 1 m 3 输出 1 解释 只有一条通往目标位置的路径。
样例 2 输入 n 3 m 3 输出 6 解释 D : Down R : Right DDRR DRDR DRRD RRDD RDRD RDDR public class Solution {/*** param m: positive integer (1 m 100)* param n: positive integer (1 n 100)* return: An integer*/public int uniquePaths(int m, int n) {int[][] f new int[m][n];int i, j;// row traversalfor (i 0; i m; i) {//column traversalfor (j 0; j n; j) {if (i 0 || j 0) { //corner casef[i][j] 1;}else {// up left f[i][j] f[i-1][j] f[i][j-1];}}}return f[m-1][n-1];}
}116 · 跳跃游戏
116 · 跳跃游戏 题目描述 给出一个非负整数数组你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
判断你是否能到达数组的最后一个位置。 注数组中的元素代表着青蛙在当前石头能跳的最大距离而不是说一定要跳这么多。 样例 1 输入 A [2,3,1,1,4] 输出 true 解释 0 - 1 - 4这里的数字为下标是一种合理的方案。
样例 2 输入 A [3,2,1,0,4] 输出 false 解释 不存在任何方案能够到达终点。
public class Solution {/*** param a: A list of integers* return: A boolean*/public boolean canJump(int[] a) {if (a null || a.length 0) {return false;}int n a.length;boolean[] f new boolean[n];//initf[0] true;for (int j 1; j n; j) {//previous stone(last step)f[j] false;for (int i 0; i j; i) {if (f[j] ia[i] j) {f[j] true;break;}}}return f[n-1];}
}注一个细节需要注意一下数组可以为空也可以长度为0 今日小结
