贪心法和递归分治法把碎片一起数一下，得到需要换的钱数。贪心（greedy）算法：其核心逻辑是我们先选择面额较大的，然后逐渐选择面额较小的。为什么这里是从大到小，而不是从小到大？因为通常面额越大，用量越小。functionminCoinChange(coins,amount){varchange=[];总变量=0；for(leti=coins.length;i>=0;i--){//从大到小循环varcoin=coins[i];while(total+coin<=amount){//一个一个添加硬币，面值要小于商品价格change.push(coin);//将硬币添加到结果中total+=coin;//给Totalnumber加币}}returnchange;}贪心是最简单的方案，但是这个方案有两个核心问题：1.找不到答案。2.找不到最优解。递归（recursion）与分治（divideandconquer）递归遍历类似于树形数据结构，遍历顺序为深度优先（DFS）。递归的问题：重叠的子问题。去重回溯和记忆功能回溯的思想记忆功能创建一个memoization，在执行中起到去重的作用。递归和动态规划第一个是无后效，第二个是最优子结构。后失效是指，如上图所示，一个顶点下的子问题分支上的问题之间的依赖是单向的，后续的决策不会影响之前某一阶段的状态。最优子结构是指子问题之间相互独立，我们可以只根据子问题路径前面的状态推导出来，而不受其他路径状态的影响。在动态规划中，状态转移方程用于求解初始化状态状态参数的问题。状态转移方程：其实就是递归公式的思维模式functionminCoinChange(coins,amount){vardp=Array(amount+1).fill(Infinity);//每个硬币需要多少dp[0]=0;//找到0元，需要0个硬币for(letcoinofcoins){//循环每个硬币for(leti=coin;i<=amount;i++){//遍历所有金额dp[i]=Math.min(dp[i],dp[i-硬币]+1);//更新所需的最少面额}}returndp[amount]===Infinity?-1:dp[数量];//如果最后一个是无穷大，就没办法找了}扩展：按位运算符（&AND）的意思是，对于每一位，如果两个操作数对应的位都为1，则结果为1，而0否则。例如5&9的运算结果为0001，即1。00000000000000000000000000000101//5000000000000000000000000000001001//900000000000000000000000000000001//5&9按位或（IOR），对于每一位，当两个操作数对应的位至少有一个1时，结果为1，否则0，比如5|9的运算结果为1101，即13。000000000000000000000000000000101//5000000000000000000000000000001001//9000000000000000000000000000001101//5|9对于按位非（~NOT），表示将操作数的位取反，即0变为1，1变为0。则~5的运算结果为-6，且~9的运算结果为-10。00000000000000000000000000000101//511111111111111111111111111111010//-5000000000000000000000000000001001//9111111111111111111111111111110110//-9按位异或(^XOR)，其操作是针对每一位的，当两个操作数对应的位有一个且只有一个1时，结果为1，否则为0。那么5^9的运算结果就是1100，也就是12。00000000000000000000000000000101//500000000000000000000000000001001//900000000000000000000000000001100//5^9让我们再看看位移。这里又分为左移（<<左移）、有符号右移（>>右移）和无符号右移（>>>补零右移）。左移将a的二进制形式向左移动b（<32）位，用0填充右侧，因此9<<1结果为18。带符号的右移将a的二进制表示向右移动b(<32)位，丢弃移位的位，所以9>>>1的结果为4。最后无符号右移将a的二进制表示右移b(<32)位，丢弃移位的位，并用0向左填充，因此9>>>1的结果为2147483643。0000000000000000000000000000001001//9000000000000000000000000000010010//9<<1000000000000000000000000000000100//9>>101111111111111111111111111111011//9>>>1极客时间《Jvascript进阶实战课》学习笔记Day21
